摘要
针对传统CBS算法在复杂工况下为多AGV规划路径时存在的运算时间较长、冲突处理效率较低,约束树扩展节点生成数较多等问题,提出了一种改进的CBS算法(WPP-CBS)。在处理冲突的顺序方面,提出了加权优先队列机制,根据路径的代价、冲突数量以及扩展节点的生成数为每个路径分配不同的权重,动态调整对冲突队列的处理优先级;在冲突检测信息采集方面,引入并行化碰撞检测算法,分解冲突集合,采用多计算单元,允许多个AGV路径同时检测碰撞,加快冲突采集速度。在路径规划方面,提出剪枝策略,剔除无效搜索空间和冗余路径,达到优化路径规划效率和质量。仿真与实验结果表明,WPP-CBS相比CBS、ECBS、ASB-CBS的运算时间平均分别减少82.04%、40.58%、40.54%,扩展节点生成数量平均分别减少80.08%、25.62%、22.57%;在实验场景下,其运算时间平均分别减少16.91%、10.56%、5.80%,扩展节点生成数量平均分别减少52.16%、23.33%、18.05%。研究为大规模多AGV系统的路径规划提供了有效解决方案。
In response to the problems of long computation time,low conflict handling efficiency,and excessive number of generated nodes in the expansion of the constraint tree when the traditional CBS algorithm plans paths for multi-AGVs under complex conditions,an improved CBS algorithm(WPP-CBS)was proposed.In terms of the sequence of conflict handling,a weighted priority queue mechanism was proposed,which assigned different weights to each path based on the cost of the path,the number of conflicts,and the number of generated nodes,dynamically adjusting the processing priority of the conflict queue.In terms of conflict detection information collection,a parallelized collision detection algorithm was introduced,the conflict set was decomposed,and multiple computing units were used to allow multi-AGV paths to simultaneously detect collisions,thereby accelerating the speed of conflict collection.In terms of path planning,a pruning strategy was proposed to eliminate invalid search spaces and redundant paths,achieving optimization of path planning efficiency and quality.Simulation and experimental results show that compared with CBS,ECBS,and ASB-CBS,the average computation time of WPP-CBS is reduced by 82.04%,40.58%,and 40.54% respectively,and the average number of generated nodes is reduced by 80.08%,25.62%,and 22.57% respectively;in the experimental scenarios,the average computation time is reduced by 16.91%,10.56%,and 5.80% respectively,and the average number of generated nodes is reduced by 52.16%,23.33%,and 18.05% respectively.The research provides an effective solution for path planning in large-scale multi-AGV systems.
作者
宋莹
杨金波
胡东东
SONG Ying;YANG Jinbo;HU Dongdong(School of Automation,Wuxi University,Wuxi Jiangsu 214105,China;School of Automation,Nanjing University of Information Science&Technology,Nanjing Jiangsu 210044,China)
出处
《机床与液压》
北大核心
2026年第5期93-102,共10页
Machine Tool & Hydraulics
