改进A*和动态窗口法的无人车路径规划

doi:10.6040/j.issn.1672-3961.0.2024.023

摘要/Abstract

摘要： 针对室内无人车路径规划问题,采用改进A^*算法和动态窗口法(dynamic window approach, DWA),提出并设计一种混合路径规划算法,有效提升规划过程中的全局最优性和实时避障能力。采用动态权重平衡节点扩展速度,提高传统A^*算法在复杂环境下的规划效率;引入24邻域搜索策略,解决双向搜索重复访问节点的问题;将前后时刻的航向角之差引入轨迹评价函数,优化传统DWA对障碍物分布适应能力,减少在障碍物处的转向角度,提高在空旷区域的行驶速度;对规划算法的结果进行分析,结合仿真试验验证混合路径规划算法的有效性。试验结果表明,改进算法可以在规划最优路径的同时保证良好的实时避障能力。

关键词: 无人车, 路径规划, 改进A^*算法, 动态窗口法, 混合路径规划算法

Abstract: To tackle the path planning challenges for indoor unmanned vehicle, an improved A^* algorithm and dynamic window approach(DWA)were utilized to develop a hybrid path planning algorithm, which significantly enhanced both global optimality and real-time obstacle avoidance capabilities. Dynamic weights were employed to balance node expansion speed, which boosted the efficiency of the traditional A^* algorithm in complex environments. 24-Neighborhood search strategy was introduced to address the issue of node revisitation in bidirectional searches. The differential in heading angles between successive moments was incorporated into the trajectory evaluation function, optimizing the adaptability of traditional DWA to obstacle distribution, reducing turning angles at obstacles, and increasing travel speed in open areas. An analysis of the planning algorithm's results, supported by simulation experiments, confirmed the efficacy of the hybrid path planning algorithm. Experimental outcomes showed that this enhanced algorithm could effectively ensure optimal path planning alongside robust real-time obstacle avoidance capabilities.

Key words: unmanned vehicle, path planning, improved A^* algorithm, dynamic window approach, hybrid path planning algorithm

中图分类号:

U469.79

韩毅,刘毅超,关甜,兰理文,汤宁业. 改进A^*和动态窗口法的无人车路径规划[J]. 山东大学学报 (工学版), 2025, 55(3): 16-24.

HAN Yi, LIU Yichao, GUAN Tian, LAN Liwen, TANG Ningye. Improved A^* and dynamic window approach for unmanned vehicle path planning[J]. Journal of Shandong University(Engineering Science), 2025, 55(3): 16-24.

参考文献

[1] 朱茂飞, 胡方亚, 李娜可, 等. 无人驾驶汽车路径规划算法综述[J]. 农业装备与车辆工程, 2023, 61(11): 18-22. ZHU Maofei, HU Fangya, LI Nake, et al. Summary of path planning algorithms for driverless vehicle[J]. Agricultural Equipment & Vehicle Engineering, 2023, 61(11): 18-22.
[2] 胡铮, 徐斌. 融合A^*算法与人工势场法的动态路径规划[J]. 组合机床与自动化加工技术, 2023(7): 46-49. HU Zheng, XU Bin. Dynamic path planning based on the interation of A^* algorithm and artificial potential field method[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2023(7): 46-49.
[3] 朱宇. 无人驾驶车辆路径规划算法综述[J]. 内燃机与配件, 2023(24): 81-84. ZHU Yu. A review of route planning algorithms for unmanned vehicles[J]. Internal Combustion Engine & Parts, 2023(24): 81-84.
[4] ZHOU X W, YAN J W, YAN M, et al. Path planning of rail-mounted logistics robots based on the improved Dijkstra algorithm[J]. Applied Sciences, 2023, 13(17): 9955.
[5] DENG Z L, WANG D. Research on parking path planning based on A-star algorithm[J]. Journal of New Media, 2023, 5(1): 55-64.
[6] 刘文光, 刘浩伟, 罗通, 等. RRT算法路径优化及仿真验证[J]. 重庆理工大学学报(自然科学), 2022, 36(11): 1-7. LIU Wenguang, LIU Haowei, LUO Tong, et al. RRT algorithm path optimization based on MATLAB simulation[J]. Journal of Chongqing University of Technology(Natural Science), 2022, 36(11): 1-7.
[7] 卞永明, 季鹏成, 周怡和, 等. 基于改进型DWA的移动机器人避障路径规划[J]. 中国工程机械学报, 2021, 19(1):44-49. BIAN Yongming, JI Pengcheng, ZHOU Yihe, et al. Obstacle avoidance path planning of mobile robot based on improved DWA[J]. Chinese Journal of Construction Machinery, 2021, 19(1): 44-49.
[8] 倪建云, 杜合磊, 谷海青, 等. 改进人工势场法的移动机器人路径规划研究[J]. 重庆理工大学学报(自然科学), 2023, 37(11): 247-256. NI Jianyun, DU Helei, GU Haiqing, et al. Improved artificial potential field method for mobile robots path planning study[J]. Journal of Chongqing University of Technology(Natural Science), 2023, 37(11): 247-256.
[9] WANG P Y, LIU Y L, YAO W M, et al. Improved A-star algorithm based on multivariate fusion heuristic function for autonomous driving path planning[J]. Proceedings of the Institution of Mechanical Engineers, 2023, 237(7): 1527-1542.
[10] YU J T, GAO Z H, JIANG M Z, et al. Robot path planning based on improved A^* algorithm[J]. Journal of Physics: Conference Series, 2023, 2637(1): 012008.
[11] 刘威, 储春华, 肖明伟. 一种基于时间和路径双重优化的改进A^*算法[J]. 制造业自动化, 2023, 45(12): 173-177. LIU Wei, CHU Chunhua, XIAO Mingwei. An improved A^* algorithm based on dual optimization of time and path[J]. Manufacturing Automation, 2023, 45(12): 173-177.
[12] 李炯逸, 李强, 张新闻, 等. 移动机器人用改进的双向A^*二次路径规划算法[J]. 系统仿真学报, 2025, 37(2): 498-507. LI Jiongyi, LI Qiang, ZHANG Xinwen, et al. Improved bidirectional A^* quadratic path planning algorithm for mobile robots[J]. Journal of System Simulation, 2025, 37(2): 498-507.
[13] 童亚男, 肖本贤. 基于无人叉车行驶时间优化的改进A^*算法[J]. 合肥工业大学学报(自然科学版), 2023, 46(11): 1447-1453. TONG Yanan, XIAO Benxian. Improved A^* algorithm based on the optimization of driving time of unmanned forklifts[J]. Journal of Hefei University of Technology(Natural Science), 2023, 46(11): 1447-1453.
[14] 徐万福, 孙渊, 马志鸿. 基于改进A^*算法的移动机器人路径规划[J]. 上海电机学院学报, 2023, 26(2): 63-68. XU Wanfu, SUN Yuan, MA Zhihong. Path planning of mobile robot based on improved A^* algorithm[J]. Journal of Shanghai Dianji University, 2023, 26(2): 63-68.
[15] 贾彬, 包长春, 蒋金成. 基于改进A^*算法的无人机路径规划研究[J]. 信息与电脑, 2023, 35(19): 71-75. JIA Bin, BAO Changchun, JIANG Jincheng. Research on unmanned aerial vehicle path planning based on improved A^* algorithm[J]. Information & Computer, 2023, 35(19): 71-75.
[16] 董雅文, 杨静雯, 张宝锋, 等. 改进邻域扩展A^*算法的移动机器人路径规划[J]. 机械设计与制造, 2025(1): 291-295. DONG Yawen, YANG Jingwen, ZHANG Baofeng, et al. An improved A^* algorithm based on neighbor expansion for mobile robot path planning[J]. Machinery Design & Manufacture, 2025(1): 291-295.
[17] ZHANG H X, TAO Y D, ZHU W L. Global path planning of unmanned surface vehicle based on improved A-star algorithm[J]. Sensors, 2023, 23(14): 6647.
[18] YOU Z Y, SHEN K Y, HUANG T, et al. Application of A^* algorithm based on extended neighborhood priority search in multi-scenario maps[J]. Electronics, 2023, 12(4): 1004.
[19] 吴振帅, 任天飞, 李佳晖, 等. 基于改进A^*算法的建筑机器人路径规划研究[J]. 河北科技大学学报, 2024, 45(6): 653-661. WU Zhenshuai, REN Tianfei, LI Jiahui, et al. Research on path planning for construction robots based on improved A^* algorithm[J]. Journal of Hebei University of Science and Technology, 2024, 45(6): 653-661.
[20] 柴红杰, 李建军, 姚明. 改进的A^*算法移动机器人路径规划[J]. 电子器件, 2021, 44(2): 362-367. CHAI Hongjie, LI Jianjun, YAO Ming. Improved A^* algorithm for path planning of mobile robot[J]. Chinese Journal of Electron Devices, 2021, 44(2): 362-367.
[21] 常新新, 胡为, 姬书得, 等. 基于改进动态窗口法的移动机器人避障研究[J]. 组合机床与自动化加工技术, 2021(7): 33-36. CHANG Xinxin, HU Wei, JI Shude, et al. Obstacle avoidance of mobile robot based on improved dynamic window method[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2021(7): 33-36.
[22] ZHANG L Y, HAN Y, JIANG B. Research on path planning method of unmanned boat based on improved DWA algorithm[J]. Journal of Sensors, 2022, 2022: 9315483.
[23] CHEN J X, YI L. Dynamic path planning for mobile robots based on the improved A-star algorithm[J]. Academic Journal of Computing Information Science, 2021, 4(8): 73-77.
[24] ZHANG J H, FENG Q, ZHAO A D, et al. Local path planning of mobile robot based on self-adaptive dynamic window approach[J]. Journal of Physics: Conference Series, 2021, 1905(1): 012019.
[25] MAI X, LI D, OUYANG J, et al. An improved dynamic window approach for local trajectory planning in the environment with dense objects[C] //Proceedings of the 2021 International Conference on Intelligent Manufacturing and Industrial Automation(CIMIA 2021). Guilin, China: IOP, 2021: 012003.
[26] XIN L, DAN W, DI W, et al. Enhanced DWA algorithm for local path planning of mobile robot[J]. The Industrial Robot, 2023, 50(1): 186-194.
[27] JONATHAN P, KENNETH R. Comparative analysis of ROS-unity 3D and ROS-gazebo for mobile ground robot simulation[J]. Journal of Intelligent Robotic Systems, 2022, 106(4): 80.
[28] 李业谦, 陈春苗. 基于ROS和激光雷达的移动机器人自动导航系统设计[J]. 现代电子技术, 2020, 43(10): 176-178. LI Yeqian, CHEN Chunmiao. Design of mobile robot automatic navigation system based on ROS and laser radar[J]. Modern Electronics Technique, 2020, 43(10): 176-178.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed