融合跳点搜索和动态窗口算法的AGV路径规划

AGV path planning combining jump point search and dynamic window algorithm

  • 摘要: 针对传统跳点搜索(jump point search,JPS)算法在复杂环境下规划的路径存在拓展节点较多、路径不平滑、安全性差以及难以跟随最优路径的问题,提出一种基于改进JPS算法和动态窗口算法(dynamic window approach,DWA)的融合方法. 首先,改进JPS算法预处理拓展节点时的跳点搜索策略,从路径的起点和目标点交替式搜索路径,提高自动引导车辆(automated guided vehicle,AGV)路径搜索效率;其次,引入环境障碍率优化启发函数,增强AGV路径搜索的安全性和目的性;然后,使用改进的Floyd算法对所得路径处理,以确保最短路径也是安全路径;接着,采用动态切点调整法对转折点平滑处理,使路径符合AGV的动态特性;最后,在DWA算法的评价函数中,对已知障碍物和未知障碍物分类处理,对方位角评价函数进行改进,使动态路径规划兼顾路径全局最优性和实时避障能力. 为验证算法的有效性,在不同复杂度的栅格地图中进行对比仿真实验. 实验结果表明,改进JPS算法规划的路径相较于传统JPS算法,拓展节点量平均减少23.3%,转弯角度平均减小45.8%,路径搜索时间平均减少48.1%,路径长度平均缩短5.7%. 所提融合算法规划的路径相较于传统融合算法,路径搜索时间平均减少6.1%,路径长度平均缩短0.9%.

     

    Abstract: The path planned by traditional jump point search (JPS) algorithm in complex environment has many expansion nodes, uneven path, poor security and difficulty to follow the optimal path. A fusion method based on improved JPS algorithm and dynamic window approach (DWA) is proposed. Firstly, JPS algorithm is improved to search the path alternately from the starting point and the target point to improve the efficiency of AGV (automated guided vehicle) path search. Secondly, the environmental obstacle rate optimization heuristic function is introduced to enhance the safety and purpose of AGV path search. Thirdly, the improved Floyd algorithm is used to process the obtained path to ensure that the shortest path is also a safe path. Then, the dynamic tangential point adjustment method is used to smooth the turning point to make the path conform to the dynamic characteristics of AGV. Finally, in the evaluation function of DWA algorithm, the known and unknown obstacles are classified, and the azimuth evaluation function is improved, so that the dynamic path planning can take into account the global optimization of the path and the real-time obstacle avoidance ability. In order to verify the effectiveness of the algorithm, comparative simulation experiments are carried out in raster maps of different complexity. The experimental results show that the paths planned by the improved JPS algorithm have an average reduction of 23.3% in the number of expanded nodes, an average reduction of 45.8% in the turning angle, an average reduction of 48.1% in path search time, and an average reduction of 5.7% in path length compared to the traditional JPS algorithm. The paths planned by the proposed fusion algorithm have an average reduction of 6.1% in path search time and an average reduction of 0.9% in path length compared to the traditional fusion algorithm.

     

/

返回文章
返回