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

Efficient Path Planning Algorithm Using Topology for Indoor Environment

作　　者：李冠达 金兢 王凡 夏营威 杨学志[2,5] LI Guanda;JIN Jing;WANG Fan;XIA Yingwei;YANG Xuezhi(College of Computer and Information,Hefei University of Technology,Hefei 230601,China;Anhui Province Key Laboratory of Industry Safety and Emergency Technology,Hefei University of Technology,Hefei 230601,China;Anhui Institute of Optics and Fine Mechanics,Hefei Institutes of Physical Science,Chinese Academy of Sciences,Hefei 230031,China;Science Island Branch of Graduate School,University of Science and Technology of China,Hefei 230026,China;College of Software,Hefei University of Technology,Hefei 230601,China)

机构地区：[1]合肥工业大学计算机与信息学院,合肥230601 [2]合肥工业大学工业安全与应急技术安徽省重点实验室,合肥230601 [3]中国科学院合肥物质科学研究院安徽光学精密机械研究所,合肥230031 [4]中国科学技术大学研究生院科学岛分院,合肥230026 [5]合肥工业大学软件学院,合肥230601

出　　处：《计算机工程》2022年第6期95-106,共12页Computer Engineering

基　　金：中央高校基本科研业务费专项资金(PA2021GDSK0070);安徽高校协同创新项目(GXXT-2019-003)。

摘　　要：针对基于随机采样的路径规划算法效率低且采样具有随机性的问题,提出一种应用拓扑结构的高效路径规划算法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.

关 键 词：全局路径规划 快速扩展随机树 角点检测算法 自适应阈值 节点扩充策略 约束条件 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]