A value-directed approach to planning
Mikel Ray Williamson, Steve Hanks · 1996
The traditional definition of planning in the field of artificial intelligence provides only a very narrow notion of plan quality, namely that a plan is good just in case it achieves a specified goal. For many applications, this all-or-nothing notion of quality is insufficiently expressive. This dissertation extends the definition of planning to provide a much richer conception of plan quality. We propose that a planning problem should be posed in terms of a decision-theoretic value function, and that planning should be seen as an optimization process. We describe P scYRRHUS, A planning system which uses a branch-and-bound algorithm to find optimal plans for a class of goal-directed value functions which is strictly more expressive than the kind of goal formulas used by classical planning. Such value functions allow one to express not just one's goals, but also how important those goals are, ways in which they may be partially achieved, and the worth of resources that may be consumed by a plan. We empirically explore issues of heuristic control that arise during the planning process, compare the difficulty of value-directed planning to comparable classical planning problems, and examine the relationship between characteristics of our value representation and the difficulty of planning.