Research on Bidirectional Jump Point Search Algorithm of Global Path Planning for Mobile Robots
-
摘要: 针对跳点搜索算法在移动机器人全局路径规划中预处理规则存在不安全、路径搜索时间长和内存消耗大等问题，提出了一种双向跳点搜索算法的全局路径规划方法。该方法改进了跳点筛选规则，且从两个方向交替进行路径搜索，使得路径搜索时间和扩展节点大大减少，同时也提高了机器人的安全。为验证该算法的有效性，使用不同规格的栅格地图进行了仿真实验，仿真结果表明，双向跳点搜索算法的路径搜索时间比跳点搜索算法短，且栅格地图越大，效果越明显。最后在实际的移动服务机器人中进行了导航实验，实验结果证明双向跳点搜索算法比跳点搜索算法的路径搜索时间减少约30%，且安全性高。Abstract: In view of the jump point search algorithm' s unsafe preprocessing rules, long path search time and large memory consumption in global path planning of mobile robots, a global path planning method based on bidirectional jump point search algorithm is proposed in this paper. This new method improves the jump point filtering rules, and alternately searches the path from two directions, which greatly reduces the search time and extension nodes, and improves the safety of the robot. In order to verify the effectiveness of the algorithm, raster maps of different specifications are used for simulation experiments. The simulation results show that the path search time of bidirectional jump point search algorithm is shorter than that of jump point search algorithm, and the larger the raster map is, the more obvious the effect is. Finally, the navigation experiment is carried out in the actual mobile service robot. The experimental results show that the bidirectional jump point search algorithm reduces the path search time by about 30% compared with the jump point search algorithm, and the security is higher.
-
Key words:
- robots /
- path planning /
- jump point search /
- A* algorithm
-
表 1 JPS和双向JPS算法的搜索时间与扩展节点数量对比
地图大小 搜索时间/ms 路径长度/格 搜索节点/个 搜索时间之比 搜索节点之比 JPS算法 双向JPS算法 JPS算法 双向JPS算法 JPS算法 双向JPS算法 15×15 2 2 26.14 28.48 19 21 1 0.90 30×30 5 4 79.21 71.99 70 45 1.25 1.55 50×50 12 8 214.08 212.08 109 68 1.5 1.60 100×100 26 12 283.97 255.56 194 98 2.17 1.98 
下载: 导出CSV
表 2 目标点1下2种算法寻路时间对比
参数 JPS算法 双向JPS算法 行走路径长度/m 5.4 5.5 寻路时间/ms 66.61 41.89 行走时间/s 25.72 22.88 搜索节点/个 53 39
下载: 导出CSV
表 3 目标点2下2种算法寻路时间对比
参数 JPS算法 双向JPS算法 行走路径长度/m 8.5 8.2 寻路时间/ms 95.74 67.56 行走时间/s 39.41 38.24 搜索节点/个 77 45
下载: 导出CSV
-
[1] 陈彦杰, 王耀南, 谭建豪, 等. 局部环境增量采样的服务机器人路径规划[J]. 仪器仪表学报, 2017, 38(5): 1093-1100 doi: 10.3969/j.issn.0254-3087.2017.05.007Chen Y J, Wang Y N, Tan J H, et al. Incremental sampling path planning for service robot based on local environments[J]. Chinese Journal of Scientific Instrument, 2017, 38(5): 1093-1100 (in Chinese doi: 10.3969/j.issn.0254-3087.2017.05.007 [2] Khatib O. Real-time obstacle avoidance for manipulators and mobile robots[J]. The International Journal of Robotics Research, 1986, 5(1): 90-98 doi: 10.1177/027836498600500106 [3] Cao L, Qiao D, Xu J W. Suboptimal artificial potential function sliding mode control for spacecraft rendezvous with obstacle avoidance[J]. Acta Astronautica, 2018, 143: 133-146 doi: 10.1016/j.actaastro.2017.11.022 [4] 李擎, 张超, 韩彩卫, 等. 动态环境下基于模糊逻辑算法的移动机器人路径规划[J]. 中南大学学报, 2013, 44(S2): 104-108Li Q, Zhang C, Han C W, et al. Path planning based on fuzzy logic algorithm for mobile robots in dynamic environments[J]. Journal of Central South University , 2013, 44(S2): 104-108 (in Chinese [5] Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271 doi: 10.1007/BF01386390 [6] Dechter R, Pearl J. Generalized best-first search strategies and the optimality of A*[J]. Journal of the ACM, 1985, 32(3): 505-536 doi: 10.1145/3828.3830 [7] 黄辰, 费继友, 刘洋, 等. 基于动态反馈A*蚁群算法的平滑路径规划方法[J]. 农业机械学报, 2017, 48(4): 34-40, 120 doi: 10.6041/j.issn.1000-1298.2017.04.004Huang C, Fei J Y, Liu Y, et al. Smooth path planning method based on dynamic feedback A* ant colony algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2017, 48(4): 34-40, 120 (in Chinese doi: 10.6041/j.issn.1000-1298.2017.04.004 [8] 裴以建, 杨亮亮, 杨超杰. 基于一种混合遗传算法的移动机器人路径规划[J]. 现代电子技术, 2019, 42(2): 183-186Pei Y J, Yang L L, Yang C J. Mobile robot path planning based on a hybrid genetic algorithm[J]. Modern Electronics Technique, 2019, 42(2): 183-186 (in Chinese [9] 王功亮, 王好臣, 李振雨, 等. 基于优化遗传算法的移动机器人路径规划[J]. 机床与液压, 2019, 47(3): 37-40, 100Wang G L, Wang H C, Li Z Y, et al. Path planning for mobile robots based on optimized genetic algorithm[J]. Machine Tool & Hydraulics, 2019, 47(3): 37-40, 100 (in Chinese [10] Tang B W, Zhu Z X, Luo J J. A convergence-guaranteed particle swarm optimization method for mobile robot global path planning[J]. Assembly Automation, 2017, 37(1): 114-129 doi: 10.1108/AA-03-2016-024 [11] 游晓明, 刘升, 吕金秋. 一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J]. 控制与决策, 2017, 32(3): 552-556You X M, Liu S, Lyu J Q. Ant colony algorithm based on dynamic search strategy and its application on path planning of robot[J]. Control and Decision, 2017, 32(3): 552-556 (in Chinese [12] 刘建华, 杨建国, 刘华平, 等. 基于势场蚁群算法的移动机器人全局路径规划方法[J]. 农业机械学报, 2015, 46(9): 18-27 doi: 10.6041/j.issn.1000-1298.2015.09.003Liu J H, Yang J G, Liu H P, et al. Robot global path planning based on ant colony optimization with artificial potential field[J]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(9): 18-27 (in Chinese doi: 10.6041/j.issn.1000-1298.2015.09.003 [13] 张原艺, 章政, 王泉. 基于改进多步长蚁群算法的机器人路径规划[J]. 计算机工程与设计, 2018, 39(12): 3829-3834, 3866Zhang Y Y, Zhang Z, Wang Q. Robot path planning based on improved multi-step ant colony algorithm[J]. Computer Engineering and Design, 2018, 39(12): 3829-3834, 3866 (in Chinese [14] 邱磊. 利用跳点搜索算法加速A*寻路[J]. 兰州理工大学学报, 2015, 41(3): 102-107 doi: 10.3969/j.issn.1673-5196.2015.03.022Qiu L. Speed-up of A* pathfinding with jump point search algorithm[J]. Journal of Lanzhou University of Technology, 2015, 41(3): 102-107 (in Chinese doi: 10.3969/j.issn.1673-5196.2015.03.022 [15] 赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910Zhao X, Wang Z, Huang C K, et al. Mobile robot path planning based on an improved A* algorithm[J]. Robot, 2018, 40(6): 903-910 (in Chinese -
点击查看大图
图(14) / 表(3)
计量
- 文章访问数: 378
- HTML全文浏览量: 57
- PDF下载量: 32
- 被引次数: 0
