面向车身数字化工艺开发的多机器人避障算法

曾 贺

（上汽大通汽车有限公司 制造工程部，上海 200082）

机器人路径规划是指对于给定的任务，机器人寻觅一条从初始位置抵达目标点后的无碰撞最优路径的过程。

单机器人无碰撞路径规划是多机器人协调运动的基础，传统单机器人无碰撞运动规划方法包括自由空间法、人工势场法、概率地图和快速扩展随机树等基于采样的规划方法，LI T G等人提出了一种改进的Q-Learning自主学习算法来解决空间操纵器在未知环境中的自适应路径规划问题，根据Q-table的自主学习，操纵器可以指导其后续的动作选择和路径规划，使机器人自由空间内寻找一条最优的机械臂无碰撞路径。焦嵩鸣等对A*的启发函数进行改进，以减少路径规划过程中的计算量，从而提高规划效率，设计障碍惩罚函数，进而实现提前避开行进路径上的障碍物，避免陷入局部最优。陈满意等人采用低振荡人工势场法进行路径搜索，当人工势场法陷入局部极小时采用自适应快速搜索树方法进行路径搜索，最终对于搜索到的冗余路径节点采用四次贝塞尔曲线进行拟合优化。何启嘉等人基于深度学习，预先学习竞争网络中的状态价值层，使状态价值参数根据环境状态进行初始化，减少了首次接触目标点所需要的步数；其次，通过改进竞争网络中的贪婪搜索算法，使环境探索与利用的转变更为合理；最后通过改进动作选择策略，使机器人路径规划不易陷入局部极小值，进一步加快了算法收敛的速度。孙灵硕提出改进的RRT- Connect算法用于焊接机器人的避障路径规划，对位于凹形障碍区域的树节点及其附近区域进行标记，并将标记的区域从自由状态空间中剔除，避免随机树再次陷入标记的凹形障碍区域。

上述方法虽然可以搜索到较优的无碰撞路径，但是对于车身等大尺寸、结构复杂的产品对象，其构型空间的建模过程复杂、计算量大，因此，如何面向机器人无碰撞检测路径最优的目标，有效降低环境建模的计算量、提高搜索效率是多机器人系统路径规划的重点。

针对现有机械臂在复杂多障碍物环境中局部路径规划时间长的问题，本文提出一种改良的APF-RRT*的机器人避障措施，缩短算法的运行时间，减少局部路径的长度，提升无碰路径的搜索效率。

1 方法概述

目前已有许多避障的算法用于解决机器人和静态环境中的运动规划问题，例如人工势场法、基于采样的规划和基于网格的方法。上述方法大多在机器人自由位形空间内进行路径搜索，实现机器人局部路径规划。然而，实际工程应用中，由于车身曲面结构复杂且所占空间巨大，导致机器人与车身所产生的位形空间建模难度高，且在高维位形空间内搜索较优路径极其费时费力。针对这一问题，本文利用改进APF-RRT*的避障算法在笛卡尔坐标系内搜索机器人可行路径节点，以关节角运动范围最小为约束条件对生成的路径节点下的机器人关节角进行优化，以保证机器人关节角变化的连续性。为进一步保证局部路径最优，减少由于RRT*算法搜索导致的路径冗余现象，本文采用贝塞尔曲线对产生的局部路径进行二次优化。

本文提出的机器人避障策略流程如图1所示。

2 传统避障算法

为了更好地阐述本文提出的避障策略，首先对传统的RRT*算法及人工势场法进行简要阐述。

2.1 传统RRT＊算法

RRT*算法是一种基于增量采样的路径搜索算法，通过多次采样的方法实现搜索路径的最优，RRT算法的前几步和RRT算法相同，RRT算法具体的算法步骤如下：

步骤1：从机器人初始位置建立根节点。

步骤2：利用随机采样的方式在机器人运动空间内进行搜索，确定随机采样点。

步骤4：判断是否与障碍物发生碰撞，若无碰撞，则确定为新节点，返回步骤2。

RRT算法中存在搜索路径非最优解的现象，为了解决此问题，RRT*算法父节点选择和重布线两个操作进一步对机器人运行路径进行优化。

RRT*算法父节点选取的示意图如图2所示，所产生的新节点搜寻所定义半径范围内潜在的父节点，依次计算→→的总路径，若此路径小于→→路径的长度，则将的父节点进行更新，最终迭代选取路径最短的节点作为的父节点。

为进一步减少机器人局部路径的长度对邻域内的节点进行重布线的操作，RRT*算法重布线示意图如图3所示，在无碰撞的前提下，重布线函数分别计算→→，→→，路径长度分别为，。若<，则将父节点更改为。最终，不断迭代上述步骤，直到新产生的节点寻找到目标点为止。

2.2 人工势场算法

人工势场法是利用虚拟势场中梯度下降引导机器人进行路径搜索的方法，该方法根据机器人所处的环境建立虚拟势场及势场力，机器人下一个运动的目标点对机器人产生引力，一般情况下引力势函数和引力函数为

车身等障碍物对机器人产生斥力，引力和斥力合力的方向即为机器人运行的方向。则斥力函数通常可表示为

机器人在所构建势力场下受到总势能和势场力分别为

当机器人所受到势能不为0时，机器人下一时刻的位置为

其中，为所设点的步长，为/||。重复上述步骤直到势能为0或找到检测特征为止。

3 基于APF-RRT＊算法的机器人避障策略

RRT*算法通过父节点的选取和重布线两个步骤解决了RRT算法中路径冗余的问题，但上述算法中机器人父节点的选取及重布线均需要重新进行大量的计算，且节点的产生均基于随机采样导致RRT*算法的时间效率较低。而采用人工势场法进行路径搜索时易于出现搜索结果陷入最优的现象。针对上述问题本文引入人工势场的思想进行新节点的产生，使得机器人新节点的产生不仅受到随机性的影响，还受到人工势场力的影响，则机器人新节点产生的公式为

式中，为权重系数；为机器人在处受到的合力；为机器人搜索的步长；当>时，随机采样性较高，机器人能够搜索到任意的无碰撞工作区间，为路径最优提供优化条件，同时增加搜索时间。当<时，机器人采样点搜索更具有目的性。但当机器人工作环境较为复杂时，易于出现机器人无法到达目标点的现象。因此，为了保证机器人能够搜索到目标点，提高搜索概率的完备性，此处应略大于，本文选取=0.6，=0.4。

基于上述新节点产生策略能够使节点向目标搜索，同时面对障碍物时能基于人工势场的斥力作用绕开障碍物，为节点搜索提供有效的随机采样点，从而提高路径规划的效率。然而，对于笛卡尔空间内确定的节点位姿，机器人利用逆运动学可以求解得到最多八组解，因此，为了保障机器人前后节点关节角的连续性，需满足每个关节的角度变化最小，可根据式（6）对于新产生节点关节角进行确定，即

RRT*搜索得到的路径为直线时，机器人在通过奇异点附近时，机器人关节速度将极速增加，导致不可达现象。因此，为了保证搜索路径的平滑性及可达性，需要对RRT*搜索到的路径进行平滑处理。在工业机器人应用中，五次贝塞尔曲线满足机器人轨迹对于平滑、速度可导、加速度连续等要求而被广泛应用于机器人控制系统。因此，为保证所规划的轨迹更接近于机器人运动轨迹，本文采用五次贝塞尔曲线对新产生节点进行拟合。五次贝塞尔曲线方程为

式中，为控制点，即为搜索到的节点；()为伯恩斯坦基函数；=5。

五次贝塞尔曲线最多可对六个控制节点进行曲线拟合，因此，需要多段贝塞尔曲线进行拟合。值得注意的是，拟合后的曲线进一步进行碰撞检测以防止新拟合的轨迹发生碰撞等现象。可通过以下步骤进行曲线拟合。

步骤1：依次选取六个节点作为控制点进行贝塞尔曲线拟合。

步骤2：对生成的节点进行碰撞检测。若不发生碰撞，对剩余节点进行曲线拟合；若发生碰撞，则转到步骤3。

步骤3：找出碰撞点前后的节点、，在、节点中间选取4个过渡节-点使得→→…→拟合得到的曲线不发生碰撞。

4 基于APF-RRT＊算法的机器人避障应用验证

机器人局部路径规划是在机器人发生碰撞时获取无碰撞局部检测路径的重要手段，局部路径的长度及算法实现的效率影响整个车身检测路径的质量及全局路径规划的时间。为验证本文提出的APF- RRT*算法的有效性，本节将基于薄板件模型，分别采用RRT、RRT*、APF、RRT*及所提出的改进APF- RRT*算法进行避障验证。

薄板件由自由曲面和平面连接而成，其CAD数模如图4(a)所示，图4(b)中的灰色部分是其三角面片化后的网格化数据。在薄板件表面随机选取两个关键尺寸特征，其检测视点位置分别为Start以及Goal。机器人需从视点Start运动到视点Goal完成机器人的局部无碰撞路径。

本节分别采用RRT、改进APF、RRT*和所提出的改进APF- RRT*分别对进行Start、Goal视点之间路径进行避障，最终的机器人末端点运动轨迹如图5所示。

为了更直观地反映所提出方法的有效性，以下分别从算法运行时间、迭代次数及最终路径总长度进行分析。不同避障策略的优化参数对比如表1所示，基于人工势场算法的运行时间为33.17 s，算法迭代次数仅为369次，其算法运行时间及迭代次数最少，但其优化后的总路径长度最长，约为536.65 mm。而本文提出算法路径总长度仅为118.1 mm，比人工势场算法路径长度减少约77.93%，比RRT*和RRT算法的局部优化分别提高35.31%和55.96%。

从运行时间看，基于本文提出的APF-RRT*算法的运行时间为115 s，相比于传统的RRT*算法提升了83.2%，且迭代次数缩短至536次，缩短了73.2%。综上所述，经典人工势场法搜索时间较短，但是在路径优化方面的不足；传统的RRT*、RRT算法优化后路径较短，但是搜索时间较长。而本文提出的APF-RRT*不仅提升了算法搜索效率，同时缩短优化后路径长度，避障效果较好。

5 结论

本文详细阐述了获取任意两个特征之间无碰撞局部检测路径的方法，提出了基于APF-RRT*的机器人局部避障策略，改进后的RRT算法在一定程度上缩短了算法的运行时间，迭代次数以及路径的总长度，实现局部路径的优化，提高局部避障算法的搜索效率。