基于改进双向RRT算法的机器人路径规划

doi:10.3976/j.issn.1002-4026.2021.03.015

山东科学 ›› 2021, Vol. 34 ›› Issue (3): 109-118.doi: 10.3976/j.issn.1002-4026.2021.03.015

基于改进双向RRT算法的机器人路径规划

韩丰键^a，邱书波^b，李庆华^b*，刘海英^a

齐鲁工业大学（山东省科学院）a. 电气工程与自动化学院；b. 电子信息工程学院（大学物理教学部），山东济南 250353

收稿日期:2020-11-09 出版日期:2021-06-20 发布日期:2021-06-07
通信作者: 李庆华，研究方向为机器学习，机器视觉。Tel：18663760168, E-mail: lqh@qlu.edu.cn
作者简介:韩丰键（1996—），男，硕士，研究方向为移动机器人路径规划。E-mail:1194475536@qq.com
基金资助:
国家自然科学基金（61701270）；齐鲁工业大学（山东省科学院）青年博士合作基金（2017BSHZ008）

Path planning of robot based on improved BI-RRT algorithm

HAN Feng-jian^a, QIU Shu-bo^b, LI Qing-hua^b*, LIU Hai-ying^a

a. School of Electrical Engineering and Automation; b. School of Electronic and Information Engineering(Department of Physics),Qilu University of Technology (Shandong Academyof Sciences), Jinan 250353, China

Received:2020-11-09 Online:2021-06-20 Published:2021-06-07

摘要/Abstract

摘要： 针对双向快速搜索随机树（BI-RRT）算法在路径规划中存在目标导向性差、收敛速度慢、路径拐点多的问题，提出了一种改进BI-RRT算法。通过目标导向引导随机树更快朝向目标点生长，提高收敛速度。引入贪婪路径优化策略，有效减少路径拐点，提高了路径规划算法的效率。同时提出了一种圆盘碰撞检测的算法，并在多个场景中用Matlab平台进行了圆盘移动机器人的路径规划仿真实验，实验结果验证了所提出算法的可行性和有效性。

关键词: 路径规划, 双向RRT算法, 贪婪算法, 收敛速度

Abstract: Aiming at the problems of BI-RRT algorithm in path planning, such as poor target orientation, slow convergence speed, and numerous inflection points, an improved BI-RRT algorithm is proposed in this paper. The random tree is guided to grow faster toward the target point through target orientation to accelerate the convergence speed. In addition, the introduction of greedy path optimization strategy effectively reduces the path inflection points and improves the efficiency of path planning algorithm. Furthermore, a disk collision detection algorithm is also proposed. Path planning simulation experiments on a disk mobile robot is performed in several scenarios using Matlab. The feasibility and effectiveness of the proposed algorithm are verified via experimental results.

Key words: path planning, BI-RRT algorithm, greedy algorithm, convergence speed

中图分类号:

TN96

韩丰键, 邱书波, 李庆华, 刘海英. 基于改进双向RRT算法的机器人路径规划[J]. 山东科学, 2021, 34(3): 109-118.

HAN Feng-jian, QIU Shu-bo, LI Qing-hua, LIU Hai-ying. Path planning of robot based on improved BI-RRT algorithm[J]. Shandong Science, 2021, 34(3): 109-118.

参考文献 17

1	HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107. doi: 10.1109/TSSC.1968.300136
2	朱颢东, 孙振, 吴迪, 等. 基于改进蚁群算法的移动机器人路径规划[J]. 重庆邮电大学学报（自然科学版）, 2016, 28（6）: 849-855. doi: 10.3979/j.issn.1673-825X.2016.06.017
3	唐志荣, 冀杰, 吴明阳, 等. 基于改进人工势场法的车辆路径规划与跟踪[J]. 西南大学学报（自然科学版）, 2018, 40（6）: 174-182. doi: 10.13718/j.cnki.xdzk.2018.06.025
4	王勇臻, 陈燕, 于莹莹. 求解多旅行商问题的改进分组遗传算法[J]. 电子与信息学报, 2017, 39（1）: 198-205. doi: 10.11999/JEIT160211
5	陈艳, 禹继国. 基于概率路线图的动态环境下移动机器人路径规划的神经网络方法[J]. 曲阜师范大学学报（自然科学版）, 2019, 45（4）: 38-42. doi: 10.3969/j.issn.1001-5337.2019.4.038
6	谭建豪, 肖友伦, 刘力铭, 等. 改进PRM算法的无人机航迹规划[J]. 传感器与微系统, 2020,39（1）: 38-41. doi: 10.13873/J.1000-9787(2020)01-0038-04
7	KAVRAKI L E, SVESTKA P, LATOMBE J C, et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces[C]//IEEE Transactions on Robotics and Automation. IEEE,1996: 566-580. doi: 10.1109/70.508439
8	HUA D, GRANICHIN O N, ZHANG X P, et al. 3D motion planning for flexible needle insertion based on rapidly-exploring random trees with environment-adaptive sampling and central angle control[J]. Journal of Medical Imaging and Health Informatics, 2019, 9（7）: 1524-1533. doi: 10.1166/jmihi.2019.2754
9	LAVALLE S M, KUFFNER J J. Randomized kinodynamic planning[EB/OL]. [2020-10-12]. https://doi.org/10.1177/02783640122067453.
10	KUFFNER J J, LAVALLE S M. RRT-connect: An efficient approach to single-query path planning[C]// IEEE International Conference on Robotics and Automation. San Francisco, USA: IEEE, 2000:995-1001. doi: 10.1109/ROBOT.2000.844730
11	URMSON C, SIMMONS R. Approaches for heuristically biasing RRT growth[C]//Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems. Las Vegas, USA: IEEE, 2003: 1178-1183. doi: 10.1109/IROS.2003.1248805
12	RODRIGUEZ S, TANG X Y, LIEN J M, et al. An obstacle-based rapidly-exploring random tree[C]//Proceedings 2006 IEEE International Conference on Robotics and Automation. Orlando, USA: IEEE, 2006: 895-900. doi: 10.1109/ROBOT.2006.1641823
13	GUO Y N, CHENG J, LUO S, et al. Robust dynamic multi-objective vehicle routing optimization method[C]//IEEE/ACM Transactions on Computational Biology and Bioinformatics. IEEE, 2017: 1891-1903. doi: 10.1109/TCBB.2017.2685320
14	POHL I. Bi-directional and heuristic search in path problems[R]. USA:Department of Energy Office of Scientific and Technical Information (OSTI), 1969. doi: 10.2172/4785039
15	AKGUN B, STILMAN M. Sampling heuristics for optimal motion planning in high dimensions[C]//2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. San Francisco, USA:IEEE,2011: 2640-2645. doi: 10.1109/IROS.2011.6095077
16	张顺, 谢习华, 陈定平. 基于改进RRT-Connect的无人机航迹规划算法[J]. 传感器与微系统, 2020, 39（12）: 146-148. doi: 10.13873/J.1000-9787(2020)12-0146-03
17	BRENT R P. Fast multiple-precision evaluation of elementary functions[J]. Journal of the ACM, 1976, 23(2):242-251. doi: 10.1145/321941.321944

[1]	秦剑, 张飞凯, 刘晨, 夏拥军. 山区公路与货运索道联合路径规划方法[J]. 山东科学, 2023, 36(3): 90-99.
[2]	范贤,徐小明,钱程. 动车运用所调车作业计划优化[J]. 山东科学, 2022, 35(2): 96-105.
[3]	李苏琪,朱孔金. 基于自动导引车辆的物流分拣系统交通控制策略[J]. 山东科学, 2022, 35(1): 73-80.
[4]	陈瑶，陈阿莲，李向东，陈伟. 变电站智能巡检机器人全局路径规划设计[J]. 山东科学, 2015, 28(1): 114-119.

基于改进双向RRT算法的机器人路径规划

Path planning of robot based on improved BI-RRT algorithm

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 17

相关文章 4

Metrics

本文评价

推荐阅读 0