Path planning of mobile robot based on improved asymptotically-optimal bidirectional rapidly-exploring random tree algorithm

doi:10.11772/j.issn.1001-9081.2018102213

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (5): 1312-1317.DOI: 10.11772/j.issn.1001-9081.2018102213

• Artificial intelligence • Previous Articles Next Articles

Path planning of mobile robot based on improved asymptotically-optimal bidirectional rapidly-exploring random tree algorithm

WANG Kun¹, ZENG Guohui¹, LU Dunke¹, HUANG Bo¹, LI Xiaobin²

1. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China;
2. School of Electrical and Electronic Engineering, Shanghai Institute of Technology, Shanghai 200235, China

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

基于改进渐进最优的双向快速扩展随机树的移动机器人路径规划算法

王坤¹, 曾国辉¹, 鲁敦科¹, 黄勃¹, 李晓斌²

1. 上海工程技术大学电子电气工程学院, 上海 201620;
2. 上海应用技术大学电气与电子工程学院, 上海 200235

通讯作者: 王坤
作者简介:王坤(1995-),男,安徽亳州人,硕士研究生,主要研究方向:机器人控制、路径规划算法;曾国辉(1975-),男,江西乐安人,副教授,博士,主要研究方向:机器人控制、电力电子及其控制技术;鲁敦科(1983-),男,湖北咸宁人,讲师,博士,主要研究方向:特种光纤设计、光纤传感;黄勃(1985-),男,湖北武汉人,讲师,博士,主要研究方向:需求工程、软件工程、人工智能;李晓斌(1966-),男,甘肃兰州人,教授,博士,主要研究方向:智能控制与决策。
基金资助:
国家自然科学基金资助项目（61603242）；江西省经济犯罪侦查与防控技术协同创新中心开放课题（JXJZXTCX-030）。

Abstract

Abstract: To overcome the randomness of RRT-Connect and slow convergence of B-RRT^*(asymptotically-optimal Bidirectional Rapidly-exploring Random Tree) in path generation, an efficient path planning algorithm based on B-RRT^*, abbreviated as EB-RRT^*, was proposed. Firstly, an intelligent sampling function was intriduced to achieve more directional expansion of random tree, which could improve the smoothness of path and reduce the seek time. A rapidly-exploring strategy was also added in EB-RRT^* by which RRT-Connect exploration mode was adopted to ensure rapidly expanding in the free space and improved asymptotically-optimal Rapidly-exploring Random Tree (RRT^*) algorithm was adopted to prevent trapped in local optimum in the obstacle space. Finally, EB-RRT^* algorithm was compared with Rapidly-exploring Random Tree (RRT), RRT-Connect, RRT^* and B-RRT^* algorithms. The simulation results show that the improved algorithm is superior to other algorithms in the efficiency and smoothness of path planning. It reduced the path planning time by 68.3% and the number of iterations by 48.6% compared with B-RRT^* algorithm.

Key words: mobile robot, path planning, Rapidly-exploring Random Tree (RRT), RRT-Connect algorithm, asymptotically-optimal Bidirectional Rapidly-exploring Random Tree (B-RRT^*) algorithm

摘要： 针对带启发式的快速扩展随机树（RRT-Connect）算法路径生成的随机性以及渐进最优的双向快速扩展随机树（B-RRT^*）算法收敛速度的缓慢性，提出了一种基于B-RRT^*改进的高效路径规划算法（EB-RRT^*）。首先引入一种智能采样函数，使随机树的扩展更具方向性，从而减少寻路时间，并提高路径的平滑性；其次在B-RRT^*算法的基础上，在EB-RRT^*算法中加入了一种快速扩展策略，使改进后的算法在自由空间中使用RRT-Connect算法的扩展方式进行快速扩展，而在障碍物空间则使用改进的渐进最优的快速扩展随机树（RRT^*）算法进行扩展，在提高扩展效率的同时避免算法陷入局部最优。将EB-RRT^*算法分别与快速扩展随机树（RRT）、RRT-Connect、RRT^*和B-RRT^*算法进行仿真对比，仿真结果表明，改进后的算法在路径规划效率及路径平滑性方面均明显优于其他算法；且相对于B-RRT^*算法，其在路径规划时间上降低了68.3%，在迭代次数上减少了48.6%。

关键词: 移动机器人, 路径规划, 快速扩展随机树, 带启发式的快速扩展随机树算法, 渐进最优的双向快速扩展随机树算法

CLC Number:

TP242.6

WANG Kun, ZENG Guohui, LU Dunke, HUANG Bo, LI Xiaobin. Path planning of mobile robot based on improved asymptotically-optimal bidirectional rapidly-exploring random tree algorithm[J]. Journal of Computer Applications, 2019, 39(5): 1312-1317.

王坤, 曾国辉, 鲁敦科, 黄勃, 李晓斌. 基于改进渐进最优的双向快速扩展随机树的移动机器人路径规划算法[J]. 计算机应用, 2019, 39(5): 1312-1317.

References

[1] DORIGO M, GAMBARELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[2] 韩明,刘教民,吴朔媚,等. 粒子群优化的移动机器人路径规划算法[J]. 计算机应用, 2017, 37(8): 2258-2263.(HAN M, LIU J M, WU S M, et al. Path planning algorithm of mobile robot based on particle swarm optimization[J]. Journal of Computer Applications, 2017, 37(8): 2258-2263.)
[3] OZDIKIA O. Genetic algorithm with random coordinates for route planning on a 3D terrain[C]// Proceedings of the 20115th International Conference on Genetic and Evolutionary Computing. Washington, DC: IEEE Computer Society, 2011: 146-149.
[4] CHEN T B, ZHANG Q. Robot motion planning based on improved artificial potential field[C]// Proceedings of the 20133rd International Conference on Computer Science and Network Technology. Piscataway, NJ: IEEE, 2013: 1208-1211.
[5] LIN M, YUAN K, SHI C, et al. Path planning of mobile robot based on improved A^* algorithm[C]// Proceedings of the 201729th Chinese Control and Decision Conference. Piscataway, NJ: IEEE, 2017: 3570-3576.
[6] KAVRAKI L E, SVESTKA P, LATOMBE J C, et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. IEEE Transactions on Robotics and Automation, 1996, 12(4): 566-580.
[7] LAVALLE S M, KUFFNER J J. Randomized Kinodynamic planning[C]// Proceedings of the 1999 IEEE International Conference on Robotics and Automation. Piscataway, NJ: IEEE, 1999: 473-479.
[8] 宋金泽,戴斌,单恩忠,等. 一种改进的RRT路径规划算法[J]. 电子学报, 2010, 38(Z1): 225-228.(SONG J Z, DAI B, SHAN E Z, et al. An improved RRT path planning algorithm[J]. Acta Electronica Sinica, 2010, 38(Z1): 225-228.)
[9] 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 the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway, NJ: IEEE, 2014: 2997-3004.
[10] DOSHI A A, POSTULA A J, FLETCHER A, et al. Development of micro-UAV with integrated motion planning for open-cut mining surveillance[J]. Microprocessors and Microsystems, 2015, 39(8): 829-835.
[11] KUFFNER J J, LAVALLE S M. RRT-connect: an efficient approach to single-query path planning[C]// Proceedings of the 2000 IEEE International Conference on Robotics and Automation. Piscataway, NJ: IEEE, 2000: 995-1001.
[12] KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.
[13] JORDAN M, PEREZ A. Optimal bidirectional rapidly-exploring random trees[EB/OL].[2018-03-20]. https://dspace.mit.edu/bitstream/handle/1721.1/79884/MIT-CSAIL-TR-2013-021.pdf.
[14] 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.
[15] OLZHAS A, HUSEYIN A V. A novel RRT^*-based algorithm for motion planning in dynamic environments[C]// Proceedings of the 2017 IEEE International Conference on Mechatronics and Automation. Piscataway, NJ: IEEE, 2017: 1416-1421.
[16] 康亮,赵春霞,郭剑辉. 基于模糊滚动RRT算法的移动机器人路径规划[J]. 南京理工大学学报(自然科学版), 2010, 34(5): 642-648. (KANG L, ZHAO C X, GUO J H. Path planning based on fuzzy rolling rapidly-exploring random tree for mobile robot[J]. Journal of Nanjing University of Science and Technology (Natural Science), 2010, 34(5): 642-648.
[17] 冯楠. 自主移动机器人路径规划的RRT算法研究[D]. 大连: 大连理工大学, 2014. (FENG N. Research on RRT algorithm of path planning for autonomous mobile robot[D]. Dalian: Dalian University of Technology, 2014.
[18] 潘思宇,徐向荣. 基于改进RRT^*的移动机器人运动规划算法[J]. 山西大学学报(自然科学版), 2017, 40(2): 244-254.(PAN S Y, XU X R. Improved RRT^*-based motion planning algorithm for mobile robot[J]. Journal of Shanxi University (Natural Science Edition), 2017, 40(2): 224-254.)
[19] ZAID T, AHMED H Q, YASAR A, et al. Potentially guided bidirectionalized RRT^* for fast optimal path planning in cluttered environments[J]. Robotics and Autonomous Systems, 2018, 108: 13-27.
[20] NOREEN I, KHAN A, HABIB Z. Optimal path planning using RRT^* based approaches: a survey and future directions[J]. International Journal of Advanced Computer Science & Application, 2016, 7(11): 97-107.
[21] IRAM N, AMNA K, HYEJEONG R, et al. Optimal path planning in cluttered environment using RRT^*-AB[J]. Intelligent Service Robotics, 2017, 11(1): 41-52.

Path planning of mobile robot based on improved asymptotically-optimal bidirectional rapidly-exploring random tree algorithm

基于改进渐进最优的双向快速扩展随机树的移动机器人路径规划算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	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.
[2]	LU Guoqing, SUN Hao. Two-dimensional mapping of swarm robot based on random walk [J]. Journal of Computer Applications, 2021, 41(7): 2121-2127.
[3]	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.
[4]	LUAN Jianing, ZHANG Wei, SUN Wei, ZHANG Ao, HAN Dong. High-accuracy localization algorithm based on fusion of two-dimensional code vision and laser lidar [J]. Journal of Computer Applications, 2021, 41(5): 1484-1491.
[5]	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.
[6]	WEI Bo, YANG Rong, SHU Sihao, WAN Yong, MIAO Jianguo. Path planning of mobile robots based on ion motion-artificial bee colony algorithm [J]. Journal of Computer Applications, 2021, 41(2): 379-383.
[7]	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.
[8]	WANG Jialiang, LI Shuhua, ZHANG Haitao. Obstacle avoidance path planning algorithm of quad-rotor helicopter based on Bayesian estimation and region division traversal [J]. Journal of Computer Applications, 2021, 41(2): 384-389.
[9]	LI Wei, JIN Shijun. Optimal path convergence method based on artificial potential field method and informed sampling [J]. Journal of Computer Applications, 2021, 41(10): 2912-2918.
[10]	LIU Sijia, TONG Xiangrong. Urban transportation path planning based on reinforcement learning [J]. Journal of Computer Applications, 2021, 41(1): 185-190.
[11]	XU Xiaoqiang, QIN Pinle, ZENG Jianchao. Orthodontic path planning based on improved particle swarm optimization algorithm [J]. Journal of Computer Applications, 2020, 40(7): 1938-1943.
[12]	XIONG Yong, ZHANG Jia, YU Jiajun, ZHANG Benren, LIANG Xuanzhuo, ZHU Qige. Intelligent layout optimization algorithm for 3D pipelines of ships [J]. Journal of Computer Applications, 2020, 40(7): 2164-2170.
[13]	QI Xuanxuan, HUANG Jiajun, CAO Jian'an. Path planning for unmanned vehicle based on improved A^* algorithm [J]. Journal of Computer Applications, 2020, 40(7): 2021-2027.
[14]	HAN Yulao, FANG Dingyi. Multi-objective path planning algorithm for mobile charging devices jointing wireless charging and data collection [J]. Journal of Computer Applications, 2020, 40(6): 1745-1750.
[15]	XU Xiaoqiang, WANG Mingyong, MAO Yan. Path planning of mobile robot based on improved artificial potential field method [J]. Journal of Computer Applications, 2020, 40(12): 3508-3512.