Efficient Decision-Theoretic Planning: Techniques and Empirical Analysis

Peter Haddawy, AnHai Doan, Richard GoodwinUAI 1995

TL;DR

This paper introduces DRIPS, a novel decision-theoretic planning system that uses abstraction hierarchies to efficiently find optimal plans in complex domains. By intelligently pruning suboptimal plans and leveraging automatically generated search control information, DRIPS significantly outperforms traditional branch-and-bound algorithms, especially in larger problem instances.

What Problem Does This Paper Address?

Decision-theoretic planning aims to find optimal plans in situations with uncertainty about the world state and action outcomes, where "optimal" is defined by a utility function over possible outcomes. The core challenge is that the space of all possible plans is astronomically large, making exhaustive search computationally infeasible. Traditional approaches often rely on simplified models (e.g., deterministic actions, categorical goals) or are limited to small domains. This paper tackles the problem of efficiently finding optimal plans in richer, more complex domains with probabilistic outcomes and continuous state variables, without imposing overly restrictive assumptions on the utility function.

Methods

The paper presents the DRIPS (Decision-theoretic Refinement Planning System), which employs two key techniques:

  • Abstraction Hierarchy: DRIPS utilizes abstraction to manage the complexity of the plan space.
  • Interaction-abstraction: Groups similar actions into abstract actions, allowing the planner to reason about sets of actions at a higher level.
  • Sequential abstraction: Creates macro-operators that represent the end effects of a sequence of actions, abstracting away intermediate states.
  • Efficient Plan Pruning: DRIPS builds abstract plans, estimates their expected utility intervals, and prunes plans whose upper bound is lower than the lower bound of any other candidate plan. This process is iterative, refining plans from more general to more specific.
  • Search Control Strategies: To further enhance efficiency, DRIPS incorporates strategies for selecting which abstract plan to refine and which abstract action within a plan to expand. These include:
  • A default "first action" heuristic.
  • A fixed priority scheme assigned by the domain designer.
  • A sensitivity analysis that dynamically adapts search control based on how much expanding an action is likely to change the expected utility bounds. This is a novel contribution, aiming to prioritize actions that offer the most significant pruning potential.

Datasets

The paper evaluates DRIPS on a complex medical planning problem: selecting an optimal test/treat strategy for patients suspected of deep-vein thrombosis (DVT). The authors constructed a model for this domain based on data from a prior study [8], incorporating up to four tests (contrast venography, impedance plethysmography, ultrasonography) and treatment options. They also mention applying the technique to a diabetic foot infection problem.

Key Insights and Ideas

  • Abstraction is Key: The paper strongly advocates for abstraction as a fundamental technique for tackling the combinatorial explosion in decision-theoretic planning. By grouping actions and sequences, DRIPS can reason about the plan space at multiple levels of detail.
  • Dynamic Search Control Matters: Simply having an abstraction hierarchy isn't enough. The paper highlights the critical role of intelligent search control strategies, particularly sensitivity analysis, in guiding the search towards optimal solutions more efficiently.
  • Empirical Validation is Crucial: The authors demonstrate that their approach is not just theoretically sound but also empirically superior to existing methods on a realistic, complex domain.
  • Uncovering Errors: The application of DRIPS to the DVT domain even led to the discovery of an error in a previously published study [9], underscoring the power of robust planning systems.

Key Results

  • Significant Speedup: In the DVT domain, DRIPS evaluated only 655 abstract and concrete plans out of a total of 6,206, achieving a pruning rate of 89%.
  • Outperforms Branch-and-Bound: DRIPS consistently outperformed a standard branch-and-bound decision tree evaluation algorithm. In the most extreme case, DRIPS's running time was only 15% of the branch-and-bound algorithm's.
  • Scalability: DRIPS scales much more effectively than the branch-and-bound algorithm. As problem size increased, DRIPS's running time per plan actually decreased, while the branch-and-bound algorithm's increased markedly.
  • Memory Efficiency: DRIPS used significantly less memory, in one case 4.4% of the branch-and-bound algorithm's memory usage.
  • Control Strategy Impact: For larger domains, search control strategies had a significant impact. Fixed priority and sensitivity analysis strategies performed much better than the default heuristic, with sensitivity analysis showing particular promise.

Limitations and Future Work

  • Abstraction Hierarchy Construction: The efficiency of DRIPS heavily relies on the quality of the abstraction hierarchy. While the paper mentions tools for automatically generating abstractions, creating "tight" abstractions (where loss due to abstraction is minimal) and quantifying this loss remains an area for future research.
  • Sensitivity Analysis Overhead: The sensitivity analysis, while effective, incurs computational overhead. Future work could involve optimizing this analysis or performing partial sensitivity analysis to balance overhead with pruning effectiveness.
  • Stochastic Dominance: The authors are exploring techniques to eliminate suboptimal plans using stochastic dominance, which could further improve efficiency by avoiding explicit utility computations.
  • Automated Abstraction Generation: The paper notes ongoing work on automatically generating good abstractions by analyzing utility functions and primitive action descriptions, using attribute weighting and clustering.

Summary updated

BibTeX
@inproceedings{haddawy1995efficient,
  author = {Peter Haddawy and AnHai Doan and Richard Goodwin},
  title = {{Efficient Decision-Theoretic Planning: Techniques and Empirical Analysis}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1995},
}
Figure