基于冗余节点过滤机制的IBRRT*机械臂路径规划

doi:10.3778/j.issn.1002-8331.2204-0038

摘要/Abstract

摘要： 针对传统的RRT*和双向RRT*规划算法在复杂环境存在下规划效率低、探索时间长、规划路径曲折等问题，提出了一种基于冗余节点过滤机制的IBRRT*机械臂路径规划算法。在IBRRT*规划算法基础上，引入局部节点替代机制避免节点的冗余拓展，当首次探索到起始点到目标点的初始路径，将椭圆状态子集采样算法引入后续的迭代中，对采样区域施加约束，避免冗余节点生成。最后针对迭代过程中对路径优化没有贡献的边缘冗余节点进行逐轮剔除。二维仿真实验结果表明，提出的算法收敛速度快效率高，相比IBRRT*算法在时间上减少50%左右，节点个数减少75%以上，并且通过机械臂路径规划实验证明了算法的有效性和实用性。

关键词: 路径规划, IBRRT*, 初始路径, 局部节点替代, 椭圆状态子集采样算法

Abstract: Aiming at the problems of low planning efficiency, long exploration time and zigzag planning path of traditional RRT* and bidirectional RRT* planning algorithms in complex environment, a path planning algorithm of IBRRT* manipulator based on redundant node filtering mechanism is proposed. Firstly, based on the IBRRT* programming algorithm, a local node substitution mechanism is introduced to avoid the redundant expansion of nodes. When the initial path from the initial point to the target point is explored for the first time, the elliptic state subset sampling algorithm is introduced into the subsequent iterations to exert constraints on the sampling area and avoid the generation of redundant nodes. Finally, the redundant edge nodes which donot contribute to the path optimization are eliminated round by round. Two-dimensional simulation results show that the proposed algorithm has fast convergence speed and high efficiency. Compared with IBRRT* algorithm, the proposed algorithm can reduce the time by about 50% and the number of nodes by more than 75%. Moreover, the effectiveness and practicability of the proposed algorithm are proved by the manipulator path planning experiment.

Key words: path planning, improved bidirectional RRT*（IBRRT*）, initial path, local node substitution, elliptic state subset sampling algorithm

杨宏韬, 孟德旭, 李秀兰, 于微波, 熊凤銮, 李浩. 基于冗余节点过滤机制的IBRRT*机械臂路径规划[J]. 计算机工程与应用, 2023, 59(13): 298-304.

YANG Hongtao, MENG Dexu, LI Xiulan, YU Weibo, XIONG Fengluan, LI Hao. Path Planning of IBRRT* Manipulator Based on Redundant Node Filtering Mechanism[J]. Computer Engineering and Applications, 2023, 59(13): 298-304.

参考文献

[1] 潘豹，王耀南，崔昊韵.基于改进RRT*FN算法的机器人路径规划[J].控制与决策，2021，36（8）：1834-1840.
PAN B，WANG Y N，CUI H Y.Robot path planning based on improved RRT*FN algorithm[J].Control and Decision，2021，36（8）：1834-1840.
[2] 代伟，李创业，杨春雨，等.基于低差异序列与快速扩展随机树融合算法的机械臂路径规划[J].控制理论与应用，2022，39（1）：130-144.
DAI W，LI C Y，YANG C Y，et al.Manipulator path planning using fusion algorithm of low difference sequence and rapidly exploring random tree[J].Control Theory & Applications，2022，39（1）：130-144.
[3] 李耀仲，王书亭，蒋立泉，等.基于稀疏节点快速扩展随机树的移动机械臂运动规划[J].中国机械工程，2021，32（12）：1462-1470.
LI Y Z，WANG S T，JIANG L Q，et al，Motion planning of mobile manipulators based on RRT with sparse nodes[J].China Mechanical Engineering，2021，32（12）：1462-1470.
[4] LAVALLE S M.Rapidly-exploring random trees：a new tool for path planning[R].Research Report，1999.
[5] HARA Y，TOMONO M.Moving object removal andsurfacesmesh mapping for path planning on 3D terrain[J].Advanced Robotics，2020，34（2）：1-13.
[6] FU B，CHEN L，ZHOU Y T，et al.An improved A* algorithm for the industrial robot path planning with high success rate and short length[J].Robotics & Autonomous Systems，2018，106：26-37.
[7] ALGFOOR Z A，SUNAR M S，ABDULLAH A.A new weighted pathfinding algorithms to reduce the search time on grid maps[J].Expert Systems with Applications，2017，71：319-331.
[8] 陈满意，张桥，张弓，等.多障碍环境下机械臂避障路径规划[J].计算机集成制造系统，2021，27（4）：990-998.
CHEN M Y，ZHANG Q，ZHANG G，et al.Obstace avoidance pathplanning of manipulator in multiple obstaclesenvironment[J].Computer Integrated Manufacturing Systems，2021，27（4）：990-998.
[9] LI B H，BADONG C，CHEN B D.An adaptive rapidly-exploring random tree[J].IEEE-CAA Journal of Automatica Sinica，2022，32（3）：283-294.
[10] AN B，KIM J，PARK F C.An adaptive stepsize RRT planning algorithm for open-chain robots[J].IEEE Robotics and Automation Letters，2018，3（1）：312-319.
[11] KUFFNER J J，LAVALLE S M.RRT-connect：an efficient approach to single- query path planning[C]//Proceedings of the IEEE International Conference on Robotics and Automation，2000：995-1001.
[12] JORDAN M，PEREZ A.Optimal bidirec tional rapidly-exploring random trees[R].Cambridge：Computer Science and Artificial Intelligence Laboratory，Massachusetts Institute of Technology，2013.
[13] 刘奥博，袁杰.目标偏置双向RRT*算法的机器人路径规划[J].计算机工程与应用，2022，58（6）：234-240.
LIU A B，YUAN J.Robot path planning based on goal biased bidirectional RRT* algorithm[J].Computer Engineering and Applications，2022，58（6）：234-240.
[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] WANG X Y.Bidirectional potential guided RRT* for motion planning[J].IEEE Access，2019，7（15）：2169-3536.
[16] QURESHI A H，AYAZ Y.Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments[J].Robotics & Autonomous Systems，2015，68：1-11.
[17] 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 IEEE/RSJ International Conference on Intelligent Robots and Systems，2014：2997-3004.