Transition Constraints for Parallel Planning

Nina Ghanbari Ghooshchi, Majid Namazi, M. A. Hakim Newton, Abdul SattarAAAI 2015 · DOI

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.

Example planning problem showing initial/goal states and action definitions for board, disembark, drive, and walk actions.

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.

Domain Transition Graph (DTG) for the driver location variable (d-loc), illustrating transitions between locations and the truck (t) with associated constraints.

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

BibTeX
@inproceedings{ghooshchi2015transition,
  author = {Nina Ghanbari Ghooshchi and Majid Namazi and M. A. Hakim Newton and Abdul Sattar},
  title = {{Transition Constraints for Parallel Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9664},
}
Figure