一种新型并联机构工作空间边界搜索算法研究

邱 栋

（黄淮学院国际教育学院，河南 驻马店 463000）

1 引言

机器人工作空间是指操作器执行末端满足约束条件所能够达到的位置点的集合［1］，机器人工作空间是衡量机器人运动操作性能优劣的重要指标，其主要取决于机构的尺寸参数和关节限位［2］，研究工作空间对机器人结构设计与运动轨迹规划具有重要意义［3］。

工作空间的形状和尺寸分析方法有很多，诸如几何法、解析法、数值法等［4］。几何法主要靠通过几何分析得到剖操作空间的截面线或剖截线，仅适用于平面机构、低自由度的机器人工作空间分析，且无法精确描述机构的工作空间［5］；解析法是根据雅克比矩阵得到机构的解析式，其求解过程复杂，直观性不强，不适用于高自由度机构工作空间分析［6］；数值法求解机器人工作空间直观性性强、过程简单、通用性强［7］。

因此，适用于任意形式的机器人的工作空间分析。数值法主要有网格划分法、蒙特卡洛法、极坐标搜索法等［8］。其中最常用的方法为蒙特卡洛搜索法，此方法通用性强、操作简单。文献［9］为解决精度不高问题提出采用一种改进的蒙特卡洛法，此方法是基于标准动态的可调的正态分布对子工作空间进行阀值计算，得到准确描述的工作空间边界。文献［10］中结合并集和交集思想，离散化处理将四维度的工作空间转化为三维工作空间。文献［11］中针对按列划分法所得边界点均匀性差且无法识别空洞的缺点，将按角度划分法与局部坐标法结合的思想搜索出精确的工作空间边界。

文献［12］提出一种改进的粒子群搜索算法，将工作空间边界点搜索转化目标优化函数寻优过程，实现并联机器人的工作空间边界搜索。

受改进粒子群搜索算法启发，提出了一种基于变步长天牛须优化算法的并联机构工作空间边界求解算法。结合变步长天牛须算法搜索原理，定义了速度、速度衰减系数等参数，研究了二维和三维机构的算例，考察了各参数对搜索过程的影响，为此算法的在并联机构工作空间搜索应用提供理论依据。

2 理论基础

2.1 机构优化目标函数的构造

机构的所有构件位态可以用向量q表示，其为：q=[q1，q2，，q3，，…qnq]，矢量q一般通过输入、输出和中间坐标表示，分别表示为u，v，w，机构逆解表达式根据输出坐标u表示为：

机构的工作空间是指满足杆长、干涉、运动副转角等约束条件情况下的执行末端运动范围A。

通过数值法的求解过程一般建立在机构逆解的基础上分析，即满足所有约束条件的输出坐标点u点的集合可表示为机构的工作空间，这些约束可以用约束函数fCi表示，约束函数fCi一般形式如下所示：

式中：n—给定约束条件的数量。

假设在工作空间边界内部有一个任意可达的输出坐标C。为了找到边界，机构工作空间边界搜索的目标函下：

式中：‖ · ‖—欧氏距离，等式（2）和式（3）表示如果f(u)的值不满足任何约束条件，f(u)的值将为0。

由于二维平面机构的工作空间是个二维平面区域，因此将二维平面区域经过点C分割成N等份，如图1（a）所示，查找出N个局部最大点uMi满足以下条件：

图1 工作空间搜索示意图Fig.1 Sketch Map of Workspace Search

因此，最大值f(u) 将在边界dA上。根据相应η以及目标函数可得到局部最大值的uMi，将这些局部最大值（边界点）点的集合构成工作空间边界。

三维机构原理也是相似的，坐标空间将由二维扩展成3维，此时搜索的三维空间区域类似于不规则球面，如图1（b）所示。

最大值将在边界dA上，其集合即是工作空间边界。从示意图1可以发现搜索的路径将是一个从起始点出发的射线，这是由欧式距离决定的搜索路径。

2.2 变步长天牛须搜索优化算法介绍

天牛须搜索算法（Beetle Antennae Search，BAS），文献［13］根据对天牛觅食行为的模拟的原理所提出的一种新型智能优化算法。该算法具有鲁棒性、求解速度快、精度高等特点［14］。是一种类似于模拟退火、遗传算法、粒子群算法、等生物启发智能优化算法。天牛主要利用头顶上两只长触角根据食物气味强弱来完成觅食过程，如果左边触角获取的气味强度大于右边的触角气味强度，则天牛沿着左边寻找食物，反之则反，根据这一简单原理有效或获取食物。

该算法的主要优点在于不需要函数的具体形式、梯度信息就能实现高效寻优，而且与其他算法相比，仅需要一个个体（一只天牛），极大的减少运算量。针对原始BAS算法步长为固定值导致搜索过程中搜索效率和精度会降低问题，设计变步长天牛须搜索算法具有先粗略搜索大致范围再精细化搜索的优点。极大的提高了搜索效率，算法搜索过程示意图，如图2所示。

图2 算法搜索过程示意图Fig.2 Schematic Diagram of Algorithm Search Process

3 算法理论和流程

3.1 算法概要

传统数值搜索法中搜索效率低通用性差，如极坐标搜索法要提高搜索精度往往通过缩减步长实现，导致搜索效率极低，针对此类问题，结合变步长天牛须搜索优化算法中搜索效率高的特点，提出一种基于变步长天牛须搜索优化算法的机器人工作空间搜索方法，其搜索原理如下：

（1）建立基于工作空间位置与机构约束条件的优化目标函数，基本形式为：

式中：f(u)的值为0 或1，满足约束为1，不满足约束为0，其中u—坐标值。

（2）因搜索路径是由起始点出发的固定方向的射线，将变步长天牛须优化算法中的随机搜索方向变为固定方向。

（3）变步长天牛须优化算法中左须和右须是不同方向的，根据步骤（2），现将左须和右须变为具有不同速度和变化量的天牛须。

（4）根据步骤（3）中的速度变化量，得出左右须的目标函数值，决定天牛的移动方向。

（5）通过步长和速度衰减以及迭代，最终逼近工作空间边界值。

3.2 算法流程和参数定义

算法流程，如图3所示。具体描述如下：

图3 机构工作空间搜索算法流程Fig.3 Algorithm Flow of Mechanism Workspace Search

（1）定义天牛群的个数sizenum 以及初始位置x0，定义每个天牛的左须和右须的速度vl和vr，左须和右须速度的衰减指数γ，定义天牛步长step，两须的距离d0，变步长参数η；定义机构参数和约束空间。

（2）计算每个天牛在初始位置的目标函数值：

fitness(i)，i= 1，2，3，…，sizeness

（3）天牛左须和右须位置更新公式：

根据式（6）计算左须位置和右须位置的目标函数值Fleft和Fright：

根据上述的式（7）计算新位置的目标函数值，若新位置的目标函数值较大，则更新新位置，否则保留旧位置，衰减式（8）所示，步长按照式（8）衰减。

（4）重复步骤（2）～步骤（3），记录当前最佳位置和天牛移动速度等。

（5）判断迭代次数是否超出最大迭代次数，如果不满足继续移动，若满足计算终止。

4 算法算例

4.1 二维平面机构3RPR算例

3RPR平面并联机构的结构简图，如图4所示。它由三条支链、动平台、静平台构成，其静、动平台形状都是等边三角形，分别为ΔA1A2A3、ΔB1B2B3，其中ΔA1A2A3的外接圆半径为R，ΔB1B2B3外接圆半径为r，分别在静平台、动平台的中心建立静、动坐标系，动坐标系中心为点P，动坐标系中U轴平行B1B2，V轴垂直于B1B2，静坐标系中心为点O，动坐标系X轴平行A1A2，Y轴垂直于A1A2，机构的姿态角为θ，为B1B2与A1A2的夹角。机构的输出(x，y，θ)即执行末端的位姿。

图4 3RPR平面并联机构的结构简图Fig.4 Structural Diagram of RPR Planar Parallel Mechanism

已知机构静平台上的点Ai静坐标系下的坐标，分别为，，，其中，动平台上Bi动坐标系坐标，可分别用表达式表示为：，，，静坐标系中点Bi的位置矢量可表示为：

式中：rp—动坐标原点P在静坐标系中的坐标（x，y）；Rot(z，θ)—坐标旋转矩阵。

根据以上坐标变换公式，能得到动平台上点Bi的坐标。

因此，可根据上述表达式可得到AiBi的表达式：

工作空间求解的约束条件是移动副Pi在范围［a，b］，以3RPR 平面并联机构为例，算法搜索机构的结构参数值，如表1所示。

表1 3RPR并联机构参数值Tab.1 Parameter Values of 3RPR Parallel Mechanism

下面需要给定基于变步长天牛须搜索优化算法的机构空间算法的参数的初始值，给定大小合适的平面区域，选择点C（0，0）作为粒子群的初始位置，且该点属于工作空间内的点，天牛群在迭代搜索之前，先将平面区域分割成N等份，分割线经过C点，每条分割线的坐标向量di=[ sin(βi)，cos(βi)) ]，粒子群沿着直线以式（4）作为目标函数进行搜索，其中，具体的参数值选择，如表2所示。

表2 算法初始化参数Tab.2 Algorithm Initialization Parameters

根据上述的搜索流程图以及参数，基于matlab软件进行编程，搜索出每个方向上（分割线）的最优值，将所有的最优值可视化绘图，即完成了基于变步长天牛须搜索优化算法的机构空间算法工作空间边界点的求解过程。其中图5表示姿态角为60°，在迭代过程中搜索的定姿态工作空间边界变化情况，第30个点的位置坐标收敛图，如图6所示。

图5 迭代过程中搜索的定姿态（60）工作空间边界变化Fig.5 Boundary Change of Attitude（60）Workspace During Iteration

图6 迭代过程中第30个点的位置变化过程Fig.6 The Position Change Process of Thirtieth Points in Iteration Process

第30个点的速度和加速度的变化情况，如图7所示。图7显示了搜索的过程边界点的变化，随着迭代次数t的增加，边界点由内向外逐步不对称扩散，t=15时已得到基本的工作空间边界点，t=100时已得到光滑的边界点。图6中可以发现第30个天牛的每代位置收敛过程，在约t=60时，以完成较好的收敛。图7可以发现第30 个天牛的速度和加速度的收敛过程，成振荡收敛模式，表明了天牛在边界点的来回搜索过程，最终加速度和速度逐步趋于0。

图7 迭代过程中第30个点的天牛移动速度和加速度变化过程Fig.7 The Change Process of the Moving Speed and Acceleration of the 30 the Point in the Iterative Process

更换机构的约束条件可以得到3RPR的可达工作空间的搜索图，如图8所示。

图8 迭代过程中搜索的可达工作空间边界变化Fig.8 Boundary Change of Reachable Workspace During Iteration

3RPR的可达工作空间形状的搜索图，如图8所示。机构工作空间形状沿着x=0对称，且内部无空洞情况，整体连续性较好，无论是可达工作空间还是定姿态工作空间都能快速搜寻。

从精度上分析，与极坐标搜索法（采用间隔为0.01，360 等分）对比，如图9所示。

图9 极坐标搜索法的可达工作空间Fig.9 Polar Search Method of the Workspace

其中一色为极坐标搜索法得到的可达工作空间，另一色为天牛群搜索法得到的边界，两种情况搜索结果基本一致，说明此算法的有效性，另外，极坐标搜索法受限于间隔精度，得到的是较为粗略的可达工作空间，当搜索角度为90°时，搜索边界点坐标，如表3所示。

表3 极坐标算法和天牛须算法精确值对比Tab.3 Comparison Between Polar Coordinate Algorithm and Antenna Whisker Algorithm

显然天牛群搜索算法获得了较高精度，若选择极坐标要获得高精度边界搜索时间较长。因此，该算法与极坐标搜索法相比具有快速高效的特点。

4.2 三维机构3UPRR算例

空间3UPRR并联机构结构简图，如图10所示。机构构型呈对称分布，机构的运动学逆解过程可参考文献［15］，在此就不详述，机构的逆解表达式可表示为：

图10 机构结构简图Fig.10 Schematic Diagram of Mechanism Structure

机构工作空间搜索约束条件为：机构的逆解存在，同时机构的位置逆解满足其移动的范围，为验证基于变步长天牛须搜索优化算法的机构空间算法（MBSA）对3维并联机构搜索工作空间边界的有效性，3UPRR并联机构的参数值选择同样参考文献［15］中的参数值，3UPRR并联机构的结构参数值如，如表4所示。算法参数选择，如表5所示。给定天牛群初始位置都为C（0，0，0），每个天牛群的固定方向采用极坐标搜索法方法确定，具体的搜索过程，如图11～图13所示。

表4 3UPRR并联机构结构参数值Tab.4 Structural Parameters of 3UPRR Parallel Mechanism

表5 算法初始化参数Tab.5 Algorithm Initialization Parameters

图11 迭代过程中搜索的工作空间边界变化Fig.11 Changes in Workspace Boundary Searched During Iteration

由图11分析发现，在3UPRR空间并联机构边界的搜索过程中，呈球面搜索过程，t=5时，由于天牛速度快，很快接近边界区域，t=8时，天牛群已经分区域聚集，达到t=100时，已完成了规定的搜索，图12表明第30个点的搜索收敛过程，在t=50时，基本完成了搜索，印证了搜索的有效性。

图12 迭代过程中第30个点的位置变化过程Fig.12 The Position Change Process of Thirtieth Points in Iteration Process

通过图13，可以发现与二维平面机构相比，速度和加速度振荡过程更加剧烈，但搜索过程很快收敛，基本和位置收敛一致。

图13 迭代过程中第30个点的天牛移动速度和加速度变化过程Fig.13 The Change Process of the Moving Speed and Acceleration of the 30th Point in the Iterative Process

同时与极坐标搜索法（采用间隔为0.1）对比，如图14所示。

图14 极坐标搜索法的工作空间Fig.14 Workspace of Polar Coordinate Search Method

其中一色为点阵法得到的可达空间图，另一色为天牛群搜索法得到的边界。

可以发现，点阵搜索法受限于间隔精度，得到的是较为粗略的切片式可达空间，当点阵搜索的间隔为0.1时，搜索边界点坐标，如表6所示。此算法与极坐标搜索法相比具有搜索精度高的特点。

表6 极坐标算法和天牛须算法精确值与耗时对比Tab.6 Comparison Between Polar Coordinate Algorithm and Antenna Whisker Algorithm

以上分析表明：该算法能够实现空间并联机构搜索与平面并联机构的工作空间边界搜索，且能实现不同维度与不同构型的并联机构的工作空间求解。

说明了此算法的通用性强，同时也验证了算法具有搜索效率高、有效性。

5 不同参数对搜索过程效率的影响

5.1 不同初始位置对搜索过程的影响

以平面机构3RPR的可达工作空间为例，给出不同初始位置C1（-0.5，0.5）、C2（0.5，0.5）、C3（-0.5，-0.5），研究初始位置对搜索结果和过程的影响。其他参数，如表1、表2所示。

根据图15分析可得：在迭代过程中，在t=5时，搜索边界最靠近初始点的位置率先获得大致轮廓，表明，初始点的偏离对搜索过程具有一定的影响，搜索距离越短越好，这与原理一致；但在初始点所得最终的工作空间边界是完全一致的，搜索时间上基本一样，因此结果表明：在工作空间内的任意初始点并不影响此工作空间边界搜索算法求解。一般情况下定义初始点为原点。

图15 不同初始位置的可达工作空间边界搜索过程（第1至3排为C1，C2，C3）Fig.15 Boundary Searching Process of Reachable Workspace at Different Initial Positions（Rows 1 to 3 are C1，C2，C3）

5.2 不同天牛须速度参数对搜索过程的影响

同样以平面机构3RPR的可达工作空间，给出不同天牛须初始速度组合，第一组：vl=0.1，vr=0.2，第二组：vl=0.1，vr=0.3，其他参数同表1、表2，初始位置都为C（0，0）。

由图16分析可得：在迭代过程中，在t=5时，左须和右须初始速度相差较大的第二组参数，获得的当前边界已经接近2，而第一组组合才接近1，这表明搜索组合的最大速度对搜索位置的影响较大，但最后得到的工作空间是一致的，根据图17发现：第二组平均天牛须速度更快的组合具有更多的振荡次数，为了减少振荡幅度和次数，可以选择较低的速度组合，可以根据具体的机构选定。

图16 不同初始天牛须速度组合的可达工作空间边界搜索过程（第1至2排为组合1和2）Fig.16 Boundary Searching Process of Reachable Workspace for Different Initial Velocity Combinations of Cercaria（Rows 1 to 2 are Combinations 1 and 2）

图17 迭代过程中不同天牛须速度组合对天牛移动速度的变化过程Fig.17 Changes of the Speed of the Long Horned Beetle During the Process of Iteration

6 结论

（1）针对传统离散化方法极坐标搜索法中搜索效率低的问题，提出一种集合变步长天牛须高效的寻优算法的优点的工作空间求解算法。

（2）重点介绍变步长天牛须优化算法的机构空间边界搜索算法的原理和流程，分别以不同构型的平面与空间并联机构进行算例分析验证其方法的有效性、通用性，同时与极坐标搜索对比验证搜索算法搜索效率高。结果表明：此算法搜索具有效率高、通用性强、搜索过程简单等特点，可作为一种通用性的并联机构工作空间快速搜索算法。

（3）比较不同初始位置和天牛须速度下工作空间边界的搜索过程表明，工作空间边界内初始点对搜索结果无影响，天牛须速度不同组合也对搜索结果无影响，两者只影响搜索过程。这表明了算法的优异性。