室内场景下应用拓扑结构的高效路径规划算法

Efficient Path Planning Algorithm Using Topology for Indoor Environment

针对基于随机采样的路径规划算法效率低且采样具有随机性的问题,提出一种应用拓扑结构的高效路径规划算法ATIRRT*。通过引入拓扑节点代替STIRRT*算法中Harris角点检测算法得到的特征点进行采样,给出基于阈值的自适应选择方法来消除路径骨架上提取的冗余特征点,利用该阈值得到的拓扑节点可以使随机树的扩展更具方向性,从而减少寻找初始路径的时间和代价。根据非单一父节点的连接方式加强交叉支路上的拓扑节点间的联系,通过节点扩充策略增加相邻拓扑节点间的节点数量以加快优化算法的收敛。在此基础上定义相关约束条件将初始路径分段并进行逐段优化,以提高优化算法的效率。在常规环境、狭长空间和仿真的室内环境3种类型地图上的仿真结果表明,相较于STIRRT*算法,改进算法在规划路径长度上平均减少8%,在规划时间上平均降低10%,可快速地找到更优的初始路径,同时在优化过程中减少了无用的探索空间,提高了搜索效率。

An efficient path planning algorithm,Adaptive Topological Informed Rapidly exploring Random Tree*(ATIRRT*),applying topology is proposed in this paper to address the low efficiency of the sampling-based path planning algorithm and the random nature of sampling.First,to reduce the time and cost of finding the initial path,topological nodes are introduced to replace the feature points obtained by the Harris corner detection algorithm in STIRRT* algorithm for sampling.Specifically,an adaptive threshold selection method is introduced to eliminate redundant feature points extracted on the path skeleton.The topological nodes obtained from this threshold can make the expansion of the random tree more directional,thereby reducing the time and cost of searching for the initial path.Second,the connection mode of a non-single parent node is proposed,which strengthens the connection between topological principle of nodes on intersecting branches.Third,the number of nodes between adjacent topological nodes is increased by the node expansion strategy to speed up the convergence of the optimization algorithm.Finally,the related constraints are defined to segment and optimize the initial path step by step,which further improves the efficiency of the optimization algorithm.The simulation results reveal that the improved algorithm can significantly improve the efficiency of path planning and the length of the planned path.Compared with STIRRT* algorithm,the length of the planned path in the three types of simulation maps was reduced by 8% on average,while the planning time was reduced by 10% on average,which can quickly find a better initial path and reduce the useless exploration space in the optimization process,thereby improving the search efficiency.