Anytime Multi-Task Multi-Agent Pickup and Delivery Under Energy Constraint

摘要

Various Multi-Agent Path Finding (MAPF) and its extension, Multi-Agent Pickup and Delivery (MAPD) algorithms have been studied in academia. In the industrial sector, however, automatic safe control of teams of robots and AGVs on factory floors and logistic warehouses for pickup and delivery operations have also been studied intensively. In this paper, we extend our previous work of online multi-task MAPD to a new problem where (i) task can be allocated to any vacant agent independent of the location of that agent — called “anytime task allocation” in this paper, and (ii) each agent is subject to energy constraint. The proposed anytime task allocation MAPD algorithm achieves <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$5 - 19 \%$</tex-math></inline-formula> shorter makespan paths compared to the baseline multi-task MAPD in wide range of agent numbers. We also examine the behavior of the proposed multi-task MAPD algorithm under various energy constraint, by changing power limits and energy charge speeds of individual agents. We find that energy charge speed has a large impact on the makespan when power limit is small. We also find that small energy charge speed typically requires a large number of agents in order to achieve the same makespan. These results demonstrate that our proposed multi-task MAPD algorithm can be useful in choosing proper agent numbers in order to achieve prescribed makespans which is more practical as compared to our previous multi-task MAPD.