2026-04-29T04:08:35Zhttps://repisalud.isciii.es/rest/oai/requestoai:repisalud.isciii.es:20.500.12105/204062024-11-29T07:06:43Zcom_20.500.12105_15322com_20.500.12105_2051col_20.500.12105_16967
Repisalud
author
Guerrero, Jose
author
Oliver, Gabriel
author
Valero, Oscar
2024-07-11T09:07:33Z
2024-07-11T09:07:33Z
2017-01-24
Guerrero J, Oliver G, Valero O. Multi-Robot Coalitions Formation with Deadlines: Complexity Analysis and Solutions. PLoS One. 2017 Jan 24;12(1):e0170659.
1932-6203
http://hdl.handle.net/20.500.13003/9980
http://hdl.handle.net/20.500.12105/20406
28118384
10.1371/journal.pone.0170659
PloS One
2-s2.0-85010739390
396160500017
L614178734
Multi-robot task allocation is one of the main problems to address in order to design a multi-robot system, very especially when robots form coalitions that must carry out tasks before a deadline. A lot of factors affect the performance of these systems and among them, this paper is focused on the physical interference effect, produced when two or more robots want to access the same point simultaneously. To our best knowledge, this paper presents the first formal description of multi-robot task allocation that includes a model of interference. Thanks to this description, the complexity of the allocation problem is analyzed. Moreover, the main contribution of this paper is to provide the conditions under which the optimal solution of the aforementioned allocation problem can be obtained solving an integer linear problem. The optimal results are compared to previous allocation algorithms already proposed by the first two authors of this paper and with a new method proposed in this paper. The results obtained show how the new task allocation algorithms reach up more than an 80% of the median of the optimal solution, outperforming previous auction algorithms with a huge reduction of the execution time.
eng
Multi-Robot Coalitions Formation with Deadlines: Complexity Analysis and Solutions
research article