Decision-Theoretic Planning: Structural Assumptions and Computational Leverage

Craig Boutilier, Thomas L. Dean, Steve Hanks

TL;DR

This landmark survey unifies classical artificial intelligence (AI) planning and operations research (OR) under the umbrella of Markov Decision Processes (MDPs). It demonstrates how AI-style factored representations—such as Bayesian networks, decision trees, and STRIPS-style operators—can break the "curse of dimensionality" by exploiting domain structure to compute optimal and approximately optimal policies without enumerating entire state spaces.

What Problem Does This Paper Address?

Automated sequential decision-making under uncertainty has historically been studied from two divergent perspectives:

  1. Operations Research (OR) & Control Theory: Relies on mathematically grounded MDP formulations and dynamic programming (DP), but typically assumes "flat," explicitly enumerated state spaces, causing exponential blowups ($|S| = 2^M$ for $M$ boolean features).
  2. AI Planning: Traditionally uses compact, feature-based (intensional) representations to handle large worlds, but historically relied on restrictive assumptions (deterministic actions, non-observability, and all-or-nothing goal achievement).

The authors bridge this divide by formulating decision-theoretic planning (DTP) as structured MDPs, investigating how structural regularities (locality, conditional independence, and context-specific independence) can provide computational leverage to solve large stochastic problems.

Methods

The paper reviews and synthesizes several representation and solution techniques:

  • Factored Representations:
  • Two-Stage Temporal Bayesian Networks (2TBNs): Model transition probabilities factor by factor, capturing diachronic (across stages) and synchronic (correlated within-stage) dependencies.
  • Structured Conditional Probability Tables (CPTs): Represent transitions using decision trees or directed graphs to capture context-specific independence.
  • Probabilistic STRIPS Operators (PSOs): Action-centric, outcome-oriented representations that specify only variables that change, solving the frame problem.
  • Structured Dynamic Programming & Decision-Theoretic Regression: Extending backward goal regression to the stochastic case. Value iteration and policy iteration manipulate intensional descriptions (trees or Algebraic Decision Diagrams [ADDs]) of the value function, updating entire clusters of states simultaneously.
  • State Abstraction & Model Minimization: Grouping states into partitions based on reward and transition indistinguishability (uniform vs. nonuniform, exact vs. approximate, fixed vs. adaptive).
  • Decomposition Techniques:
  • Serial Decomposition: Exploits communicating structures (recurrent and transient classes) and kernel/periphery boundaries.
  • Parallel Decomposition: Splits systems into weakly coupled, parallel sub-MDPs using additive, multi-attribute reward structures.

Datasets

As a foundational synthesis and survey paper, no single standardized empirical benchmark dataset is introduced. Instead, the paper draws on:

  • A running office-robot domain: Used throughout the paper to illustrate tasks like mail delivery, coffee fetching, and lab tidying under stochastic action failures and exogenous events.
  • Surveyed empirical domains: Synthesis of test domains from cited literature, notably an abstract process-planning domain with up to 1.7 million states (and scaled examples up to 268 million states evaluated in Hoey et al., 1999) and stochastic resource allocation domains with state spaces as large as $2^{1000}$.

Key Insights and Ideas

  • AI Planning is a Special Case of MDPs: Classical deterministic planning corresponds to a deterministic, non-observable (or fully observable with no sensing penalty) MDP where absorbing goal states yield positive reward and actions incur non-negative cost.
  • Regression as Value Iteration: Classical goal regression directly mirrors backward dynamic programming over an implicitly partitioned, binary-valued value function.
  • Exploiting Regularity: The true computational barrier in MDPs is not the number of physical states, but the degree of distinctness in value. When vast swathes of state space share the same future utility and optimal policy, decision trees or ADDs compress exponential state spaces into small, tractable structures.
  • Decoupled Actions vs. Outcomes: 2TBNs excel when an action has multiple independent stochastic effects; PSOs excel when action effects are tightly correlated.

Key Results

  • Exact Tree/ADD Abstraction: In a 1.7-million-state process-planning MDP, structured value iteration produced an exact value tree requiring only 40,000 leaves, solving in less than half the time of standard modified policy iteration. Using Algebraic Decision Diagrams (SPUDD/ADDs), the exact value function collapsed to just 178 distinct values and under 2,200 internal nodes, solving in 7 minutes (~40× faster than trees) and scaling up to 268 million states.
  • Approximate Tree Pruning: On worst-case synthetic problems with 10 variables ($2^{10}$ distinct values), approximate value-tree pruning introduced an average error of only 0.5% while accelerating computation by a factor of 50.
  • Large-Scale Parallel Decomposition: Weakly coupled parallel decompositions combined with online heuristic search solved stochastic resource-allocation problems with state spaces as large as $2^{1000}$ in approximately 30 minutes.

Limitations and Future Work

  • Worst-Case Overhead: When domains lack structural regularities (e.g., all states have distinct values), tree and graph manipulation overhead makes structured algorithms substantially slower (~100× slower) than basic flat vector-matrix operations.
  • Heuristics for Decomposition: Finding optimal serial or region-based decompositions automatically remains computationally hard (analogous to finding minimal circuits); general, robust heuristics remain an open challenge.
  • Continuous and Relational Spaces: The methods surveyed focus overwhelmingly on propositional (discrete) state-action spaces, leaving the integration of continuous variables, linear-quadratic-Gaussian control models, and first-order relational representations as critical areas for future work.

Summary updated

Abstract

Planning under uncertainty is a central problem in the study of automated sequential decision making, and has been addressed by researchers in many different fields, including AI planning, decision analysis, operations research, control theory and economics. While the assumptions and perspectives adopted in these areas often differ in substantial ways, many planning problems of interest to researchers in these fields can be modeled as Markov decision processes (MDPs) and analyzed using the techniques of decision theory. This paper presents an overview and synthesis of MDP-related methods, showing how they provide a unifying framework for modeling many classes of planning problems studied in AI. It also describes structural properties of MDPs that, when exhibited by particular classes of problems, can be exploited in the construction of optimal or approximately optimal policies or plans. Planning problems commonly possess structure in the reward and value functions used to describe performance criteria, in the functions used to describe state transitions and observations, and in the relationships among features used to describe states, actions, rewards, and observations. Specialized representations, and algorithms employing these representations, can achieve computational leverage by exploiting these various forms of structure. Certain AI techniques -- in particular those based on the use of structured, intensional representations -- can be viewed in this way. This paper surveys several types of representations for both classical and decision-theoretic planning problems, and planning algorithms that exploit these representations in a number of different ways to ease the computational burden of constructing policies or plans. It focuses primarily on abstraction, aggregation and decomposition techniques based on AI-style representations.
BibTeX
@article{boutilier1999decision,
  author = {Craig Boutilier and Thomas L. Dean and Steve Hanks},
  title = {{Decision-Theoretic Planning: Structural Assumptions and Computational Leverage}},
  journal = {J. Artif. Intell. Res.},
  year = {1999},
  url = {https://openreview.net/forum?id=Bcb0zRbt1cx},
}

Loading related content...

Figure