Beyond Symbolic Goals: A Step Towards Utility-Directed Planning Statements of Interest

Decision-Theoretic Planning

Volume

Papers from the 1994 AAAI Spring Symposium

Contents

Classical AI planning adopts a very narrow notion of plan quality, namely that a plan is good just in case it achieves a specified goal. Despite the fact that planning is intractable in the worst case, goal-satisfying planning algorithms can effectively solve classes of problems by using the goal to focus the search for a solution (by using backwardchaining techniques), and by exploiting domainspecific heuristic knowledge to control search. Our work extends the definition of plan quality to take into account partial satisfaction of the goal and the cost of resources used by the plan, while at the same time building an effective planning algorithm by exploiting classical planning techniques like backward chaining and knowledge-based search control rules. This paper presents PYRRHUS, an extension to the UCPOP planning system [Barrett et al., 1993] that finds optimal plans for a class of goal-directed utility models suggested by Haddawy and Hanks [Haddawy and Hanks, 1993]. Our empirical results suggest that optimal plans can be generated effectively by a planner using domain:specific heuristic knowledge, and furthermore that the planner can use the same knowledge as a goai-satisfying planner to solve corresponding optimization problems.