基于链状结构保持的多AGV系统灵活高效死锁避免控制策略

来源：机器人杂志2023年第5期北京时间：

作者：陈果, 何代钰, 欧阳博, 颜志, 文蔚, 饶有福, 王耀南

摘要：现有的多AGV(自动导引车)系统处理死锁的方案往往约束过强, 压缩了潜在的性能优化空间。本文提出一种高度灵活的死锁避免算法, 通过分析系统状态图中的宏环结构并结合银行家算法来实现状态图的链状结构判断, 在确保算法高效性(最坏情形时间复杂度为O((|V|+|E|)|A|), 其中V、E、A分别代表节点、边、AGV)的同时, 实现了灵活的死锁避免。通过离散事件系统仿真及实际系统应用验证了算法的有效性, 结果表明, 在典型路线图上, 该算法相较于经典的银行家算法及其变种, 容许覆盖率提升高于16%, 在使用相同任务分配、路径规划算法的情况下, 任务平均完成时间降低了15%, 具有更高的灵活性, 有效提升了系统性能优化的潜力。

关键词：多AGV系统, 死锁避免, 集中式控制, 调度策略, 图论