Multi-Robot Scheduling for Deadlock Avoidance Using Nonstop Areas

Warehouse automation has become an essential aspect of modern logistics management. A critical component of warehouse automation is the path finding algorithm, which is responsible for calculating the route for automated guided vehicles to navigate the warehouse. However, conventional single-agent path planning suffers from deadlocks, resulting in a significant reduction in throughput. On the other hand, optimal and complete multi-agent path finding algorithms are slow and computationally expensive, making them unsuitable for warehouses with multiple uncertainties that require constant replanning. In this paper, we propose a novel scheduling technique to avoid deadlocks by introducing nonstop areas based on the dynamics of vehicle intersections. We define critical areas in the warehouse as nonstop areas and prohibit robots from stopping and waiting within these areas. The robot’s reservation length is dynamically extended to ensure that it reserves the entire path through the nonstop area, preventing it from blocking other robots moving through the intersection in other directions. The optimal positions of the nonstop areas were determined in two steps: the placement step to find where the deadlock occurred, and the trimming step to remove the excess nonstop area tiles. Simulation results showed 100% deadlock prevention and significantly improved throughput with the inclusion of the proposed nonstop area. Moreover, the addition of the trimming step further increases the throughput up to 12.27%.