Narrow channel path planning based on bidirectional rapidly-exploring random tree

doi:10.11772/j.issn.1001-9081.2019030508

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (10): 2865-2869.DOI: 10.11772/j.issn.1001-9081.2019030508

• Artificial intelligence • Previous Articles Next Articles

Narrow channel path planning based on bidirectional rapidly-exploring random tree

FU Jiupeng, ZENG Guohui, HUANG Bo, FANG Zhijun

School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China

Received:2019-03-27 Revised:2019-05-16 Online:2019-10-14 Published:2019-10-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61603242), the Project of Jiangxi Province Economic Crime Investigation and Collaborative Innovation Center of Prevention and Control Technology (JXJZXTCX-030).

基于双向快速探索随机树的狭窄通道路径规划

付久鹏, 曾国辉, 黄勃, 方志军

上海工程技术大学电子电气工程学院, 上海 201620

通讯作者: 曾国辉
作者简介:付久鹏(1994-),男,江苏扬州人,硕士研究生,主要研究方向:机器人路径规划、智能控制;曾国辉(1975-),男,江西乐安人,副教授,博士,主要研究方向:机器人控制、电力电子及其控制;黄勃(1985-),男,湖北武汉人,讲师,博士,主要研究方向:需求工程、软件工程、人工智能;方志军(1971-),男,江西鄱阳人,教授,博士,主要研究方向:模式识别、智能计算、视频分析。
基金资助:
国家自然科学基金资助项目（61603242）；江西省经济犯罪侦查与防控技术协同创新中心开放课题（JXJZXTCX-030）。

Abstract

Abstract: In the process of mobile robot path planning, it is difficult for the Rapidly-exploration Random Tree (RRT) algorithm to sample narrow channels. In order to deal with this problem, an improved bridge detection algorithm was proposed, which is dedicated to narrow channel sampling. Firstly, the environment map was pre-processed and the obstacle edge coordinate set was extracted as the sampling space for the bridge detection algorithm, thus avoiding a large number of invalid sampling points and making the sampling points distribution of the narrow channel more rational. Secondly, the process for bridge endpoint construction was improved, and the operation efficiency of the bridge detection algorithm was increased. Finally, a slight variant Connect algorithm was used to expand the narrow channel sample points rapidly. For the narrow channel environment map in the experiment, the improved algorithm has the success rate increased from 68% to 92% compared with the original RRT-Connect algorithm. Experimental results show that the proposed algorithm can sample the narrow channel well and improve the efficiency of path planning.

Key words: path planning, Rapidly-exploring Random Tree (RRT), narrow channel, bridge detection algorithm, obstacle edge detection

摘要： 针对移动机器人路径规划过程中基于快速探索随机树（RRT）算法难以对窄道进行采样的问题，提出一种专门用于狭窄通道路径规划的改进桥梁检测算法。首先对环境地图预处理并提取出障碍物边缘节点集合作为桥梁检测算法的采样空间，从而避免了大量无效采样点，并使窄道样本点分布更加合理化；其次改进了桥梁端点的构建过程，提高了桥梁检测算法的运算效率；最后使用一种轻微变异Connect算法快速扩展窄道样本点。对于实验中的窄道环境地图，与原始RRT-Connect算法相比较，所提改进算法的路径探索成功率由68%提高到92%。实验结果表明，该算法能够较好地完成窄道样本点采样并有效地提高路径规划效率。

关键词: 路径规划, 快速探索随机树, 狭窄通道, 桥梁检测算法, 障碍物边缘检测

CLC Number:

TP242.6

FU Jiupeng, ZENG Guohui, HUANG Bo, FANG Zhijun. Narrow channel path planning based on bidirectional rapidly-exploring random tree[J]. Journal of Computer Applications, 2019, 39(10): 2865-2869.

付久鹏, 曾国辉, 黄勃, 方志军. 基于双向快速探索随机树的狭窄通道路径规划[J]. 计算机应用, 2019, 39(10): 2865-2869.

References

[1] LATOMBE, J. Motion planning:a journey of robots, molecules, digital actors, and other artifacts[J]. The International Journal of Robotics Research, 1999, 18(11):1119-1128.
[2] 王春颖, 刘平, 秦洪政. 移动机器人的智能路径规划算法综述[J]. 传感器与微系统, 2018, 37(8):5-8. (WANG C Y, LIU P, QIN H Z. Review on intelligent path planning algorithm of mobile robots[J]. Transducer and Microsystem Technologies, 2018, 37(8):5-8.)
[3] LAVALLE S M, KUFFNER J J. Randomized kinodynamic planning[J]. International Journal of Robotics and Research, 1999, 20(5):473-479.
[4] 康亮, 赵春霞, 郭剑辉. 未知环境下改进的基于RRT算法的移动机器人路径规划[J]. 模式识别与人工智能, 2009, 22(3):337-343. (KANG L, ZHAO C X, GUO J H. Improved path planning based on rapidly-exploring random tree for mobile robot in unknown environment[J]. Pattern Recognition and Artificial Intelligence, 2009, 22(3):337-343.)
[5] KUFFNER J J, LAVALLE S M. RRT-Connect:an efficient approach to single-query path planning[C]//Proceedings of the 2000ⅡEEE International Conference on Robotics and Automation. Piscataway:IEEE, 2000:995-1001.
[6] KARAMAN S, FRAZZOLI E. Incremental sampling-based algorithms for optimal motion planning[EB/OL].[2018-12-10]. https://arxiv.org/abs/1005.0416.
[7] QURESHI A H, AYAZ Y. Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments[J]. Robotics and Autonomous Systems, 2015, 68:1-11.
[8] GAMMELL J D, BARFOOT T D, SRINIVASA S S. Informed sampling for asymptotically optimal path planning[J]. IEEE Transactions on Robotics, 2018, 34(4):966-984.
[9] LUAN C, FANG Z. Random particles boosted RRT for complicated 3D environments with narrow passages[C]//Proceedings of the 12th World Congress on Intelligent Control and Automation. Piscataway:IEEE, 2016:3271-3276.
[10] 钟建冬, 苏剑波. 基于概率路标的机器人狭窄通道路径规划[J]. 控制与决策, 2010, 25(12):1831-1836. (ZHONG J D, SUN J B. Robot path planning in narrow passage based on probabilistic roadmap method[J]. Control and Decision, 2010, 25(12):1831-1836.)
[11] 莫栋成, 刘国栋. 改进的RRT-Connect双足机器人路径规划算法[J]. 计算机应用, 2013, 33(8):2289-2292. (MO D C, LIU G D. Improved RRT-Connect path planning algorithm for biped robot[J]. Journal of Computer Applications, 2013, 33(8):2289-2292.)
[12] SUN Z, HSU D, JIANG T, et al. Narrow passage sampling for probabilistic roadmap planning[J]. IEEE Transactions on Robotics, 2005, 21(6):1105-1115.
[13] BASTA R A, MEHROTRA R, VARANASI M R. Collision detection for planning collision-free motion of two robot arms[C]//Proceedings of the 1998 IEEE International Conference on Robotics and Automation. Piscataway:IEEE, 1988:638-640.
[14] 段瑞玲, 李庆祥, 李玉和. 图像边缘检测方法研究综述[J]. 光学技术, 2005, 31(3):415-419. (DUAN R L, LI Q X, LI Y H. Summary of image edge detection[J]. Optical Technique, 2005, 31(3):415-419.)
[15] JOSHI S R, KOJU R. Study and comparison of edge detection algorithms[C]//Proceedings of the 3rd Asian Himalayas International Conference on Internet. Piscataway:IEEE, 2012:1-5.
[16] NADARAJAH S, KOTZ S. Exact distribution of the max/min of two Gaussian random variables[J]. IEEE Transactions on Very Large Scale Integration Systems, 2008, 16(2):210-212.
[17] 付妍, 朱晓明, 周秉锋. 基于圆形参数域和重要性采样的三维模型网格重建[J]. 计算机学报, 2007, 30(12):2124-2131. (FU Y, ZHU X M, ZHOU B F. 3D model remeshing using circular parameter domain and importance sampling[J]. Chinese Journal of Computers, 2007, 30(12):2124-2131.)
[18] 霍红卫, 许进. 快速排序算法研究[J]. 微电子学与计算机, 2002(6):6-9. (HUO H W, XU J. A study on quicksort algorithm[J]. Microelectronics and Computer, 2002(6):6-9.)
[19] YANG Y, YU P, GAN Y. Experimental study on the five sort algorithms[C]//Proceedings of the 2nd International Conference on Mechanic Automation and Control Engineering. Piscataway:IEEE, 2011:1314-1317.

Narrow channel path planning based on bidirectional rapidly-exploring random tree

基于双向快速探索随机树的狭窄通道路径规划

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	Tian MA, Runtao XI, Jiahao LYU, Yijie ZENG, Jiayi YANG, Jiehui ZHANG. Mobile robot 3D space path planning method based on deep reinforcement learning [J]. Journal of Computer Applications, 2024, 44(7): 2055-2064.
[2]	Runze TIAN, Yulong ZHOU, Hong ZHU, Gang XUE. Local information based path selection algorithm for service migration [J]. Journal of Computer Applications, 2024, 44(7): 2168-2174.
[3]	Jianqiang LI, Zhou HE. Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery [J]. Journal of Computer Applications, 2024, 44(4): 1187-1194.
[4]	Haixin HUANG, Guangwei YU, Shoushan CHENG, Chunming LI. Full coverage path planning of bridge inspection wall-climbing robot based on improved grey wolf optimization [J]. Journal of Computer Applications, 2024, 44(3): 966-971.
[5]	Ziyang SONG, Junhuai LI, Huaijun WANG, Xin SU, Lei YU. Path planning algorithm of manipulator based on path imitation and SAC reinforcement learning [J]. Journal of Computer Applications, 2024, 44(2): 439-444.
[6]	Jian SUN, Baoquan MA, Zhuiwei WU, Xiaohuan YANG, Tao WU, Pan CHEN. Joint optimization of UAV swarm path planning and task allocation balance in earthquake scenarios [J]. Journal of Computer Applications, 2024, 44(10): 3232-3239.
[7]	Yongdi LI, Caihong LI, Yaoyu ZHANG, Guosheng ZHANG. Mobile robot path planning based on improved SAC algorithm [J]. Journal of Computer Applications, 2023, 43(2): 654-660.
[8]	Lin HUANG, Qiang FU, Nan TONG. Solving robot path planning problem by adaptively adjusted Harris hawk optimization algorithm [J]. Journal of Computer Applications, 2023, 43(12): 3840-3847.
[9]	Chen LIU, Yang CHEN, Hao FU. UAV path planning for persistent monitoring based on value function iteration [J]. Journal of Computer Applications, 2023, 43(10): 3290-3296.
[10]	Houming FAN, Shuang MU, Lijun YUE. Collaborative optimization of automated guided vehicle scheduling and path planning considering conflict and congestion [J]. Journal of Computer Applications, 2022, 42(7): 2281-2291.
[11]	Sheng CHEN, Jun ZHOU, Xiaobing HU, Ji MA. Optimization of airport arrival procedures based on hybrid simulated annealing algorithm [J]. Journal of Computer Applications, 2022, 42(2): 606-615.
[12]	LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568.
[13]	TANG Andi, HAN Tong, XU Dengwu, XIE Lei. Path planning method of unmanned aerial vehicle based on chaos sparrow search algorithm [J]. Journal of Computer Applications, 2021, 41(7): 2128-2136.
[14]	ZHANG Kang, CHEN Jianping. Path planning algorithm in complex environment using self-adjusting sampling space [J]. Journal of Computer Applications, 2021, 41(4): 1207-1213.
[15]	HUANG Shuzhao, TIAN Junwei, QIAO Lu, WANG Qin, SU Yu. Unmanned aerial vehicle path planning based on improved genetic algorithm [J]. Journal of Computer Applications, 2021, 41(2): 390-397.