基于改进A^(*)算法的机器人导航研究

Robot navigation based on an improved A^(*) algorithm

针对机器人导航在面向复杂环境时A^(*)算法占用内存大、搜索时间长等问题,提出了一种基于改进A^(*)算法的机器人导航方法。改进A^(*)算法抛弃遍历周围点,直接将起点和终点的欧氏距离作为最短路径,若线段上有障碍物,则选取障碍物附近2个点为子起点和子终点,用A^(*)算法寻找路径;采用n阶贝塞尔曲线平滑小范围A^(*)算法所造成的路径曲折,根据A^(*)算法获得的不同曲线判断贝塞尔曲线的阶数。仿真结果表明,本算法只需使用小范围的A^(*)规划且仅需考虑A^(*)算法部分的曲率连续问题,路径实时性得到较大提高。

To solve the problems of high memory consumption and long search time of A^(*) algorithm in line segment in complex environments,this paper proposes a robot navigation method based on an improved A^(*) algorithm.The im-proved A^(*) algorithm abandons the traversal of surrounding nodes and directly takes the Euclidean distance between the start and the end points as the shortest path.If there are obstacles on the line segment,the two points near the obstacle are taken as the sub-starting point and sub-ending point,and the A^(*) algorithm is used to find the path.In addition,the n-order Bezier curve is used to smooth out the path tortuosity caused by the A^(*) algorithm in a small range,and the order of the Bezier curve is determined according to the different curves obtained by the A^(*) algorithm.The simulation results show that the real-time performance of the path can be greatly improved by using only a small range of A^(*) planning and only considering the curvature continuity problem of the A^(*) algorithm part.