TY - GEN
T1 - Multi-robot task allocation-complexity and approximation
AU - Aziz, Haris
AU - Chan, Hau
AU - Cseh, Ágnes
AU - Li, Bo
AU - Ramezani, Fahimeh
AU - Wang, Chenhao
N1 - Funding Information:
Aziz and Ramezani are supported by the Australian Defence Science and Technology Group (DSTG) under the project “Auctioning for distributed multi vehicle planning” (MYIP 9953) and by US Dept. of Air force under the project “Efficient and fair decentralized task allocation algorithms for autonomous vehicles” (FA2386-20-1-4063). Cseh was supported by the Federal Ministry of Education and Research of Germany in the framework of KI-LAB-ITSE (project number 01IS19066). Bo Li is supported by The Hong Kong Polytechnic University (Grant NO. P0034420).
Publisher Copyright:
© 2021 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Complexity
KW - Matching
KW - Robot-task allocation
UR - http://www.scopus.com/inward/record.url?scp=85111205467&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
AN - SCOPUS:85111205467
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 133
EP - 141
BT - 20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2021
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
T2 - 20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2021
Y2 - 3 May 2021 through 7 May 2021
ER -