Decision-Theoretic Planning: Structural Assumptions and Computational Leverage

Craig Boutilier, Thomas L. Dean, Steve Hanks

Abstract

Planning under uncertainty is a central problem in automated sequential decision making, addressed by fields ranging from AI and decision analysis to control theory and economics. This paper synthesizes these perspectives by modeling planning problems as Markov decision processes (MDPs). It identifies structural properties—such as independence in reward functions, state transitions, and feature relationships—that can be exploited to construct optimal policies efficiently. By focusing on abstraction, aggregation, and decomposition techniques, the authors demonstrate how structured, intensional representations provide the computational leverage necessary to overcome the "curse of dimensionality" in complex domains.

Introduction: Bridging the Divide

In the late 1990s, a significant gap existed between classical AI planning and decision-theoretic approaches. Classical planning excelled at managing complex, feature-rich environments but struggled with stochasticity and varying plan quality. Conversely, Operations Research utilized Markov Decision Processes (MDPs) to handle uncertainty and rewards optimally, but these models typically required an explicit (extensional) enumeration of every possible state.

As state spaces grow exponentially with the number of features—a phenomenon known as the "curse of dimensionality"—standard MDP algorithms become intractable for real-world applications. A robot with just 20 binary sensors, for instance, faces over a million states. This paper argues that the solution lies in Structural Assumptions: by exploiting the inherent structure of a problem, we can solve complex MDPs without ever enumerating the full state space.

Modeling Sequential Decisions

The core of the decision-theoretic approach is the MDP, which models an agent's interactions with an environment over time. A critical assumption in many tractable models is the Markov property, which posits that the future state depends only on the current state and action, not the history of previous states.

Graphical representations of state dependencies: (a) general dependencies, (b) first-order Markov chain, and (c) a single state transition.

While a general process might have complex dependencies across all previous time steps (as shown in Figure 2a), the Markov assumption (Figure 2b and 2c) simplifies the transition model significantly. The authors extend this by proposing Factored MDPs, where the world is described by a set of variables rather than atomic states. This allows the use of 2-Stage Temporal Bayesian Networks (2TBNs) to represent actions, capturing the reality that most actions only affect a small subset of the world's features.

Illustrative Example: The Robot Delivery Domain

To demonstrate these concepts, the authors frequently reference a "Robot Coffee/Mail Delivery" example. This domain involves a robot navigating a structured environment to perform various tasks, such as delivering mail or fetching coffee.

The Robot Coffee/Mail Delivery domain, illustrating a structured environment with discrete locations and tasks.

In this environment (Figure 1), the state is defined by features like the robot's location, whether it has mail, and whether the office occupant wants coffee. A "flat" MDP would treat every combination of these features as a unique state. However, a structured approach recognizes that the action "Move to Hallway" only changes the Location variable, leaving HasMail or WantsCoffee unaffected. This local influence is the key to computational leverage.

Computational Leverage through Abstraction

The paper surveys several techniques to exploit this structure:

  • Structured Policy/Value Iteration: Instead of updating a massive table of values, algorithms can operate directly on Decision Trees or Algebraic Decision Diagrams (ADDs). These representations automatically group together states that share the same value or optimal action, effectively partitioning the state space into "abstract states."
  • Reachability Analysis: AI search techniques can identify states that are impossible to reach from the initial configuration, allowing the solver to prune irrelevant parts of the state space.
  • Decomposition: Large problems can often be broken into smaller, independent sub-problems that can be solved in parallel or sequence.

Key Results and Impact

The synthesis provided in this paper demonstrated that structured representations could lead to exponential compression. For example, using ADDs in the SPUDD algorithm allowed researchers to solve a process-planning domain with 1.7 million states by identifying that there were only 178 distinct values across the entire space. In many structured domains, these methods proved to be orders of magnitude faster than traditional matrix-based MDP solvers.

Limitations and Future Directions

Despite the advantages, the authors note several challenges:

  • Overhead: Maintaining and simplifying structured representations (like decision trees) incurs its own computational cost.
  • POMDPs: Extending these techniques to Partially Observable MDPs remains difficult, as the "leverage" is harder to find when the state is not fully known.
  • Automatic Discovery: There is a continuing need for methods that can automatically discover the best abstractions or decompositions without human intervention.
  • Continuous Domains: Most of the discussed techniques focus on discrete variables; extending these to continuous state and action spaces remains a significant research frontier.

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},
}
Figure