目标偏置双向RRT*算法的机器人路径规划

doi:10.3778/j.issn.1002-8331.2009-0439

摘要/Abstract

摘要： 针对RRT*和B-RRT*算法在较复杂环境下路径规划时，存在搜索时间长、采样效率低和规划路径曲折的问题，提出一种目标偏置双向快速扩展随机树算法——GBB-RRT*（goal biased bidirectional RRT*）。该算法每次迭代中两棵随机树都进行扩展，一次迭代能生成两个新节点，加快扩展速度。然后引入目标偏置策略来优化采样点的选取，使两棵随机树在一定概率下朝各自的目标点方向扩展。针对得到的规划路径，设计一种逆向寻优结合转角约束路径简化方法，结合B样条曲线生成光滑可执行路径。在仿真实验中将提出的算法与B-RRT*进行对比实验，结果表明所提算法搜索时间缩短40%左右、扩展节点减少10%左右，结合路径简化方法后路径长度缩短3%左右。

关键词: 路径规划, 目标偏置, RRT*算法, 双向搜索, 路径简化, B样条曲线

Abstract: In order to solve the problems of long search time, low sampling efficiency and tortuous path planning of RRT* and B-RRT* algorithms in complex environment, a goal biased bidirectional rapidly-exploring random tree algorithm GBB-RRT*（goal biased bidirectional RRT*） is proposed. In each iteration, two random trees are expanded, and two new nodes can be generated in one iteration to speed up the expansion. Then, the goal bias strategy is introduced to optimize the selection of sampling points, so that the two random trees expand towards their respective goal points under a certain probability. According to the obtained planning path, a reverse optimization method combined with corner constraint path simplification is designed, and the smooth executable path is generated by combining with B-spline curve. In the simulation experiment, the algorithm is compared with B-RRT*. The results show that the search time of the proposed algorithm is reduced by about 40%, the expansion node is reduced by about 10%, and the path length is reduced by about 3% combined with the path simplification method.

Key words: path planning, goal bias, RRT* algorithm, bidirectional search, path simplification, B-spline curve

刘奥博, 袁杰. 目标偏置双向RRT*算法的机器人路径规划[J]. 计算机工程与应用, 2022, 58(6): 234-240.

LIU Aobo, YUAN Jie. Robot Path Planning Based on Goal Biased Bidirectional RRT* Algorithm[J]. Computer Engineering and Applications, 2022, 58(6): 234-240.

参考文献

[1] LAVALLE S.Rapidly-exploring random trees：a new tool for path planning[R].Iowa State University，1998.
[2] KUFFNER J J，LAVALLE S M.RRT-connect：an efficient approach to single-query path planning[C]//2002 IEEE International Conference on Robotics and Automation，2002：995-1001.
[3] 李成雷，贺继林，邓宇，等.基于改进RRT-connect的四旋翼无人机避障轨迹规划算法[J].传感器与微系统，2019，38（5）：136-139.
LI C L，HE J L，DENG Y，et al.Obstacle-free trajectory planning algorithm for quadrotor UAV based on improved RRT-connect[J].Transducer and Microsystem Technologies，2019，38（5）：136-139.
[4] KARAMAN S，FRAZZOLI E.Sampling-based algorithms for optimal motion planning[J].The International Journal of Robotics Research，2011，30（7）：846-894.
[5] JORDAN M，PEREZ A.Optimal bidirectional rapidly-exploring random trees，MIT-CSAIL-TR-2013-021[R].Csail MIT，2013.
[6] 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.
[7] LAVALLE S M，KUFFNER J J.Randomized kinodynamic planning[J].The International Journal of Robotics Research，2001，20（5）：378-400.
[8] 阮晓钢，周静，张晶晶，等.基于子目标搜索的机器人目标导向RRT路径规划算法[J].控制与决策，2020，35（10）：2543-2548.
RUAN X G，ZHOU J，ZHANG J J，et al.Robot goal guide RRT path planning based on sub-target search[J].Control and Decision，2020，35（10）：2543-2548.
[9] WU X J，XU L，ZHEN R，et al.Biased sampling potentially guided intelligent bidirectional RRT* algorithm for UAV path planning in 3D environment[J].Mathematical Problems in Engineering，2019.
[10] 杜明博，梅涛，陈佳佳，等.复杂环境下基于RRT的智能车辆运动规划算法[J].机器人，2015，37（4）：443-450.
DU M B，MEI T，CHEN J J，et al.RRT-based motion planning algorithm for intelligent vehicle in complex environments[J].Robot，2015，37（4）：443-450.
[11] ZHENG K Y，LIU S.RRT based path planning for autonomous parking of vehicle[C]//2018 IEEE 7th Data Driven Control and Learning Systems Conference（DDCLS），2018：627-632.
[12] NASIR J，ISLAM F，MALIK U，et al.RRT*-smart：a rapid convergence implementation of RRT*[J].International Journal of Advanced Robotic Systems，2013，10（4）.
[13] LIU H Y，ZHANG X B，WEN J，et al.Goal-biased bidirectional RRT based on curve-smoothing[J].IFAC-Papers-
OnLine，2019，52（24）：255-260.
[14] 刘建宇，范平清.基于改进的RRT*-connect算法机械臂路径规划[J].计算机工程与应用，2021，57（6）：274-278.
LIU J Y，FAN P Q.Path planning of manipulator based on improved RRT*-connect algorithm[J].Computer Engineering and Applications，2021，57（6）：274-278.
[15] 陈敏，李笑，武交峰.基于改进RRT算法的差动机器人路径规划[J].计算机应用与软件，2019，36（9）：276-280.
CHEN M，LI X，WU J F.Path planning of differential drive robot based on improved RRT algorithm[J].Computer Application and Software，2019，36（9）：276-280.
[16] 董敏，陈铁桩，杨浩.基于改进RRT算法的无人车路径规划仿真研究[J].计算机仿真，2019，36（11）：96-100.
DONG M，CHEN T Z，YANG H.Simulation research on unmanned vehicle path planning based on improved RRT algorithm[J].Computer Simulation，2019，36（11）：96-100.
[17] 刘成菊，韩俊强，安康.基于改进RRT算法的RoboCup机器人动态路径规划[J].机器人，2017，39（1）：8-15.
LIU C J，HAN J Q，AN K.Dynamic path planning based on an improved RRT algorithm for RoboCup robot[J].Robot，2017，39（1）：8-15.
[18] 刘华伟，张帅，赵搏欣，等.改进RRT算法陷阱空间下的无人机航迹规划[J].计算机工程与应用，2018，54（8）：119-122.
LIU H W，ZHANG S，ZHAO X，UAV path planning based on algorithm in trap space[J].Computer and Applications，2018，54（8）：119-122