TL;DR
This paper introduces ShaPer, a novel domain-independent task planner that tackles the combinatorial explosion of state spaces in large planning problems. By pre-computing a "shape graph" that represents abstract states (shapes) rather than concrete ones, ShaPer significantly speeds up on-line planning by reducing the search space.
What Problem Does This Paper Address?
Traditional AI planning systems often struggle with "large problems" – those with a vast number of possible states and actions. This is primarily due to the combinatorial explosion of the state space, where the number of reachable states grows exponentially with the number of objects or complexity of the domain. While existing planners use various techniques like heuristics or restricted search to prune this space, they can still be overwhelmed by problems with many similar objects or symmetries. This paper addresses the challenge of efficiently planning in domains with high degrees of symmetry and redundancy, where many distinct concrete states might represent the same underlying abstract situation.
Methods
ShaPer employs a two-step approach:
- Off-line Shape Graph Construction: For a given domain subclass (a set of operators and objects), ShaPer first explores the state space to build a "shape graph." This graph doesn't represent every single concrete state but rather "shapes." A shape is an equivalence class of states that are structurally identical, meaning one can be transformed into the other via a substitution of objects. This is the core innovation, allowing ShaPer to "resist" combinatorial explosion by manipulating these abstract shapes. The process is akin to a breadth-first search but focuses on discovering and representing these shapes and their transitions.
- On-line Planning with Shape Graphs: Once the shape graph is built, ShaPer uses it to answer planning requests very efficiently. For a given initial state and goal, ShaPer instantiates the shape graph to create initial and goal graphs. It then searches for a single action that connects a state in the initial graph to a state in the goal graph. The final plan is constructed by combining the path from the initial state to the connecting state in the initial graph, the connecting action, and the path from the connecting state to the goal in the goal graph. To ensure completeness, a meta-graph "H" is also computed, which represents a transitive closure of the shape graph, guaranteeing a solution can always be found with at most one action connecting H and the goal graph.
Datasets
The paper evaluates ShaPer on several standard AI planning benchmarks:
- Ferry Domain: Known for its high number of applicable actions and potential for redundant states.
- Gripper Domain: A classic domain involving picking and placing objects, also susceptible to combinatorial explosion with more objects.
- Blocks-World Domain: Tested with varying numbers of blocks and stacks, demonstrating performance on problems with structural complexity.
The paper does not introduce new benchmarks but rather uses these existing ones to compare ShaPer's performance against other state-of-the-art planners.
Key Insights and Ideas
- Abstraction is Key: The fundamental insight is that many planning problems exhibit significant symmetry. By abstracting away from concrete object identities and focusing on structural similarities (shapes), the state space can be drastically reduced.
- Off-line Pre-computation Pays Off: The significant computational cost of exploring the state space is shifted to an off-line phase. This allows for extremely fast on-line planning, making ShaPer suitable for scenarios where many queries are made on the same domain subclass.
- "One Action is Enough" for Solution Extraction: The meta-graph "H" ensures that even if the initial shape graph doesn't directly connect to the goal shape graph, a connection can always be found through H, effectively reducing the on-line search to finding a single connecting action.
- Predictable Plan Length: The shape graph structure allows for bounding the maximum length of the extracted plan, providing a useful theoretical guarantee.
Key Results
ShaPer demonstrates very promising results, particularly in its ability to handle large problems efficiently.
- Speed: ShaPer consistently outperforms other planners like IPP and STAN in terms of on-line planning time, often by orders of magnitude, especially on larger instances of the ferry, gripper, and blocks-world domains.
- Scalability: The paper shows that the size of the shape graph grows much slower than the full state space for domains with many similar objects (e.g., blocks-world and gripper), highlighting its effectiveness in managing complexity.
- Quality of Solutions: ShaPer produces near-optimal solutions, with the number of plan steps being comparable to or better than other planners, despite its focus on speed.
- Comparison: While FF and HSP also perform well, ShaPer's off-line pre-computation strategy offers a distinct advantage for repeated planning queries within the same domain subclass.
Limitations and Future Work
- Domain Subclass Dependency: The shape graph is specific to a domain subclass. If a planning problem falls outside the pre-computed shapes, ShaPer might need to generate a complementary shape graph on-line, which could impact efficiency.
- State Decomposition: The authors suggest future work on state decomposition. This would involve breaking down complex states into smaller, independent parts to further reduce the state space and potentially enable re-use of shape graphs across different subclasses.
- Contingent and Conformant Planning: Extending ShaPer to handle more complex planning scenarios like contingent and conformant planning is also mentioned as a future research direction.
Summary updated