TL;DR
This paper introduces "Symbolic Pattern Planning," a novel approach to numeric AI planning that uses patterns of actions to create more efficient encodings. This method significantly reduces the complexity of planning problems, leading to faster and more capable planners, as demonstrated by strong performance in experimental evaluations.
What Problem Does This Paper Address?
Artificial intelligence planning, particularly numeric planning, aims to find a sequence of actions to achieve a goal from an initial state. Numeric planning involves variables that can take on real-valued numbers, making it more complex than traditional Boolean planning. Existing symbolic approaches to numeric planning often rely on encoding the planning problem into a satisfiability (SAT) or satisfiability modulo theories (SMT) problem. However, these encodings can become computationally expensive, especially as the number of steps (bound) increases or when dealing with complex actions. Specifically, the "rolled-up" and "relaxed-relaxed-∃" (R2∃) encodings, while powerful, suffer from either a large number of clauses or a large number of variables, respectively. This paper addresses the challenge of creating more compact and efficient symbolic encodings for numeric planning problems that can solve problems with lower bounds and fewer computational resources.
Methods
The core contribution is the Symbolic Pattern Planning approach, which generalizes existing methods like "rolled-up" and "R2∃" encodings. The key innovation is the introduction of a "pattern," which is an arbitrary sequence of actions. This pattern is used to define a new encoding that:
- Generalizes Action Execution: Allows for multiple executions of actions, not just once or zero times, and can handle actions that are not eligible for "rolling" (a technique to compress repeated action executions).
- Reduces Complexity: The proposed encoding produces formulas with fewer clauses than the rolled-up encoding and significantly fewer variables than the R2∃ encoding, even for the same bound.
- Introduces Pattern-Based Encoding: The encoding uses action variables that range over natural numbers, representing the number of times a specific action (or sequence of actions defined by the pattern) is executed.
- Leverages Pattern Structure: The pattern itself can be arbitrary, allowing for flexibility. The paper suggests using the Asymptotic Relaxed Planning Graph (ARPG) to construct effective patterns.
- Dominance Proof: The authors prove that their pattern encoding dominates both the rolled-up and R2∃ encodings, meaning if a plan can be found with those encodings for a given bound, it can also be found with their pattern encoding.
- Bridging Symbolic and Search: The paper highlights that with a suitable pattern, any planning problem can be solved with a bound of n=1. This opens up possibilities for symbolically searching and incrementally defining patterns, bridging the gap between purely symbolic and search-based planning.
Datasets
The paper evaluates its approach on the domains and problems from the 2023 Numeric International Planning Competition (IPC). They also mention experiments on the LINEEXCHANGE domain, which is a generalization of an example used throughout the paper.
Key Insights and Ideas
- Patterns as a Powerful Abstraction: The core insight is that by defining a "pattern" of action sequences, we can create a more abstract and efficient representation of the planning problem. This pattern acts as a guide for how actions can be combined and repeated.
- Flexibility in Action Representation: Unlike previous methods that strictly limited action occurrences (e.g., at most once), the pattern encoding allows for a more flexible interpretation of action execution counts, leading to more compact encodings.
- Theoretical Dominance: The formal proof that the pattern encoding dominates existing methods is a significant theoretical contribution, providing a strong foundation for its practical benefits.
- Bridging the Gap: The idea that a suitable pattern can solve any problem with a bound of n=1 is a major conceptual leap, suggesting a path towards more unified planning paradigms.
- ARPG for Pattern Generation: Using ARPG to generate patterns is a practical and effective strategy, demonstrating how theoretical advancements can be translated into concrete algorithmic solutions.
Key Results
- Improved Performance: The planner "PATTY," which implements the Symbolic Pattern Planning approach, demonstrated remarkably good comparative performances on the 2023 IPC problems.
- Lower Bounds: PATTY consistently found solutions with lower bounds compared to other symbolic planners (SPRINGROLL, R2∃, OMTPLAN), aligning with theoretical predictions.
- Compact Encodings: For a bound of n=1, PATTY produced formulas with a comparable number of variables to SPRINGROLL and far fewer than R2∃, and fewer assertions than both SPRINGROLL and R2∃.
- High Coverage and Speed: PATTY achieved high coverage (solving a large percentage of problems) and fast solving times, often outperforming other symbolic and search-based planners, especially on "Highly Numeric" domains.
- LINEEXCHANGE Domain: On the LINEEXCHANGE domain, PATTY and SPRINGROLL outperformed search-based planners as the complexity (number of items to exchange) increased, highlighting the benefit of rolling-up actions.
Limitations and Future Work
- Pattern Generation: While ARPG is used for pattern generation, the paper acknowledges that more research is needed to extend the ARPG construction for better patterns. The effectiveness of the pattern encoding is highly dependent on the quality of the generated pattern.
- Completeness with Arbitrary Patterns: The paper notes that if a pattern does not include all actions, the encoding might not be complete unless those actions are never executable.
- Search-Based Planners: For certain domains (e.g., DRONE, PLANTWATERING) and "Lowly Numeric" domains, PATTY performed poorly compared to search-based planners. This is attributed to the fact that the required planning bounds were often unreachable for symbolic planners, including PATTY.
- Future Work: The authors suggest further research into developing better pattern generation techniques and exploring how to combine multiple patterns for even greater flexibility and completeness. They also propose investigating the use of symbolic search to incrementally define patterns.
Summary updated