Abstract
In many real world planning scenarios, agents often do not have enough resources to achieve all of their goals. Consequently, they are forced to find plans that satisfy only a subset of the goals. Solving such partial satisfaction planning (PSP) problems poses several challenges, including an increased emphasis on modeling 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 paper, we start by describing a spectrum of PSP problems and focus on one of the more general PSP problems, termed PSP NET BENEFIT. We develop three techniques, (i) one based on integer programming, called OptiPlan, (ii) the second based on regression planning with reachability heuristics, called AltAlt ps, and (iii) the third based on anytime heuristic search for a forward state-space heuristic planner, called Sapa ps. Our empirical studies with these planners show that the heuristic planners generate plans that are comparable to the quality of plans generated by OptiPlan, while incurring only a small fraction of the cost.
Original language | English (US) |
---|---|
Title of host publication | Proceedings of the National Conference on Artificial Intelligence |
Pages | 562-569 |
Number of pages | 8 |
State | Published - 2004 |
Event | Proceedings - Nineteenth National Conference on Artificial Intelligence (AAAI-2004): Sixteenth Innovative Applications of Artificial Intelligence Conference (IAAI-2004) - San Jose, CA, United States Duration: Jul 25 2004 → Jul 29 2004 |
Other
Other | Proceedings - Nineteenth National Conference on Artificial Intelligence (AAAI-2004): Sixteenth Innovative Applications of Artificial Intelligence Conference (IAAI-2004) |
---|---|
Country/Territory | United States |
City | San Jose, CA |
Period | 7/25/04 → 7/29/04 |
ASJC Scopus subject areas
- Software