Utility-Directed Planning

Mike Williamson, Steve HanksAAAI 1994

Abstract

Classical AI planning has traditionally operated under a binary paradigm: a plan is either successful if it reaches a goal state or a failure if it does not. This "all-or-nothing" approach fails to account for the complexities of real-world scenarios where the value of a goal may diminish over time or where resource consumption must be weighed against the benefits of success. This paper introduces PYRRHUS, a planner that bridges the gap between classical planning and decision theory. By utilizing decision-theoretic utility models, PYRRHUS identifies optimal plans that balance goal importance, soft deadlines, and resource costs. Through the integration of branch-and-bound optimization with least-commitment planning, the authors demonstrate that utility-directed planning is not only feasible but can occasionally be more efficient than traditional goal-satisfaction methods.

Introduction

In classical AI planning, the primary metric for a "good" plan is its ability to reach a predefined state. While this binary view simplifies search techniques—such as backward chaining—it lacks the expressiveness required for realistic environments. In practice, the quality of a plan is rarely binary; it is often a gradient determined by how well and at what cost a goal is met.

Historically, the planning community has avoided decision-theoretic utility models due to concerns regarding computational tractability. The authors identify two critical gaps in the classical approach that necessitate a shift toward utility-directed planning:

  1. Partial Satisfaction: Traditional planners cannot represent plans that achieve a goal partially or late.
  2. Cost-Benefit Tradeoffs: There is no inherent mechanism to weigh the intrinsic value of a goal against the resources (e.g., time, fuel, or capital) expended to reach it.

The PYRRHUS Framework

To address these limitations, the authors developed PYRRHUS, a planning algorithm designed to find optimal plans within a specific class of utility models. PYRRHUS is built upon the foundation of UCPOP, a "least-commitment" plan-space planner. By using a least-commitment approach, the system avoids premature ordering of actions, maintaining flexibility during the search process.

The Utility Model

PYRRHUS evaluates plans based on a multi-faceted utility function. The value of a plan is determined by three primary components:

  • Temporal Decay: The model incorporates "soft deadlines" where a goal retains its maximum value until a specific time, after which the value decreases monotonically.
  • Goal-Value Coefficient: A multiplier representing the intrinsic importance of the goal relative to others.
  • Residual Utility: A function representing the cost of resources consumed. This function must decrease as resource consumption increases, ensuring that more expensive plans are penalized.

Optimization and Pruning

PYRRHUS synthesizes branch-and-bound optimization with classical planning. To maintain efficiency, the planner utilizes the mathematical structure of the utility model to calculate an "upper bound" on the potential utility of any given partial plan. If the maximum possible utility of a partial plan is lower than the utility of a solution already discovered, the partial plan is immediately pruned. This allows the planner to focus search efforts on the most promising areas of the plan space.

Empirical Evaluation

The authors evaluated PYRRHUS using a simulated transportation domain, a standard benchmark where agents move goods or passengers between locations using limited resources. The experiments focused on the planner's ability to navigate the trade-offs between speed, resource usage, and goal achievement.

Key Insights

  • Optimization as a Search Accelerator: A surprising finding was that adding a utility model does not necessarily slow down the planning process. In several scenarios, the added structure provided by the utility function allowed PYRRHUS to prune the search space more aggressively than a classical goal-satisfying planner, leading to faster solution times.
  • Transferability of Heuristics: The research demonstrates that domain-specific heuristic knowledge, which is commonly used to accelerate classical planners, can be effectively adapted for optimal, utility-directed planners.
  • Utility "Shape" and Complexity: The difficulty of a planning task is heavily influenced by the nature of the utility function. While some functions clearly define the optimal path, others create a complex landscape that requires more intensive computation.

Conclusion and Future Work

PYRRHUS represents a significant step toward integrating decision theory into the planning process, proving that optimal planning is feasible in complex domains like transportation. The results suggest that utility models provide a powerful metric for early pruning, sometimes making the search for an optimal plan more efficient than a search for a merely satisfying one.

However, the current implementation has limitations. The model requires monotonic decay for time and resources, which may not accommodate non-linear or "jagged" utility functions. Future work involves a more formal mathematical characterization of how different utility functions impact search complexity and exploring the scalability of PYRRHUS in large-scale industrial applications.

Summary updated

BibTeX
@inproceedings{williamson1994utility,
  author = {Mike Williamson and Steve Hanks},
  title = {{Utility-Directed Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure