基于改进遗传算法的时间最优轨迹规划*

杨星涛 库祥臣 赵欢乐 米 显 马东阳

(河南科技大学机电工程学院,河南 洛阳 471003)

当今工业机器人技术广泛应用在焊接、码垛、磨削抛光、装配和喷涂等领域[1]。在优化操作时间、提高工业机器人自动化操作效率上，国内外学者对工业机器人时间最优轨迹规划问题进行了大量的研究。在轨迹生成上，董甲甲等[2]采用改进的B样条曲线生成轨迹，提高了机器人空间运动轨迹的平滑性；李俊等[3]采用4-3-4次样条函数生成轨迹，降低了轨迹规划中的计算量；总体来说，三次多项式插值、五次多项式插值、组合多项式插值、B样条插值、PH样条插值[4]等方法可以实现光滑连续的轨迹，但随着插值轨迹的复杂度提高，轨迹规划的计算量也在提高。在优化算法的设计上，Lin C S等[5]应用三次样条插值生成关节轨迹，并开发优化插值时间间隔的数学算例，实现了机器人轨迹的时间最优；徐海黎等[6]提出一种新颖的罚函数排序方法，在时间最优轨迹规划上获得了更好的优化效率；邓伟等[7]在遗传算法中结合混沌优化算法，提高了算法的全局搜索能力；殷凤健等[8]采用交叉、变异概率自适应的遗传算法，提高了遗传算法的收敛效率，但罚函数惩罚因子难以选取，需要多次尝试。递推法、模式搜索法可以快速计算理想结果，但容易陷入局部最优解，粒子群算法、遗传算法及免疫算法等进化类算法可以获得更好的全局最优解，但存在约束条件复杂，中间参数难以选取等问题。

基于以上分析，本文研究通过随机排序方法改进遗传算法在时间最优轨迹规划上的应用，简化遗传算法中间参数的选取，提高遗传算法的全局搜索和局部搜索的能力，进而优化工业机器人操作时间，提高工业自动化生产的效率。

1 最优轨迹规划问题描述

1.1 作业的描述

根据机器人自动化加工过程中的操作工艺，可以将机器人在笛卡尔空间中的轨迹描述为一系列的关键点pi(i=1,2,…,n)之间的运动。如图1所示，以测量作业为例，机器人携带测量工具从p1点出发，接近送料机构到达p2点，在p3点夹取工件，远离送料机构到达p2点，接近物料箱到达p4点，在p5点将工件送入指定的物料箱，之后远离物料箱，经过p4点回到p2点。可以把机器人测量的自动化作业看作是笛卡尔空间中机器人在关键点之间的自动化运动。通过优化关键点之间的时间间隔，可以实现多个关键点之间轨迹规划时间间隔的最优化，进而提高自动化操作的效率。

1.2 轨迹生成

(1)

式中:aj、aj+1表示θj(t)在区间[tj,tj+1]上左右端点处加速度值，hj(j=1,2,…,n-1)表示[tj,tj+1]的时间间隔,同时hj=tj+1-tj。

(2)

对θj(t)一次求导，得

(3)

(4)

(5)

(6)

式(6)中:

因为需要足够的自由度来求解约束问题，所以增加关于初末速度的边界条件，根据已知轨迹初速度和末速度条件：

(7)

可以得到以q2和qn-1为参数，关于aj的两个等式：

(8)

结合式(6)和式(8)可以看出，关键点处加速度值aj可以表示为关于hj和qj的为参数的方程组，如下所示：

Ha=d

(9)

式(9)中:

若已知关键点位置qj和关键点之间的时间间隔hj，可通过追赶法可以求解方程组(9)得到轨迹关键点加速度aj(j=1,2,3,…,n)，进而代入式(1)～(4)得到三次样条曲线规划的位移、速度、加速度和加加速度。

1.3 随机排序

将自动化作业的总时间作为优化目标，由于各关键点之间位移已由自动化作业工艺的要求确定，测量时间的减少必然会导致关节速度、加速度及加加速度的增大。然而由于机器人硬件上的限制，关节速度、加速度和加加速度存在最大值，所以机器人自动化作业时间最优轨迹规划的数学描述如式(10)所示。

(10)

式(10)中：x=[h1,h2,h3,…,hj,…,hn-1]表示各关键点之间的时间序列，vjmax、ajmax、jjmax分别表示机器人关节j的速度、加速度、加加速度最大值。

机器人时间最优轨迹规划实际上是含有多个复杂约束的目标优化问题，通常以式(11)罚函数的形式处理约束条件，但罚函数的惩罚系数rg难以选取。

F(x)=H(x)+rgφ(gm(x);m=1,2,3)

(11)

式(11)中：x表示种群中的个体，F(x)表示种群适应度，H(x)表示种群的目标函数值，由式(10)计算，rg表示约束条件的惩罚系数，φ(gm(x);m=1,2,3)表示3个约束条件的约束函数值，由式(12)计算。

(12)

式(12)中：φ(gm(x))不妨简记为φ(x)。

种群适应度值是进化算法中评价个体优劣的标准，本文评价种群适应度为避免惩罚系数rg的选取，根据种群目标函数值以及约束条件引用基于冒泡排序的随机排序法[9]，在两个个体适应度高低的评价中，引入概率参数Pf，满足以下两条规则：当两个个体都满足约束条件时，以个体目标函数值从小到大排序；存在一个个体不满足约束条件时，以概率Pf判断依据目标函数值从小到大排序或依据罚函数值从小到大排序。随机排序的具体操作如图2所示。

1.4 遗传算法

随机排序后的最优轨迹规划问题可以通过进化策略、免疫算法、粒子群算法、遗传算法等进化算法优化，本文以操作较为简单的遗传算法为例说明最优轨迹规

划问题的优化过程。机器人时间最优轨迹规划中应用遗传算法的关键在于设计种群编码方式、适应度函数和遗传算子。

编码方式，根据公式(10)最优轨迹规划需要对一条关节轨迹中的时间间隔h=[h1,h2,…,hj,…,hn-1]T进行编码，编码采用长度为n-1的定长方式，设计种群的编码方式为满足均匀分布的浮点数编码，即编码的每一位hj都是区间[(qj+1-qj)/vjmax,A]上均匀分布的随机数，其中A为一个足够大的常数。

适应度函数，根据类冒泡随机排序的结果确定适应度函数的大小。

选择算子，模仿生物进化过程中优胜劣汰的法则，采用轮盘赌的方法，

交叉算子，采用算数交叉方式交叉，具体方式如式(13)所示。

x′=pcxi+(1-pc)xj

(13)

式(13)中：xi、xj为随机选择的父代个体，x′为交叉产生的新个体,pc为交叉概率。

其中:pcmax、pcmin为交叉最大概率和交叉最小概率，Fmax、Favg为种群最大适应度和种群平均适应度。

变异算子，采用非一致实值变异方式，具体方式如式(14)所示。

(14)

1.5 时间最优轨迹规划的步骤

基于以上分析，基于改进遗传算法的时间最优轨迹规划步骤如下：

(1)根据测量工艺确定笛卡尔坐标系中测量关键点，通过机器人逆运动学将关键点映射到各个关节空间中，得到关节空间中的关键点位移值。

(2)根据关节关键点位移值和初始化种群中的时间间隔序列，进行三次样条轨迹的插值计算，获得轨迹速度、加速度及加加速度参数，进而计算目标函数值及罚函数值。

(3)结合目标函数值及罚函数值以随机排序法对种群个体排序。

(4)对排序后的种群个体分配适应度。

(5)种群进行遗传操作。

(6)判断是否达到遗传代数，如果是，进入步骤(7);否则，回到步骤(2)。

(7)将改进遗传算法得到最优轨迹的各段时间间隔输出，得到轨迹的位移、速度、加速度和加加速度曲线。

2 仿真模型的建立

如图3所示，以某气动量仪测量圆柱轴承滚子的自动化测量工艺路径为例，该机械手需要完成抓取、测量、分类等动作，以机器人末端手爪相对于机器人基坐标的位置p=[x,y,z]T和姿态R表示机器人末端手爪的位姿T，其中姿态R使用RPY角方式表示。该目标路径工作所需的关键点如表1所示。

表1 轴承圆柱滚子自动化测量工艺路径过程

仿真模型采用Stanford Manipulator机器人，DH参数如表2所示，机器人各关节的约束如表3所示。根据自动化测量工艺路径分析得到的各关键点相对于机器人坐标系的位姿，通过MATLAB中robot toolbox计算机器人逆运动学，得到机器人移动路线对应关节空间中的各关节关键路径点角位移值如表4所示。结合谢菲尔德(Sheffield)遗传算法工具箱完成遗传算法优化过程。

表2 机器人DH参数

表3 机器人各关节的约束

表4 机器人移动路线关键点对应关节角度

3 仿真结果及分析

在关节路径规划中，一次处理机器人的1个关节，以仿真模型中的关节1为例，将关节1路径关键点输入改进遗传算法优化模型，设置遗传算法参数：种群规模为100、进化代数200代。遗传算法计算收敛曲线函数运行优化过程，优化过程的收敛曲线如图4所示，规划轨迹在进化60代后得到最优解。

在三次样条插值轨迹规划中采用改进遗传算法和采用模式搜索法[10]都可以得到满足速度、加速度连续，加加速度满足约束的各阶段时间间隔，如图5和图6所示。但采用改进的遗传算法得到的结果比模式搜索法整体缩短了36.93%的时间，两种方法各阶段具体优化时间间隔对比如表5所示，可以看出模式搜索法可以找到问题的可行解，但改进遗传算法对全局最优解的搜索能力远高于模式搜索法。

表5 优化路径时间间隔对比

4 结语

(1)本文详细阐述了三次多项式插值拟合关节空间中关键点的方法，说明了关节轨迹在关节关键点确定的条件下取决于各关节关键点加速度的理论依据，推导出了在边界条件为初末速度时根据关键点之间时间间隔和关键点位移值计算关节轨迹的方法，建立了测量机器人时间最优轨迹规划的数学模型。

(2)针对测量机器人时间最优轨迹规划问题，通过提出一种随机排序法改进遗传算法。基于机器人自身的约束和机器人测量工艺确定的路径关键点，建立仿真实验模型，以斯坦福机器人关节1路径关键点为例仿真得到的优化轨迹与采用模式搜索法相比优化得到的总时间缩短了36.93%，达到了良好的效果。其他关节仿真优化过程与结果与关节1类似，故不再赘述。