Probabilistic Planning with Reduced Models

Luis Enrique PinedaAAAI 2014 · DOI

Abstract

This paper introduces a flexible framework for probabilistic planning that bridges the gap between fast-but-risky deterministic methods and robust-but-slow full Markov Decision Process (MDP) solvers. By utilizing $M^k_l$-reductions, planners can account for a limited number of "exceptional" outcomes, resulting in plans that are significantly more robust than simple determinization while remaining computationally efficient.

Introduction

In AI planning, Markov Decision Processes (MDPs) are the standard for modeling environments with uncertain action outcomes. However, MDPs suffer from the "curse of dimensionality," making optimal planning computationally prohibitive in real-time for large state spaces. Common workarounds involve determinization, which simplifies the model by assuming a single outcome per action. While computationally efficient, this "overly optimistic" approach often ignores critical risks, leading to catastrophic failures in stochastic environments. This research seeks a "middle ground" that maintains the speed of simplified models while incorporating enough probabilistic awareness to ensure reliability.

The $M^k_l$-Reduction Framework

The core contribution is the $M^k_l$-reduction framework, which defines a spectrum of model complexity based on two parameters:

  • $l$ (Primary Outcomes): The number of outcomes per state-action pair fully accounted for in the model.
  • $k$ (Exception Budget): The maximum number of "exceptional" (non-primary) outcomes the planner is prepared to handle during a single execution.

Under this framework, a standard deterministic planner is an $M^0_1$-reduction (1 outcome, 0 exceptions). Increasing $k$ and $l$ allows the planner to anticipate more failures. The research also introduces a Continual Planning paradigm for parallel planning and execution, and a Model Compilation method to translate reduced models into standard PPDDL for use with off-the-shelf MDP solvers.

Experimental Evaluation

The approach was evaluated on several standard benchmarks: the Racetrack domain (path-finding under uncertainty) and various IPPC’08 domains, including Triangle-tireworld (known for "dead ends"), Blocksworld, and Zenotravel.

Performance across 10 instances of the IPPC'08 domains: triangle-tireworld, zenotravel, and blocksworld.

Key Results and Insights

The experimental results highlight several advantages of the $M^k_l$-reduction approach:

  1. Near-Optimality and Efficiency: In the racetrack domain, $M^1_1$ and $M^1_2$ reductions achieved near-optimal total costs (combining planning and execution time). As shown in the comparison below, these reduced models offer a significant performance advantage over full Value Iteration (VI) and simple Determinization (DET).
  2. Competitive Robustness: The $M^1_1$ planner performed on par with state-of-the-art specialized planners in IPPC’08 benchmarks, successfully navigating domains with significant risk factors.
  3. State Space Compression: The primary driver of speedup is the dramatic shrinkage of the reachable state space considered by the planner when using a well-chosen reduction.
Comparison of performance metrics for various solvers including Value Iteration (VI), Determinization (DET), and $M^k_l$ reductions (M11, M12).

Conclusion and Future Work

The $M^k_l$-reduction framework demonstrates that determinization is not a separate category but an extreme point on a spectrum of MDP simplifications. By relaxing these restrictions slightly, planners gain massive robustness for a fraction of the cost of a full MDP. Future work will focus on automated model selection to eliminate manual parameter tuning and developing "anytime" algorithm variants for even more responsive planning.

Summary updated

BibTeX
@inproceedings{pineda2014probabilistic,
  author = {Luis Enrique Pineda},
  title = {{Probabilistic Planning with Reduced Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8775},
}
Figure