# MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem

arXiv: https://arxiv.org/abs/2404.19518 · HTML: https://mlsanity.com/paper/2404.19518/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 30 Apr 2024.

## Builds on (most cited first, 8 of 8)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots](https://mlsanity.com/paper/1409.2399/) (2014)
- [Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering](https://mlsanity.com/paper/2009.05161/) (2020)
- [Multi-Goal Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2208.01223/) (2022)
- [MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding](https://mlsanity.com/paper/2103.09979/) (2021)
- [Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks](https://mlsanity.com/paper/2110.08802/) (2021)

## Built on by (most cited first, 3 of 3)

- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [PaperFit: Vision-in-the-Loop Typesetting Optimization for Scientific Documents](https://mlsanity.com/paper/2605.10341/) (2026)
- [Solving Multi-Agent Multi-Goal Path Finding Problems in Polynomial Time](https://mlsanity.com/paper/2512.22171/) (2025)

## Abstract (arXiv)

With the expansion of the scale of robotics applications, the multi-goal multi-agent pathfinding (MG-MAPF) problem began to gain widespread attention. This problem requires each agent to visit pre-assigned multiple goal points at least once without conflict. Some previous methods have been proposed to solve the MG-MAPF problem based on Decoupling the goal Vertex visiting order search and the Single-agent pathfinding (DVS). However, this paper demonstrates that the methods based on DVS cannot always obtain the optimal solution. To obtain the optimal result, we propose the Multi-Goal Conflict-Based Search (MGCBS), which is based on Decoupling the goal Safe interval visiting order search and the Single-agent pathfinding (DSS). Additionally, we present the Time-Interval-Space Forest (TIS Forest) to enhance the efficiency of MGCBS by maintaining the shortest paths from any start point at any start time step to each safe interval at the goal points. The experiment demonstrates that our method can consistently obtain optimal results and execute up to 7 times faster than the state-of-the-art method in our evaluation.