In context
By 2023, multi-AGV systems were widely deployed in smart manufacturing and warehousing, yet deadlock handling remained a bottleneck. Existing methods often imposed overly strict constraints, limiting performance optimization. This paper, published in the Chinese journal Robot, addressed the need for a more flexible deadlock avoidance approach that balances efficiency and state-space permissiveness.
What was reported
Researchers from Hunan University and SANY Heavy Industry proposed a deadlock avoidance control strategy based on preserving the chain structure of the system state diagram. The algorithm analyzes macro-ring structures and uses the banker's algorithm to judge chain structure, achieving a worst-case time complexity of O((|V|+|E|)|A|), where V, E, and A represent nodes, edges, and AGVs, respectively.
Unlike prior methods that required strict reachability conditions, this approach allows AGVs to stop and reverse at leaf nodes, converting the system into an equivalent irreversible one by adding self-loops. The strategy constructs a macro-cycle compression graph (MCG) to efficiently identify and maintain safe states.
Validation via discrete-event simulation and practical application showed that on typical roadmaps, the algorithm increased the allowable state space by over 16% compared to classical banker's algorithm variants. Under the same task allocation and path planning, average task completion time dropped by 15%, demonstrating higher flexibility and improved optimization potential.
Why it mattered
This work offered a practical way to relax constraints in deadlock avoidance without sacrificing polynomial-time efficiency, enabling more dynamic and efficient AGV fleet operations in real-world industrial settings. It also provided a scheduling architecture integrating task allocation, path planning, and real-time dispatch, supporting the trend toward more adaptive and scalable automation.
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%.
Source: 《机器人》期刊 (robot.sia.cn) · Published 2023-09-16 · “基于链状结构保持的多AGV系统灵活高效死锁避免控制策略”