一种装配路径规划改进GoalBia-RRT算法

张璐璐，刘恩福，刘晓阳

1 引言

随着工业4.0战略提出，复杂产品智能装配规划的研究得到学者的广泛关注，与其相关的路径规划问题是重要的研究课题之一。路径规划，即指在有障碍物的约束环境内，搜索一条从起始点到终点的无碰撞路径。传统的路径规划算法主要有栅格法、人工神经网络法、遗传算法、蚁群优化算法、粒子群算法等，这些方法都需要对一个确定障碍空间进行建模，但当空间维度增大和工作环境复杂时，会提高算法的计算复杂度，从而严重影响算法求解效率[1-2]。

快速随机扩展树（RRT）算法作为一种基于随机采样的快速搜索路径的算法在路径规划领域得到了广泛的研究和应用。该算法通过利用采样点的碰撞检测信息，避免了对自由空间和障碍空间的精确建模，使其能有效地解决高维空间和复杂环境下的路径规划问题。RRT算法因其随机性采样的特点，具有路径搜索的概率完备性[3]。但它的随机性也导致其包含一些缺点：（1）稳定性差，即对同一任务反复规划时，会产生不同的路径；（2）无导向性，即搜索树无任何偏向于目标的导向，收敛速度可能是缓慢的；（3）偏差性，即规划出的路径常常不是最优路径或次优路径。

针对传统RRT算法的不足，国内外学者对RRT算法不断的进行改进优化。改进的策略大致分为以下几个方面：（1）随机树的数量，设置两个随机扩展树，分别从起点和终点进行扩展[4]。（2）利用局部信息，传统RRT算法是一种全局搜索的算法，利用采样点附近的局部信息进行局部路径规划，使局部与全局路径规划相结合[5]。（3）搜索步长设置，由固定步长改为动态变化的步长，提高避障能力[6]。此外，还有增强目标性，减少随机性的改进，引入目标引力思想[7]，偏向目标的策略[8]等。

RRT算法是通过均匀随机分布生成采样点进行路径搜索，增强其目标偏向性，可提高效率，但当障碍物环境复杂时，这种具有贪婪思想的扩展，会很难绕过障碍物，出现局部极小值问题。基于偏向目标快速扩展策略，改进采样点的生成方法，引入混沌映射分布产生采样点取代均匀随机分布采样，这样可充分发挥混沌运动的遍历性和规律性，避免产生局部极小值问题，同时提出局部引导新节点生成策略，设计了一种装配路径规划改进GoalBia-RRT算法，通过仿真实验及实例验证了算法优越性和可行性。

2 RRT算法

2.1 传统RRT算法

RRT是不同于传统的基于反应模式或基于仿生学的算法，基本思想是通过树杈延伸的方式逐步地降低树结构与目标点的距离，直至树杈达到目标点或目标点附件的一定范围内，最后用树的脉络来表示从起点到目标点路径，这条树的脉络就可以规划出一条从起始点到目标点的路径。传统RRT算法的扩展方式，如图1所示。

图1 RRT算法扩展过程示例Fig.1 RRT Algorithm Extension Process Sample

首先，最开始以qstart为随机树的起点，随机采样得到点qrand，然后从目前生成的随机树中找到距离其最近的点qnear，在qrand和qnear的连线上，依据步长得到新点qnew，判断是否发生碰撞，否，加入随机树中，是，则继续重新采样。直到随机树扩展到目标点，算法结束。

2.2 偏向目标型RRT算法

传统RRT算法，具备路径搜索的概率完备性，但是其扩展方式是在全空间随机产生的，扩展树在空间分布过于平均，效率较低。为了提高随机树到达目标点的速率，改进的方法是：在随机树每次生长过程中，以一定概率出现qrand=qgoal，这样随机树的扩展有朝向目标区域牵引的趋势，从而提高了算法搜索速率。在传统RRT算法产生随机点过程中，设定一个0到1偏置参数P，具体改进步骤如下：

（1）生成随机点qrand；

（2）生成一个0到1的随机数rand；

（3）如果 rand＜P，则 qrand=qgoal，否则，qrand不变。

此改进方式相当于利用了贪婪规则思想[9]，偏置参数P使qrand=qgoal的概率是（5～10）%为最好，若此概率为 100%，即令随机采样点恒为目标点，该算法会尽力拉扯扩展树朝着目标点方向搜索，但贪婪思想会使路径陷在局部，产生局部极小问题，从而搜索路径效率达不到理想效果。

3 改进RRT算法

为满足装配过程中高效直接的要求，在偏向目标RRT算法的基础上，提出混沌搜索策略和局部引到新节点生成策略两种方面进行改进，这样既保留了偏向目标RRT算法本身的优势，同时也可解决其易陷入局部极小的问题，具体改进方法如下所述。

3.1 混沌搜索策略

混沌运动具有以下独特性质[10]：（1）随机性，类似于随机变量的杂乱的变化；（2）规律性，因由具有确定性的迭代方程产生，具有一定的规律性；（3）遍历性，可不重复地经历区域空间的每一点。因此，可以利用混沌现象的这种遍历性特点作为搜索过程中避免陷入局部极小点的一种优化机制，混沌搜索策略己成为一种新颖的优化方法而被广泛应用与开发。

目前比较常用的混沌映射主要有Logistic映射和Tent帐篷映射，Logistic映射的混沌遍历性较好。Logistic映射又称为虫口模型，是描述生物种群系统演化的典型数学模型，其表达为：

式中：x（k）—混沌变量；k＝0，1，2，3…—迭代次数；μ—控制参数。分析和研究表明[11]当3.5699456＜μ≤4时，Logistic映射处于混沌状态。μ＝4时的Logistic映射称为满映射，此时的Logistic映射处于完全混沌状态，具有了很好的遍历性，因此实际选取Logistic控制参数等于4。Logistic方程产生的映射点分布，如图2所示。

图2 Logistic混沌映射的遍历性Fig.2 Logistic Chaotic Mapping Distribution

由图3可知，Logistic映射分布能在区域范围内达到全面覆盖，并且表现出有向工作空间边缘分布的特点，与均匀随机采样分布相比，这种不完全平均的遍历规律，可使搜索路径快速脱离易于产生局部极小的区域。因此，改进的策略是利用混沌运动的遍历性进行混沌寻优，采用混沌变量在RRT路径规划的位姿空间内生成随机节点的位置取代传统RRT的均匀随机生成采样点。利用Logistic混沌映射产生随机采样点，这样既能够保证采样点的随机性，又能充分发挥混沌运动的遍历性和规律性，使随机采样点尽量覆盖整个状态空间，避免陷入局部极小区域，结合目标偏好的扩展策略，还能保证搜索效率。

3.2 局部引导新节点生成策略

从图2中的混沌映射点分布图可以看出，边缘部分分布较多，中间部分分布较少。因此，为了增强算法的避障能力，综合利用局部碰撞信息进行新节点的生成，针对新节点方向确定和位置确定两方面进行改进。

传统的RRT算法，新节点qnew的是在qnear和qrand的连线上生成，对于新节点的选取，希望更多的接近目标点方向，而障碍物相对稀疏的空间，采样点尽量少为最好。基于实现此目的，改进的方法是对于新节点是否在qnear和qrand的连线上生成，加入判定条件。首先设定一个偏向自由空间的参数Pz（［0，1］），若得到的qnear经检测不在障碍物附近并且Pz的值大于一个随机数rand，可判定qnear和qrand的连线在相对自由的空间，让新的节点向qnear和qgoal的连线上扩展生成，此操作相当于对随机树的“剪枝”，减少随机树的随机扩散性，同时增强向目标区域搜索的能力；否则，则向qnear和qrand的连线上生成qnew。

以上步骤确定了新节点的产生方向，还有就是确定步长，传统RRT算法是固定步长来选择新节点的位置，但是得到的路径平滑性差，借鉴黄金分割法则在建筑学和美学的应用，将其引入到新节点步长确定上，改进后的新节点位置计算公式，如式（2）所示。

式中：lnear—qrand到 qnear方向的单位坐标分量；lgoal—qgoal到 qrand方向单位坐标分量；ρ—固定步长。

在实际的装配过程中，Pz大小可根据实际的装配环境进行确定。自由空间比较多，障碍物分布比较扩散等环境，Pz的值较大为好，反之可以较小，一般设置为0.6左右。

3.3 改进RRT算法流程图

根据上述分析，改进RRT算法的流程，如图3所示。

图3 改进RRT算法流程图Fig.3 This Paper Improved RRT Algorithm Flow Chart

4 仿真实验

为了验证算法的正确性和有效性，采用Matlab2010b编程实现。仿真实验在Intel（R）CORE（TM）3.09GHz、3.24GB内存的计算机上运行。环境为100×100下的矩形区域，起始点为（1，1），终点为（100，95）。图中黑色部分为障碍区域，黑色的“*”点为记录下来的采样点，黑色的粗线和细线为形成的随机扩展树，黑色粗线连接着起点和终点，为规划出的路径。

在一般障碍物环境下，传统RRT算法与改进算法路径规划的结果，对比之下可以明显看出传统RRT算法采样点随机分散性，改进的算法利用局部碰撞信息，随机树体现出具有贴近障碍物生长趋势，采样点的数量和路径长度得到明显提高，生成的路径平滑性得到很大改善，如图4所示。

图4 一般环境路径规划结果Fig.4 General Environment Path Planning Result

在装配过程中经常出现的狭窄环境，如图5所示。改进RRT算法，在障碍物的左侧基本按照贴近障碍物扩展路径，采样分布趋势性强，在右侧则几乎以直线到达目标点，体现出了极强的“退随机化”，并且整体的曲线体现出了良好的绕过障碍物的能力，比较符合实际装配的理想路径，而传统的RRT，即使在通道的右侧依然体现出较大的随机扩散性，规划的路径折点多，路径长度不是最优。

图5 狭窄通道环境路径规划结果Fig.5 Narrow Channel Environment Path Planning Result

在图6的稀疏障碍物分布环境中，（a）中偏向目标RRT算法体现出快速高效的特点。（b）中是这里算法，通过调节偏向自由空间的参数Pz的大小得到的路径，Pz=0.8，在采样点数量和耗时上与（a）中相差不多，但是路径长度更短，可通过性更好。实际装配中，可根据环境特点，通过调节参数Pz来获得比较好的规划路径，改进后算法拥有高的灵活性和环境适应性。

图6 随机稀疏障碍物环境路径规划结果Fig.6 Random Sparse Obstacles Environment Path Planning Result

在2.2节中提到目标偏好型RRT算法在复杂环境下，会出现陷入局部最小的问题，在易出现局部极小的复杂的随机密集障碍环境下，对改进RRT算法和GoalBia-RRT算法进行仿真实验对比，各自运行20次，仿真数据结果，如表1所示。从采样点个数和运行时间对比，这里的算法具有明显的效率优势，可以看出改进后算法解决局部极小问题的效果很突出。

表1 随机密集环境路径规划仿真实验数据对比Tab.1 Random Dense Environment Path Planning Simulation Experiment Data

5 原型系统及实例验证

利用CATIA二次开发工具CAA+RADE，设计了基于改进RRT算法的装配路径规划原型系统，该系统是在VS2005上利用C++进行开发，主要包括干涉检验功能[12]，路径规划功能，保存路径信息功能和生成重放功能。验证以盲板阀的翻板推杆为例，选取其中的一个螺母作为装配路径规划的对象，操作界面和路径规划结果，如图7所示。交互式选择零件、起始点等参数，完成初始化，点击“路径规划”按钮，运用改进算法进行路径的搜索，最后在界面上显示路径规划的节点信息，如图7（a）所示。并且在装配结构树上建立相应的RRT规划路径，如图7（b）所示。

图7 装配路径规划系统界面及规划实例Fig.7 Assembly Path Planning System Interface and Programming Examples

路径节点信息为零件装配过程中不同位置的位姿矩阵的集合，点击“生成重放”按钮，可以生成相对应零件的装配路径仿真运动信息，并添加到结构树上。运行重放的效果，如图8所示。

图8 零件装配路径仿真Fig.8 Simulation of Component Assembly Path

该系统可以很好实现零件装配路径的自动生成，并且将得到的相关路径信息自动添加到装配结构树上，便于装配路径信息的查询及信息后续的再利用，具有极高的实际价值，通过实例也进一步验证了改进的GoalBia-RRT算法的可行性和实用性。

6 结论

（1）针对装配路径规划问题，提出一种偏目标型快速扩展随机树改进算法，主要是在采样点生成上引入混沌运动和利用局部碰撞信息引导新节点生成策略进行改进，不仅能够快速的搜索从起点到目标点的路径，在解决局部极小值问题上效果突出，而且规划的路径可通行性得到极大改善，更接近实际理想路径。通过仿真实验，验证了改进算法的优越性和有效性。

（2）基于这里的算法，利用CATIA二次开发技术设计了装配路径规划原型系统，该系统是对于CATIA的装配分析模块的一个有意义的功能扩展和优化，可以极大的提高装配仿真工作的效率。进行了实例装配路径规划应用，进一步验证了算法的实用性和可行性。

（3）这里的算法能够得到较好的装配路径规划结果，但是由于装配环境的复杂性，并没有全面考虑工程约束，这些都在后续工作中进一步探索。