Abstract
Cassandra is a partial-order planner designed to handle uncertainty by incorporating contingency branching and treating decisions as explicit plan steps. By extending the SNLP framework, Cassandra successfully addresses the "keys and boxes" problem—a benchmark involving hidden information and non-deterministic outcomes that classical planners struggle to solve. The system introduces the oneof construct to model heterogeneous environments and demonstrates the ability to generate robust plans that account for all possible states of the world.
Introduction: The Blind Robot’s Dilemma
In classical AI planning, agents typically operate under the assumption of complete knowledge and deterministic action outcomes. However, real-world environments are rarely so predictable. A classic example of this challenge is the "keys and boxes" problem proposed by Donald Michie in 1974. In this scenario, a robot must retrieve a red object from a room, but can only exit if a key is placed by the door. The key is hidden in one of several boxes, and the robot is "blind"—it can manipulate objects but cannot sense their identity without specific actions.
Classical planners fail in this domain because they cannot reason about "maybe." For instance, if a robot attempts to pick up a red object from a pile that might contain the key, it risks a failure state it cannot recover from. To succeed, a planner must recognize the need to isolate the target object before moving the key, ensuring that the key is not accidentally displaced.
Methods: Contingency Planning with Cassandra
Cassandra is built upon the Systematic Nonlinear Planning (SNLP) family, specifically extending the UCPOP algorithm to navigate uncertainty. Its architecture is defined by four primary innovations:
- Unknowable Preconditions: Cassandra utilizes an "unknown" pseudo-predicate to represent outcomes that cannot be predicted a priori, such as the contents of a specific container.
- Contingency Branching: When encountering uncertainty, Cassandra splits the plan into multiple branches. To be valid, a plan must guarantee goal achievement across every possible branch.
- Decisions as Plan Steps: Unlike systems that handle logic "behind the scenes," Cassandra treats a decision as an explicit step within the plan. These steps require "knowledge preconditions," necessitating actions (like a sensor scan) to acquire the information needed to select a branch.
- The
oneofConstruct: To handle heterogeneous piles of objects, the authors introduced aoneofconstraint. This forces the planner to account for every individual object in a collection, effectively modeling the uncertainty inherent in selecting an item from an unknown set.
Results: Deriving General Solutions
Cassandra is the first general-purpose framework to derive the optimal solution for the keys and boxes problem from first principles. The generated plan follows a logical sequence:
- Isolate a red object by moving it to a "clean" location (e.g., an empty table).
- Move the key from its unknown location to the door.
- Retrieve the isolated red object from the table.
- Exit the room.
A key insight demonstrated by Cassandra is the strategy of "parallel execution." If the robot lacks sensing capabilities, Cassandra suggests executing plan branches in parallel, provided they do not interfere with one another. This allows the robot to create a "homogeneous pile" of one, effectively removing uncertainty through strategic manipulation. Furthermore, if sensing actions (like a "scan") are available, Cassandra adaptively switches from parallel execution to an informed decision-making process.
Discussion and Limitations
While Cassandra represents a significant leap in symbolic planning, it faces challenges regarding scalability. The primary limitation is the "search space explosion"; every source of uncertainty can double the number of plan branches, making the approach computationally expensive in complex environments.
Future work aims to address these issues by:
- Recognizing Equivalence Classes: Reducing redundancy by treating identical objects (e.g., any red object) as a single contingency rather than separate cases.
- Generalization: Developing mechanisms that allow the planner to formulate general problem descriptions, preventing it from having to "rediscover" the logic of heterogeneous piles in every new instance.
Despite these hurdles, Cassandra provides a robust foundation for reasoning about the unknown, moving AI planning closer to the complexities of the real world.
Summary updated