Over-Subscription in Planning: a Partial Satisfaction Problem
Menkes van den Briel, Romeo Sanchez, Subbarao Kambhampati, Ira A. Fulton · 2004
In many real world planning scenarios, agents often do not have enough resources to achieve all of their goals. Hence, this requires finding plans that satisfy only a subset of the them. Solving such partial satisfaction planning (PSP) problems poses several challenges, in-cluding an increased emphasis on modelling and han-dling plan quality (in terms of action costs and goal utilities). Despite the ubiquity of such PSP problems, very little attention has been paid to them in the plan-ning community. In this paper, we start by describing a spectrum of PSP problems and focus on one of the more general PSP problems, termed PSP NET BENE-FIT. We develop two techniques, one based on integer programming, called OptiPlan, and the other based on regression planning with reachability heuristics, called AltAltps. Our empirical studies with these two plan-ners show that the heuristic planner AltAltps generates plans that are quite close to the quality of plans gener-ated by OptiPlan, while incurring only a small fraction of the cost. Finally, we also present interesting connec-tions among our work and over-subscription schedul-ing.