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

doi:10.19678/j.issn.1000-3428.0061761

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

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

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

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 Guanda^1,2, JIN Jing^1,2, WANG Fan^3,4, XIA Yingwei³, YANG Xuezhi^2,5

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

摘要/Abstract

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

中图分类号:

TP18

李冠达, 金兢, 王凡, 夏营威, 杨学志. 室内场景下应用拓扑结构的高效路径规划算法[J]. 计算机工程, 2022, 48(6): 95-106.

LI Guanda, JIN Jing, WANG Fan, XIA Yingwei, YANG Xuezhi. Efficient Path Planning Algorithm Using Topology for Indoor Environment[J]. Computer Engineering, 2022, 48(6): 95-106.

https://www.ecice06.com/CN/Y2022/V48/I6/95

图/表 19

20220625174656

20220625174700

20220625174703

20220625174707

20220625174711

20220625174715

20220625174718

20220625174722

20220625174726

20220625174731

20220625174735

20220625174739

20220625174744

20220625174748

20220625174752

20220625174757

20220625174801

20220625174805

20220625174810

参考文献

[1] GAO W X, TANG Q, YE B F, et al.An enhanced heuristic ant colony optimization for mobile robot path planning[J].Soft Computing, 2020, 24(8):6139-6150.
[2] SEDIGHIZADEH D, MASEHIAN E, SEDIGHIZADEH M, et al.GEPSO:a new generalized particle swarm optimization algorithm[J].Mathematics and Computers in Simulation, 2021, 179:194-212.
[3] LAMINI C, BENHLIMA S, ELBEKRI A.Genetic algorithm based approach for autonomous mobile robot path planning[J].Procedia Computer Science, 2018, 127:180-189.
[4] WANG S M, ZHAO T T, LI W J.Mobile robot path planning based on improved artificial potential field method[C]//Proceedings of International Conference of Intelligent Robotic and Control Engineering.Lanzhou, China:[s.n.], 2018:29-33.
[5] LIN M X, YUAN K, SHI C Z, et al.Path planning of mobile robot based on improved a algorithm[C]//Proceedings of the 29th Chinese Control and Decision Conference.Chongqing, China:[s.n.], 2017:3570-3576.
[6] WU K Y, WANG H, ESFAHANI M A, et al.Achieving real-time path planning in unknown environments through deep neural networks[J].IEEE Transactions on Intelligent Transportation Systems, 2022, 23(3):2093-2102.
[7] 董永峰, 杨琛, 董瑶, 等.基于改进的DQN机器人路径规划[J].计算机工程与设计, 2021, 42(2):552-558. DONG Y F, YANG C, DONG Y, et al.Robot path planning based on improved DQN[J].Computer Engineering and Design, 2021, 42(2):552-558.(in Chinese)
[8] JANSON L, SCHMERLING E, CLARK A, et al.Fast marching tree:a fast marching sampling-based method for optimal motion planning in many dimensions[J].International Journal of Robotics Research, 2013, 34(7):883-921.
[9] 朱金辉, 梁明杰, 梁颖驹, 等.一种自适应加权快速探索随机树算法[J].计算机工程, 2010, 36(23):16-18. ZHU J H, LIANG M J, LIANG Y J, et al.Adaptive weighted rapidly-exploring random tree algorithm[J].Computer Engineering, 2010, 36(23):16-18.(in Chinese)
[10] LAVALLE S M.Rapidly-exploring random trees:a new tool for path planning[D].Ames, USA:Lowa State University, 1998.
[11] URMSON C, SIMMONS R.Approaches for heuristically biasing RRT growth[C]//Proceedings of 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems.Washington D.C., USA:IEEE Press, 2003:1178-1183.
[12] KALISIAK M, VAN DE PANNE M.RRT-blossom:RRT with a local flood-fill behavior[C]//Proceedings of 2006 IEEE International Conference on Robotics and Automation.Washington D.C., USA:IEEE Press, 2006:1237-1242.
[13] NOREEN I, KHAN A, HABIB Z.A comparison of RRT, RRT^* and RRT^*-smart path planning algorithms[J].International Journal of Computer Science and Network Security, 2016, 16(10):20-27.
[14] 黄壹凡, 胡立坤, 薛文超.基于改进RRT-Connect算法的移动机器人路径规划[J].计算机工程, 2021, 47(8):22-28. HUANG Y F, HU L K, XUE W C.Mobile robot path planning based on improved RRT-connect algorithm[J].Computer Engineering, 2021, 47(8):22-28.(in Chinese)
[15] MASHAYEKHI R, IDRIS M Y I, ANISI M H, et al.Informed RRT*-connect:an asymptotically optimal single-query path planning method[J].IEEE Access, 2020, 8:19842-19852.
[16] 龙建全, 梁艳阳.多路口环境下RRT的最优路径规划[J].计算机工程与应用, 2020, 56(19):273-278. LONG J Q, LIANG Y Y.Optimal path planning of RRT in multi-intersection environment[J].Computer Engineering and Applications, 2020, 56(19):273-278.(in Chinese)
[17] KARAMAN S, FRAZZOLI E.Sampling-based algorithms for optimal motion planning[J].The International Journal of Robotics Research, 2011, 30(7):846-894.
[18] GAMMELL J D, SRINIVASA S S, BARFOOT T D.Batch Informed Trees(BIT):sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs[C]//Proceedings of IEEE International Conference on Robotics and Automation.Washington D.C., USA:IEEE Press, 2015:3067-3074.
[19] 许万, 杨晔, 余磊涛, 等.一种基于改进RRT^*的全局路径规划算法[J].控制与决策, 2022, 37(4):829-838. XU W, YANG Y, YU L T, et al.A global path planning algorithm based on improved RRT^*[J].Control and Decision, 2022, 37(4):829-838.(in Chinese)
[20] GAMMELL J D, SRINIVASA S S, BARFOOT T D.Informed RRT:optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]//Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems.Washington D.C., USA:IEEE Press, 2014:2997-3004.
[21] RYU H, PARK Y.Improved informed RRT* using gridmap skeletonization for mobile robot path planning[J].International Journal of Precision Engineering and Manufacturing, 2019, 20(11):2033-2039.
[22] RYU H.Hierarchical path-planning for mobile robots using a skeletonization-informed rapidly exploring random tree[J].Applied Sciences, 2020, 10(21):7846.
[23] GUO Z C, HALL R W.Parallel thinning with two-subiteration algorithms[J].Communications of the ACM, 1989, 32(3):359-373.
[24] ZHANG F, WANG Y S, GAO C Y, et al.An improved parallel thinning algorithm with two subiter-ations[J].Optoelectronics Letters, 2008, 4(1):69-71.
[25] 张立亭, 黄晓浪, 鹿琳琳, 等.基于灰度差分与模板的Harris角点检测快速算法[J].仪器仪表学报, 2018, 39(2):218-224. ZHANG L T, HUANG X L, LU L L, et al.Fast Harris corner detection based on gray difference and template[J].Chinese Journal of Scientific Instrument, 2018, 39(2):218-224.(in Chinese)
[26] HARRIS C, STEPHENS M.A combined corner and edge detector[C]//Proceedings of Alvey Vision Conference.Manchester, UK:Alvey Vision Club, 1988:147-151.
[27] 王民, 周兆镇, 李昌华, 等.基于像素点灰度差的Harris角点检测算法[J].计算机工程, 2015, 41(6):227-230. WANG M, ZHOU Z Z, LI C H, et al.Harris corner detection algorithm based on pixel point gray difference[J].Computer Engineering, 2015, 41(6):227-230.(in Chinese)
[28] GAMMELL J D, BARFOOT T D.The probability density function of a transformation-based hyperellipsoid sampling technique[EB/OL].[2021-04-20].https://arxiv.org/abs/1404.1347.
[29] RUITER A H J, FORBES J R.On the solution of Wahba's problem on SO(n)[J].The Journal of the Astronautical Sciences, 2013, 60(1):1-31.

选择文件类型/文献管理软件名称

选择包含的内容

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

Efficient Path Planning Algorithm Using Topology for Indoor Environment

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 19

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王国栋, 叶剑, 谢萦, 钱跃良. 基于梯度的自适应阈值结构化剪枝算法[J]. 计算机工程, 2022, 48(9): 113-120.
[2]	许春冬, 周静, 应冬文, 龙清华. 基于非平稳系统辨识的心音包络自适应分割[J]. 计算机工程, 2020, 46(8): 290-296,304.
[3]	解扬,苗付友,白建峰. 基于整数规划的一般访问结构秘密共享方案[J]. 计算机工程, 2019, 45(6): 165-170.
[4]	吴强,刘华凯,稂时楠. 基于HVS的空中红外小目标快速检测算法[J]. 计算机工程, 2019, 45(5): 210-215,221.
[5]	蒋华,张红福,罗一迪,王鑫. 基于KL距离的自适应阈值网络流量异常检测[J]. 计算机工程, 2019, 45(4): 108-113,118.
[6]	张树涛, 谭海波, 陈良锋, 吕波. 一种高效的分布式爬虫系统负载均衡策略[J]. 计算机工程, 2019, 45(11): 62-67.
[7]	吴腾,张志利,赵军阳,张海峰. 一种局部最佳阈值预测的自适应角点检测方法[J]. 计算机工程, 2018, 44(3): 270-274.
[8]	周滔,赵津,胡秋霞,席阿行,刘东杰. 复杂环境下移动机器人全局路径规划与跟踪[J]. 计算机工程, 2018, 44(12): 208-214.
[9]	杨牧,陈长兴,凌云飞,林兴,王晓东. 基于自适应阈值的数据链协作抗干扰方法[J]. 计算机工程, 2018, 44(10): 101-106.
[10]	张晶,陈垚,孙俊,范洪博. 嵌入式控制驱动状态转移事件的预测调度模型[J]. 计算机工程, 2017, 43(8): 90-94,100.
[11]	梁元,车明. 基于约束条件的模糊等价关系聚类方法[J]. 计算机工程, 2017, 43(6): 276-280,288.
[12]	孟明,鲁少娜,马玉良. 基于EEMD与改进提升小波的脑电信号消噪方法[J]. 计算机工程, 2016, 42(4): 313-317.
[13]	刘杰,闫清东,唐正华. 基于激光雷达的移动机器人避障规划仿真研究[J]. 计算机工程, 2015, 41(4): 306-310.
[14]	李利, 杨恢先, 何雅丽, 冷爱莲, 岳许要. 结合FT与NSCT的自适应阈值去噪算法[J]. 计算机工程, 2012, 38(17): 238-241.
[15]	王思文, 贾克斌, 王纯, 刘帷. 基于运动信息的镜头切变检测与关键帧提取[J]. 计算机工程, 2012, 38(16): 5-8.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

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

Efficient Path Planning Algorithm Using Topology for Indoor Environment

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 19

参考文献

相关文章 15

编辑推荐

Metrics

本文评价