Name
Abstract | ||
|---|---|---|
We present a heuristic search approach to solve partial satisfaction planning (PSP) problems. In these problems, goals are modeled as soft constraints with utility values, and actions have costs. Goal utility represents the value of each goal to the user and action cost represents the total resource cost (e.g., time, fuel cost) needed to execute each action. The objective is to find the plan that maximizes the trade-off between the total achieved utility and the total incurred cost; we call this problem PSP Net Benefit. Previous approaches to solving this problem heuristically convert PSP Net Benefit into STRIPS planning with action cost by pre-selecting a subset of goals. In contrast, we provide a novel anytime search algorithm that handles soft goals directly. Our new search algorithm has an anytime property that keeps returning better quality solutions until the termination criteria are met. We have implemented this search algorithm, along with relaxed plan heuristics adapted to PSP Net Benefit problems, in a forward state-space planner called Sapa^P^S. An adaptation of Sapa^P^S, called Yochan^P^S, received a ''distinguished performance'' award in the ''simple preferences'' track of the 5th International Planning Competition. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.artint.2008.11.010 | Artif. Intell. |
Keywords | Field | DocType |
new search algorithm,partial satisfaction,total resource cost,problem psp,search algorithm,action cost,heuristic search approach,benefit problem,utility value,partial satisfaction planning,search,planning,goal utility,heuristics,fuel cost,state space,heuristic search | Constraint satisfaction,Mathematical optimization,Heuristic,Search algorithm,Planner,Heuristics,STRIPS,Soft goal,Anytime algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
173 | 5-6 | 0004-3702 |
Citations | PageRank | References |
24 | 1.22 | 28 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Benton | 1 | 155 | 9.45 |
| Minh Do | 2 | 244 | 14.17 |
| Subbarao Kambhampati | 3 | 3453 | 450.74 |