Research on Improved A<sup>*</sup> Algorithm Integrating Vector Cross-product and Jump Point Search Strategy

HU Shiqiang; WU Meiping; SHI Jian; MIAO Xiaojin

doi:10.13433/j.cnki.1003-8728.20230017

Volume 43 Issue 7

Jul. 2024

Turn off MathJax

Article Contents

Article Navigation > Mechanical Science and Technology for Aerospace Engineering > 2024 > 43(7): 1266-1276

HU Shiqiang, WU Meiping, SHI Jian, MIAO Xiaojin. Research on Improved A* Algorithm Integrating Vector Cross-product and Jump Point Search Strategy[J]. Mechanical Science and Technology for Aerospace Engineering, 2024, 43(7): 1266-1276. doi: 10.13433/j.cnki.1003-8728.20230017

Citation:

HU Shiqiang, WU Meiping, SHI Jian, MIAO Xiaojin. Research on Improved A^* Algorithm Integrating Vector Cross-product and Jump Point Search Strategy[J]. Mechanical Science and Technology for Aerospace Engineering, 2024, 43(7): 1266-1276. doi: 10.13433/j.cnki.1003-8728.20230017

Citation:

PDF( 7042 KB)

Research on Improved A^* Algorithm Integrating Vector Cross-product and Jump Point Search Strategy

doi: 10.13433/j.cnki.1003-8728.20230017

1.
School of Mechanical Engineering, Jiangnan University, Wuxi 214122, Jiangsu, China
2.
Shenzhen Zhongzhi Yonghao robot Co., Ltd., Shenzhen 518107, Guangdong, China

Received Date: 2022-04-03
Publish Date: 2024-07-25

Abstract

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.
- path planning,
- cross-product,
- jump point search,
- A^* algorithm,
- mobile robot

FullText(HTML)

References(16)

References

[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.htm SHI 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.htm ZHOU 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.htm FENG 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.htm WU 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.htm KONG 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.htm WANG 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.htm ZHAO 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.20190342 MA 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