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.
[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.
2019, Vol. 39 
