Research on Robot Dynamic Obstacle Avoidance Method Based on Improved A* and Dynamic Window Algorithm

doi:10.16182/j.issn1004731x.joss.24-0143

Abstract

Abstract:

Aiming at the problems that the traditional A* algorithm has too many extension nodes and path turning points, and can't deal with dynamic obstacles in complex environment, a robot obstacle avoidance method combining improved A* algorithm and DWA algorithm is proposed. The A* algorithm improves the neighborhood expansion method and effectively avoids the problem of redundant nodes in the classical four-neighborhood expansion and the path through the obstacle in the eight-neighborhood expansion. A quadrant selection method is proposed, which can effectively reduce the number of extended nodes in the path search process. The redundant point elimination strategy is proposed to eliminate the redundant nodes in the path, and the DWA algorithm is used to carry out local path planning between each two adjacent nodes to ensure the dynamic obstacle avoidance based on the global optimal path. The experimental results show the feasibility of the algorithm in robot path planning.

Key words: robot path planning, improved A * algorithm, DWA algorithm, dynamic obstacle avoidance

CLC Number:

TP242.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.

Figures/Tables 19

Fig. 1

Fig. 2

Fig. 3

Table 1

Correspondence between angle and search direction

$θ$ 值	$s i n θ$ 值	搜索方向
正	正	第一象限
负	正	第二象限
正	负	第三象限
负	负	第四象限

Table 1

Table 2

Coordinate difference and direction correspondence

$x$ 轴坐标差	$y$ 轴坐标差	方向
正	正	第一象限
负	正	第二象限
负	负	第三象限
正	负	第四象限

Table 2

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Table 3

Fig. 10

Table 4

Table 5

Fig. 11

Table 6

Fig. 12

Fig. 13

References 21

1	Liu Jianhua, Yang Jianguo, Liu Huaping, et al. An Improved Ant Colony Algorithm for Robot Path Planning[J]. Soft Computing, 2017, 21(19): 5829-5839.
2	徐玉琼, 娄柯, 李婷婷, 等. 改进自适应蚁群算法的移动机器人路径规划[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.
3	李卫硕, 孙剑, 陈伟. 基于BP神经网络机器人实时避障算法[J]. 仪器仪表学报, 2019, 40(11): 204-211.
	Li Weishuo, Sun Jian, Chen Wei. Real-time Obstacle Avoidance Algorithm for Robots Based on BP Neural Network[J]. Chinese Journal of Scientific Instrument, 2019, 40(11): 204-211.
4	江明, 王飞, 葛愿, 等. 基于改进蚁群算法的移动机器人路径规划研究[J]. 仪器仪表学报, 2019, 40(2): 113-121.
	Jiang Ming, Wang Fei, Ge Yuan, et al. Research on Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm[J]. Chinese Journal of Scientific Instrument, 2019, 40(2): 113-121.
5	马少博, 王立勇, 丁炳超, 等. 方向性JPS的移动机器人全局路径规划方法[J]. 重庆理工大学学报(自然科学版), 2022, 36(10): 192-199.
	Ma Shaobo, Wang Liyong, Ding Bingchao, et al. Global Path Planning for Mobile Robots with Directional JPS Algorithm[J]. Journal of Chongqing University of Technology(Natural Science), 2022, 36(10): 192-199.
6	马小陆, 梅宏, 龚瑞, 等. 基于改进ACS算法的移动机器人路径规划研究[J]. 湖南大学学报(自然科学版), 2021, 48(12): 79-88.
	Ma Xiaolu, Mei Hong, Gong Rui, et al. Research on Path Planning of Mobile Robot Based on Improved ACS Algorithm[J]. Journal of Hunan University(Natural Sciences), 2021, 48(12): 79-88.
7	陆皖麟, 雷景森, 邵炎. 基于改进A^*算法的移动机器人路径规划[J]. 兵器装备工程学报, 2019, 40(4): 197-201.
	Lu Wanlin, Lei Jingsen, Shao Yan. Path Planning for Mobile Robot Based on An Improved A^* Algorithm[J]. Journal of Ordnance Equipment Engineering, 2019, 40(4): 197-201.
8	赵晓, 王铮, 黄程侃, 等. 基于改进A^*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910.
	Zhao Xiao, Wang Zheng, Huang Chengkan, et al. Mobile Robot Path Planning Based on an Improved A^* Algorithm[J]. Robot, 2018, 40(6): 903-910.
9	曹如月, 张振乾, 李世超, 等. 基于改进A^*算法和Bezier曲线的多机协同全局路径规划[J]. 农业机械学报, 2021, 52(增1): 548-554.
	Cao Ruyue, Zhang Zhenqian, Li Shichao, et al. Multi-machine Cooperation Global Path Planning Based on A-star Algorithm and Bezier Curve[J]. Transactions of the Chinese Society for Agricultural Machinery, 2021, 52(S1): 548-554.
10	劳彩莲, 李鹏, 冯宇. 基于改进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.
11	齐凤莲, 王晓庆, 张帼英. 改进A^*算法的AGV避障路径规划研究[J]. 机床与液压, 2023, 51(9): 34-39.
	Qi Fenglian, Wang Xiaoqing, Zhang Guoying. Research on AGV Obstacle Avoidance Path Planning Based on Improved A^* Algorithm[J]. Machine Tool & Hydraulics, 2023, 51(9): 34-39.
12	Yokoyama Koki, Morioka Kazuyuki. Autonomous Mobile Robot with Simple Navigation System Based on Deep Reinforcement Learning and a Monocular Camera[C]//2020 IEEE/SICE International Symposium on System Integration (SII). Piscataway: IEEE, 2020: 525-530.
13	Sasaki Yoko, Matsuo Syusuke, Kanezaki Asako, et al. A3C Based Motion Learning for an Autonomous Mobile Robot in Crowds[C]///2019 IEEE International Conference on Systems, Man and Cybernetics (SMC). Piscataway: IEEE, 2019: 1036-1042.
14	Jiao Zhuqing, Ma Kai, Rong Yiling, et al. A Path Planning Method Using Adaptive Polymorphic Ant Colony Algorithm for Smart Wheelchairs[J]. Journal of Computational Science, 2018, 25: 50-57.
15	Tuvshinjargal Doopalam, Dorj Byambaa, Jin Lee Deok. Hybrid Motion Planning Method for Autonomous Robots Using Kinect Based Sensor Fusion and Virtual Plane Approach in Dynamic Environments[J]. Journal of Sensors, 2015, 2015(1): 471052.
16	Fazlollahtabar Hamed, Hassanli Samaneh. Hybrid Cost and Time Path Planning for Multiple Autonomous Guided Vehicles[J]. Applied Intelligence, 2018, 48(2): 482-498.
17	李志锟, 黄宜庆, 徐玉琼. 改进变步长蚁群算法的移动机器人路径规划[J]. 电子测量与仪器学报, 2020, 34(8): 15-21.
	Li Zhikun, Huang Yiqing, Xu Yuqiong. Path Planning of Mobile Robot Based on Improved Variable Step Size Ant Colony Algorithm[J]. Journal of Electronic Measurement and Instrumentation, 2020, 34(8): 15-21.
18	赵久强, 赵庭辉, 冯毅萍, 等. 基于改进A^*算法和DWA融合的机器人路径规划研究[J]. 实验技术与管理, 2023, 40(3): 87-92.
	Zhao Jiuqiang, Zhao Tinghui, Feng Yiping, et al. Research on Robot Path Planning Based on Improved A^* Algorithm and DWA[J]. Experimental Technology and Management, 2023, 40(3): 87-92.
19	邓云峥, 黄翼虎. 复杂动态环境下基于A^*的改进DWA算法研究[J]. 电子测量技术, 2023, 46(9): 69-76.
	Deng Yunzheng, Huang Yihu. Research on Improved DWA Algorithm Based on A^* in Complex Dynamic Environment[J]. Electronic Measurement Technology, 2023, 46(9): 69-76.
20	唐昀超, 祁少军, 朱立学, 等. 移动机器人避障运动研究[J]. 系统仿真学报, 2024, 36(1): 1-26.
	Tang Yunchao, Qi Shaojun, Zhu Lixue, et al. Obstacle Avoidance Motion in Mobile Robotics[J]. Journal of System Simulation, 2024, 36(1): 1-26.
21	Hu Kewei, Chen Zheng, Kang Hanwen, et al. 3D Vision Technologies for a Self-developed Structural External Crack Damage Recognition Robot[J]. Automation in Construction, 2024, 159: 105262.

算法	路径规划长度	路径节点个数	扩展节点个数	转折次数	运行时间/s
Ⅰ	13.313 7	11	25	2	2.617
Ⅱ	15.071 1	13	17	7	1.735
Ⅲ	15.071 1	13	12	7	1.727
Ⅳ	14.472 4	6	12	4	1.767

算法	路径规划长度	路径节点个数	扩展节点个数	转折次数	运行时间/s
Ⅰ	28.627 4	23	40	11	9.368
Ⅱ	35.071 1	30	15	19	8.691
Ⅲ	35.071 1	30	12	19	8.542
Ⅳ	34.240 0	15	12	13	8.759

算法	路径规划长度	危险节点个数	转折次数	运行时间/s	迭代次数
Dijkstra	28.627	9	7	0.064 8	22
传统A*	31.556	5	7	0.059 5	27
角度搜索	28.627	9	7	0.053 6	22
本文	30.970	0	3	0.052 2	6

算法	路径规划长度	危险节点个数	转折次数	运行时间/s	迭代次数
Dijkstra	28.627	6	7	0.065 7	22
传统A*	30.627	10	11	0.060 3	24
角度搜索	28.627	8	5	0.053 0	22
本文	30.370	0	6	0.051 8	7

[1]	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.
[2]	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.
[3]	Yan Xingyu, Wang Niya, Mao Jianlin, He Zhigang, Li Dayan. EECBS Multi-robot Path Planning Based on Variable Suboptimal Factors of Prioritizing Conflicts [J]. Journal of System Simulation, 2024, 36(11): 2662-2673.
[4]	Menglong Cao, Wenbin Zhao, Zhiqiang Chen. Robot Path Planning by Fusing Particle Swarm Algorithm and Improved Grey Wolf Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1768-1775.
[5]	Xiangyang Deng, Limin Zhang, Wei Fang, Miao Tang. Robot Path Planning Based on Bidirectional Aggregation Ant Colony Optimization [J]. Journal of System Simulation, 2022, 34(5): 1101-1108.