A Possibilistic Planner that Deals with Non-Determinism and Contingency

Emmanuel Guere, Rachid Alami

Introduction

Autonomous robots operating in real-world environments face two primary hurdles: qualitative uncertainty and non-determinism. A robot may lack precise knowledge of its surroundings (e.g., whether a door is locked) or face actions with multiple possible outcomes (e.g., a slippery object falling during a pick-up). Traditional planners often rely on extensive probabilistic data or computationally expensive "possible worlds" logic. This paper introduces a "possibilistic" planner that bridges this gap by extending the Graphplan algorithm with Possibility Theory, allowing for robust planning in the face of incomplete information and contingent environmental events.

Methodology: Possibilistic Graphplan

The core of the system is a possibilistic extension of the Graphplan search paradigm. Unlike probabilistic models, this approach uses "Possibility" ($\Pi$) and "Necessity" ($N$) to represent beliefs. This allows the robot to distinguish between complete ignorance (something is possible but not necessary) and qualitative certainty.

Action Taxonomy and Modeling

The planner classifies actions into four categories: deterministic, conditional (context-dependent), non-deterministic (multiple outcomes), and perception (knowledge-gathering). During the expansion phase, the planner propagates necessity values through the graph. To ensure robustness, it adopts a "pessimistic" approach, associating the lowest necessity with a fact to guarantee that any found plan meets a minimum certainty threshold.

The possibilistic action model illustrating fact necessity propagation through actions.

Contingent Events and Safety

A unique feature of this planner is its handling of "contingent events"—environmental changes triggered automatically by specific conditions (e.g., a room overheating if a door remains open). By modeling "Fail" states as outcomes of these events, the planner treats safety as a hard constraint. It performs a safety check during plan extraction to ensure no sequence of actions inadvertently triggers a failure state.

Key Insights: Perception as a Bridge

The planner distinguishes between non-determinism caused by inherent action variability and that caused by insufficient knowledge. It can generate "conformant" plans that work regardless of outcomes, but it will automatically pivot to "conditional" plans if the required goal necessity is high. This pivot involves using perception actions (e.g., WhichOne?) to resolve ambiguity before proceeding.

Perception action model (WhichOne?) used to resolve ambiguity and branch into more certain states.

Evaluation and Results

The planner was evaluated on several AI benchmarks, including the "ColdRoom" frame example, "Bomb in Toilet," and medical diagnosis problems.

  • Efficiency: The system demonstrated high performance, solving the ColdRoom problem in 95ms and the Bomb in Toilet benchmark in as little as 30ms on an Ultra-Sparc 10.
  • Adaptive Complexity: The planner adjusts plan complexity based on the desired necessity threshold. For a goal necessity of $N > 0.7$, it produced a simple 6-action plan. When raised to $N > 0.9$, it generated a more complex sequence involving a perception action at a well-lit table.
  • Safe Synthesis: In the ColdRoom scenario, the planner successfully avoided failure by recognizing that leaving a door open would trigger a "HighTemperature" event, thus planning to close the door as a safety requirement.

Conclusion and Future Work

While the current planner is efficient and robust, future work aims to optimize for the "necessity" of the plan itself rather than just plan length. Additionally, the authors suggest incorporating qualitative utility theory to allow for flexible goals where safety and mission success can be explicitly weighted against one another.

Summary updated

Abstract

This paper proposes a new planning approach that authorizes an autonomous robot to reason about the inaccuracy of the world description and of its possible evolutions. We represent the uncertainty with the possibility theory; this allows us to distinguish between two types of nondeterminism: a non-determinism from insufficient modeling and a non-determinism from uncertainty. Besides, we introduce perception actions as well as a model of the environment dynamics through "contingent events". Finally, we present an implemented experimental planner, based on Graphplan search paradigm. This planner is able to produce plans that are robust with respect to contingent events, and whose goal-achieving ability is evaluated a priori. The obtained plans can be conformant or conditional depending on the context and the user requirements. 1
BibTeX
@inproceedings{guere1999possibilistic,
  author = {Emmanuel Guere and Rachid Alami},
  title = {{A Possibilistic Planner that Deals with Non-Determinism and Contingency}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=H14LIEfOWB},
}

Loading related content...

Figure