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

来源：计算机工程杂志2022年第6期北京时间：

作者：李冠达, 金兢, 王凡, 夏营威, 杨学志

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

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

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

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