Flexible and Efficient Deadlock Avoidance Control Strategy for multi-AGV Systems Based on Chain Structure Preservation

The existing deadlock handling methods for multi-AGV (automated guided vehicle) system are often too restrictive, which compresses the potential performance optimization space. This paper proposes a highly flexible deadlock avoidance algorithm to judge the chain structure of the state diagram based on the banker algorithm by analyzing the macro ring structure in the system state diagram, and implement flexible deadlock avoidance while ensuring the algorithm efficiency (the time complexity of the algorithm is O((|V|+|E|)|A|) in the worst case, where V, E, and A represent nodes, edges, and AGVs, respectively). The effectiveness of the proposed algorithm is verified by discrete event system simulation and practical system application. The results show that compared with the classical banker algorithm and its variants, the proposed algorithm can improve the allowable state space by more than 16% on typical road map, and the average task completion time is reduced by 15% when using the same task allocation and path planning algorithms. It demonstrates higher flexibility and effectively improves the potential of system performance optimization.