TY - GEN
T1 - Planning graph heuristics for selecting objectives in over-subscription planning problems
AU - Nigenda, Romeo Sanchez
AU - Kambhampati, Subbarao
PY - 2005
Y1 - 2005
N2 - Partial Satisfaction or Over-subscription Planning problems arise in many real world applications. Applications in which the planning agent does not have enough resources to accomplish all of their given goals, requiring plans that satisfy only a subset of them. Solving such partial satisfaction planning (PSP) problems poses several challenges, from new models for handling plan quality to efficient heuristics for selecting the most beneficial goals. In this paper, we extend planning graph-based reachability heuristics with mutex analysis to overcome complex goal interactions in PSP problems. We start by describing one of the most general PSP problems, the PSP Net Benefit problem, where actions have execution costs and goals have utilities. Then, we present AltWlt,] our heuristic approach augmented with a multiple goal set selection process and mutex analysis. Our empirical studies show that AltWlt is able to generate the most beneficial solutions, while incurring only a small fraction of the cost of other PSP approaches. Introduction.
AB - Partial Satisfaction or Over-subscription Planning problems arise in many real world applications. Applications in which the planning agent does not have enough resources to accomplish all of their given goals, requiring plans that satisfy only a subset of them. Solving such partial satisfaction planning (PSP) problems poses several challenges, from new models for handling plan quality to efficient heuristics for selecting the most beneficial goals. In this paper, we extend planning graph-based reachability heuristics with mutex analysis to overcome complex goal interactions in PSP problems. We start by describing one of the most general PSP problems, the PSP Net Benefit problem, where actions have execution costs and goals have utilities. Then, we present AltWlt,] our heuristic approach augmented with a multiple goal set selection process and mutex analysis. Our empirical studies show that AltWlt is able to generate the most beneficial solutions, while incurring only a small fraction of the cost of other PSP approaches. Introduction.
UR - http://www.scopus.com/inward/record.url?scp=84890306498&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84890306498&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84890306498
SN - 1577352203
SN - 9781577352204
T3 - ICAPS 2005 - Proceedings of the 15th International Conference on Automated Planning and Scheduling
SP - 192
EP - 201
BT - ICAPS 2005 - Proceedings of the 15th International Conference on Automated Planning and Scheduling
T2 - 15th International Conference on Automated Planning and Scheduling, ICAPS 2005
Y2 - 5 June 2005 through 10 June 2005
ER -