Reduced Time-Expansion Graphs and Goal Decomposition for Solving Cooperative Path Finding Sub-Optimally

Pavel SurynekIJCAI 2015

Introduction

Cooperative Path Finding (CPF) involves moving multiple agents from their respective starting positions to target goals on a graph without collisions. While Propositional Satisfiability (SAT) solvers are powerful tools for finding optimal makespan solutions, they often encounter a "size wall." As the number of agents or the environment size increases, the resulting SAT formulas become too large to process efficiently. This paper, presented at IJCAI 2015, introduces UniAGENT, a sub-optimal approach that leverages reduced time-expansion graphs and goal decomposition to achieve significant scalability gains.

The Cooperative Path Finding Problem

In a standard CPF instance, agents must navigate a graph $G=(V,E)$ such that no two agents occupy the same vertex at the same time, and no two agents traverse the same edge in opposite directions simultaneously.

Example of a CPF instance and its solution sequence.

Traditional SAT-based solvers represent this by expanding the graph over time, creating a copy of the map for every discrete time step. If a solution requires $T$ steps, the solver manages $T$ layers of the graph. This "full expansion" leads to a combinatorial explosion in the number of variables and clauses as $T$ grows, making high-density problems unsolvable in reasonable time.

Methodology: Reduced Time-Expansion Graphs (rExpT)

The core innovation of this work is the Reduced Time-Expansion Graph ($rExpT$). Instead of expanding the graph for every single time step, the author proposes using a fixed, small number of layers ($\vartheta$).

Visualization of the Reduced Time-Expansion Graph (rExpT).

In this model, a solution is found by identifying vertex-disjoint paths through these layers. This allows the solver to represent complex coordination, such as one agent yielding to another, without the overhead of a massive temporal expansion. The $\vartheta$-RELAXED encoding further optimizes the SAT formula by using flow-based logic and bit-vector IDs for agents, keeping the formula size manageable even at high agent densities.

Goal Decomposition with UniAGENT

To further enhance scalability, the paper introduces UniAGENT, a "divide and conquer" strategy. Rather than attempting to move all agents simultaneously—which would require a large $\vartheta$—UniAGENT relocates agents one by one. Once an agent reaches its goal, it is treated as a stationary obstacle for subsequent agents. Because only one agent moves at a time, the required number of graph layers $\vartheta$ remains very low (typically between 1 and 3), allowing the SAT solver to operate within its most efficient range.

Experimental Evaluation and Results

The approach was tested on $8 \times 8$ and $6 \times 6$ grids with 20% obstacle density and varying agent counts, as well as on $(N^2 - 2)$-puzzles.

Key findings include:

  • Formula Efficiency: For a high-density scenario (32 agents on an $8 \times 8$ grid), the $\vartheta$-RELAXED encoding generated approximately 53,000 clauses, a massive reduction from the 2.7 million clauses required by standard optimal encodings.
  • Performance: UniAGENT outperformed leading search-based methods like OD+ID and WHCA* in high-density environments. It successfully solved instances with up to 83% occupancy within a one-minute timeout.
  • Solution Quality: While the resulting makespans are sub-optimal due to the sequential nature of UniAGENT, they remain significantly better than those produced by simpler rule-based algorithms like PUSH-AND-ROTATE.

Conclusion

By relaxing the requirement for makespan optimality, the UniAGENT framework demonstrates that SAT solvers can be effectively applied to large-scale, highly constrained CPF problems. The combination of reduced time-expansion graphs and sequential goal decomposition provides a robust middle ground between slow optimal solvers and fast but poor-quality rule-based heuristics.

Summary updated

BibTeX
@inproceedings{surynek2015reduced,
  author = {Pavel Surynek},
  title = {{Reduced Time-Expansion Graphs and Goal Decomposition for Solving Cooperative Path Finding Sub-Optimally}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure