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

doi:10.3976/j.issn.1002-4026.2021.03.015

Abstract

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

CLC Number:

TN96

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.

References 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]	QIN Jian, ZHANG Feikai, LIU Chen, XIA Yongjun. Path planning for material transportation by combining mountain road and freight ropeway [J]. Shandong Science, 2023, 36(3): 90-99.
[2]	LI Su-qi,ZHU Kong-jin. Traffic control for AGV-based logistics sorting system [J]. Shandong Science, 2022, 35(1): 73-80.
[3]	CHEN Yao, CHEN Alian, LI Xiangdong, CHEN Wei. Globalpath planning design of transformer substation intelligent inspection robot [J]. SHANDONG SCIENCE, 2015, 28(1): 114-119.

Path planning of robot based on improved BI-RRT algorithm

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References 17

Related Articles 3

Metrics

Comments

Recommended 0