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).
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.
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