作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2022, Vol. 48 ›› Issue (6): 95-106. doi: 10.19678/j.issn.1000-3428.0061761

• 人工智能与模式识别 • 上一篇    下一篇

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

李冠达1,2, 金兢1,2, 王凡3,4, 夏营威3, 杨学志2,5   

  1. 1. 合肥工业大学 计算机与信息学院, 合肥 230601;
    2. 合肥工业大学 工业安全与应急技术安徽省重点实验室, 合肥 230601;
    3. 中国科学院合肥物质科学研究院 安徽光学精密机械研究所, 合肥 230031;
    4. 中国科学技术大学 研究生院科学岛分院, 合肥 230026;
    5. 合肥工业大学 软件学院, 合肥 230601
  • 收稿日期:2021-05-26 修回日期:2021-08-09 发布日期:2021-08-13
  • 作者简介:李冠达(1997—),男,硕士研究生,主研方向为路径规划、机器人环境感知;金兢,博士;王凡,博士研究生;夏营威,高级工程师、博士;杨学志,教授、博士生导师。
  • 基金资助:
    中央高校基本科研业务费专项资金(PA2021GDSK0070);安徽高校协同创新项目(GXXT-2019-003)。

Efficient Path Planning Algorithm Using Topology for Indoor Environment

LI Guanda1,2, JIN Jing1,2, WANG Fan3,4, XIA Yingwei3, YANG Xuezhi2,5   

  1. 1. College of Computer and Information, Hefei University of Technology, Hefei 230601, China;
    2. Anhui Province Key Laboratory of Industry Safety and Emergency Technology, Hefei University of Technology, Hefei 230601, China;
    3. Anhui Institute of Optics and Fine Mechanics, Hefei Institutes of Physical Science, Chinese Academy of Sciences, Hefei 230031, China;
    4. Science Island Branch of Graduate School, University of Science and Technology of China, Hefei 230026, China;
    5. College of Software, Hefei University of Technology, Hefei 230601, China
  • Received:2021-05-26 Revised:2021-08-09 Published:2021-08-13

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

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

Abstract: 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.

Key words: global path planning, Rapidly-exploring Random Tree(RRT), corner detection algorithm, adaptive threshold, node expansion strategy, constraint condition

中图分类号: