Global path planning based on a bidirectional alternating search A* algorithm for mobile robots
Global path planning based on a bidirectional alternating search A* algorithm for mobile robots
复制标题
DOI：
10.1016/j.cie.2022.108123
复制
发表时间：
2022-04-04
影响因子：
7.9
通讯作者：
Lu, Shiqing
中科院分区：
文献类型：
--
作者：
Li, Changgeng;Huang, Xia;Lu, Shiqing
虽然A* 算法在路径规划问题中得到了广泛的研究和应用，但它存在计算时间长、转弯角度大、大任务空间下路径不平滑等突出问题。针对这些问题，提出了一种改进的A* 算法。首先，在A* 算法中引入双向交替搜索（BAS）策略，前向和后向路径列表以相对列表中的当前路径节点为目标节点，交替搜索路径，直到路径相遇，提高了算法的搜索效率。然后，通过指数衰减对启发式函数进行加权，克服了BAS-A* 算法的不足。最后，引入路径节点的过滤功能，减少路径中的冗余节点，从而有效减小转弯角度。此外，使用Be′zier曲线满足光滑路径规划的要求，这是移动的机器人的运动控制的关键。在不同尺寸的地图上进行了路径规划仿真，并与A* 算法、遗传算法（GA）和模拟退火算法（SA）在计算时间、路径长度和转弯角度等方面进行了比较。结果表明，该算法能更有效地解决机器人路径规划问题，比上述其他算法顺利。最后，在TurtleBot 3 Waffle Pi移动的机器人上验证了该算法的实用性。
While the A* algorithm has been widely investigated and applied in path planning problems, it has outstanding issues such as long calculation time, large turning angles, and the unsmoothed path in large task spaces. Aiming at overcoming these problems, an improved A* algorithm is proposed in this work. First, a bidirectional alternating search (BAS) strategy is introduced into the A* algorithm; the forward and backward path lists use the current path node in the opposite list as the target node to alternately search for paths until the paths meet, which improves the search efficiency of the algorithm. Then, the heuristic function is weighted via exponential attenuation, which overcomes the shortcomings of the BAS-A* algorithm. Finally, the filtering function of path nodes is introduced to reduce redundant nodes in the path, thereby effectively reducing the turning angle. Moreover, the use of Be & PRIME;zier curves fulfills the requirements of smooth path planning, which is critical for the motion control of mobile robots. Simulations of path planning on maps of different sizes were performed, and the proposed algorithm was compared with that of the A* algorithm, the genetic algorithm (GA) and the simulated annealing algorithm (SA) in terms of the computation time, path length, and turning angle. The results reveal that the proposed algorithm can solve the robot path planning problem more efficiently and smoothly than the other algorithms mentioned above. Additionally, the practicability of the proposed algorithm is validated on the TurtleBot3 Waffle Pi mobile robot.