Deadlock avoidance dynamic routing algorithm for a massive fleet bi-directional AGV system

Abstract

In a bi-directional AGV system, it is essential to avoid the deadlock of AGVs. Avoiding deadlock becomes more challenging if AGV's tasks are continuously given in a fulfillment warehouse where operates dozens to hundreds of AGVs. In this paper, to prevent deadlock in the corresponding environment, the Active path reservations method limits the direction of some path in real-time when AGV moves, and the Dynamic Dijkstra algorithm, which finds the shortest route based on the path reserved status, were used in simultaneously. In addition to the Dijkstra algorithm, the proposed method can be used with other routing algorithms. Therefore, a more efficient transport system considering the congestion of AGV can be developed. The proposed method's efficiency and scalability were verified using Applied Materials AutoMod™ (version 14.0) simulation software.