Using relaxed plan heuristic to select goals in oversubscription planning problems

www.plg.inf.uc3m.es Abstract. Oversubscription planning (OSP) appears in many real problems where finding a plan achieving all goals is infeasi-ble. The objective is to find 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 different domains with good results.