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

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.This work has been partially supported by MICIIN TIN2008-06701-C03-03 and CCG10-UC3M/TIC-5597 projects.Publicad