融合改进A*算法与DWA算法的机器人动态避障方法研究

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

摘要/Abstract

摘要：

针对传统A*算法在路径规划过程中存在扩展节点多、路径转折点多，并且无法处理复杂环境中出现的动态障碍物等问题，提出了一种融合改进A*算法与DWA算法的机器人动态避障方法。在传统A*算法基础上改进邻域扩展方法，有效避免了经典四邻域扩展中存在的冗余节点多和八邻域扩展中存在的从障碍物中间穿过的路径等问题；设计了一种象限选择方法，在路径搜索过程中可以有效减少扩展节点的数量；设计了冗余点剔除策略，剔除路径多余节点；在每两个相邻节点间采用DWA算法进行局部路径规划，保证在全局最优路径的基础上实现了动态避障。实验结果验证了算法在机器人路径规划中的可行性。

关键词: 机器人路径规划, 改进A*算法, DWA算法, 动态避障

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

中图分类号:

TP242.6

张艳,李炳华,霍涛等 . 融合改进A*算法与DWA算法的机器人动态避障方法研究[J]. 系统仿真学报, 2025, 37(6): 1555-1564.

Zhang Yan,Li Binghua,Huo Tao,et al . 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.

图/表 19

图1

图2

图3

表1

夹角与搜索方向的对应关系

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

表1

表2

坐标差与方向对应关系

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

表2

图4

图5

图6

图7

图8

图9

表3

图10

表4

表5

图11

表6

图12

图13

参考文献 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]	叶晨, 邵鹏, 张少平, 李文婷, 周腾明. 面向移动机器人路径规划的增强型人工大猩猩算法[J]. 系统仿真学报, 2025, 37(6): 1474-1485.
[2]	林桂娟, 李子涵, 王宇. 基于全局关键点提取的改进A*算法全局路径规划研究[J]. 系统仿真学报, 2025, 37(3): 667-678.
[3]	刘斌, 兰莹, 黄文焘, 范勤勤. 融合动态窗口法的无人机动态路径规划算法[J]. 系统仿真学报, 2024, 36(8): 1843-1853.
[4]	张瑞, 周丽, 刘正洋. 融合RRT*与DWA算法的移动机器人动态路径规划[J]. 系统仿真学报, 2024, 36(4): 957-968.
[5]	闫星宇, 李大焱, 王妮娅, 张凯翔, 毛剑琳. 带障碍物惩罚因子的多机器人路径规划[J]. 系统仿真学报, 2024, 36(3): 673-685.
[6]	闫星宇, 王妮娅, 毛剑琳, 贺志刚, 李大焱. 基于冲突优先级变次优因子的EECBS多机器人路径规划[J]. 系统仿真学报, 2024, 36(11): 2662-2673.
[7]	曹梦龙, 赵文彬, 陈志强. 融合粒子群算法与改进灰狼算法的机器人路径规划[J]. 系统仿真学报, 2023, 35(8): 1768-1775.
[8]	邓向阳, 张立民, 方伟, 汤淼. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
[9]	乔乔, 王艳, 纪志成. 基于冲突搜索算法的多机器人路径规划[J]. 系统仿真学报, 2022, 34(12): 2659-2669.
[10]	赵萍, 雷新宇, 陈波芝, 杨矫云. 基于TI-A*的多机器人动态规划协调方法研究[J]. 系统仿真学报, 2019, 31(5): 925-935.