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]	Yu Yiran, Lai Huicheng, Gao Guxue, Zhang Guo, Peng Wangyinan, Yang Longfei, Huang Junhao. Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2397-2408.
[2]	Ni Peilong, Mao Pengjun, Wang Ning, Yang Mengjie. Robot Path Planning Based on Improved A-DDQN Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2420-2430.
[3]	Zhang Kaixiang, Mao Jianlin, Wang Niya, Xu Zhihao. Multi-robot Hierarchical Collaborative k-robust Path Planning for Path Interference [J]. Journal of System Simulation, 2025, 37(8): 2074-2088.
[4]	Wan Yuhang, Zhu Zilu, Zhong Chunfu, Liu Yongkui, Lin Tingyu, Zhang Lin. Dynamic Path Planning for Robotic Arms Based on an Improved PPO Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1462-1473.
[5]	Ye Chen, Shao Peng, Zhang Shaoping, Li Wenting, Zhou Tengming. Enhanced Artificial Gorilla Algorithm for Mobile Robot Path Planning [J]. Journal of System Simulation, 2025, 37(6): 1474-1485.
[6]	Zhang Yan, Li Binghua, Huo Tao, Liu Rong. Research on Robot Dynamic Obstacle Avoidance Method Based on Improved A* and Dynamic Window Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1555-1564.
[7]	Zhou Xiaohui, Li Yanqiang, Wang Yong, Zhao Decai, Yang Xiaoyao. Robot Path Planning Based on Ant Colony Algorithm with Dual Heuristic Information [J]. Journal of System Simulation, 2025, 37(5): 1280-1289.
[8]	Yu Die, Bao Baizhong, Si Yan, Duan Jian, Zhan Xiaobin, Shi Tielin. Mobile Robot Path Planning Based on Search-step Optimized A* Algorithm [J]. Journal of System Simulation, 2025, 37(4): 1041-1050.
[9]	Zhang Sen, Dai Qiangqiang. UAV Path Planning Based on Improved Deep Deterministic Policy Gradients [J]. Journal of System Simulation, 2025, 37(4): 875-881.
[10]	He Zhigang, Li Dayan, Wang Niya, Mao Jianlin, Wang Ning. A Multi-robot Collaborative Path Planning Algorithm with Chain Working Mode [J]. Journal of System Simulation, 2025, 37(4): 953-967.
[11]	Lin Guijuan, Li Zihan, Wang Yu. Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction [J]. Journal of System Simulation, 2025, 37(3): 667-678.
[12]	Bai Yuxin, Chen Zhenya, Shi Ruitao, Su Weitao, Ma Zhuoqiang, Yang Shangjin. Research on Robot Path Planning Based on Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2025, 37(3): 742-752.
[13]	Jin Xu, Mo Yuanbin. Multi-strategy Hybrid Mountain Gazelle Optimizer for Robot Path Planning [J]. Journal of System Simulation, 2025, 37(3): 803-821.
[14]	Peng Yi, Lei Yunkui, Yang Qingqing, Li Hui, Wang Jianming. Improved PID Search Algorithm for UAV Path Planning in Mountainous Environments [J]. Journal of System Simulation, 2025, 37(12): 3075-3086.
[15]	Xing Lijing, Li Min, Zeng Xiangguang, Zhang Ping, Peng Bei. AUV Path Planning Based on Behavior Cloning and Improved DQN in Partially Unknown Environments [J]. Journal of System Simulation, 2025, 37(11): 2754-2767.