# MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 27 references that are in the map.
- First posted on arXiv 18 Mar 2021.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Optimal Target Assignment and Path Finding for Teams of Agents](https://mlsanity.com/paper/1612.05693/) (2016)
- [Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering](https://mlsanity.com/paper/2009.05161/) (2020)
- [An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem](https://mlsanity.com/paper/1907.10360/) (2019)
- [Subdimensional Expansion for Multi-objective Multi-agent Path Finding](https://mlsanity.com/paper/2102.01353/) (2021)
- [S^*: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding](https://mlsanity.com/paper/2103.08155/) (2021)
- [Generalized multiple depot traveling salesmen problem - polyhedral study and exact algorithm](https://mlsanity.com/paper/1508.01813/) (2015)

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

- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks](https://mlsanity.com/paper/2201.06014/) (2022)
- [iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning](https://mlsanity.com/paper/2405.00285/) (2024)
- [Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree](https://mlsanity.com/paper/2307.00663/) (2023)
- [MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem](https://mlsanity.com/paper/2404.19518/) (2024)
- [Multi-objective Conflict-based Search Using Safe-interval Path Planning](https://mlsanity.com/paper/2108.00745/) (2021)
- [Subdimensional Expansion Using Attention-Based Learning For Multi-Agent Path Finding](https://mlsanity.com/paper/2109.14695/) (2021)
- [DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding](https://mlsanity.com/paper/2312.06314/) (2023)

## Abstract (arXiv)

In multi-agent applications such as surveillance and logistics, fleets of mobile agents are often expected to coordinate and safely visit a large number of goal locations as efficiently as possible. The multi-agent planning problem in these applications involves allocating and sequencing goals for each agent while simultaneously producing conflict-free paths for the agents. In this article, we introduce a new algorithm called MS* which computes an optimal solution for this multi-agent problem by fusing and advancing state of the art solvers for multi-agent path finding (MAPF) and multiple travelling salesman problem (mTSP). MS* leverages our prior subdimensional expansion approach for MAPF and embeds the mTSP solvers to optimally allocate and sequence goals for agents. Numerical results show that our new algorithm can solve the multi-agent problem with 20 agents and 50 goals in a minute of CPU time on a standard laptop.