A Deadlock-Free Solution for Multi-Agent Pickup and Delivery in Presence of External Agents

We address the Multi-Agent Pickup and Delivery (MAPD) problem within environments populated by higher-priority external agents. MAPD requires a team of agents to find collision-free paths to complete pickup and delivery tasks that appear online. The presence of external agents imposes an additional challenge, requiring team agents to perform collision avoidance also with external agents. While team agents can use local observations to reactively avoid collisions with external agents, such reactive strategies are susceptible to causing deadlocks, where team agents cannot proceed without causing a collision. We demonstrate that, by imposing constraints on the cardinality of both team and external agents within defined regions of the environment, proactive prevention of deadlocks can be achieved. Compared to state-of-the-art solutions for the same problem, our method broadens the range of environments that can be traversed deadlock-free and reduces the restrictions on the placement of tasks. Experimental results indicate that our approach effectively eliminates deadlocks at the cost of increasing the time required by team agents to solve the MAPD problem, compared to baseline solutions that assume full cooperation or that allow the occurrence of deadlocks.