TL;DR
This paper introduces a novel task reformulation framework for classical planning using factored transition systems (FTS). By adapting the merge-and-shrink (M&S) methodology, they demonstrate significant reductions in state-space complexity, leading to faster and more efficient planning, especially for complex problems.
What Problem Does This Paper Address?
Classical planning systems aim to find a sequence of actions to achieve a goal from an initial state. The efficiency of these systems heavily relies on how the planning problem is represented. While common representations like STRIPS and finite-domain representation (FDR) are widely used, they can sometimes obscure the problem's inherent structure, leading to "accidental complexity" and slower planning. This paper addresses this by proposing a more flexible and powerful task reformulation method that can simplify complex planning tasks, making them more amenable to automated planners.
Methods
The core of this paper is the application of the Merge-and-Shrink (M&S) framework, originally from model checking, to classical planning tasks represented as Factored Transition Systems (FTS). The authors adapt several M&S transformations for this purpose:
- Label Reduction: Simplifies the set of actions (labels) by mapping similar ones to a common label, improving efficiency.
- Shrinking (Bisimulation and Weak Bisimulation): Reduces the state space of individual transition systems (representing variables) by merging equivalent states. Bisimulation shrinking is exact and preserves optimality, while weak bisimulation is more aggressive and can lead to larger reductions but may not preserve optimality.
- Merging: Combines multiple transition systems into a single, larger one, which can enable further simplifications through other transformations.
- Pruning: Removes irrelevant or unreachable states and labels, further reducing complexity.
They also adapt heuristic search algorithms (like delete-relaxation and M&S heuristics) to work with the FTS representation, enabling planners to effectively search the reformulated tasks. A key contribution is the development of plan reconstruction functions that translate solutions found in the reformulated task back to valid plans for the original task.
Datasets
The paper evaluates their approach on STRIPS benchmarks from the optimal/satisficing tracks of International Planning Competitions (IPCs). They also mention using two additional sets of tasks, totaling 1827/1816 tasks across 48 unique domains.
Key Insights and Ideas
- FTS as a More Flexible Representation: The paper argues that FTS, by allowing for more expressive representations of transitions, offers greater flexibility for reformulation compared to FDR.
- M&S Transformations for Planning: Adapting M&S techniques, originally for model checking and heuristic generation, as direct task reformulation methods proves highly effective.
- Dominance of FTS Reformulations: The paper formally shows that their FTS-based M&S reformulations strictly dominate certain FDR-based methods, meaning they can achieve at least the same simplifications and often more.
- Trade-off between Optimality and Reduction: Weak bisimulation shrinking offers significant state-space reduction but may not preserve optimality, highlighting a trade-off that planners can leverage.
- Synergy with Pruning: Merging, while increasing task size, can unlock significant pruning opportunities, leading to substantial overall simplification.
Key Results
- Significant State-Space Reduction: Reformulations using label reduction and bisimulation shrinking (a-ls) achieved state-space reductions of up to an order of magnitude.
- Dramatic Reductions with Merging: Incorporating merge transformations (d-ls) led to state-space reductions of several orders of magnitude, with some domains being solved entirely during reformulation (0 expansions).
- Weak Bisimulation's Power: For satisficing planning, weak bisimulation shrinking was particularly effective, solving 305 tasks (including entire domains) without any search.
- Improved Coverage: Various M&S configurations consistently improved coverage over the baseline FDR representation, especially when combined with merging and pruning.
- Overhead of FTS Representation: The paper acknowledges that the FTS representation itself can introduce some overhead compared to FDR, but this is often outweighed by the benefits of reformulation.
Limitations and Future Work
- Automatic Selection of Reformulations: The paper notes that not all reformulations are always helpful, suggesting that methods for automatically selecting the best reformulation strategy for a given domain are needed.
- Controlling Shrinking: The authors mention that they cannot exactly control the amount of shrinking without risking non-refinable abstractions, which limits plan reconstruction.
- Future Work: The authors suggest integrating additional M&S transformations like subsumed transition pruning and graph factorization, and exploring automatic reformulation selection. They also point to the potential for further research in integrating these techniques with other planning paradigms.
Summary updated