基于改进A*算法的煤矿救援机器人路径规划

Path planning of coal mine rescue robot based on improved A* algorithm

  • 摘要: 路径规划是煤矿救援机器人研究的重要内容之一。针对灾后煤矿环境非结构化的特点,以及传统A*算法规划的路径长度非最短、拐弯次数多和平滑度较差等问题,提出一种基于改进A*算法的煤矿救援机器人路径规划方法。对真实环境中的地图信息进行二值化处理,构建栅格地图;判断当前点与目标点的相对位置,利用改进A*算法进行路径规划,得到一条从当前点到目标点的路径;利用Douglas-Peucker(D−P)算法提取路径上的关键节点,采用三次样条插值函数对关键节点进行拟合,完成对路径的平滑处理。改进A*算法将传统A*算法的8邻域搜索扩展为有目的性的13邻域搜索,在进行路径搜索时,先对当前点和目标点的位置关系进行判断,从而减少路径节点,减小路径长度,提升路径平滑度。Matlab仿真结果表明:与8邻域A*算法、24邻域A*算法、48邻域A*算法相比,改进A*算法在路径长度、拐弯次数、平滑度等方面有一定优化,更适用于煤矿救援机器人路径规划;与Fuzzy算法相比,改进A*算法路径规划所用时间更短,规划的路径长度更短,拐弯次数更少。

     

    Abstract: Path planning is one of the important contents of research on coal mine rescue robots. A path planning method for coal mine rescue robots based on improved A* algorithm is proposed to address the unstructured features of post disaster coal mine environments and the problems of non-shortest path length, multiple turns, and poor smoothness of path planned by traditional A* algorithm. The method constructs raster maps by binarizing map information in real environments, determines the relative position between the current point and the target point, and uses the improved A* algorithm for path planning. Then a path from the current point to the target point is obtained. Douglas-Pucker (D-P) algorithm is used to extract key nodes on the path, and cubic spline interpolation function is used to fit the key nodes, thereby completing the smooth processing of the path. The improved A* algorithm expands the traditional A* algorithm's 8 neighborhood search to a purposeful 13 neighborhood search. When conducting path search, the position relationship between the current point and the target point is first determined, thereby reducing path nodes and length, and improving path smoothness. The Matlab simulation results show that compared with the 8 neighborhood A* algorithm, 24 neighborhood A* algorithm, and 48 neighborhood A* algorithm, the improved A* algorithm has certain optimizations in path length, number of turns and smoothness. It is more suitable for path planning of coal mine rescue robots. Compared with the Fuzzy algorithm, the improved A* algorithm achieve shorter path planning time, shorter planned path length, and fewer turns.

     

/

返回文章
返回