Planning Graph Based Heuristics for Partial Satisfaction Problems. Sanchez, R. In the 14th International Conference on Automated Planning and Scheduling Doctoral Consortium, 2004. Whistler, Canada
Planning Graph Based Heuristics for Partial Satisfaction Problems [pdf]Paper  abstract   bibtex   
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 them. Solving such partial satisfaction planning (PSP) problems poses several challenges, including an increased emphasis on modelling and handling 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 planning community. In this extended abstract, we focus on one of the more general PSP problems, termed PSP NET BENEFIT. After describing our problem, we present an initial approach for solving it based on AltAlt (Nguyen, Kambhampati, & Sanchez 2002), a regression planner enforced with reachability heuristics. We called our approach AltAltps . We describe how cost information could be propagated in a planning graph data structure, and how this information could be used to select a subset of the top level goals upfront, and also to generate cost sensitive heuristics to guide the regression search. We also present an evaluation plan of our approach, as well as some possible improvements to AltAltps.

Downloads: 0