# DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 35 references that are in the map.
- First posted on arXiv 11 Dec 2023.

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

- [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)
- [Optimal Target Assignment and Path Finding for Teams of Agents](https://mlsanity.com/paper/1612.05693/) (2016)
- [Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning](https://mlsanity.com/paper/2006.08845/) (2020)
- [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)
- [An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem](https://mlsanity.com/paper/1907.10360/) (2019)
- [MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding](https://mlsanity.com/paper/2103.09979/) (2021)
- [Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions](https://mlsanity.com/paper/2103.04516/) (2021)
- [Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding](https://mlsanity.com/paper/2208.01222/) (2022)

## Abstract (arXiv)

Multi-Agent Combinatorial Path Finding (MCPF) seeks collision-free paths for multiple agents from their initial to goal locations, while visiting a set of intermediate target locations in the middle of the paths. MCPF is challenging as it involves both planning collision-free paths for multiple agents and target sequencing, i.e., solving traveling salesman problems to assign targets to and find the visiting order for the agents. Recent work develops methods to address MCPF while minimizing the sum of individual arrival times at goals. Such a problem formulation may result in paths with different arrival times and lead to a long makespan, the maximum arrival time, among the agents. This paper proposes a min-max variant of MCPF, denoted as MCPF-max, that minimizes the makespan of the agents. While the existing methods (such as MS*) for MCPF can be adapted to solve MCPF-max, we further develop two new techniques based on MS* to defer the expensive target sequencing during planning to expedite the overall computation. We analyze the properties of the resulting algorithm Deferred MS* (DMS*), and test DMS* with up to 20 agents and 80 targets. We demonstrate the use of DMS* on differential-drive robots.