1、Computer Engineering and Applications计算机工程与应用2023，59（13）随着机械臂的应用普及，机械臂路径规划问题至关重要1。机械臂路径规划问题可以定义为机械臂依据某些优化准则在工作空间内搜索到一条从起始状态到目标状态的无碰撞路径的过程2。传统路径规划算法仅在低维空间具有一定的优势，但是针对于机械臂高维空间下，传统路径规划算法的复杂性将会大幅度增加，而基于采样的路径规划算法在高维空间下同样适用3。相比于A*算法、遗传算法、蚁群算法等传统路径规划算法，基于采样的路径规划算法不需要明确障碍物在状态空间的具体位置，以节点连接的方式构建路径并进行碰撞检测4-6。近
2、年来，国内外学者针对机械臂路径规划问题进行了大量研究，其中RRT算法应用较为广泛，但RRT算法存在规划时间长，节点个数多等问题，在实际应用中具有一定局限性7-10。Kuffner等11提出RRT-connect算法，通过采用随机树双向搜索，提高了算法搜索效率，但存基于冗余节点过滤机制的IBRRT*机械臂路径规划杨宏韬，孟德旭，李秀兰，于微波，熊凤銮，李浩长春工业大学 电气与电子工程学院，长春 130012摘要：针对传统的RRT*和双向RRT*规划算法在复杂环境存在下规划效率低、探索时间长、规划路径曲折等问题，提出了一种基于冗余节点过滤机制的IBRRT*机械臂路径规划算法。在IBRRT*规划算法
3、基础上，引入局部节点替代机制避免节点的冗余拓展，当首次探索到起始点到目标点的初始路径，将椭圆状态子集采样算法引入后续的迭代中，对采样区域施加约束，避免冗余节点生成。最后针对迭代过程中对路径优化没有贡献的边缘冗余节点进行逐轮剔除。二维仿真实验结果表明，提出的算法收敛速度快效率高，相比IBRRT*算法在时间上减少50%左右，节点个数减少75%以上，并且通过机械臂路径规划实验证明了算法的有效性和实用性。关键词：路径规划；IBRRT*；初始路径；局部节点替代；椭圆状态子集采样算法文献标志码：A中图分类号：TP241doi：10.3778/j.issn.1002-8331.2204-0038Path P
4、lanning of IBRRT*Manipulator Based on Redundant Node Filtering MechanismYANG Hongtao,MENG Dexu,LI Xiulan,YU Weibo,XIONG Fengluan,LI HaoSchool of Electrical and Electronic Engineering,Changchun University of Technology,Changchun 130012,ChinaAbstract：Aiming at the problems of low planning efficiency,l
5、ong exploration time and zigzag planning path of traditionalRRT*and bidirectional RRT*planning algorithms in complex environment,a path planning algorithm of IBRRT*manip-ulator based on redundant node filtering mechanism is proposed.Firstly,based on the IBRRT*programming algorithm,alocal node substi
6、tution mechanism is introduced to avoid the redundant expansion of nodes.When the initial path from theinitial point to the target point is explored for the first time,the elliptic state subset sampling algorithm is introduced intothe subsequent iterations to exert constraints on the sampling area a
7、nd avoid the generation of redundant nodes.Finally,the redundant edge nodes which donot contribute to the path optimization are eliminated round by round.Two-dimensionalsimulation results show that the proposed algorithm has fast convergence speed and high efficiency.Compared withIBRRT*algorithm,the
8、 proposed algorithm can reduce the time by about 50%and the number of nodes by more than75%.Moreover,the effectiveness and practicability of the proposed algorithm are proved by the manipulator path plan-ning experiment.Key words：path planning;improved bidirectional RRT*（IBRRT*）;initial path;local n
9、ode substitution;elliptic statesubset sampling algorithm基金项目：国家自然科学基金（62106023）；吉林省教育厅科学技术研究项目（JJKH20210744KJ）；吉林省科技发展计划项目（20190303099SF，20200401118GX）。作者简介：杨宏韬（1982），男，博士，副教授，研究方向为光电测量与信息融合；李秀兰，通信作者，女，硕士，研究方向为光电测量，E-mail：。收稿日期：2022-04-06修回日期：2022-07-08文章编号：1002-8331（2023）13-0298-072982023，59（13）在路径
10、代价较大的问题。Jordan等12提出经典的双向版的RRT*算法，称为B-RRT*算法，提升了路径代价的最优性，但在复杂环境下仍存在节点数量过多，随机树拓展盲目，搜索时间过长的问题，并且在机械臂高维工作空间更为显著。针对以上问题，刘奥博等13提出改进的GBB-RRT*算法，通过目标偏置策略，每次迭代两棵随机树进行双向拓展，提高了运行效率，但未解决随机树的拓展规模的问题。刘建宇等14提出改进的RRT*-connect算法，在采样过程中引入目标导向因子，并通过限制采样区域实现随机树朝着目标区域生长，加快搜索效率。Wang 等15将目标引力变量加入 B-RRT*算法，提出了P-RRT*-connec
11、t算法，适用于狭窄通道的规划环境，并减少了机械臂规划时间，但搜索过程中存在陷入极小值的问题。Qureshi等16提出智能双向搜索的IBRRT*寻优算法，相比B-RRT*算法，IBRRT*算法在节点插入过程中引入代价启发式算法选择所在树，通过结构变化很大程度上减少了时间消耗，适用于机械臂复杂环境的规划问题，但是采样节点的扩展是随机的，在无用区域采样造成不必要的时间消耗。基于上述研究，本文提出了基于冗余节点过滤机制的IBRRT*（IBRRT*with redundant node filtering mech-anism，RNFM-IBRRT*）机械臂路径规划算法。继承了IBRRT*结构上的优势，
12、引入了随机节点过滤机制避免子节点重复拓展造成局部冗余节点堆积重叠。引入了椭圆状态子集采样算法，使采样点集中在有效分布区域，避免了随机树在自由空间的盲目拓展增加冗余节点，针对算法迭代过程中对于路径优化没有贡献的大量冗余节点的增加问题，引入了边缘节点删除机制。通过实验对比，验证了所提算法具有的优势。1背景知识1.1路径规划问题定义给定的状态空间用XRn表示，其中n代表给定空间的维度。状态空间被分类为由Xobs和Xfree=XXobs表示的障碍区域和无障碍区域。XgoalXfree，采用Ta(Va,Ea)Xfree和Tb（Vb,Eb）Xfree代表两棵随机生长树，其中V表示节点，E表示连接节点的边。
13、Xainit和Xbinit作为两棵随机树Ta、0Tb的起点。连接初始状态Xinit和随机状态X的可行路径函数由:(0,s)表示：0,s Xfree|()0=Xinit,()s=X（1）所有可行路径集合由表示。代价函数由C()表示，规划的可行路径最终要收敛到最优解，即找到连接初始状态和目标状态的无碰撞路径，同时保持代价函数最小，即：*=argminc()|()0=Xinit,()1=Xgoal,s0,1,()s Xfree（2）1.2IBRRT*算法基本原理经证明IBRRT*具有概率完备性以及渐进最优性，设计用于复杂环境探索，相比双向RRT*，IBRRT*在节点插入过程中引入代价启发式算法选择所
14、在树，提高了算法收敛速度。算法1给出了IBRRT*的算法伪代码。分别以Xainit和Xbinit作为两棵随机树起点进行拓展，首先在采样空间获取随机点Xnew，执行函数Near-Vertices，在邻近Xnew节点的圆形区域范围Bx,r搜索得到两棵随机树的邻近节点集合Xanear和Xbnear。若随机树在Bx,r区域内没有节点存在，距离Xnew节点最近节点作为Xnear。并且当Xanear和Xbnear均为空集时，不满足连接条件。执行GetSortedList函数分别计算两棵随机树起始节点Xinit经过Xnear中的节点到Xnew节点代价并排序，然后执行 GetBestTreeParent函数，
15、选取两棵随机树中经过代价排序后满足避障条件的节点Xamin和Xbmin，选取路径代价较小的节点作为Xnew的最优父节点候选。算法1IB-RRT*(xaint,xbint)1.Vaxaint；Ea0；Ta(Va,Ea)2.Vbxbint；Eb0；Tb(Vb,Eb)3.f；E4.ConnectionTrue5.fori0toNdo6.xrandSample(i)7.Xanear,XbnearNearVertices(xrand,Ta,Tb)8.ifXanear=Xbnear=then9.Xanear,XbnearNearVertices(xrand,Ta,Tb)10.ConnectionFalse
16、11.LasGetSortedList()xrand,Xanear12.LbsGetSortedList()xrand,Xbnear13.xmin,flag,fGetBestTreeParent(Las,Lbs,Connection)14.If()flagthen15.TaInsertVertex(xrand,xmin,Ta)16.TaRewrieVertices(xrand,Ls,Ea)17.else18.TbInsertVertex(xrand,xmin,Tb)19.TbRewrieVertices(xrand,Ls,Eb)20.EEaEb21.VVaVb22.return(Ta,Tb=V,E)23.IfConnectionthen24.fConnectTress(a,b)如图1（a）所示，通过比较随机树父节点所在树Ta、Tb的路程代价Camin和Cbmin大小，选取Xnew的父节点。杨宏韬，等：基于冗余节点过滤机制的IBRRT*机械臂路径规划299Computer Engineering and Applications计算机工程与应用2023，59（13）如图1（b）所示，完成
