# Multi-Robot Task Allocation -- Complexity and Approximation

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 45 references that are in the map.
- First posted on arXiv 23 Mar 2021.

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

- [Task Allocation using a Team of Robots](https://mlsanity.com/paper/2207.09650/) (2022)
- [The Viability of Domain Constrained Coalition Formation for Robotic Collectives](https://mlsanity.com/paper/2306.05590/) (2023)
- [GRAPE-S: Near Real-Time Coalition Formation for Multiple Service Collectives](https://mlsanity.com/paper/2310.12480/) (2023)
- [Towards Practical Multi-Robot Hybrid Tasks Allocation for Autonomous Cleaning](https://mlsanity.com/paper/2303.06531/) (2023)
- [Model-Based Reinforcement Learning for Heterogeneous Multi-Robot Task Assignment Under Distribution Shifts](https://mlsanity.com/paper/2608.21554/) (2026)

## Abstract (arXiv)

Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations as well as polynomial-time algorithms for the general setting and important restricted settings.