Utility-directed planning

Classical AI planning has adopted a very narrow notion of plan quality, namely that a plan is good just in case it achieves a specified goal. Goals provide a valuable point of computational leverage: despite the fact that planning is intractable in the worst case, goalsatisfying planning algorithms can effectively solve classes of problems by using the goal to focus the search for a solution (using backward-chaining techniques), and by exploiting domain-specific heuristic knowledge to control search. But as the sole description of a planning problem, goals are in several regards inadequate. Goals provide neither a means of representing partial satisfaction (either a plan succeeds in achieving the desired world state or it does not), nor a way of describing the value of the specified world state relative to the cost of achieving it. In short, goals provide insufficient information to measure plan quality in any satisfying way. Decision theory has been proposed as a solution to this problem. It provides a rich theoretical framework for the construction of utility models capturing precisely the notion of partial satisfaction and the cost-benefit tradeoff mentioned above. But the planning community has been slow to adopt utility models for the description of planning problems, since planning with utility models requires optimization, commonly thought to be less tractable and less amenable to heuristic control than classical goal satisfaction. We claim that optimal planning can be made heuristically tractable for a class of utility models that is significantly more expressive than simple goal formulas. We extend 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. We have adopted a goal-directed utility model similar to proposals by (Haddawy & Hanks 1993). This utility model allows the description of soft deudline goals whose value is a function of the time when the goal is satisfied. A goal is represented by a propositional goal formula, a temporal decuy function, and a goal-vulue coeficient. The temporal decay function must, be uniformly 1.0 until the deadline, and decrease monotonically thereafter. The goal-value coefficient determines the relative value of achieving the goal. The cost of the plan is captured with a residual utility function, a function of the resources consumed by a plan. Like temporal decay, the residual utility must be monotonically decreasing with respect to increased consumption of any given resource. We have implemented PYRRHUS, a planning algorithm which finds optimal plans for the utility model described above. PYRRHUS is a synthesis of branchand-bound optimization with a least-commitment, plan-space planner. The underlying planning mechanism is based on the UCPOP planning system (Penberthy & Weld 1992), with extensions to provide support0 for time and metric resources. In addition to the sort of search control knowledge employed by classical goal-satisfying planners, PYRRHUS uses the structure of the utility model to compute an upper bound on the utility of partial plans, possibly allowing them to be pruned from the search space. Our initial empirical results are encouraging. We have conducted a number of experiments in a simulated transportation domain, comparing classical goalsatisfying planning to optimal planning with various utility models. PYRRHUS is able to employ the same heuristic search control knowledge as a classical planner to solve problems that would be intractable otherwise. We found the difficulty of optimal planning depends strongly on the nature of the utility model; in some cases the additional structure of the utility model makes optimal planning much easier than simple goal-satisfying planning, while in other cases it is more difficult. We are in the process of developing a formal characterization of the relationship between the structure of the utility function and the difficulty of optimal planning.