TL;DR
This paper introduces "rolling" to classical AI planning with conditional effects, allowing actions to be repeated multiple times within a single planning step. This significantly reduces the search space and planning time, especially for problems requiring many action repetitions, by effectively compressing sequences of actions.
What Problem Does This Paper Address?
Classical AI planning typically assumes actions are "idempotent," meaning applying an action multiple times has the same effect as applying it once. However, many real-world scenarios involve actions whose effects depend on how many times they've been executed (conditional effects). While dealing with single applications of such actions is well-studied, efficiently handling their consecutive repetitions has been a challenge. Existing planning-as-satisfiability (PAS) approaches require a separate planning step for each action repetition, leading to excessively long planning horizons and computational blow-up. This paper tackles the problem of efficiently modeling and exploiting these action repetitions in planning.
Methods
The core contribution is a novel PAS encoding that incorporates "rolling." Here's a breakdown:
- Conditional Effects (CEs): The paper starts by formalizing planning tasks with CEs, where an action's outcome can vary based on specific conditions.
- Transition Relations: For each action, they define a transition relation that captures all possible states reachable after one application.
- Transitive Closure (TC): To handle repetitions, they compute the transitive closure of the transition relation. This TC relation, denoted $T^+$, represents all states reachable by applying an action at least once consecutively.
- Rolling Encoding ($\Pi^+$): A new PAS encoding, $\Pi^+$, is proposed. It uses a propositional variable $a^+$ for each action $a$ to indicate if $a$ is applied at least once in a step. The TC relation $T^+$ is then used to compute the resulting state.
- Constraint Handling: The paper emphasizes how constraints on reachable states can be leveraged to simplify the computation of the TC, making it more manageable.
- BDDs for TC: Reduced Ordered Binary Decision Diagrams (BDDs) are used to represent and compute the TC relations, leveraging their compact and canonical representation for efficient manipulation.
- Timeout Mechanism: To address the potential intractability of computing the full TC, a "timeout index" is introduced. This allows stopping the TC computation at an intermediate step, still providing benefits of rolling by modeling states reachable within a limited number of repetitions ($2^m$).
- Repetition Calculation: A crucial algorithm,
REPETITIONS, is presented to determine the exact number of times an action was repeated within a planning step, given the initial and final states and the computed TC. This allows reconstructing the actual plan from the compressed representation.
Datasets
The paper introduces three novel domains for experimental analysis:
- Counter: Models a counter with $B$ bits, where an action increments it, resetting to 0 if it reaches its maximum value. Plans require $2^B - 1$ repetitions of the increment action.
- Cube: Involves three robots moving on a cubic space, requiring them to reach a common vertex. This domain uses constraints to ensure robots stay in single positions.
- Loops: Combines elements of the Counter and Cube domains, featuring multiple loops with counters, requiring complex movement and counter manipulation.
These domains are specifically designed to necessitate consecutive action repetitions, making them suitable for evaluating the proposed rolling technique.
Key Insights and Ideas
- PSPACE-Completeness of CEs: Even with a single action, planning with CEs remains PSPACE-complete, highlighting the inherent difficulty of handling state-dependent effects.
- Rolling as Action Compression: The core idea is that "rolling" allows compressing a sequence of identical action applications into a single planning step, drastically reducing the number of steps ($n$) required in a PAS encoding.
- TC as the Key to Rolling: The transitive closure of an action's transition relation is the mathematical tool that enables modeling multiple repetitions within one step.
- Constraints as Simplifiers: Constraints on reachable states are not just for plan validity but can actively simplify the computation of the transitive closure, making the approach more practical.
- BDDs for Scalability: Using BDDs for representing and computing transition relations and their TCs is crucial for managing the complexity, especially in domains with many variables.
- Timeout for Practicality: The ability to stop TC computation early and still gain benefits from rolling is a pragmatic approach to handle cases where full TC computation is infeasible.
Key Results
The experimental analysis across the Counter, Cube, and Loops domains demonstrated the effectiveness of the rolling approach ($\Pi^+$) compared to a baseline approach without rolling ($\Pi^0$).
- Reduced Bound: For the Counter domain, $\Pi^+$ achieved a bound of 1 for $B$ up to 11, while $\Pi^0$ required a bound that grew exponentially with $B$. For example, with $B=12$, $\Pi^0$ required a bound of $2^{12}-1$ repetitions, while $\Pi^+$ found a plan with a bound of 4.
- Faster Planning Time: In many cases, $\Pi^+$ significantly reduced planning time, especially for larger problem instances where $\Pi^0$ timed out or required excessively long planning horizons.
- TC Computation Dominates Time: For $\Pi^+$, when the problem size grew large enough, the time spent computing the transitive closure became the dominant factor, indicating the efficiency of the rolling mechanism itself.
- Constraints Improve TC: In the Cube domain, using constraints led to a 40% reduction in BDD nodes for the transitive closure, demonstrating their practical benefit.
- Theoretical Guarantees: The paper proves the correctness and completeness of the proposed $\Pi^+$ encoding, ensuring that it finds a valid plan if one exists and that any found plan is valid.
Limitations and Future Work
- TC Computation Intractability: While BDDs and the timeout mechanism help, computing the transitive closure can still be computationally expensive for very complex actions or large state spaces.
- Combining Actions: The current work focuses on rolling a single action. Future work aims to integrate this rolling approach with techniques that allow multiple different actions to be executed in a single step, further compressing plans.
- Integrating with SOTA: The authors plan to integrate their TC approach into the latest state-of-the-art PAS techniques that already employ multi-action steps, potentially leading to even greater planning efficiency.
Summary updated