Research on Improved A* Algorithm Integrating Vector Cross-product and Jump Point Search Strategy
-
摘要: 为解决传统A*寻路算法在搜索过程中会产生大量冗余节点，导致算法整体搜索效率低，运算内存消耗大等问题，从A*算法的两个重要决策点出发，改进算法的代价评估函数与邻节点搜索策略，提出一种改进融合算法。首先，采用向量叉积与尺度平衡因子相结合的方法优化传统A*算法的启发函数，减少A*算法寻路过程中在最优路径周围产生的具有相同代价值的冗余节点，减少了对称路径的搜索；其次，融合跳点搜索(Jump point search, JPS)策略，通过逻辑判断实现路径的变步长跳跃搜索，避免了A*算法逐层搜索效率低的弊端。在不同尺寸的栅格地图中进行仿真分析，发现改进融合算法相比于传统A*算法，在路径长度基本相等的情况下，节点搜索数量约减少95%，且与传统JPS寻路算法相比，有效过滤了路径周围复杂形状障碍物产生的大量冗余跳点。最后，将改进融合算法应用于ROS移动机器人并进行对比实验以验证算法的可行性。实验结果表明：改进融合算法在获得高效安全的路径基础上，搜索效率相比于A*算法可提高约94%。Abstract: The traditional A* routing algorithm has many problems in the search process, such as many redundant nodes, low overall search efficiency and large computational memory consumption. To solve these problems, in this paper, starting from the two important decision points of the A* algorithm, an improved fusion algorithm was proposed by improving the cost evaluation function and adjacent node search strategy of the algorithm. Firstly, the combination of vector cross-product and scale balance factor was selected to optimize the heuristic function of traditional A* algorithm, which reduced the redundant nodes with the same generation value around the optimal path in the routing process of A* algorithm and reduced the search of symmetric path. Secondly, the algorithm integrated the jump point search strategy and realized the variable step size jump search of the path through logical judgment, which avoided the disadvantages of low search efficiency of A* algorithm layer by layer. Through simulation analysis in grid maps of different sizes, it was found that, compared with the traditional A* algorithm, the improved fusion algorithm reduced the number of node searches by approximately 95% at the same path length, and effectively filtered many redundant hops generated by complex shape obstacles around the path compared with the traditional JPS routing algorithm. Finally, the improved fusion algorithm was applied to ROS mobile robot, and comparative experiments were carried out to verify the feasibility of the algorithm. The experimental results showed that the search efficiency of the improved fusion algorithm was approximately 94% higher than that of A* algorithm on the basis of obtaining efficient and safe paths.
-
Key words:
- path planning /
- cross-product /
- jump point search /
- A* algorithm /
- mobile robot
-
图 9 5种不同算法的50×50地图仿真结果
Figure 9. 50×50 map simulation results of five different algorithms
图 10 5种不同算法的100×100地图仿真结果
Figure 10. 100×100 map simulation results of five different algorithms
表 1 不同尺寸栅格地图中几种算法的搜索性能
Table 1. Search performance of several algorithms in occupancy grid maps of different sizes
地图大小 算法 搜索时间/ms 搜索节点 路径长度/格 A* 1.995 120 22.73 改进A* 0.997 89 23.30 20×20 JPS 0.979 23 22.73 文献[11] 0.928 140 23.31 融合 0.960 23 22.73 A* 16.284 1 002 69.84 改进A* 10.198 692 69.84 50×50 JPS 6.491 113 69.84 文献[11] 5.845 1 028 73.012 融合 3.981 76 69.84 A* 80.385 3 949 111.88 改进A* 32.413 1 506 112.37 75×75 JPS 38.895 206 111.88 文献[11] 24.321 2 706 115.05 融合 14.129 63 112.37 A* 109.307 5 807 145.82 改进A* 50.273 3 044 149.92 100×100 JPS 64.539 425 145.82 文献[11] 39.432 3 166 150.17 融合 17.764 155 149.92 
下载: 导出CSV
-
[1] MAC T T, COPOT C, TRAN D T, et al. Heuristic approaches in robot path planning: a survey[J]. Robotics and Autonomous Systems, 2016, 86: 13-28. doi: 10.1016/j.robot.2016.08.001 [2] DENG X, LI R F, ZHAO L J, et al. Multi-obstacle path planning and optimization for mobile robot[J]. Expert Systems with Applications, 2021, 183: 115445. doi: 10.1016/j.eswa.2021.115445 [3] 史恩秀, 黄玉美, 朱从民, 等. 差速驱动轮式移动机器人路径规划新策略[J]. 中国机械工程, 2012, 23(23): 2805-2809. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGJX201223007.htmSHI E X, HUANG Y M, ZHU C M, et al. A novel method of planning path for DDWMR[J]. China Mechanical Engineering, 2012, 23(23): 2805-2809. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGJX201223007.htm [4] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271. doi: 10.1007/BF01386390 [5] HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107. doi: 10.1109/TSSC.1968.300136 [6] 周相坡, 周依尔, 徐立军, 等. 一种基于概率路线图的月球巡航车路径规划算法[J]. 空间控制技术与应用, 2020, 46(6): 43-49. https://www.cnki.com.cn/Article/CJFDTOTAL-KJKZ202006006.htmZHOU X P, ZHOU Y E, XU L J, et al. A path planning algorithm for lunar cover based on probabilistic roadmap[J]. Aerospace Control and Application, 2020, 46(6): 43-49. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-KJKZ202006006.htm [7] QI J, YANG H, SUN H X. MOD-RRT*: a sampling-based algorithm for robot path planning in dynamic environment[J]. IEEE Transactions on Industrial Electronics, 2021, 68(8): 7244-7251. doi: 10.1109/TIE.2020.2998740 [8] MAC T T, COPOT C, TRAN D T, et al. A hierarchical global path planning approach for mobile robots based on multi-objective particle swarm optimization[J]. Applied Soft Computing, 2017, 59: 68-76. doi: 10.1016/j.asoc.2017.05.012 [9] 冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262. https://www.cnki.com.cn/Article/CJFDTOTAL-XTYD202207021.htmFENG H B, HU Q, ZHAO Z Y. AUV swarm path planning based on elite family genetic algorithm[J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTYD202207021.htm [10] MIAO C W, CHEN G Z, YAN C L, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J]. Computers & Industrial Engineering, 2021, 156: 107230. [11] 吴鹏, 桑成军, 陆忠华, 等. 基于改进A*算法的移动机器人路径规划研究[J]. 计算机工程与应用, 2019, 55(21): 227-233. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201921032.htmWU P, SANG C J, LU Z H, et al. Research on mobile robot path planning based on improved A* algorithm[J]. Computer Engineering and Applications, 2019, 55(21): 227-233. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201921032.htm [12] 孔继利, 张鹏坤, 刘晓平. 双向搜索机制的改进A*算法研究[J]. 计算机工程与应用, 2021, 57(8): 231-237. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202108032.htmKONG J L, ZHANG P K, LIU X P. Research on improved A* algorithm of bidirectional search mechanism[J]. Computer Engineering and Applications, 2021, 57(8): 231-237. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202108032.htm [13] 王洪斌, 郝策, 张平, 等. 基于A*算法和人工势场法的移动机器人路径规划[J]. 中国机械工程, 2019, 30(20): 2489-2496. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGJX201920012.htmWANG H B, HAO C, ZHANG P, et al. Path planning of mobile robots based on A* algorithm and artificial potential field algorithm[J]. China Mechanical Engineering, 2019, 30(20): 2489-2496. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGJX201920012.htm [14] HARABOR D, GRASTIEN A. The JPS pathfinding system[C]//5th Annual Symposium on Combinatorial Search. Niagara Falls, USA: AAAI, 2012: 207-208. [15] 赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910. https://www.cnki.com.cn/Article/CJFDTOTAL-JQRR201806016.htmZHAO 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) https://www.cnki.com.cn/Article/CJFDTOTAL-JQRR201806016.htm [16] 马小陆, 梅宏. 双向跳点搜索算法的移动机器人全局路径规划研究[J]. 机械科学与技术, 2020, 39(10): 1624-1631. doi: 10.13433/j.cnki.1003-8728.20190342MA X L, MEI H. Research on bidirectional jump point search algorithm of global path planning for mobile robots[J]. Mechanical Science and Technology for Aerospace Engineering, 2020, 39(10): 1624-1631. (in Chinese) doi: 10.13433/j.cnki.1003-8728.20190342 -
点击查看大图
图(13) / 表(2)
计量
- 文章访问数: 11
- HTML全文浏览量: 2
- PDF下载量: 1
- 被引次数: 0
