Planning Under Uncertainty: Some Key Issues

Gregg Collins, Louise Pryor

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:

  1. 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.
  2. 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.
  3. 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.
  4. The oneof Construct: To handle heterogeneous piles of objects, the authors introduced a oneof constraint. 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.
The `oneof` construct allows Cassandra to model the effects of actions on uncertain sets of objects.

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:

  1. Isolate a red object by moving it to a "clean" location (e.g., an empty table).
  2. Move the key from its unknown location to the door.
  3. Retrieve the isolated red object from the table.
  4. Exit the room.
A generated plan trace showing the sequence of steps required to solve the keys and boxes problem under uncertainty.

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

BibTeX
@inproceedings{collins1995planning,
  author = {Gregg Collins and Louise Pryor},
  title = {{Planning Under Uncertainty: Some Key Issues}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure