# An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2019.

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

- [MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding](https://mlsanity.com/paper/2103.09979/) (2021)
- [Task Allocation for Multi-Robot Task and Motion Planning: a case for Object Picking in Cluttered Workspaces](https://mlsanity.com/paper/2110.04089/) (2021)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding](https://mlsanity.com/paper/2208.01222/) (2022)
- [Hypergraph-based Multi-Robot Task and Motion Planning](https://mlsanity.com/paper/2210.04333/) (2022)
- [Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree](https://mlsanity.com/paper/2307.00663/) (2023)
- [A Task and Motion Planning Framework Using Iteratively Deepened AND/OR Graph Networks](https://mlsanity.com/paper/2503.07700/) (2025)
- [Optimal Multi-Agent Path Finding for Precedence Constrained Planning Tasks](https://mlsanity.com/paper/2202.10449/) (2022)
- [DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding](https://mlsanity.com/paper/2312.06314/) (2023)

## Abstract (arXiv)

We consider multi-agent transport task problems where, e.g. in a factory setting, items have to be delivered from a given start to a goal pose while the delivering robots need to avoid collisions with each other on the floor. We introduce a Task Conflict-Based Search (TCBS) Algorithm to solve the combined delivery task allocation and multi-agent path planning problem optimally. The problem is known to be NP-hard and the optimal solver cannot scale. However, we introduce it as a baseline to evaluate the sub-optimality of other approaches. We show experimental results that compare our solver with different sub-optimal ones in terms of regret.