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 contingency plans, and making informed decisions during execution. This work is significant because it provides a robust framework for planning in unpredictable environments, a crucial step towards more capable intelligent agents.
What Problem Does This Paper Address?
Traditional AI planning systems often assume a perfect, deterministic world. They operate under the assumption that the effects of actions are fully known and predictable. However, in the real world, uncertainty is pervasive. Actions might have unpredictable outcomes, sensors might be unreliable, and the state of the world might be partially unknown. This paper addresses the challenge of building AI planners that can effectively operate in such uncertain environments. Specifically, it focuses on the need for planners to:
- Reason about uncertainty: Understand how uncertain outcomes can affect a plan's success.
- Select robust plans: Choose plans that avoid uncertain outcomes when possible.
- Develop contingency plans: Create backup plans for situations where uncertainty cannot be avoided.
The authors use the "keys and boxes" problem, a long-standing benchmark in AI planning, to illustrate these challenges. In this problem, a robot needs to retrieve a key from one of two boxes to unlock a door, but it cannot sense which box contains the key. Additionally, it needs to retrieve a "red thing" from a pile, but picking from a heterogeneous pile introduces uncertainty about what will actually be picked up.
Methods
Cassandra is built upon the UCPOP (Universal Conditional Partial Order Planner) framework, extending it to handle uncertainty. Its key innovations include:
- Secondary Preconditions: Actions are represented with modified STRIPS operators. Crucially, effects can have "secondary preconditions" that are unknowable, representing sources of uncertainty (e.g., a coin flip). These secondary preconditions are constructed using a pseudo-predicate
unknown. - Contingency Planning: When an uncertainty is encountered, Cassandra splits the plan into branches, with each branch representing a possible outcome of the uncertainty. It then constructs contingency plans for each branch.
- Decision Making: Cassandra treats decisions about which contingency to execute as explicit plan steps. It annotates these decision steps with condition-action rules. The agent must acquire information to evaluate these rules, and these information-gathering steps are integrated into the plan.
- Label Propagation: Cassandra propagates labels over actions, effects, and goals to track the contingencies under which they are relevant or compatible. This helps manage the complexity of branching plans.
- "Oneof" Construct: For situations like picking from a heterogeneous pile, Cassandra uses a "oneof" construct. This allows it to represent that an action will result in holding one of a set of possible objects. It then enumerates these possibilities and constructs plans to ensure only desired outcomes occur.
- Avoiding Uncertainty: Cassandra can also explicitly plan to avoid uncertain outcomes by enforcing conditions that prevent them from occurring.
Datasets
Not discussed in the paper. The paper focuses on a theoretical problem (keys and boxes) and a general planning framework, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Uncertainty is not just about outcomes, but about how outcomes affect plans: Cassandra's ability to determine if an uncertainty is relevant to a plan (i.e., if a subgoal's achievement depends on it) is crucial. Irrelevant uncertainties are ignored.
- Decisions are first-class plan components: Treating decision-making as an explicit part of the plan, rather than an external process, is key to robust planning under uncertainty. This includes planning how to gather information for decisions.
- Parallel execution of contingencies: For some problems, Cassandra can construct plans where multiple contingency branches are executed in parallel, a powerful capability for dealing with situations where sequential decision-making is not feasible or efficient.
- The "oneof" construct is a powerful abstraction: It elegantly captures the uncertainty of picking from a pile, allowing the planner to reason about the need to enforce conditions that prevent unwanted items from being picked.
- Soundness requires more than just achieving goals: It means achieving goals for all possible outcomes of relevant uncertainties, or explicitly ruling out problematic outcomes.
Key Results
Cassandra successfully produces a sound plan for the keys and boxes problem, which had eluded classical planners for years. It also handles variants of the problem, such as when a sensing operation (like "scan") is available to resolve uncertainty. The paper demonstrates Cassandra's ability to:
- Construct contingency plans for different outcomes of uncertainty.
- Integrate decision-making steps into plans.
- Handle the "oneof" uncertainty of picking from heterogeneous piles.
- Produce plans that avoid problematic outcomes.
The paper contrasts Cassandra's approach with previous attempts by Tate and Sacerdoti, highlighting their limitations in handling general uncertainty, variants of the problem, or explicit reasoning about removing sources of uncertainty.
Limitations and Future Work
The authors acknowledge several limitations and suggest future research directions:
- Efficiency of "oneof" and "forall": The current implementation can be computationally expensive as it enumerates all objects of a given type. Future work could involve filters to consider only relevant objects or to identify equivalence classes among uncertain outcomes (e.g., all red things are equivalent for the purpose of picking one up).
- Exhaustive Search: Like other classical planners, Cassandra faces the problem of combinatorial explosion in its search space, especially with many contingencies. Merging plan branches that consist of the same actions is suggested as a potential optimization, though complex.
- General Problem Characterization: Cassandra currently "rediscovers" the same problem (e.g., heterogeneous piles) repeatedly. Future work could involve incorporating mechanisms for the planner to formulate and recognize general problem characterizations, similar to Sussman's work on skill acquisition.
- Domain-Independent Search Heuristics: The need for effective domain-independent search heuristics to manage the large search space is highlighted.
Summary updated