Improved Bidirectional A* Quadratic Path Planning Algorithm for Mobile Robots

doi:10.16182/j.issn1004731x.joss.23-1183

Abstract

Abstract:

Aiming at the problems of the traditional A* algorithm, such as the unhoped intersection between the planned path and the obstacles, the planned path has many inflection points and the search time is long, an improved bidirectional A* quadratic path planning algorithm for the indoor environments is proposed. Through the expansion of the map, the intersection between the planned path and the obstacle is solved. By new heuristic functions and bidirectional expansion methods, the search speed and accuracy of the bidirectional A* algorithm are improved. Turning cost function and adaptive weight are introduced to reduce the number of turning points. Quadratic programming and second-order Bezier curves are used to smooth the path, and the redundant nodes and the corners that do not conform to actual movement are deleted. Simulation results show that, the search speed is increased by 55.7%, the path length is shortened by 15.6%, and the inflection points and corners are reduced by 31.6% and 56.1%.

Key words: evaluation function, path smoothing, bidirectional A* algorithm, quadratic programming, path planning, mobile robots

CLC Number:

TP242.6

Li Jiongyi, Li Qiang, Zhang Xinwen, Htet Zin Myo, Cai Yongbin. Improved Bidirectional A* Quadratic Path Planning Algorithm for Mobile Robots[J]. Journal of System Simulation, 2025, 37(2): 498-507.

Figures/Tables 16

Fig. 1

Table 1

Fig. 2

Table 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Table 3

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Fig. 12

Fig. 13

References 18

1	Thi Thoa Mac, Copot Cosmin, Duc Trung Tran, et al. Heuristic Approaches in Robot Path Planning: A Survey[J]. Robotics and Autonomous Systems, 2016, 86: 13-28.
2	Jeddisaravi Kossar, Reza Javanmard Alitappeh, C A Pimenta Luciano, et al. Multi-objective Approach for Robot Motion Planning in Search Tasks[J]. Applied Intelligence, 2016, 45(2): 305-321.
3	吴宗胜. 室外移动机器人的道路场景识别及路径规划研究[D]. 西安: 西安理工大学, 2017.
	Wu Zongsheng. Research for the Road Scene Recognition and Path Planning for the Outdoor Mobile Robots[D]. Xi'an: Xi'an University of Technology, 2017.
4	Min Haitao, Xiong Xiaoyong, Wang Pengyu, et al. Autonomous Driving Path Planning Algorithm Based on Improved A^* Algorithm in Unstructured Environment[J]. Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering, 2021, 235(2/3): 513-526.
5	江洪, 蒋潇杰. 基于RRT改进的路径规划算法[J]. 重庆理工大学学报(自然科学), 2021, 35(7): 10-16, 124.
	Jiang Hong, Jiang Xiaojie. Improved Path Planning Algorithm Based on RRT[J]. Journal of Chongqing University of Technology(Natural Science), 2021, 35(7): 10-16, 124.
6	Yue Longwang, Chen Hanning. Unmanned Vehicle Path Planning Using a Novel Ant Colony Algorithm[J]. EURASIP Journal on Wireless Communications and Networking, 2019, 2019(1): 136.
7	邓修朋, 崔建明, 李敏, 等. 深度强化学习在机器人路径规划中的应用[J]. 电子测量技术, 2023, 46(6): 1-8.
	Deng Xiupeng, Cui Jianming, Li Min, et al. Application of Deep Reinforcement Learning in Robot Path Planning[J]. Electronic Measurement Technology, 2023, 46(6): 1-8.
8	Zhang Xin, Shi Xiaoxu, Zhang Zuqiong, et al. A DDQN Path Planning Algorithm Based on Experience Classification and Multi Steps for Mobile Robots[J]. Electronics, 2022, 11(14): 2120.
9	Wang Huanwei, Qi Xuyan, Lou Shangjie, et al. An Efficient and Robust Improved A^* Algorithm for Path Planning[J]. Symmetry, 2021, 13(11): 2213.
10	Saeed R A, Diego Reforgiato Recupero, Remagnino P. A Boundary Node Method for Path Planning of Mobile Robots[J]. Robotics and Autonomous Systems, 2020, 123: 103320.
11	Wang Xiangyu, Liu Zuoshi, Liu Jiahu. Mobile Robot Path Planning Based on an Improved A^*Algorithm[C]//International Conference on Computer Graphics, Artificial Intelligence, and Data Processing (ICCAID 2022). Bellingham: SPIE, 2023: 1260449.
12	李鑫, 廖凯文, 陈薇, 等. 多自动导引车路径规划的时空冲突约束A^*算法[J]. 计算机集成制造系统, 2021, 27(11): 3219-3226.
	Li Xin, Liao Kaiwen, Chen Wei, et al. Space-time Conflict Constrained A^* Algorithm for Path Planning of Multiple AGVS[J]. Computer Integrated Manufacturing Systems, 2021, 27(11): 3219-3226.
13	Song Baoye, Wang Zidong, Zou Lei. An Improved PSO Algorithm for Smooth Path Planning of Mobile Robots Using Continuous High-degree Bezier Curve[J]. Applied Soft Computing, 2021, 100: 106960.
14	孙小飞, 余涛, 陈锐. 基于ROS的自动分拣机器人系统设计[J]. 制造业自动化, 2021, 43(7): 141-146.
	Sun Xiaofei, Yu Tao, Chen Rui. Design of Automatic Sorting Robot System Based on ROS[J]. Manufacturing Automation, 2021, 43(7): 141-146.
15	Shi Yangyang, Li Qiongqiong, Bu Shengqiang, et al. Research on Intelligent Vehicle Path Planning Based on Rapidly-exploring Random Tree[J]. Mathematical Problems in Engineering, 2020, 2020(1): 5910503.
16	鲁毅, 高永平, 龙江腾. A^*算法在移动机器人路径规划中的研究[J]. 湖北师范大学学报(自然科学版), 2022, 42(2): 59-65.
	Lu Yi, Gao Yongping, Long Jiangteng. A study on A^* Algorithm in Mobile Robot Path Planning[J]. Journal of Hubei Normal University(Natural Science), 2022, 42(2): 59-65.
17	高九州, 徐威峰, 张立辉, 等. 基于改进A^*算法的无人机避障航线规划[J]. 现代电子技术, 2023, 46(8): 181-186.
	Gao Jiuzhou, Xu Weifeng, Zhang Lihui, et al. Obstacle Avoidance Route Planning of UAV Based on Optimized A^*Algorithm[J]. Modern Electronics Technique, 2023, 46(8): 181-186.
18	Liao Maosheng, Wang Di, Yang Hao. Deploy Indoor 2D Laser SLAM on a Raspberry Pi-based Mobile Robot[C]//2019 11th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC). Piscataway: IEEE, 2019: 7-10.

算法	搜索邻域数	方向
传统A*算法	4	4
传统3×3搜索邻域的A*	8	8
改进5×5搜索邻域的A*	24	16
改进7×7搜索邻域的A*	48	32

角度θ/(˚)	保留的节点扩展方向
[0, 22.5)∪[337.5, 360)	D1、D2、D3、D4、D5、D6、D7、D8、D9、D10、D11、D12、D13、D14、D15、D16、D17
[22.5, 67.5)	D1、D2、D3、D4、D5、D6、D7、D8、D9、D10、D11、D12、D13、D29、D30、D31、D32
[67.5, 112.5)	D1、D2、D3、D4、D5、D6、D7、D8、D9、D25、D26、D27、D28、D29、D30、D31、D32
[112.5, 157.5)	D1、D2、D3、D4、D5、D21、D22、D23、D24、D25、D26、D27、D28、D29、D30、D31、D32
[157.5, 202.5)	D1、D17、D18、D19、D20、D21、D22、D23、D24、D25、D26、D27、D28、D29、D30、D31、D32
[202.5, 247.5)	D13、D14、D15、D16、D17、D18、D19、D20、D21、D22、D23、D24、D25、D26、D27、D28、D29
[247.5, 292.5)	D9、D10、D11、D12、D13、D14、D15、D16、D17、D18、D19、D20、D21、D22、D23、D24、D25
[292.5, 337.5)	D5、D6、D7、D8、D9、D10、D11、D12、D13、D14、D15、D16、D17、D18、D19、D20、D21

算法名称	路径长度	路径拐点	搜索节点	危险节点	路径节点	转弯总角度/(°)	时间/s
传统4搜索A*算法	100.000	15	1 087	47	101	1 350	2.398
传统8搜索A*算法	86.125	20	1 120	11	66	1 170	1.752
文献[16]算法	89.397	17	1 062	33	73	900	1.398
文献[17]算法	102.770	13	370	0	20	825	1.527
本文算法	84.387	12	744	0	15	592	1.062

[1]	Qi Bensheng, Li Yan, Miao Hongxia, Chen Jialin, Li Chenglin. Research on Path Planning Method for Autonomous Underwater Vehicles Based on Improved Informed RRT [J]. Journal of System Simulation, 2025, 37(1): 245-256.
[2]	Xu Jianmin, Song Lei, Deng Dongdong, Chen Yaoruo, Yang Wei. Path Planning of Mobile Robot Based on the Integration of Multi-scale A* and Optimized DWA Algorithm [J]. Journal of System Simulation, 2025, 37(1): 257-270.
[3]	Wang Qiwei, Zhang Qi, Yang Shuo, Peng Yong. Design of Robust Behavior Tree Control Architecture for Agents in Dynamic Task Environment [J]. Journal of System Simulation, 2025, 37(1): 54-65.
[4]	Yin Anlin, Zhang Zhuhong. UAV Path Planning in Complex Environments and Its Improved Artificial Rabbits Optimization Algorithm [J]. Journal of System Simulation, 2025, 37(1): 79-94.
[5]	Wang Yuelong, Wang Songyan, Chao Tao. Multi-step Information Aided Q-learning Path Planning Algorithm [J]. Journal of System Simulation, 2024, 36(9): 2137-2148.
[6]	Huo Hanlin, Zou Xiangjun, Chen Yan, Zhou Xinzhao, Chen Mingyou, Li Chengen, Pan Yaoqiang, Tang Yunchao. Visual Robot Obstacle Avoidance Planning and Simulation Using Mapped Point Clouds [J]. Journal of System Simulation, 2024, 36(9): 2149-2158.
[7]	Ji Peng, Zhang Xinyuan, Gao Shuaixuan, Wei Shuorang. Path Planning Based on Improved A* and Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(9): 2171-2180.
[8]	Sun Haijie, San Hongjun, Xiao Le, Yao Dexin, Chen Jiupeng, Yang Xiaoyuan. An Improved Path Planning Algorithm for Mobile Robots [J]. Journal of System Simulation, 2024, 36(9): 2193-2207.
[9]	Liu Jialun, Yang Fan, Xie Lingli, Li Shijie, Wang Tengfei. Research on Virtual Simulation Testing Technology for Intelligent Navigation Collision Avoidance Decision-making and Planning [J]. Journal of System Simulation, 2024, 36(8): 1780-1789.
[10]	Liu Bin, Lan Ying, Huang Wentao, Fan Qinqin. UAV Dynamic Path Planning Algorithm Combined with Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(8): 1843-1853.
[11]	Lai Rongshen, Dou Lei, Wu Zhiyong, Sun Shuai. Fusion of Improved A* and Dynamic Window Approach for Mobile Robot Path Planning [J]. Journal of System Simulation, 2024, 36(8): 1884-1894.
[12]	Kang Liang, Du Yi, Yin Lihua. An Improved Cat Swarm Optimization for Heterogeneous Multiple Mobile Robots [J]. Journal of System Simulation, 2024, 36(8): 1958-1968.
[13]	Huang Zhifeng, Liu Yuanhua. UAV Path Planning Based on Improved Harris Hawk Algorithm and B-spline Curve [J]. Journal of System Simulation, 2024, 36(7): 1509-1524.
[14]	Wang Yaru, Yao Dexin, Liu Zengli, Peng Yi. Path Planning for Mobile Robot Based on Angle Search [J]. Journal of System Simulation, 2024, 36(7): 1643-1654.
[15]	Lei Xu, Chen Jingyi, Chen Xiaoyang. Research on Path Planning of Warehouse Robot with Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1081-1092.