Multi-Robot Task Allocation -- Complexity and Approximation

Haris Aziz, Hau Chan, Agnes Cseh, Bo Li, Fahimeh Ramezani, Chenhao Wang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


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.
Original languageEnglish
Title of host publicationThe 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021)
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Number of pages9
Publication statusPublished - 2021

Cite this