Robust Space-Time A* for Human-In-The-Loop Multi-Agent Pickup and Delivery

The Multi-Agent Path Finding (MAPF) and its extension, Multi-Agent Pickup and Delivery (MAPD), have received much attention and various algorithms have been proposed in academia. In the industrial sector, on the other hand, automatic safe control of teams of robots and AGVs on factory floors and logistic warehouses for pickup and delivery operations has also been studied intensively. However, it is still difficult for robots to fully automate all tasks in real warehouses/factories. Therefore, robots and human workers are desired to collaborate on tasks that suit each other and work at the same time in the same warehouse. In this paper, we extend the MAPD problem to a new problem with a human-in-theloop environment where robots and human workers work at the same time in the same warehouse. We propose a robust spacetime A* based multi-task MAPD algorithm that provably solves this extended problem. We also demonstrate the robustness of our proposed algorithm by comparing with the traditional (non-robust) MAPD algorithm; it is observed that workers and robots tend to gather around themselves in clusters when robust parameters are large.