Problem Compilation for Multi-Agent Path Finding: a Survey

Pavel SurynekIJCAI 2022 · DOI

TL;DR

This survey paper provides a unified overview of compilation-based approaches for solving the Multi-Agent Path Finding (MAPF) problem. It explains how complex MAPF instances can be translated into more established formalisms like CSP, SAT, and MILP, leveraging powerful existing solvers to find collision-free paths for multiple agents. The paper highlights key advancements like reachability analysis and lazy refinements that have made compilation a competitive alternative to traditional search-based MAPF methods.

What Problem Does This Paper Address?

The Multi-Agent Path Finding (MAPF) problem is a fundamental challenge in artificial intelligence and robotics. It involves finding paths for multiple agents to navigate from their starting positions to individual goal positions without colliding with each other. While seemingly straightforward, the requirement for collision avoidance and optimality (e.g., minimizing total travel time) makes MAPF computationally demanding, especially as the number of agents and the complexity of the environment increase. Traditional approaches often involve specialized search algorithms. This paper focuses on an alternative paradigm: compilation, where the MAPF problem is translated into a different, well-understood formalism for which efficient solvers already exist. The goal is to provide a comprehensive survey of these compilation-based methods, making them more accessible to a wider audience.

Methods

The paper surveys compilation-based approaches that translate MAPF instances into three primary target formalisms:

  • Constraint Satisfaction Problem (CSP): MAPF is modeled by defining variables for agent positions at each time step and adding constraints to enforce movement rules (e.g., agents must use edges) and collision avoidance (agents cannot be in the same vertex at the same time). CSP solvers use propagation and filtering techniques to find solutions.
  • Boolean Satisfiability (SAT): MAPF problems are encoded into Boolean formulas, typically in Conjunctive Normal Form (CNF). This involves creating variables representing agent presence at specific locations and times. Modern SAT solvers employ sophisticated techniques like conflict-driven clause learning.
  • Mixed Integer Linear Programming (MILP): MAPF is formulated as an optimization problem where decision variables represent agent paths or proportions of paths. MILP solvers aim to minimize an objective function (e.g., sum of costs) subject to linear constraints.

Key methodological advancements discussed include:

  • Time Expansion: Representing the state of agents at discrete time steps within the target formalism.
  • Reachability Analysis: Using techniques like planning graphs or multi-valued decision diagrams (MDDs) to prune unreachable states or paths, significantly reducing the size of the encoded problem.
  • Lazy Refinements: Instead of encoding the full problem upfront, these methods start with an underspecified problem and incrementally add constraints to resolve detected conflicts. This is inspired by algorithms like Conflict-Based Search (CBS) and is implemented in approaches like SMT-CBS and Lazy-CBS. This "lazy" approach allows solvers to find solutions or proofs of impossibility more quickly.

Datasets

Not discussed in the paper. The paper focuses on the formalisms and algorithms for solving MAPF instances, rather than specific datasets for training or evaluation.

Key Insights and Ideas

  • Compilation as a Powerful Alternative: Translating MAPF to CSP, SAT, or MILP allows leveraging decades of research and highly optimized solvers, making it a competitive approach to specialized MAPF search algorithms.
  • The Power of Abstraction: Different formalisms offer varying levels of expressiveness and computational strengths. CSP excels at global constraints, SAT is efficient for Boolean logic, and MILP handles arithmetic optimization well.
  • Lazy Approaches Revolutionize Compilation: Starting with underspecified problems and refining them incrementally (e.g., SMT-CBS, Lazy-CBS) significantly improves efficiency. This mirrors techniques in other AI domains like Benders' decomposition and abstraction refinement.
  • Reachability Analysis is Crucial: Pruning impossible states or paths early through techniques like MDDs drastically reduces the complexity of the encoded problem, making compilation feasible for larger instances.
  • Bridging the Gap: A significant challenge is effectively encoding objectives (which often involve arithmetic) into formalisms like SAT, which are inherently Boolean. MILP offers a more natural fit for cost optimization.

Key Results

The paper is a survey and does not present new experimental results. However, it highlights that compilation-based approaches, particularly those incorporating reachability analysis and lazy refinements, have become competitive with traditional search-based methods for MAPF. The effectiveness of these methods is demonstrated through their successful implementation using SAT, CSP, and MILP solvers. The paper points to experimental evidence (e.g., from SMT-CBS and BCP algorithms) showing that these methods perform well and can find solutions or proofs of infeasibility efficiently.

Limitations and Future Work

  • Integration of Domain-Specific Heuristics: While MILP-based compilation offers more flexibility for integrating domain-specific heuristics, SAT and CSP approaches often leave more decisions to the general-purpose solver, making it harder to inject such heuristics without modifying the solver itself.
  • Closer Cooperation between Solvers: The paper suggests that even closer cooperation between the main MAPF solver and the target formalism solver, similar to DPLL(T) solvers, could lead to further improvements.
  • Complexity of Fractional Solutions in MILP: MILP-based approaches, while powerful, introduce the complexity of handling fractional solutions, requiring techniques like branch-and-bound.
  • Future Work: The authors emphasize the need for further cross-fertilization between different compilation formalisms and the integration of MAPF-specific heuristics into these frameworks. They also advocate for tighter integration between the MAPF problem and the target formalism solver.

Summary updated

BibTeX
@inproceedings{surynek2022problem,
  author = {Pavel Surynek},
  title = {{Problem Compilation for Multi-Agent Path Finding: a Survey}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/783},
}
Figure