Abstract
Constraint-based planning offers the potential to leverage advanced pruning and propagation techniques from the Constraint Satisfaction Problem (CSP) community. However, traditional encodings often suffer from state-space explosion as the planning horizon increases. This paper presents TCPP (Transition Constraints for Parallel Planning), a novel system that utilizes Domain Transition Graphs (DTGs) and compact table constraints with "wildcards" to create efficient parallel planning models. By leveraging the SAS+ formalism and specialized solvers, TCPP demonstrates superior performance over existing constraint-based planners and rivals top-tier heuristic search planners on standard benchmarks.
Introduction
Automated planning—the process of finding a sequence of actions to reach a goal state from an initial state—is a cornerstone of artificial intelligence. While many modern planners rely on heuristic search, constraint-based planners attempt to solve planning by translating it into a CSP. In theory, this allows planners to use powerful pruning techniques developed for CSPs. However, performance remains a significant hurdle; as the number of steps (the "horizon") increases, the number of variables and constraints typically explodes, making the problem computationally intractable.
Methodology
TCPP addresses these scalability challenges through several key innovations in model representation and constraint encoding.
SAS+ Formalism and Problem Representation
Instead of using simple Boolean variables, TCPP employs the SAS+ representation. In this formalism, variables can take multiple values (e.g., a truck's location can be A, B, or C), which naturally reduces the total number of variables in the model compared to traditional STRIPS encodings.
Domain Transition Graphs (DTGs)
TCPP extracts a Domain Transition Graph (DTG) for every state variable. A DTG maps all possible transitions for a variable's value. By basing constraints on DTGs rather than just logical formulas, the planner captures the inherent structural movement and state changes within the environment.
Table Constraints with Wildcards
The core innovation of TCPP is the use of table constraints with wildcards (or "don't cares"). Transitions are encoded as a list of allowed value combinations. If a transition for one variable does not depend on another, the entry for the latter is a wildcard. This allows a single row in a constraint table to represent thousands of possible states, drastically compressing the model size.
Solver-Model Synergy
TCPP utilizes the Minion constraint solver, specifically the SHORTSTR2 algorithm. This algorithm is designed to handle table constraints with wildcards efficiently, maintaining General Arc Consistency (GAC) without expanding wildcards into massive explicit tables. Furthermore, the model supports parallelism, allowing multiple non-conflicting actions to occur at the same time step to find shorter plans faster.
Experimental Evaluation
The researchers evaluated TCPP on 12 standard benchmark domains from the International Planning Competitions (IPC), including Logistics, Blocks, and Zenotravel. TCPP was compared against Constance (sequential constraint-based), PaP2 (parallel constraint-based), and FDLMC (a state-of-the-art heuristic search planner).
Key Results
- Overall Performance: TCPP solved 165 out of 213 problem instances, significantly outperforming PaP2 (131 solved) and beating the heuristic search-based FDLMC (158 solved).
- Efficiency: TCPP solved 16% more problems than the previous state-of-the-art constraint planner, PaP2, showing particular strength in domains like Blocks and Depot.
- Scalability: The wildcard-based encoding allowed TCPP to handle larger, more complex problems that previously caused constraint-based methods to fail due to memory or time limits.
Conclusion and Future Work
TCPP demonstrates that constraint-based planning can be highly competitive when structural properties like DTGs and compact wildcard encodings are exploited. While TCPP excelled in most domains, it showed sensitivity to specific domain structures, such as in Miconic. Future work includes incorporating planning-specific heuristics into the CSP solver's search process and developing better methods for estimating the starting plan horizon to improve search efficiency.
Summary updated