Preventing Deadlocks for Multi-Agent Pickup and Delivery in Dynamic Environments

The Multi-Agent Pickup and Delivery (MAPD) problem, in which a team of agents has to plan paths to accomplish incoming pickup and delivery tasks without collisions, has recently attracted significant attention both from academia and industry. In this paper, we consider a MAPD setting in which the environment is dynamic, namely it is populated by other moving agents, beyond those belonging to the team. For instance, in a warehouse, moving agents could be humans or cleaning robots. We assume that the team agents cannot communicate with the moving agents and cannot interfere with their tasks and paths, which are a priori unknown and cannot be modified. As a consequence, team agents have to reactively try to solve potential collisions when they appear. However, it can happen that some conflicts are not solvable without affecting the moving agents, resulting in deadlocks. Since deadlocks can become rather frequent, especially in crowded environments, in this paper we propose an approach that, by imposing minor constraints on the environment and the movements of the agents, solves potential collisions and prevents the formation of deadlocks by design. Experimental results show that our approach prevents deadlocks, even in very crowded environments, with negligible impact on the performance of task completion.