TL;DR
This paper explores how to effectively use "red-black planning," a technique that interpolates between simplified (delete-relaxed) and full AI planning, to generate actual plans. They introduce two key enhancements to their Red-Black State Space Search (RBS) method: combining RBS with a tractable planning fragment (ACI) and an adaptive refinement strategy that prunes non-realizable transitions. These improvements allow for more efficient and effective plan generation, outperforming state-of-the-art systems in several domains.
What Problem Does This Paper Address?
AI planning systems aim to find a sequence of actions to achieve a goal from an initial state. A common technique to speed up planning is "relaxation," where certain aspects of the problem are simplified. The "delete relaxation" is particularly popular, but it ignores important real-world constraints like resource consumption and the need to move back and forth. "Red-black planning" offers a way to bridge this gap by allowing some variables to be treated with delete-relaxed semantics ("red" variables) while others retain their true semantics ("black" variables).
However, a major challenge is that for plan generation to be tractable (i.e., solvable in a reasonable amount of time), the set of black variables must be carefully chosen, often restricted to a very simple "ACI" fragment. This severely limits the expressiveness of red-black planning. The paper addresses the question: how can we fully leverage the power of red-black planning to generate real plans, even when the black variables don't fit the simple ACI fragment? They build upon prior work on Red-Black State Space Search (RBS) and propose new methods to make RBS more practical for generating plans directly.
Methods
The paper introduces two main enhancements to their Red-Black State Space Search (RBS) framework:
- RBS + ACI Synergy (Enhancement A): This approach combines the strengths of RBS with the tractable ACI fragment. Instead of using a simple delete-relaxed planning step for the "red" variables within RBS, they use ACI planning where possible. This means that if a part of the problem can be solved using the ACI fragment (e.g., moving back and forth on a road), ACI is used. For parts that are not tractable under ACI (e.g., resource consumption), RBS is employed. This is made possible by identifying specific conditions on the dependencies between black variables that allow this combination.
- Adaptive Refinement via Realizability (Enhancement B): This method introduces a more dynamic way to refine the search. During the RBS search, each state transition is checked for "realizability" – essentially, whether the simplified (delete-relaxed) plan for the red variables would actually work in the real world. If a transition is found to be non-realizable, it's pruned. Crucially, this pruning also triggers the creation of "refinement options." These options are new, more constrained red-black planning tasks that start from the problematic state, incorporating additional black variables to address the specific reason for the non-realizability. These refinement options are then integrated into the search as new nodes.
Datasets
The authors evaluate their techniques on the International Planning Competition (IPC) benchmarks, specifically the satisficing STRIPS benchmarks. No new datasets were introduced.
Key Insights and Ideas
- Complementarity of Planning Techniques: The paper highlights that different planning techniques (like ACI and RBS) have different strengths. ACI is good for certain types of tractable problems (like invertible movements), while RBS can handle more complex scenarios but can be computationally expensive. Combining them allows for a more robust approach.
- The Cost of Refinement: While adaptive refinement (Enhancement B) is conceptually appealing for focusing the search, the paper finds that it can lead to significant overhead due to the generation of too many refinement options.
- The Importance of Variable Dependencies: The success of combining RBS with ACI hinges on the dependencies between the black variables. Specifically, if the variables handled by ACI do not depend on those handled by RBS, the combination is more straightforward and guarantees success.
- RBS as a Foundation: The paper demonstrates that RBS, when augmented with these new techniques, can be a powerful foundation for solving complex planning problems that are challenging for other methods.
Key Results
- Performance Improvements: Both proposed enhancements (ACI combination and adaptive refinement) lead to substantial performance improvements in terms of overall coverage compared to a baseline RBS approach.
- ACI's Impact: The combination with ACI significantly reduces the number of black variables needed to find a real plan, as shown in Figure 1.
- Adaptive Refinement Challenges: While adaptive refinement shows promise, it often suffers from too many refinement options, leading to worse performance in many cases. However, it can be complementary to other methods.
- Outperforming State-of-the-Art: In five specific domains, the authors' best configurations significantly outperform established planners like LAMA and Mercury.
- Complementarity: The proposed methods are highly complementary to existing approaches like LPG plan repair, with different techniques excelling in different domains.
Limitations and Future Work
- Adaptive Refinement Overhead: The primary limitation of the adaptive refinement strategy (Enhancement B) is the computational overhead caused by generating too many refinement options. The authors suggest that finding a better way to manage these options is crucial.
- Completeness of Adaptive Refinement: The paper notes that the adaptive refinement strategy, due to its under-approximation, can lose completeness. They suggest exploring alternative definitions for realizability and refinement.
- Future Work on Refinement: The authors explicitly state that the best way to implement adaptive refinement is still an open question and a direction for future research.
- Exploration of Other Techniques: The paper mentions that exploring alternative definitions for realizability and refinement is a topic for future work. They also suggest that combining RBS with other planning techniques beyond ACI could be beneficial.
Summary updated