An Algorithm for Probabilistic Least-Commitment Planning

Nicholas Kushmerick, Steve Hanks, Daniel S. WeldAAAI 1994

Introduction

In the early 1990s, classical planning algorithms operated under the assumption of "stringent certainty," where the initial state and action outcomes were perfectly known. However, real-world environments are inherently uncertain. A robot's gripper might be wet, or a pickup action might fail due to mechanical slippage. This paper introduces BURIDAN, a landmark planning algorithm that bridges the gap between symbolic "least-commitment" planning and probabilistic reasoning. BURIDAN enables an agent to generate action sequences guaranteed to achieve a goal with a probability exceeding a user-defined threshold $\tau$.

Probabilistic Planning Framework

The core challenge addressed by BURIDAN is building plans when only a probability distribution over initial states and action outcomes is available. Unlike classical planners that seek a "provably correct" plan, BURIDAN seeks one that is "sufficiently likely" to succeed.

Action Representation

Actions in BURIDAN are modeled with "triggers" (conditions) that lead to specific "effects" with associated probabilities. This allows for the representation of both conditional effects and purely stochastic outcomes. For instance, the success of a pickup action might depend on whether the gripper is dry (GD).

Probabilistic representation of the 'pickup' action.

The BURIDAN Algorithm

BURIDAN is built upon the foundations of Systematic Nonlinear Planning (SNLP). It introduces several key technical innovations:

  • Cumulative Causal Support: In classical planning, a single causal link typically satisfies a precondition. In BURIDAN, multiple actions can be used to "boost" the probability of a condition being true, making causal support a cumulative concept.
  • Confrontation: This is a novel mechanism for resolving "threats." Instead of simply reordering actions to avoid a threat, BURIDAN can "confront" it by planning additional steps to ensure the threatening outcome of an action is unlikely to occur.
  • Plan Assessment: Determining if a partial plan meets the success threshold $\tau$ is NP-hard. The authors explored four strategies: FORWARD (simulation), QUERY (subset division), NETWORK (Bayesian networks), and REVERSE (backward reasoning).

Evaluation

The algorithm was evaluated using a Robot/Block/Gripper domain, where the task is to pick up and paint a block while keeping the gripper clean. Uncertainty arises from the initial state of the gripper (dry vs. wet) and the non-deterministic outcomes of the pickup and dry actions.

A complete plan trace for the Robot/Block/Gripper domain.

On 1994-era hardware, a Common Lisp implementation of BURIDAN found valid solutions for this domain in approximately 4.5 seconds. The authors proved that the algorithm is both sound (if it returns a plan, it meets the threshold) and complete (it will find a plan if one exists).

Conclusion and Future Work

BURIDAN represents a significant shift from logical entailment to threshold-based success in planning. While it provides a robust theoretical framework, it is limited by its open-loop nature—it produces fixed sequences rather than contingent plans that respond to observations. Future work, such as the C-BURIDAN extension, aims to address these limitations by incorporating sensing and conditional branching.

Summary updated

BibTeX
@inproceedings{kushmerick1994algorithm,
  author = {Nicholas Kushmerick and Steve Hanks and Daniel S. Weld},
  title = {{An Algorithm for Probabilistic Least-Commitment Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure