在静态栅格地图中,针对传统蚁群算法进行 AGV(Automated Guided Vehicle,自动引导车)路径规划收敛慢且搜索结果容易陷入局部最优的问题,提出一种融合跳点搜索(Jump Point Search,JPS)和双向并行蚁群搜索的改进算法.首先,对实际研究环境进行栅格化建模,使用改进的跳点搜索算法生成双向搜索的初始次优路径,为双向蚁群搜索提供初始搜索方向参考.其次,在双向并行蚁群搜索过程中采用改进的转移概率启发函数,该函数在确定下一个转移节点时考虑了避免AGV与障碍物碰撞的因素,同时通过设计信息素共享机制并结合改进的信息素增量及浓度两种融合模型,共享和更新全局信息素浓度,以更好地探索和优化路径,保证双向路径连结.最后,与传统蚁群算法进行实验结果对比,验证了改进算法的全局搜索能力、效率和安全性.
AGV path planning via integration of jump point search with bi-directional parallel ant colony algorithm
In this article,an improved algorithm that combines jump point search and bi-directional parallel ant colony search is proposed for static grid maps to address the slow convergence and easy trapping in local optima per-plexed traditional ant colony algorithms for Automated Guided Vehicle(AGV)path planning.First,the actual re-search environment is modeled by gridization,and the improved jump point search algorithm is used to generate the initial suboptimal path for bi-directional search,providing a reference for the initial search direction of bi-directional ant colony search.Second,an improved transition probability heuristic function is used in the bi-directional parallel ant colony search process,which considers the avoidance of collision between AGV and obstacles when determining the next transition node.Meanwhile,by designing an information sharing mechanism and combining two fusion models of improved information increment and concentration,the global information concentration is shared and up-dated to better explore and optimize the path and ensure the connection of bi-directional paths.Finally,experimental results are compared with those of traditional ant colony algorithms to verify the improved algorithm's global search capability,efficiency and security.
jump point search algorithmant colony algorithmautomated guided vehicle(AGV)path planningbi-directional parallel
万方数据
维普
