A TSP-Based Online Algorithm for Multi-Task Multi-Agent Pickup and Delivery

The Multi-Agent Path Finding (MAPF) and its extension, Multi-Agent Pickup and Delivery (MAPD), have received much attention in academia. In industry, on the other hand, automatic control of teams of robots and AGVs on factory floors and logistic warehouses for pickup and delivery operations have also been studied intensively. Currently, MAPD problem formulation does not fully capture important aspects of many real-world industrial applications, e.g., MAPD allocates only one task at a time for each agent, payload capacity for each agent is ignored, and pickup & dropoff operations are assumed to be done immediately. In this letter, we extend MAPD problem to a multi-task setting where each agent is allocated multiple tasks considering payload capacity as well as pickup & dropoff cost. We propose an online multi-task MAPD algorithm which is a combination of MAPF and Traveling Salesman Problem (TSP) algorithm. Comparisons between the proposed and conventional MAPD show that the proposed MAPD is able to achieve 18% -38% shorter makespan paths in wide range of agent numbers. We also examine the behavior of the proposed online multi-task MAPD by changing payload capacity distribution and pickup & dropoff cost. Simulation results indicate that increase of pickup cost can largely increase the makespan when agent number is small; on the other hand, increase of dropoff cost tend to increase the makespan when agent number is large. Our empirical study also demonstrates that the proposed online multi-task MAPD is applicable to large scale environment (e.g., agent number =300) in an online manner.