Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering

Pavel SurynekAAAI 2021 · DOI

Abstract

Multi-Goal Multi-Agent Path Finding (MG-MAPF) is a generalization of the standard pathfinding problem where each agent must visit multiple goal locations. This paper presents two novel algorithms: Hamiltonian Conflict-Based Search (HCBS), which decouples goal ordering from pathfinding using search-based heuristics, and SMT-HCBS, which integrates both challenges into a logic-based SAT-solving framework. We evaluate these approaches on standard benchmarks, showing that while SMT-HCBS excels in tightly constrained, small-scale scenarios, HCBS provides superior scalability as the number of goals per agent increases.

1. Introduction

In standard Multi-Agent Path Finding (MAPF), agents move from unique start points to unique goal points without colliding. Real-world applications, such as warehouse logistics or maintenance robotics, often require agents to visit a set of locations in an efficient order. This Multi-Goal MAPF (MG-MAPF) problem combines collision avoidance with the Traveling Salesman Problem (TSP), making the search space significantly more complex as finding the optimal order to visit multiple goals is NP-hard.

2. Problem Definition

The MG-MAPF problem requires finding collision-free paths for a set of agents such that each agent visits all its assigned goal vertices. The objective is typically to minimize the Sum-of-Costs (SoC).

Figure 1: Illustration of an MG-MAPF instance where agents $a_1$ and $a_2$ must visit multiple goal locations.

As shown in Figure 1, the complexity arises from determining the optimal order to visit goals (the Hamiltonian path) while simultaneously resolving spatial-temporal conflicts with other agents.

3. Proposed Algorithms

We propose two distinct algorithmic paradigms to address the MG-MAPF challenge:

3.1 Hamiltonian Conflict-Based Search (HCBS)

HCBS is a search-based approach extending Conflict-Based Search (CBS). It employs a three-level hierarchy:

  • High Level: Resolves inter-agent collisions via constraints.
  • Middle Level: Determines the optimal goal vertex ordering for a single agent using A* search.
  • Low Level: Computes the shortest path between specific goals under collision constraints. To maintain efficiency, HCBS utilizes a Minimum Spanning Tree (MST) heuristic to estimate the cost of visiting remaining goals, offering a fast lower bound for the Hamiltonian path.

3.2 SMT-Hamiltonian-CBS (SMT-HCBS)

SMT-HCBS is a compilation-based approach that translates goal ordering and collision avoidance into a unified Boolean formula solved by a Satisfiability Modulo Theories (SMT) solver. It utilizes Multi-valued Decision Diagrams (MDDs) pruned by spanning tree costs to manage the formula size. This approach integrates goal ordering and collision resolution into a single logic-solving step.

4. Experimental Evaluation

The algorithms were tested on standard benchmarks from movingai.com, including small grids (empty-16-16), medium maps (random-32-32-20), and large game maps (lak303d). We varied the number of agents and the number of goals per agent ($|g| \in \{1, 2, 4, 8\}$).

5. Results and Discussion

Our experiments reveal a clear performance trade-off between the two methods:

  • Small Scale: SMT-HCBS generally outperforms HCBS on small maps with few goals ($|g| \le 4$), where SAT solvers efficiently handle tight constraints.
  • Scalability: As the number of goals increases, HCBS becomes the dominant approach.
Figure 4: Success rate comparison on the empty-16-16 map with 8 goals per agent. HCBS maintains a significantly higher success rate as the number of agents increases.

As illustrated in Figure 4, HCBS's decoupled approach and use of domain-specific MST heuristics allow it to scale to larger agent populations and more complex goal sets where the SMT-based approach's performance drops sharply.

6. Conclusion

This work demonstrates that decoupling goal ordering from pathfinding is highly effective for complex MG-MAPF instances. While integrated logic-based solvers like SMT-HCBS are powerful for small, highly constrained problems, the search-based HCBS framework offers the scalability required for real-world multi-goal applications. Future work includes exploring lazy formula generation and more advanced pruning techniques for the SMT-based framework.

Summary updated

BibTeX
@inproceedings{surynek2021multi,
  author = {Pavel Surynek},
  title = {{Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i14.17472},
}
Figure