Strategies to Improve Goal Selection in Satisficing Oversubscription Planning

Abstract

Oversubscription planning (OSP) tackles the infeasibility of finding a plan that achieves all goals, due to a limited resource, typically a cost-bound. The objective is to discover a plan under this cost-bound that maximizes the utility. A leading-edge technique in satisficing OSP employs relaxed plans to estimate the cost of achieving goals and focuses planning efforts on goals deemed attainable based on this estimation. However, this approach faces two main challenges: the time required to calculate all estimations can result in no effective goal selection, and using relaxed plans often underestimates the real cost, leading to sets of oversubscribed goals. To address these challenges, our paper studies two solutions: computing the estimations only when needed and using real plans instead of relaxed plans to calculate cost estimations. Experiments show that real plans offer advantages in terms of initial plan utility, but the gap between both approaches narrows when more time is given for plan refinement.