Computer Engineering and Applications ›› 2022, Vol. 58 ›› Issue (20): 247-254.DOI: 10.3778/j.issn.1002-8331.2112-0095

• Engineering and Applications • Previous Articles     Next Articles

Dynamic Path Planning Based on Improved BIT* and DWA Algorithm

WANG Xin, YAO Nianmin, TAN Guozhen   

  1. College of Computer Science and Technology, Dalian University of Technology, Dalian, Liaoning 116024, China
  • Online:2022-10-15 Published:2022-10-15

改进BIT*与DWA算法的动态路径规划

汪馨,姚念民,谭国真   

  1. 大连理工大学 计算机科学与技术学院,辽宁 大连 116024

Abstract: Traditional batch informed trees(BIT*) algorithm combines the advantages of RRT* algorithm and A* algorithm, but this algorithm cannot avoid unknown dynamic obstacles and cannot complete dynamic path planning in complex environment. To solve this problem, an algorithm combining the improved BIT* with DWA algorithm is proposed. Firstly, the stretch optimization of the path is carried out based on the BIT* algorithm to extract the key turning points and reduce the length of the path. Then, the distance evaluation function of the traditional DWA algorithm is improved and the track point evaluation function is introduced to avoid excessive deviation of local planning and reduce the influence of known obstacles on the path. Finally, the improved BIT* algorithm is fused with the improved DWA algorithm, and the extracted key turning points are taken as the intermediate target points of DWA to compensate for the shortcomings of the global planning algorithm that cannot avoid dynamic obstacles and the local planning algorithm that has low global capability. The RRT *algorithm, BIT* algorithm, DWA algorithm, improved BIT* algorithm and fusion algorithm are simulated in dynamic and static maps. The simulation results show that the improved BIT* algorithm has shorter paths and fewer inflection points in complex environments. Compared with the traditional DWA algorithm, the route planned by the fusion algorithm is smoother. The robot can not only reach the destination in real time and dynamically avoid obstacles, but also get closer to the global path to ensure the global optimal route.

Key words: path planning, improved BIT* algorithm, DWA algorithm, RRT* algorithm

摘要: 传统批通知树(batch informed trees,BIT*)算法结合了RRT*算法和A*算法的优势,但是该算法在复杂环境下无法躲避未知的动态障碍物,无法完成动态路径规划。针对该问题,提出了一种将改进的BIT*算法和改进的DWA算法相融合的算法。在传统BIT*算法的基础上对路径进行拉伸优化,提取关键转折点,减少路径长度;对传统DWA算法的距离评价函数进行改进、引入轨迹点评价函数,避免局部规划过分偏离,也减少了已知障碍物对路径的影响;将改进的BIT*算法与改进的DWA算法相融合,将提取的关键转折点作为DWA的中间目标点,弥补全局规划算法无法躲避动态障碍物的缺点以及局部规划算法全局能力低下的缺点。在动静态地图中对RRT*算法、BIT*算法、DWA算法、改进BIT*算法以及融合算法进行仿真实验,仿真结果表明:在复杂环境中,改进的BIT*算法具有更短的路径和更少的拐点;与传统的DWA算法相比,融合算法规划的路线更平滑,机器人既能实时动态避障抵达终点,又能更加贴近全局路径,保证路线全局最优。

关键词: 路径规划, 改进BIT*算法, DWA算法, RRT*算法