计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (6A): 220500038-7.doi: 10.11896/jsjkx.220500038

• 人工智能 • 上一篇    下一篇

基于改进B-RRT*算法的移动机器人路径规划

喻九阳, 张德安, 戴耀南, 胡天豪, 夏文凤   

  1. 武汉工程大学机电工程学院湖北省绿色化工装备工程技术研究中心 武汉 430205
  • 出版日期:2023-06-10 发布日期:2023-06-12
  • 通讯作者: 戴耀南(dyn1121758919@163.com)
  • 作者简介:(1216137495@qq.com)
  • 基金资助:
    湖北省重点研发计划项目(2020BAB030)

Path Planning of Mobile Robot Based on Improved B-RRT* Algorithm

YU Jiuyang, ZHANG Dean, DAI Yaonan, HU Tianhao, XIA Wenfeng   

  1. Hubei Green Chemical Equipment Engineering Technology Research Center,School of Mechanical and Electrical Engineering,Wuhan Institute of Technology,Wuhan 430205,China
  • Online:2023-06-10 Published:2023-06-12
  • About author:YU Jiuyang,born in 1963,master,se-cond-level professor,doctoral supervisor.His main research interests include chemical machinery process equipment control,oil and gas chemical pipeline robots. DAI Yaonan,born in 1993,Ph.D,lecturer.His main research interests include chemical pipeline robot motion control and mobile robot image recognition.
  • Supported by:
    Key R&D Program of Hubei Province,China(2020BAB030).

PDF (PC)

556

摘要： 在移动机器人运动路径规划领域,渐近最优双向快速探索随机树(B-RRT*)算法虽然具有良好的避障和路径搜索能力,但是存在迭代次数多、规划时间长的缺点。基于运动学约束的双向快速探索随机树(KB-RRT)算法作为B-RRT*算法的高效分支,虽然有效减少了无效树的扩展,加快了寻找最优路径的速度,但迭代次数过大。针对B-RRT*算法的最新改进算法是具有高效分支的运动学约束B-RRT*(KB-RRT*)算法,KB-RRT*算法虽然可以有效减少无效树的扩展,加快寻找最优路径的速度,但其迭代次数仍然过大。因此,提出了一种基于自适应采样和快速搜索的改进B-RRT*算法(AFB-RRT*)。该算法设定障碍物的安全区域,根据提出的自适应采样和快速搜索确定随机树的搜索方向,减少冗余采样点,即AFB-RRT*在路径规划中可以实现快速收敛。仿真和实验表明,与KB-RRT*相比,AFB-RRT*在规划路径长度基本相同的前提下,减少了规划时间和收敛迭代次数。

关键词: B-RRT*, KB-RRT*, AFB-RRT*, 收敛迭代, 规划时间

Abstract: In the field of mobile robot motion path planning,the asymptotically optimal bidirectional rapid exploration random tree(B-RRT*) algorithm has good obstacle avoidance and path search capabilities,but B-RRT* has the shortcomings of many iterations and long planning time.As an efficient branch of the B-RRT* algorithm,the kinematic constraint-based bidirectional rapid exploration random tree(KB-RRT) algorithm can effectively reduce the expansion of invalid trees and speed up the search for the optimal path,but the number of iterations of the algorithm is too large.For the improvement of the B-RRT* algorithm,the latest B-RRT* improved algorithm is the kinematically constrained B-RRT*(KB-RRT*) algorithm with efficient branches.Although the KB-RRT* algorithm can effectively reduce the expansion of invalid trees,to speed up the search for the optimal path,but the number of iterations of the algorithm is still too large.Therefore,this paper proposes an improved B-RRT* algorithm(AFB-RRT*) based on adaptive sampling and fast search,which sets a safe area for obstacles and determines the search direction of a random tree according to the proposed adaptive sampling and fast search,reduces redundant sampling points,that is,AFB-RRT* can achieve fast convergence in path planning.Simulation and experiments show that,compared with KB-RRT*,AFB-RRT* reduces the planning time and the number of convergence iterations under the premise that the planned path length is basically the same.

Key words: B-RRT*, KB-RRT*, AFB-RRT*, Convergence iterations, Planning time

中图分类号: 

  • TP242
[1]LIU Y J,YU M J,YE P,et al.A review of path planning me-thods for self-reconfigurable modular robots[J].Science in China:Information Science,2018,48(2):143-176.
[2]DONG Y,CAMCI E,KAYACAN E.Faster RRT-based non-holonomic path planning in 2D building environments using skeleton-constrained path biasing[J].Journal of Intelligent & Robotic Systems,2018,89(3):387-401.
[3]MU X,LIU Y,GUO L,et al.Intelligent reflecting surface enhanced indoor robot path planning:A radio map-based approach[J].IEEE Transactions on Wireless Communications,2021,20(7):4732-4747.
[4]DAS P K,JENA P K.Multi-robot path planning using improved particle swarm optimization algorithm through novel evolutiona-ry operators[J].Applied Soft Computing,2020,92:106312.
[5]VOTION J,CAO Y.Diversity-based cooperative multivehiclepath planning for risk management in costmap environments[J].IEEE Transactions on Industrial Electronics,2018,66(8):6117-6127.
[6]ZHANG Z,LU R,ZHAO M,et al.Robot path planning based on genetic algorithm with hybrid initialization method[J].Journal of Intelligent & Fuzzy Systems,2022,42(3):2041-2056.
[7]YI G,FENG Z,MEI T,et al.Multi-AGVs path planning basedon improved ant colony algorithm[J].The Journal of Supercomputing,2019,75(9):5898-5913.
[8]DAS P K,BEHERA H S,PANIGRAHI B K.A hybridization of an improved particle swarm optimization and gravitational search algorithm for multi-robot path planning[J].Swarm and Evolutionary Computation,2016,28:14-28.
[9]WANG X,CHEN W,ZHAO J.The evolution of cooperationwith in the multigame environment based on the particle swarm optimization algorithm[J].Physics Letters A,2020,384(7):126165.
[10]DEWANGAN R K,SHUKLA A,GODFREY W W.A solution for priority-based multi-robot path planning problem with obstacles using ant lion optimization[J].Modern Physics Letters B,2020,34(13):2050137.
[11]HU B,CAO Z,ZHOU M C.An efficient RRT-based framework for planning short and smooth wheeled robot motion under kinodynamic constraints[J].IEEE Transactions on Industrial Electronics,2020,68(4):3292-3302.
[12]LAVALLE S M,KUFFNER JRJ J.Randomized kinodynamic planning[J].The International Journal of Robotics Research,2001,20(5):378-400.
[13]KARAMAN S,FRAZZOLI E.Sampling-based algorithms foroptimal motion planning[J].The International Journal of Robotics Research,2011,30(7):846-894.
[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]QI J,YANG H,SUN H.MOD-RRT*:A sampling-based algorithm for robot path planning in dynamic environment[J].IEEE Transactions on Industrial Electronics,2020,68(8):7244-7251.
[16]JEONG I B,LEE S J,KIM J H.Quick-RRT*:Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate[J].Expert Systems with Applications,2019,123:82-90.
[17]LI Y,WEI W,GAO Y,et al.PQ-RRT*:An improved path planning algorithm for mobile robots[J].Expert systems with applications,2020,152:113425.
[18]MOON C,CHUNG W.Kinodynamic planner dual-tree RRT(DT-RRT) for two-wheeled mobile robots using the rapidly exploring random tree[J].IEEE Transactions on Industrial Electronics,2014,62(2):1080-1090.
[19]TAHIR Z,QURESHI A H,AYAZ Y,et al.Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments[J].Robotics and Autonomous Systems,2018,108:13-27.
[20]WU X,XU L,ZHEN R,et al.Biased sampling potentiallyguided intelligent bidirectional RRT* algorithm for UAV path planning in 3D environment[J].Mathematical Problems in Engineering,2019,2019.
[21]SHOME R,SOLOVEY K,DOBSONA,et al.dRRT*:Scalable and informed asymptotically-optimal multi-robot motion planning[J].Autonomous Robots,2020,44(3):443-467.
[22]WANG J,LI B,MENGM Q H.Kinematic Constrained Bi-directional RRT with Efficient Branch Pruning for robot path planning[J].Expert Systems with Applications,2021,170:114541.
[23]SUN Y,ZHANG C,LIU C.Collision-free and dynamically feasible trajectory planning for omnidirectional mobile robots using a novel B-spline based rapidly exploring random tree[J].International Journal of Advanced Robotic Systems,2021,18(3):17298814211016609.
[24]WANG J,LU Y,YE L,et al.Efficient analysis-suitable T-spline fitting for freeform surface reconstruction and intelligent sampling[J].Precision Engineering,2020,66:417-428.
[25]DELGADO R,YOU B J,HAN M,et al.Integration of ROS and RT tasks using message pipe mechanism on Xenomai for telepresence robot[J].Electronics Letters,2019,55(3):127-128.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发