Goal Probability Analysis in Probabilistic Planning: Exploring and Enhancing the State of the Art

Marcel Steinmetz, Jörg Hoffmann, Olivier Buffet

TL;DR

This paper tackles the challenge of finding optimal plans in probabilistic settings where reaching the goal isn't guaranteed due to action failures or resource constraints. The authors introduce a comprehensive framework and new algorithms for "MaxProb" planning, significantly advancing the state-of-the-art and demonstrating the effectiveness of heuristic search and early termination strategies.

What Problem Does This Paper Address?

Many real-world planning problems involve uncertainty. Actions might fail, or we might operate under strict resource limitations (like a budget), meaning there's no guarantee of reaching a desired goal state. In such scenarios, a crucial objective is to find a plan that maximizes the probability of reaching the goal (MaxProb). However, existing research on MaxProb planning, especially using heuristic search, has been limited, leaving the empirical state-of-the-art unclear. This paper aims to fill this gap by systematically exploring a vast design space of algorithms for MaxProb and related objectives, including achieving a minimum goal probability (AtLeastProb) or a goal probability within a certain accuracy (ApproxProb). They also consider both general cyclic problems and the more constrained acyclic planning, particularly with limited budgets.

Methods

The authors propose a broad algorithmic framework that combines several key components:

  • Search Algorithms: They adapt and extend established search algorithms like AO* and LRTDP, and introduce variants of depth-first heuristic searches. A key innovation is the simultaneous maintenance of both optimistic (upper bound) and pessimistic (lower bound) estimates of goal probability, which is crucial for early termination.
  • FRET (Find, Revise, Eliminate Traps): They introduce a new variant of the FRET framework, specifically designed to handle problems with uninformative initial upper bounds. FRET is an iterative process that eliminates "traps" (states from which one cannot escape to a goal) to improve planning.
  • Bisimulation Reduction: A novel probabilistic state-space reduction technique is presented, leveraging bisimulation to group equivalent states and solve a smaller, equivalent problem. This is combined with classical planning techniques for efficiency.
  • Dead-End Pruning: Classical planning heuristics are adapted to identify and prune "dead-end" states (where the goal is unreachable), significantly reducing the search space. This is particularly effective in limited-budget scenarios.
  • Node Selection Strategies: A variety of strategies are explored for biasing action and state selection to foster early termination, aiming to find good solutions faster.

Datasets

The authors designed a comprehensive benchmark suite comprising over 1000 instances. This suite is derived from:

  • IPPC (International Probabilistic Planning Competition): Domains from IPPC'04 and IPPC'08.
  • Resource-Constrained Planning: Benchmarks adapted to have a single consumed resource (fuel, energy, money), simulating limited-budget planning.
  • Simulated Penetration Testing: Models based on attack-asset MDPs, where exploits are probabilistic and actions might be attempted only once.

The suite includes both acyclic and cyclic versions of these domains, as well as limited-budget variants.

Key Insights and Ideas

  • Heuristic Search is Powerful, Even Without Perfect Heuristics: The paper demonstrates that heuristic search significantly outperforms value iteration (VI), even when using trivial initial estimates for goal probability. This suggests that the search guidance itself is highly beneficial.
  • Early Termination is Key: For weaker objectives like AtLeastProb and ApproxProb, the ability to terminate early based on lower or upper bounds provides substantial benefits, especially in terms of anytime performance.
  • Lower Bounds Enable Early Success: Maintaining a pessimistic lower bound (VL) is crucial for achieving early termination when a sufficiently good plan is found, even if the optimal plan hasn't been discovered yet.
  • FRET-πU Outperforms Previous Methods: The novel FRET-πU variant, which uses the current greedy policy's graph instead of the optimistic one, shows dramatic improvements on cyclic benchmarks, significantly outperforming prior FRET approaches and even VI.
  • Bisimulation Reduction is Effective: State-space reduction via bisimulation can drastically reduce problem sizes, making previously intractable problems solvable.

Key Results

  • Coverage Improvements: The new algorithm variants and techniques led to significant improvements in coverage (the number of problems solved within time/memory limits). For instance, FRET-πU achieved +32% total coverage on cyclic benchmarks.
  • Search Space Reduction: Heuristic search algorithms, especially with dead-end pruning, visited substantially fewer states than value iteration. For example, LRTDP visited an order of magnitude fewer states than VI in many cases.
  • Early Termination Benefits: For AtLeastProb, early termination strategies yielded benefits of +8% with θ=0.2 and +7% with θ=0.9.
  • FRET-πU Dominance: On cyclic benchmarks, FRET-πU consistently outperformed other methods, often by a large margin in terms of both search space size and runtime.
  • LM-cut Pruning: The LM-cut heuristic was identified as a standout dead-end pruning method, providing the best overall coverage for most search algorithms.

Limitations and Future Work

  • Computational Overhead of Bisimulation: While bisimulation reduction is powerful, computing it can incur a prohibitive overhead, sometimes making it infeasible.
  • Heuristic Search vs. VI Runtime: While heuristic search visits fewer states, it doesn't always translate to faster runtimes compared to VI, especially when VI is already efficient. This is attributed to the potentially higher cost of updates in heuristic search.
  • Future Directions: The authors suggest several promising avenues:
  • Advanced Goal Probability Estimators: Developing better admissible heuristics for goal probability, potentially by leveraging classical planning abstraction techniques.
  • Hybrid Search: Combining heuristic search with Monte-Carlo Tree Search (MCTS) for improved anytime behavior and early termination.
  • Exploiting Dominance Relations: Using dominance relations to prune states and transfer bounds, particularly relevant for limited-budget planning.
  • Simulated Penetration Testing: Further research into the specific structure of simulated penetration testing models to develop more efficient algorithms.

Summary updated

Abstract

Unavoidable dead-ends are common in many probabilistic planning problems, e.g. when actions may fail or when operating under resource constraints. An important objective in such settings is MaxProb, determining the maximal probability with which the goal can be reached, and a policy achieving that probability. Yet algorithms for MaxProb probabilistic planning are severely underexplored, to the extent that there is scant evidence of what the empirical state of the art actually is. We close this gap with a comprehensive empirical analysis. We design and explore a large space of heuristic search algorithms, systematizing known algorithms and contributing several new algorithm variants. We consider MaxProb, as well as weaker objectives that we baptize AtLeastProb (requiring to achieve a given goal probabilty threshold) and ApproxProb (requiring to compute the maximum goal probability up to a given accuracy). We explore both the general case where there may be 0-reward cycles, and the practically relevant special case of acyclic planning, such as planning with a limited action-cost budget. We design suitable termination criteria, search algorithm variants, dead-end pruning methods using classical planning heuristics, and node selection strategies. We design a benchmark suite comprising more than 1000 instances adapted from the IPPC, resource-constrained planning, and simulated penetration testing. Our evaluation clarifies the state of the art, characterizes the behavior of a wide range of heuristic search algorithms, and demonstrates significant benefits of our new algorithm variants.
BibTeX
@article{steinmetz2016goal,
  author = {Marcel Steinmetz and Jörg Hoffmann and Olivier Buffet},
  title = {{Goal Probability Analysis in Probabilistic Planning: Exploring and Enhancing the State of the Art}},
  journal = {J. Artif. Intell. Res.},
  year = {2016},
  url = {https://openreview.net/forum?id=1bBMvrq_MOD},
}
Figure