Efficient Path Planning Algorithm Using Topology for Indoor Environment

doi:10.19678/j.issn.1000-3428.0061761

Abstract

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

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

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

CLC Number:

TP18

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.

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

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0061761

http://www.ecice06.com/EN/Y2022/V48/I6/95

Figures/Tables 19

References

[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.

Please choose a citation manager

Content to export