Path Planning Based on Improved A* and Dynamic Window Approach

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

Abstract

Abstract:

In response to the low efficiency, redundant turning points, and collision issues of the traditional A* algorithm, a smart vehicle path planning algorithm that integrates an improved A* algorithm with a dynamic window approach has been proposed. The algorithm has enhanced the search point selection method, optimized the evaluation function, selected key turning points based on the slope values between turning points, and removed redundant turning points. Between every two optimized key turning points, a dynamic window approach that balances speed and safety is used for local obstacle avoidance. Experiments show that compared to the traditional A* algorithm, this algorithm has increased retrieval speed by 45%, reduced turning points by 91%, and improved path smoothness. The integrated algorithm can achieve local optimality while ensuring global path optimality and can achieve real-time obstacle avoidance.

Key words: optimization A* algorithm, optimizing dynamic window approach, fusion algorithms, path planning, real time obstacle avoidance

CLC Number:

TP242.6

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.

Figures/Tables 17

Fig. 1

Table 1

Fig. 2

Fig. 3

Table 2

Fig. 4

Table 3

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Table 4

Fig. 11

Fig. 12

Fig. 13

References 19

1	Patle B K, Ganesh Babu L, Pandey Anish, et al. A Review: On Path Planning Strategies for Navigation of Mobile Robot[J]. Defence Technology, 2019, 15(4): 582-606.
2	Adamu Patience I, Okagbue Hilary I, Pelumi E Oguntunde. Fast and Optimal Path Planning Algorithm (FAOPPA) for a Mobile Robot[J]. Wireless Personal Communications, 2019, 106(2): 577-592.
3	劳彩莲, 李鹏, 冯宇. 基于改进A^*与DWA算法融合的温室机器人路径规划[J]. 农业机械学报, 2021, 52(1): 14-22.
	Lao Cailian, Li Peng, Feng Yu. Path Planning of Greenhouse Robot Based on Fusion of Improved A^*Algorithm and Dynamic Window Approach[J]. Transactions of the Chinese Society for Agricultural Machinery, 2021, 52(1): 14-22.
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	段书用, 王启帆, 韩旭, 等. 具有确保安全距离的A^*路径优化方法[J]. 机械工程学报, 2020, 56(18): 205-215.
	Duan Shuyong, Wang Qifan, Han Xu, et al. Improved A-star Algorithm for Safety Insured Optimal Path with Smoothed Corner Turns[J]. Journal of Mechanical Engineering, 2020, 56(18): 205-215.
6	Xiong Xiaoyong, Min Haitao, Yu Yuanbin, et al. Application Improvement of A^* Algorithm in Intelligent Vehicle Trajectory Planning[J]. Mathematical Biosciences and Engineering, 2021, 18(1): 1-21.
7	张瑜, 宋荆洲, 张琪祁. 基于改进动态窗口法的户外清扫机器人局部路径规划[J]. 机器人, 2020, 42(5): 617-625.
	Zhang Yu, Song Jingzhou, Zhang Qiqi. Local Path Planning of Outdoor Cleaning Robot Based on an Improved DWA[J]. Robot, 2020, 42(5): 617-625.
8	王彬, 聂建军, 李海洋, 等. 优化A^*与动态窗口法的移动机器人路径规划[J/OL]. 计算机集成制造系统. (2022-03-08) [2023-03-09]. .
	Wang Bin, Nie Jianjun, Li Haiyang, et al. Based on Optimized A^* and Dynamic Window Approach for Mobile Robot Path Planning[J/OL]. Computer Integrated Manufacturing Systems. (2022-03-08) [2023-03-09]. .
9	王志中. 复杂动态环境下自主机器人路径规划研究[J]. 组合机床与自动化加工技术, 2018(1): 64-68.
	Wang Zhizhong. Automatic Robot Path Planning Under Complicit Dynamic Environment[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2018(1): 64-68.
10	王凡, 李铁军, 刘今越, 等. 基于BIM的建筑机器人自主路径规划及避障研究[J]. 计算机工程与应用, 2020, 56(17): 224-230.
	Wang Fan, Li Tiejun, Liu Jinyue, et al. Research on Autonomous Path Planning and Obstacle Avoidance of Building Robot Based on BIM[J]. Computer Engineering and Applications, 2020, 56(17): 224-230.
11	徐玉琼, 娄柯, 李婷婷, 等. 改进自适应蚁群算法的移动机器人路径规划[J]. 电子测量与仪器学报, 2019, 33(10): 89-95.
	Xu Yuqiong, Lou Ke, Li Tingting, et al. Path Planning of Mobile Robot Based on Improved Adaptive Ant Colony Algorithm[J]. Journal of Electronic Measurement and Instrumentation, 2019, 33(10): 89-95.
12	张松灿, 普杰信, 司彦娜, 等. 蚁群算法在移动机器人路径规划中的应用综述[J]. 计算机工程与应用, 2020, 56(8): 10-19.
	Zhang Songcan, Pu Jiexin, Si Yanna, et al. Survey on Application of Ant Colony Algorithm in Path Planning of Mobile Robot[J]. Computer Engineering and Applications, 2020, 56(8): 10-19.
13	Dai Xiaolin, Long Shuai, Zhang Zhiwen, et al. Mobile Robot Path Planning Based on Ant Colony Algorithm With A^* Heuristic Method[J]. Frontiers in Neurorobotics, 2019, 13: 15.
14	曹毅, 周轶, 张亚宾. 基于优化A^*和DWA算法的移动机器人避障路径规划[J]. 机床与液压, 2020, 48(24): 246-252.
	Cao Yi, Zhou Yi, Zhang Yabin. Path Planning for Obstacle Avoidance of Mobile Robot Based on Optimized A^* and DWA Algorithm[J]. Machine Tool & Hydraulics, 2020, 48(24): 246-252.
15	石英托, 陈华, 张连新, 等. 基于改进A^*算法的AGV转运机器人路径规划研究[J]. 制造技术与机床, 2022(5): 19-22.
	Shi Yingtuo, Chen Hua, Zhang Lianxin, et al. Research on Path Planning of AGV Transport Robot Based on Improved A^* Algorithm[J]. Manufacturing Technology & Machine Tool, 2022(5): 19-22.
16	高鹏, 姜军生, 白阳, 等. 基于改进A^*算法的果园移动机器人建图定位与路径规划方法与试验[J]. 中国农机化学报, 2022, 43(1): 142-149.
	Gao Peng, Jiang Junsheng, Bai Yang, et al. Method and Experiment of Map Building and Path Planning for Mobile Robot in Orchard Based on Improved A^* Algorithm[J]. Journal of Chinese Agricultural Mechanization, 2022, 43(1): 142-149.
17	陈娇, 徐菱, 陈佳, 等. 改进A^*和动态窗口法的移动机器人路径规划[J]. 计算机集成制造系统, 2022, 28(6): 1650-1658.
	Chen Jiao, Xu Ling, Chen Jia, et al. Path Planning Based on Improved A^* and Dynamic Window Approach for Mobile Robot[J]. Computer Integrated Manufacturing Systems, 2022, 28(6): 1650-1658.
18	Xiquan Mai, Li Di, Ouyang Jian, et al. An Improved Dynamic Window Approach for Local Trajectory Planning in the Environment with Dense Objects[J]. Journal of Physics: Conference Series, 2021, 1884(1): 012003.
19	槐创锋, 郭龙, 贾雪艳, 等. 改进A^*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(8): 244-248.
	Huai Chuangfeng, Guo Long, Jia Xueyan, et al. Improved A^*Algorithm and Dynamic Window Method for Robot Dynamic Path Planning[J]. Computer Engineering and Applications, 2021, 57(8): 244-248.

θ	保留的5个方向	去除的3个方向
[330°, 360°）∪ [0°, 30°）	n₁、n₂、n₃、n₄、n₅	n₆、n₇、n₈
[30°, 90°）	n₁、n₂、n₃、n₅、n₈	n₄、n₆、n₇
[90°, 150°）	n₃、n₅、n₆、n₇、n₈	n₁、n₂、n₄
[150°, 210°）	n₄、n₅、n₆、n₇、n₈	n₁、n₂、n₃
[210°, 270°）	n₁、n₄、n₆、n₇、n₈	n₂、n₃、n₅
[270°, 330°）	n₁、n₂、n₃、n₄、n₆	n₅、n₇、n₈

路径规划算法	路径长度/m	规划时间/s	拐点数量
传统A*算法	46.560 3	0.685 3	33
改进A*算法	44.860 9	0.376 8	3

路径规划算法	路径长度/m	规划时间/ms
传统DWA	19.212	133.478
改进DWA	19.106	117.461

硬件名称	具体型号
激光雷达	思岚雷达RPLIDAR A1
深度相机	奥比中光Astra pro
ROS主机	英伟达Jetson Nano
底盘控制	STM32F103RCT6
惯导测量单元	MPU6050
电机	直流有刷电机

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	Xiao Peng, Xie Feng, Ni Haihong, Zhang Min, Tang Zhili, Li Ni. Research on Collaborative Optimization Method of Multi-UAV Task Allocation and Path Planning [J]. Journal of System Simulation, 2024, 36(5): 1141-1151.
[10]	Liu Zesen, Bi Sheng, Guo Chuanhong, Wang Yankui, Dong Min. Deep Learning Based Local Path Planning Method for Moving Robots [J]. Journal of System Simulation, 2024, 36(5): 1199-1210.
[11]	Wang Xiaokang, Ji Jie, Liu Yang, He Qing. Path Planning of Unmanned Delivery Vehicle Based on Improved Q-learning Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1211-1221.
[12]	Jiang Zhaozhen, Wang Wenlong, Sun Wenqi. Path Planning Rapid Algorithm Based on Modified RRT* for Unmanned Surface Vessel [J]. Journal of System Simulation, 2024, 36(4): 888-900.
[13]	Zhang Rui, Zhou Li, Liu Zhengyang. Dynamic Path Planning for Mobile Robot Based on RRT* and Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(4): 957-968.
[14]	Li Gaoyang, Li Xiangfeng, Zhao Kang, Jin Yuchao, Yi Zhidong, Zuo Dunwen. Three-Dimensional Path Planning of UAV Based on All Particles Driving Wild Horse Optimizer Algorithm [J]. Journal of System Simulation, 2024, 36(3): 595-607.
[15]	Yu Xiang, Jiang Chen, Duan Sirui, Deng Qianrui. Path Planning for Improvement of A* Algorithm and Artificial Potential Field Method [J]. Journal of System Simulation, 2024, 36(3): 782-794.