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.
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.
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