改进A*与DWA的室内服务机器人路径规划研究

doi:10.3778/j.issn.1002-8331.2310-0140

摘要/Abstract

摘要： 鉴于全局规划无法规避动态障碍以及局部规划可能陷入局部最优的缺陷，提出一种基于服务机器人的改进A*与DWA（dynamic window approach）融合的路径规划算法。针对传统A*算法搜索速度较慢的缺陷，优化了评估函数；根据差速机器人运动模型，对搜索邻域进行了优化；针对传统A*算法路径折线线段多等缺陷，引入新的避障策略，对路径进行折线优化以及曲线平滑；针对全局与局部规划的缺陷，融合改进A*算法与DWA算法，根据全局路径关键节点分段应用动态规划算法，确保机器人能够实时避障。仿真实验证明，改进A*算法的性能更好，其中关键节点减少了75%，转折次数减少了80%，路径长度减少了5.9%，搜索时间减少了46%。融合算法相较于单一的静态算法，能够通过随机障碍物，顺利到达终点。

关键词: 服务机器人, 路径规划, A*算法, DWA算法, 算法融合

Abstract: Considering that global planning cannot avoid dynamic obstacles and local planning may fall into local optima, a path planning algorithm based on the fusion of improved A* and DWA (dynamic window approach) using service robots is proposed. To address the drawback of slow search speed in traditional A* algorithm, the evaluation function has been optimized. Based on the motion model of the differential robot, the search neighborhood is optimized. To address the shortcomings of traditional A* algorithm with multiple broken line segments in the path, a new obstacle avoidance strategy is introduced to optimize the path with broken lines and smooth the curve. To address the shortcomings of global and local planning, the improved A* algorithm and DWA algorithm are integrated, and dynamic planning algorithms are segmented based on key nodes of the global path to ensure real-time obstacle avoidance for robots. Simulation experiments have shown that the improved A* algorithm performs better, with key nodes reduced by 75%, turning times reduced by 80%, path length reduced by 5.9%, and search time reduced by 46%. Compared to a single static algorithm, the fusion algorithm can smoothly reach the endpoint through random obstacles.

Key words: service robots, path planning, A* algorithm, dynamic window approach (DWA) algorithm, algorithm fusion

姜佩贺, 王敬, 桑忠启, 林立峰. 改进A*与DWA的室内服务机器人路径规划研究[J]. 计算机工程与应用, 2024, 60(15): 327-335.

JIANG Peihe, WANG Jing, SANG Zhongqi, LIN Lifeng. Research on Indoor Service Robot Path Planning Based on Improved A* and DWA[J]. Computer Engineering and Applications, 2024, 60(15): 327-335.

参考文献

[1] JIN M, WANG H. Robot path planning by integrating improved A* algorithm and DWA algorithm[J]. Journal of Physics: Conference Series, 2023, 2492(1): 012017.
[2] ANIL K G, SRILATHA P, BUSIREDDY V R, et al. A mobile robot path planning algorithm based on improved A* algorithm and dynamic window approach[J]. Journal of Survey in Fisheries Sciences, 2023: 2601-2607.
[3] LAI R, WU Z, LIU X, et al. Fusion algorithm of the improved A* algorithm and segmented Bézier curves for the path planning of mobile robots[J]. Sustainability, 2023, 15(3): 2483.
[4] 崔炜, 朱发证. 机器人导航的路径规划算法研究综述[J]. 计算机工程与应用, 2023, 59(19): 10-20.
CUI W, ZHU F Z. Review of path planning algorithms for robot navigation[J]. Computer Engineering and Applications, 2023, 59(19): 10-20.
[5] 徐万福, 孙渊, 马志鸿. 基于改进A*算法的移动机器人路径规划[J]. 上海电机学院学报, 2023, 26(2): 63-68.
XU W F, SUN Y, MA Z H. Path planning of mobile robots based on improved A* algorithm[J]. Journal of Shanghai Dianji University, 2023, 26(2): 63-68.
[6] 徐嘉骏, 辛绍杰, 邓寅喆. 基于改进A*与TEB算法融合的移动机器人路径规划[J]. 计量与测试技术, 2022, 49(5): 26-30.
XU J J, XIN S J, DENG Y Z. Mobile robot path planning based on the fusion of improved A* and TEB algorithm[J]. Metrology & Measurement Technique, 2022, 49(5): 26-30.
[7] 张涛, 陈璋, 李玉梅, 等. 融合改进A*算法与动态窗口法的机器人避障研究[J]. 仪表技术与传感器, 2023(4): 102-106.
ZHANG T, CHEN Z, LI Y M, et al. Research on robot obstacle avoidance based on improved A* algorithm and dynamic window method[J]. Instrument Technique and Sensor, 2023(4): 102-106.
[8] 徐微, 汤俊伟, 张驰. 改进A*与动态窗口算法的移动机器人路径规划[J]. 计算机仿真, 2023, 40(3): 447-452.
XU W, TANG J W, ZHANG C. Path planning of mobile robot based on improved A?and dynamic window algorithm[J]. Computer Simulation, 2023, 40(3): 447-452.
[9] 王旭, 朱其新, 朱永红. 面向二维移动机器人的路径规划算法综述[J]. 计算机工程与应用, 2023, 59(20): 51-66.
WANG X, ZHU Q X, ZHU Y H. Review of path planning algorithms for mobile robots[J]. Computer Engineering and Applications, 2023, 59(20): 51-66.
[10] ZHEN Y X, WEI Y. Mobile robot path planning based on fusion of improved A* algorithm and adaptive DWA algorithm[J]. Journal of Physics: Conference Series, 2022, 2330(1): 012003.
[11] LI Y, JIN R, XU X, et al. A mobile robot path planning algorithm based on improved A* algorithm and dynamic window approach[J]. IEEE Access, 2022, 10: 57736-57747.
[12] 宾海茵, 吴超龙, 赵琳. 避障机器人路径规划算法的研究[J]. 现代信息科技, 2023, 7(7): 157-160.
BIN H Y, WU C L, ZHAO L. Research on path planning algorithm of obstacle avoidance robot[J]. Modern Information Technology, 2023, 7(7): 157-160.
[13] 张柏鑫, 杨毅镔, 朱华中, 等. 基于深度强化学习的移动机器人动态路径规划算法[J]. 计算机测量与控制, 2023, 31(1): 153-159.
ZHANG B X, YANG Y B, ZHU H Z, et al. Dynamic path planning algorithm of mobile robot based on deep reinforcement learning[J]. Computer Measurement & Control, 2023, 31(1): 153-159.
[14] 丁皓, 刘浩宇, 庄逸, 等. 基于四轮差速模型的多机器人路径规划[J]. 控制工程, 2023, 30(4): 730-738.
DING H, LIU H Y, ZHUANG Y. Multi-robot path planning based on four-wheel differential speed model[J]. Control Engineering of China, 2023, 30(4): 730-738.
[15] WANG X, LIU Z, LIU J. Mobile robot path planning based on an improved A* algorithm[C]//International Conference on Computer Graphics, Artificial Intelligence, and Data Processing (ICCAID 2022), 2022: 1093-1098.
[16] 陈曦, 石博强, 郭辉. 优化TEB算法的四轮差速机器人局部路径规划[J]. 软件, 2022, 43(6): 133-137.
CHEN X, SHI B Q, GUO H. Local path planning of four-wheel differential robot based on optimized TEB algorithm[J]. Software, 2022, 43(6): 133-137.
[17] KARUR K, SHARMA N, DHARMATTI C, et al. A survey of path planning algorithms for mobile robots[J]. Vehicles, 2021, 3(3): 448-468.
[18] LAI X, WU Dan, WU Di, et al. Enhanced DWA algorithm for local path planning of mobile robot[J]. Industrial Robot: the International Journal of Robotics Research and Application, 2022, 50(1): 186-194.