摘要
针对基于栅格地图的路径规划算法大多存在路径规划时间长、转折点数量多、路径安全性差的问题,提出一种改进的跳点搜索方法。该算法主要有以下两点改进:①提出了新的邻居点选取策略,可以根据当前搜索方向和当前节点与终点方向动态选取有效邻居点;②改进了跳点选取机制,由于障碍物周围必然存在跳点,因此利用当前搜索方向和障碍物所在方向,将障碍物的顶点处作为新的跳点。为了验证改进跳点搜索算法的有效性,通过仿真实验将改进算法与跳点搜索算法分别在简单环境和复杂环境下作对比。结果表明,改进算法在扩展节点数量上平均减少了43.4%,运行时间平均减少了19.15%,转折点数量减少了42.44%,路径长度减少了2.12%。为了进一步验证路径安全性,在ROS机器人上进行实验,结果表明,将改进的跳点搜索算法应用于ROS机器人,机器人安全性良好。
Aiming at the problems of long path planning time,a large number of turning points,and poor path safety in most path planning algorithms based on grid maps,this paper proposes an improved jumping point search method.The algorithm mainly has the following two improvements:First,a new neighbor point selection strategy is proposed,which can dynamically select effective neighbor points according to the current search direction and the direction of the current node and the end point;second,improve the jump point selection mechanism,Because there must be jumping points around the obstacle,the current search direction and the direction of the obstacle are used to use the apex of the obstacle as the new jumping point.In order to verify the effectiveness of the improved jump point search algorithm proposed in this paper,we compared the improved algorithm with the jump point search algorithm in a simple environment and a complex environment through simulation experiments.The number of expanded nodes was reduced by 43.4% on average,the running time is reduced by an average of 19.15%,the number of turning points is reduced by 42.44%,and the path length is reduced by 2.12%.In order to further verify the safety of the path,we conducted experiments on the ROS robot.The results show that the improved jump point search algorithm is applied to the ROS robot,and the safety of the robot is good.
作者
王嘉翔
张赛
张伟
WANG Jiaxiang;ZHANG Sai;ZHANG Wei(School of Management,University of Shanghai for Science and Technology;School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)
出处
《软件导刊》
2025年第2期129-137,共9页
Software Guide
基金
国家自然科学基金项目(11502145)。
