.png){kind=icon}
Return
Efficient Decentralized Parallel Task Allocation for Multiple Robots
.png){kind=icon}
PRE
AI
DOI：10.1109/TRO.2025.3613566.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This article deals with large-scale decentralized task allocation problems for multiple heterogeneous robots. One of the grand challenges with decentralized task allocation problems is the NP-hardness for computation and communication. This article proposes a decentralized decreasing threshold task allocation (DTTA) algorithm that enables parallel allocation by leveraging a decreasing threshold to handle the NP-hardness. DTTA can release both computation and communication burdens for multiple robots in a decentralized network. In addition, DTTA provides a theoretical guarantee of the quality of the solution for maximizing submodular utility functions. Theoretical analysis indicates that DTTA can provide an optimality guarantee of $(1-\epsilon)/2$ with computation complexity of $O(\min (r^{2}, \frac{r}{\epsilon }\ln \frac{r}{\epsilon }))$ for each robot, where $\epsilon$ is the parameter controlling the decreasing speed of the threshold, $r$ is the number of tasks. To examine the performance of the proposed algorithm, we conduct numerical simulations based on a multitarget surveillance scenario. Simulation results demonstrate that DTTA delivers comparable solution quality significantly faster than state-of-the-art task allocation algorithms. Its advantages are particularly pronounced in large-scale missions with thousands of tasks and robots.
Keywords:
Decentralized task allocation
decreasing threshold
multirobot systems
parallel allocation
submodularity
Journal
IF:
10.5
Papers:
3.3K
Citations:
2.8W
Organization
Cited Papers
No cited papers available