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

doi:10.11772/j.issn.1001-9081.2019030508

计算机应用 ›› 2019, Vol. 39 ›› Issue (10): 2865-2869.DOI: 10.11772/j.issn.1001-9081.2019030508

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

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

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

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

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

摘要/Abstract

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

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

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

中图分类号:

TP242.6

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

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	马天, 席润韬, 吕佳豪, 曾奕杰, 杨嘉怡, 张杰慧. 基于深度强化学习的移动机器人三维路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2055-2064.
[2]	田润泽, 周宇龙, 朱洪, 薛岗. 基于局部信息的服务迁移路径选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2168-2174.
[3]	李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194.
[4]	黄海新, 于广威, 程寿山, 李春明. 基于改进灰狼优化的桥梁检测爬壁机器人全覆盖路径规划[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 966-971.
[5]	邓辅秦, 官桧锋, 谭朝恩, 付兰慧, 王宏民, 林天麟, 张建民. 基于请求与应答通信机制和局部注意力机制的多机器人强化学习路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 432-438.
[6]	宋紫阳, 李军怀, 王怀军, 苏鑫, 于蕾. 基于路径模仿和SAC强化学习的机械臂路径规划算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 439-444.
[7]	邓辅秦, 谭朝恩, 黎俊炜, 钟家铭, 付兰慧, 张建民, 王宏民, 李楠楠, 姜炳春, 林天麟. 面向大型仓储环境的基于冲突搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3854-3860.
[8]	孙鉴, 马宝全, 吴隹伟, 杨晓焕, 武涛, 陈攀. 地震场景下无人机群路径规划与任务分配均衡联合优化[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3232-3239.
[9]	李永迪, 李彩虹, 张耀玉, 张国胜. 基于改进SAC算法的移动机器人路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 654-660.
[10]	王龙宝, 栾茵琪, 徐亮, 曾昕, 张帅, 徐淑芳. 基于动态簇粒子群优化的无人机集群路径规划方法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3816-3823.
[11]	黄霖, 符强, 童楠. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3840-3847.
[12]	刘晨, 陈洋, 符浩. 基于值函数迭代的持续监测无人机路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3290-3296.
[13]	范厚明, 牟爽, 岳丽君. 考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2281-2291.
[14]	陈昇, 周隽, 胡小兵, 马霁. 基于混合模拟退火算法的机场进场程序优化[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 606-615.
[15]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.