TL;DR
This paper introduces SMT-CBS, a novel algorithm that unifies two leading approaches to multi-agent path finding (MAPF): search-based (like Conflict-Based Search) and compilation-based (like SAT-based solvers). SMT-CBS leverages Satisfiability Modulo Theories (SMT) to efficiently find optimal paths for multiple agents, outperforming existing methods in many scenarios by lazily constructing problem models.
What Problem Does This Paper Address?
Multi-agent path finding (MAPF) is a crucial problem in AI and robotics, involving multiple agents navigating an undirected graph to reach their designated goal locations without colliding. Finding optimal solutions, minimizing either the total cost of all agent movements (sum-of-costs) or the time until all agents reach their goals (makespan), is computationally challenging (NP-hard).
Two primary paradigms exist for solving MAPF optimally:
- Search-based approaches: Conflict-Based Search (CBS) is a prominent example. CBS works by incrementally adding constraints to avoid agent collisions. It uses a high-level search to manage conflicts and a low-level search to find paths for individual agents. While effective, CBS can struggle with highly constrained scenarios.
- Compilation-based approaches: These methods translate the MAPF problem into a propositional satisfiability (SAT) problem. A SAT solver then determines if a solution exists for a given cost. MDD-SAT is a state-of-the-art solver in this category. These methods can be powerful but may generate very large SAT formulas, especially in complex scenarios.
The challenge lies in bridging the gap between these two approaches to achieve efficient optimal MAPF solving across a wider range of problem instances. Specifically, the authors aim to combine the strengths of CBS (efficiency in sparse, less constrained environments) with the strengths of SAT-based methods (robustness in highly constrained environments).
Methods
The paper introduces SMT-CBS, a novel algorithm that unifies search-based and compilation-based MAPF solving using Satisfiability Modulo Theories (SMT).
The core idea is to rephrase the Conflict-Based Search (CBS) algorithm using SMT. SMT solvers break down problems into a propositional (SAT) part and a theory-specific decision procedure. SMT-CBS uses the SAT encoding framework from MDD-SAT (a SAT-based MAPF solver) for its low-level reasoning.
Instead of CBS's high-level search that branches on conflicts, SMT-CBS refines a propositional model with disjunctive constraints. This means it doesn't branch; instead, it incrementally builds and extends the propositional model. When a conflict is detected (similar to CBS's low-level validation), SMT-CBS adds a new constraint to the propositional model to resolve it, rather than creating new search nodes. This process is akin to how SMT solvers handle conflicts by adding lemmas.
The algorithm operates in two main parts:
- SMT-CBS (main loop): Iteratively calls
SMT-CBS-Fixedwith increasing cost thresholds (ξ). - SMT-CBS-Fixed:
- Encodes the MAPF problem into an incomplete propositional model
H(ξ)usingencode-Basic. This model includes constraints for valid paths but initially omits collision avoidance constraints.
- Encodes the MAPF problem into an incomplete propositional model
- Consults a SAT solver on
H(ξ). - If satisfiable, it extracts a potential solution and validates it for collisions.
- If collisions are found, it refines
H(ξ)by adding disjunctive constraints (e.g.,¬X(a₁) ∨ ¬X(a₂)for colliding agentsa₁anda₂at a specific time and location) and adds these to theconflictsset for the next iteration. This is the key difference from CBS's branching. - If
H(ξ)is unsatisfiable, it means no solution exists for the current costξ.
This approach allows SMT-CBS to potentially find solutions without fully constructing the complete propositional model, which is hypothesized to be faster in sparse environments.
Datasets
The paper evaluates SMT-CBS on two categories of benchmarks:
- Small Graphs: These include 4-connected open grids (8x8), random graphs (20% edges, 16 vertices), star graphs (16 vertices), and cliques (16 vertices). Agent start and goal configurations were generated randomly.
- Large Maps: These are 4-connected maps taken from "Dragon Age" (used in prior work). These maps are characterized by being sparsely populated with agents. Up to 50 agents were tested, with random start and goal configurations.
The authors also mention that they provide their implementation and experimental data online for reproducibility.
Key Insights and Ideas
- Unifying Paradigms: The core insight is that SMT provides a natural framework to unify the incremental constraint satisfaction of search-based methods (like CBS) with the declarative modeling of compilation-based methods (like SAT solvers).
- Lazy Model Construction: SMT-CBS's key innovation is its ability to lazily build the propositional model. By omitting collision constraints initially and adding them only when conflicts arise, it can potentially solve problems faster, especially in scenarios where agents interact infrequently.
- SMT as a Conflict Resolution Mechanism: The paper demonstrates how SMT's conflict analysis and lemma generation mechanisms can be adapted to resolve agent collisions in MAPF, mirroring CBS's conflict resolution but within a SAT-based framework.
- Hypothesis Validation: The experimental results support the hypothesis that SMT-CBS excels in scenarios with less agent interaction, where it can avoid generating a full, complex SAT formula.
Key Results
- Performance on Small Graphs: SMT-CBS shows significant speedups over MDD-SAT, particularly in medium-difficulty instances (2-10x faster). In harder instances where agents interact heavily, SMT-CBS's performance converges with MDD-SAT, as expected.
- Performance on Large Maps: SMT-CBS maintains a significant advantage over MDD-SAT in easier cases. In harder regions, its performance is comparable to MDD-SAT.
- Clause Generation: SMT-CBS generates orders of magnitude fewer clauses than MDD-SAT, leading to smaller memory consumption. This directly reflects its ability to avoid building the full propositional model.
- Comparison with ICBS: SMT-CBS outperforms ICBS (a state-of-the-art CBS variant with heuristics) on small grids, especially as instances become harder. On large maps, SMT-CBS is generally faster, though the performance can vary significantly between algorithms on individual instances.
Limitations and Future Work
- Limitations:
- The paper notes that SMT-CBS requires calling the SAT solver more times than MDD-SAT, which introduces an overhead. This is why the performance gap in terms of runtime isn't as dramatic as the gap in clause generation.
- The implementation of ICBS used in the experiments does not support general graphs, only grids.
- The specific MAPF variant considered is "move-to-unoccupied," where agents can move to adjacent unoccupied vertices.
- Future Work:
- The authors plan to generalize SMT-CBS to handle geometric agents in continuous environments, which is a significant extension of the current graph-based approach.
Summary updated