TL;DR
This paper introduces Cassandra, a novel AI planner designed to handle real-world uncertainty. It tackles the classic "keys and boxes" problem by explicitly representing and reasoning about uncertain outcomes, constructing plans that are robust to these uncertainties, and even generating contingency plans for different scenarios. This work represents a significant step towards AI agents that can operate effectively in unpredictable environments.
What Problem Does This Paper Address?
Classical AI planning systems typically assume a deterministic world where the outcome of every action is perfectly predictable. However, in the real world, uncertainty is pervasive. Actions can have unpredictable effects, and an agent might not know the exact state of its environment. This gap between idealized planning and real-world complexity is a major challenge. The paper focuses on extending classical planning to handle this uncertainty, specifically addressing how an agent can reason about, avoid, and plan for uncertain outcomes. The "keys and boxes" problem, a long-standing benchmark, serves as a concrete example to illustrate these challenges.
Methods
Cassandra is built upon the UCPOP (Universal Conditional Partial Order Planner) framework, extending it to handle uncertainty. Key innovations include:
- Modified STRIPS Operators with Secondary Preconditions: Actions are represented by operators with preconditions and effects. Crucially, effects can have "secondary preconditions" that specify the conditions under which they occur. These secondary preconditions can be "unknowable," representing sources of uncertainty (e.g., a coin flip).
- Explicit Representation of Uncertainty: Cassandra uses the
oneofconstruct to represent situations where an action can result in one of several possible outcomes, each dependent on different conditions. This allows the planner to reason about situations like picking an object from a heterogeneous pile. - Contingency Planning and Branching: When an uncertainty is encountered, Cassandra constructs multiple plan branches, one for each possible outcome. It then propagates labels to track which parts of the plan are relevant under which contingencies.
- Decision Steps: Cassandra treats decisions about which contingency to execute as explicit plan steps. These decision steps are annotated with condition-action rules, and their preconditions involve acquiring the necessary information to make the decision.
- Strategies for Handling Uncertainty: Cassandra employs two main strategies:
- Contingency Plans with Explicit Decisions: The agent makes a decision during execution based on acquired information.
- Parallel Execution of Contingency Plans: When possible, Cassandra constructs plans where multiple branches are executed in parallel, ensuring the goal is met regardless of the outcome.
- Avoiding Uncertainty: Cassandra can also construct plans that actively avoid uncertain outcomes by enforcing conditions that prevent problematic scenarios (e.g., ensuring a pile contains only red things before picking one up).
Datasets
Not discussed in the paper. The paper uses the "keys and boxes" problem as a benchmark, which is a well-established AI planning challenge rather than a dataset.
Key Insights and Ideas
- Uncertainty is not just about outcomes, but about reasoning: The paper emphasizes that effective planning under uncertainty requires not just generating plans that work for different outcomes, but also reasoning about how to determine which outcome has occurred and making informed decisions.
- The "keys and boxes" problem is harder than it looks: The paper highlights why classical planners struggled with this problem, particularly the inability to distinguish objects and the uncertainty of picking from a heterogeneous pile. Cassandra's solution demonstrates the need for explicit uncertainty representation.
- Explicit decision-making is crucial: Treating decisions as plan steps, with associated information-gathering actions, makes plans more robust and executable in uncertain environments.
- Avoiding uncertainty is a valid planning strategy: Cassandra's ability to enforce conditions to eliminate uncertainty (e.g., making a pile homogeneous) is a powerful technique for ensuring plan soundness.
- The
oneofconstruct is a powerful tool: This construct effectively models situations where an action's outcome depends on the presence or absence of specific items, a common scenario in real-world manipulation tasks.
Key Results
- Cassandra successfully produces a sound plan for the "keys and boxes" challenge problem, which had eluded classical planners for over twenty years.
- The planner can handle variants of the problem, such as when sensing operations are available to resolve uncertainty.
- Cassandra's approach allows for explicit reasoning about the relevance of uncertainties to a plan and the construction of contingency plans.
- The paper demonstrates Cassandra's ability to handle both decision-based execution of contingency plans and parallel execution of branches.
Limitations and Future Work
- Computational Efficiency: The paper acknowledges that Cassandra's approach can be computationally expensive, especially when dealing with many objects or uncertainties. The
oneofconstruct, in particular, can lead to a massive search space. - Equivalence Classes: The planner currently treats each object in a pile as a distinct outcome. Future work could involve identifying "equivalence classes" of objects (e.g., all red things are interchangeable) to reduce search space.
- Filtering for
oneofandforall: The current implementation considers all objects within the scope of these constructs. Future work could involve developing filters to focus on relevant objects, reducing overhead. - General Problem Characterization: Cassandra currently re-solves similar uncertainty problems repeatedly. Future work could explore mechanisms for formulating and reusing general problem characterizations, similar to Sussman's work.
- Merging Plan Branches: While Cassandra can construct contingency plans, merging branches that consist of the same actions is noted as an extremely complex problem for future investigation.
Summary updated