Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (10): 173-180.DOI: 10.3778/j.issn.1002-8331.2007-0102

Previous Articles     Next Articles

Robot Path Planning Method of Multiple A* Algorithm in Dynamic Environment

HUA Hong, ZHANG Zhi’an, SHI Zhenwen, CHEN Guanxing   

  1. School of Mechanical Engineering, Nanjing University of Science and Technology, Nanjing 210094, China
  • Online:2021-05-15 Published:2021-05-10

动态环境下多重A*算法的机器人路径规划方法

华洪,张志安,施振稳,陈冠星   

  1. 南京理工大学 机械工程学院,南京 210094

Abstract:

The traditional A* algorithm is only applicable to the global static environment. When solving path planning problems, it has the disadvantages of low search efficiency and uneven path. In response to these problems, the following improvements have been made:Optimizing the global path nodes and introducing the deleting redundant points criterion and the new node criterion, which can make the global path smoother and more in line with robot kinematics; Combined with the idea of the rolling window method, local path planning is performed in each rolling window. The local sub-target area is determined by the node information of the previous step, and then obstacle avoidance control strategies are introduced in the local sub-target area to implement real-time obstacle avoidance. Finally, a variety of grid map simulations are established on the Matlab, where the improved algorithm is compared with the original algorithm in terms of path smoothness, search efficiency and local planning ability, and the simulation analysis is performed in a dynamic environment. The simulation results show that the improved algorithm has good local planning capabilities, at the same time the path trajectory is smoother and the search efficiency is higher in complex environments.

Key words: path planning, obstacle avoidance control, A* algorithm, moving robot

摘要:

传统的A*算法仅适用于全局的静态环境,在求解路径规划问题时存在搜索效率低,路径不平滑等不足。针对这些问题,进行了以下改进:优化全局路径节点,引入删除冗余点准则与新增节点准则,使得全局路径更加平滑,更符合机器人运动学规律;结合滚动窗口法的思想,在每个滚动窗口内进行局部路径规划,首先根据前一步的节点信息确定局部子目标区域,然后在局部子目标区域内引入避障控制策略进行实时避障。最后通过Matlab软件建立多种栅格地图仿真,从路径轨迹的平滑度、搜索效率与局部规划能力方面将改进后的算法与原算法进行对比,并在动态环境下进行仿真分析,仿真结果表明改进后算法拥有良好局部规划能力,且路径轨迹更加平滑,在复杂环境下搜索效率更高。

关键词: 路径规划, 避障控制, A*算法, 移动机器人