Conditional, Probabilistic Planning: A Unifying Algorithm and Effective Search Control Mechanisms

AAAI 1999

TL;DR

This paper presents a unifying algorithm for conditional and probabilistic planning that decouples search control from plan refinement. This allows for more principled handling of plan failures and the development of effective heuristics, leading to significant efficiency improvements in generating complex plans.

What Problem Does This Paper Address?

Planning in real-world scenarios is challenging because actions don't always have predictable outcomes, and the agent may not always know the state of the world. Traditional AI planning systems often assume deterministic actions and complete knowledge. To address this, researchers have developed conditional planning (handling uncertain outcomes by observing and reacting) and probabilistic planning (reasoning about action outcome probabilities). However, existing approaches to combining these often suffer from computational inefficiency, particularly when dealing with plan failures. This paper aims to unify these techniques into a more efficient and principled framework, specifically tackling the problem of how to effectively manage and repair potential plan failures.

Methods

The core contribution is a unifying algorithm that separates the search-control strategy from the plan-refinement process. This is achieved by treating "failure points" (where an uncertain action's undesired outcome occurs) as "flaws" alongside traditional flaws like open conditions and threats.

Key techniques include:

  • Decoupling Search Control and Plan Refinement: The algorithm explicitly separates decisions about when and how to handle failures from the process of actually constructing the plan. This allows for more focused and efficient search.
  • Principled Failure Handling: Instead of indiscriminately addressing all potential failures, the algorithm allows for a principled selection of which failures to address. This is crucial for managing the combinatorial explosion of possibilities.
  • Three Repair Techniques:
    1. Corrective Repair: Reasoning about what to do if an undesired outcome occurs (similar to conditional planning).
  • Preventive Repair: Reasoning about how to increase the likelihood of a desired outcome (similar to probabilistic planning).
  • Replacement: Backtracking and replacing a problematic action with an alternative.
  • Branch Joining: A novel technique to improve efficiency by sharing common sub-plans between different branches of a conditional plan, avoiding redundant computation.
  • Heuristics: The paper introduces heuristics for selecting failure points to repair and for prioritizing preventive repairs based on expected value.

Datasets

Not discussed in the paper. The authors mention using a "synthetic domain" and a "coffee domain" for experiments, but these appear to be custom-built for the research rather than standard benchmarks.

Key Insights and Ideas

  • The Power of Decoupling: Separating search control from plan refinement is as beneficial for conditional/probabilistic planning as it has been for classical planning, enabling more effective heuristics.
  • Failure Points as Flaws: Explicitly treating potential failure outcomes as "flaws" provides a unified framework for managing uncertainty.
  • Principled Selection is Key: The combinatorial explosion of possibilities in conditional/probabilistic planning can be managed by intelligently selecting which failures to address, rather than trying to address all of them.
  • Branch Joining for Efficiency: Sharing common plan segments across branches significantly reduces the computational cost of generating conditional plans.
  • Expected Value Heuristics: Using expected value calculations to prioritize repairs offers a principled way to guide the search towards more promising solutions.

Key Results

The paper demonstrates significant efficiency improvements through its proposed algorithm and heuristics.

  • Orders of Magnitude Improvement: The implemented system, Mahinur, achieved efficiency improvements of "several orders of magnitude" compared to baseline approaches.
  • Threat Resolution Heuristic: Using a heuristic to resolve threats by placing new steps into new branches (when forming a conditional branch) drastically reduced search space and runtime. For example, a problem that took 27.66 seconds and 6902 plan nodes without the heuristic was solved in 1.35 seconds and 105 plan nodes with it.
  • Branch Joining Impact: Branch joining also showed substantial benefits. For a problem with increasing complexity (more alternative steps), the CPU time required with branch joining remained relatively low, while the time without it increased significantly. For the most complex problem tested, the planner without branch joining was terminated after 24 hours and 350,000 plan nodes, while the version with branch joining was still performing well.

Limitations and Future Work

  • Completeness vs. Efficiency Trade-off: The algorithm is less complete than some prior methods (like C-Buridan) because it requires explicit encoding of connections between observation actions and conditions. However, this trade-off is deemed necessary for practical efficiency.
  • Domain-Specific Tuning: The effectiveness of branch joining might require domain-specific tuning to determine when to attempt it and which steps to use as join points.
  • Future Work: The authors suggest that their framework is well-suited for applying conditional probabilistic planning to real-world problems and plan to make their Mahinur system and domain encoding publicly available. They also mention that a similar strategy could be used for estimating the expected value of preventive repairs.

Summary updated

BibTeX
@inproceedings{1999conditional,
  title = {{Conditional, Probabilistic Planning: A Unifying Algorithm and Effective Search Control Mechanisms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure