Efficient TSP-Based Task Group Allocation for Multi-Task Multi-Agent Pickup and Delivery

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.