融合改进A*算法与动态窗口法的路径规划研究

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

摘要/Abstract

摘要：

针对传统A*算法搜索效率较低、拐点冗余和易碰撞等问题，提出了一种融合改进A*算法与动态窗口法的智能车辆路径规划算法。改进了搜索点筛选方法、优化了评价函数、根据拐点间的斜率值筛选出关键拐点，并去除冗杂拐点。在优化后的每两个关键拐点间采用兼备速度与安全的优化动态窗口法进行局部避障。实验表明：该算法相较传统A*算法在检索速度上提升了45%，拐点数量减少了91%，提高了路径平滑度。融合后的算法能在确保全局路径最优的情况下达到局部最优，可以实现实时避障。

关键词: 优化A*算法, 优化动态窗口法, 融合算法, 路径规划, 实时避障

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

中图分类号:

TP242.6

姬鹏,张新元,高帅轩等 . 融合改进A*算法与动态窗口法的路径规划研究[J]. 系统仿真学报, 2024, 36(9): 2171-2180.

Ji Peng,Zhang Xinyuan,Gao Shuaixuan,et al . Path Planning Based on Improved A* and Dynamic Window Approach[J]. Journal of System Simulation, 2024, 36(9): 2171-2180.

图/表 17

图1

表1

图2

图3

表2

图4

表3

图5

图6

图7

图8

图9

图10

表4

图11

图12

图13

参考文献 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]	王越龙, 王松艳, 晁涛. 基于多步信息辅助的Q-learning路径规划算法[J]. 系统仿真学报, 2024, 36(9): 2137-2148.
[2]	霍韩淋, 邹湘军, 陈燕, 周馨曌, 陈明猷, 李承恩, 潘耀强, 唐昀超. 基于视觉机器人障碍点云映射避障规划及仿真[J]. 系统仿真学报, 2024, 36(9): 2149-2158.
[3]	刘佳仑, 杨帆, 谢玲利, 李诗杰, 王腾飞. 面向智能航行避碰决策与规划的虚拟仿真测试技术研究[J]. 系统仿真学报, 2024, 36(8): 1780-1789.
[4]	刘斌, 兰莹, 黄文焘, 范勤勤. 融合动态窗口法的无人机动态路径规划算法[J]. 系统仿真学报, 2024, 36(8): 1843-1853.
[5]	赖荣燊, 窦磊, 巫志勇, 孙帅. 融合改进A*算法和动态窗口法的移动机器人路径规划[J]. 系统仿真学报, 2024, 36(8): 1884-1894.
[6]	黄志锋, 刘媛华. 基于改进哈里斯鹰和B-spline曲线的无人机路径规划研究[J]. 系统仿真学报, 2024, 36(7): 1509-1524.
[7]	王雅如, 姚得鑫, 刘增力, 彭艺. 基于角度搜索的移动机器人路径规划方法[J]. 系统仿真学报, 2024, 36(7): 1643-1654.
[8]	雷旭, 陈静夷, 陈潇阳. 改进哈里斯鹰算法的仓储机器人路径规划研究[J]. 系统仿真学报, 2024, 36(5): 1081-1092.
[9]	刘泽森, 毕盛, 郭传鈜, 王延葵, 董敏. 基于深度学习的机器人局部路径规划方法[J]. 系统仿真学报, 2024, 36(5): 1199-1210.
[10]	王小康, 冀杰, 刘洋, 贺庆. 基于改进Q学习算法的无人物流配送车路径规划[J]. 系统仿真学报, 2024, 36(5): 1211-1221.
[11]	姜兆祯, 王文龙, 孙文祺. 基于改进RRT^*算法的无人艇路径规划快速求解算法[J]. 系统仿真学报, 2024, 36(4): 888-900.
[12]	张瑞, 周丽, 刘正洋. 融合RRT*与DWA算法的移动机器人动态路径规划[J]. 系统仿真学报, 2024, 36(4): 957-968.
[13]	李高扬, 黎向锋, 赵康, 金玉超, 易志东, 左敦稳. 全粒子推动野马优化算法的无人机三维路径规划[J]. 系统仿真学报, 2024, 36(3): 595-607.
[14]	闫星宇, 李大焱, 王妮娅, 张凯翔, 毛剑琳. 带障碍物惩罚因子的多机器人路径规划[J]. 系统仿真学报, 2024, 36(3): 673-685.
[15]	余翔, 姜陈, 段思睿, 邓千锐. 改进A*算法和人工势场法的路径规划[J]. 系统仿真学报, 2024, 36(3): 782-794.