一种基于障碍物登陆点检测的全局路径规划算法

A global path planning algorithm based on obstacle landing node detection

地图栅格化是机器人路径规划的常用方法,但地图规模的扩大会造成搜索栅格数量呈指数级增长,使得算法效率大幅下降。针对这一问题,提出了一种基于障碍物登陆点检测的全局路径规划算法。依据障碍物的分布特点,通过计算障碍物映射角寻找登陆点,并在障碍物边缘区域建立赋权图,缩小结点搜索范围,避免大规模搜索栅格结点;然后,依据赋权图特点对Dijkstra算法进行改进,利用改进的Dijkstra搜索全局最短路径。分别将所提的算法与传统A*算法及其变体JPS算法进行实验对比,结果表明,所提算法比传统A*算法以及JPS算法规划路径略短,搜索速度更快,尤其在走廊等障碍物块较少的大规模地图中,搜索时间仅为A*算法的1/8,JPS算法的1/3。

Map rasterization is a common method for robot path planning,but a significant decrease in algorithm efficiency arises as the number of grids searched increases exponentially with the expansion of map scale.A global path planning algorithm based on obstacle landing node detection is proposed.Based on the distribution characteristics of obstacles,landing nodes are found out by calculating the mapping angles of obstacles,and a weighted graph is established in the edge region of obstacles to narrow the range of nodes searched and avoid large-scale search in grid nodes.Then according to the characteristics of weighted graph,Dijkstra algorithm is improved and used to search the global shortest path.The proposed algorithm is compared with the traditional A*algorithm and a variant of A*,JPS algorithm.The experimental results show that the proposed algorithm has slightly shorter length and faster speed of path planning than the traditional A*algorithm and JPS algorithm,especially in large-scale maps with fewer obstacle blocks such as hallway,the search time is only one-eighth of the A*algorithm and one third of the JPS algorithm.