Using the relaxed plan heuristic to select goals in oversubscription planning problems

Abstract

Oversubscription planning (OSP) appears in many real problems where nding a plan achieving all goals is infeasi- ble. The objective is to nd a feasible plan reaching a goal sub- set while maximizing some measure of utility. In this paper, we present a new technique to select goals \a priori" for problems in which a cost bound prevents all the goals from being achieved. It uses estimations of distances between goals, which are com- puted using relaxed plans. Using these distances, a search in the space of subsets of goals is performed, yielding a new set of goals to plan for. A revised planning problem can be created and solved, taking into account only the selected goals. We present experiments in six di erent domains with good results.