BROWSE
Detail
Journal Article
Efficient TSP-Based Task Group Allocation for Multi-Task Multi-Agent Pickup and Delivery
- Authors
- Seungbeen Lee, Chanyoung Lee, Wonpil Yu, Soohwan Song
- Issue Date
- 2025-12
- Citation
- IEEE Access, v.13, pp.198748-198761
- ISSN
- 2169-3536
- Publisher
- IEEE
- Language
- English
- Type
- Journal Article
- Abstract
- This study addresses the multi-agent pickup and delivery (MAPD) problem, which involves assigning tasks and planning paths for multiple robots to transport goods. Specifically, we focus on the multi-task MAPD where each task consists of multiple targets, and robots are assigned multiple tasks within a budget to deliver in one trip. This problem is challenging because it involves considering an optimal visitation sequence of targets during task assignment. Additionally, managing tasks that are continuously released online demands an efficient algorithm. Therefore, we propose a new task allocation method that iteratively identifies tasks with the shortest detour paths using the TSP algorithm. This method consistently ensures that task groups have the most efficient travel routes for tasks released online. Additionally, we boost computational efficiency by addressing an online TSP, speeding up the computation by focusing on the visitation sequence of only new targets instead of all targets. Extensive experiments on benchmark scenarios demonstrate that our method outperforms existing state-of-the-art approaches, achieving over a 31% reduction in service time.
- KSP Keywords
- Allocation method, Computational Efficiency, Efficient algorithms, Multiple tasks, Pickup and delivery, Service Time, Task allocation, existing state, multi-agent, multi-task, multiple robots
This work is distributed under the term of Creative Commons License (CCL)
(CC BY)
(CC BY)
