基于改进性遗传算法的Bezier曲线笛卡尔空间轨迹规划

周 苑

（上海交通大学 电子信息与电气工程学院，上海200240）

一般而言，对于机械手臂的空间轨迹规划可分为关节空间规划和笛卡尔空间规划两种[1]。其中，关节空间规划计算量小，且在关节空间的轨迹规划中能满足机器人运动学约束条件，从而能够保证机器人运动平稳，对机器人的冲击小；笛卡尔空间轨迹规划则能更好地满足运动精度的要求，能对机器人运行的轨迹做更精确地跟踪，在很多需要提高轨迹精度的场合，如一些焊接机器人上，一般都采用笛卡尔空间轨迹规划。

在空间轨迹规划的研究中，文献[2] 中利用三次多项式插值算法和防止加速度突变的三次样条插值算法对四自由度教学机器人进行运动轨迹规划，使得书写的字体笔划平滑、稳定。文献[3] 中则在保证工作精度的情况下，对机器人运动轨迹规划做优化调整，使机器人的运动轨迹时间最优化。文献[4] 中，在机器人B样条运动轨迹插值中引入了遗传算法控制每段样条曲线插值的分段时间，大幅度地提高了机器人移动所需的时间。Kim等[5]基于机械手的动力学模型，在关节空间中设计了一种满足力矩约束的最小时间路径规划方法。Shiller等[6]在综合考虑了工作环境中障碍物的影响以及机械手关节运动的约束后，提出了一种机械手的最优时间动作规划算法。Gasparetto[7-8]也提出了2种以时间最优的轨迹规划方法。但上述算法都只针对了关节空间的轨迹规划，且都只考虑时间最优，不针对路径精确度。

在笛卡尔空间曲线拟合的研究中，文献[9] 中利用自适应算法满足一定空间精度要求的最少节点有理B样条曲线的拟合，并在叶片造型上应用，但算法损失了空间精度。文献[10] 中利用退火算法结合节点最少的最优化有理B样条曲线拟合，迭代计算量大，遗传最大代数达到500。文献[11-12] 中提出平面曲线拟合中可能出现的精度问题以及一些解决的方案。

本文研究利用机器人进行汉字书写。鉴于中国书法要求笔画圆润、精确，因此，要求机器人的关节空间规划快速，同时，还要保证运行轨迹精确与平滑，故进行笛卡尔空间轨迹规划尤为重要。本文针对笛卡尔空间轨迹规划计算量大、算法复杂等缺点，设计一种改进的遗传算法。该算法从初始种群中剔除不良基因，并对每次种群进行评估，利用MatLab中的遗传工具箱运行程序。实验结果表明，与传统遗传算法相比，本文方法不但避免了遗传算法随机性大、计算量大的特点，还提高了收敛速度。

1 Bezier曲线

Bezier曲线是1962年由法国雷诺公司的工程师Bezier提出的一种曲线逼近方法。四阶三次Bezier曲线包含4个控制点和一个节点向量，曲线方程[13-14]为

式中，P0，P1，P2，P3为4个控制点。

本文采用4次Bezier曲线拟合随机产生N个控制点，同时按照给定型值点的数目产生N-2个节点向量，用于分析误差。控制顶点的数量若无指定一般为4个，但也可以根据需要由用户自定义；对于精度较高的场合可以适当调高控制顶点的数量来实现分段逼近。本文采用最小二乘法计算误差，即逼近曲线的节点和用户指定型值点之间的距离最小。由m个Bezier曲线节点坐标和实际跟踪曲线的累积误差产生的距离为

式中，P（ti）为实际跟踪曲线节点坐标；Q（i）为Bezier曲线坐标。

由于遗传算法随机性较大，故规定Bezier曲线的起点、终点始终与用户指定型值点的起点、终点相同，以减少遗传算法的随机性，这样也能减少计算机的计算量，对后期的最优收敛也有一定辅助作用。故有

式中，P（t0），P（tn）为实际逼近曲线起点坐标与终点坐标；Q（0）和Q（n）为Bezier曲线型值起点和终点。

实际计算中，在遗传算法中加入跟随误差率变化的变异因子，即当判断误差小于一定误差后，可以随时调整遗传算法中的变异率，甚至可以直接停止计算。虽然在计算的初期阶段，变异率较高，误差有所增大，但是在后期整体收敛阶段改进效果明显，收敛速度明显加快。

2 改进的遗传算法

2.1 遗传个体的编码

遗传算法的编码主要分成3类，本文选用二进制编码方式。个体表述为默认4个控制点的x、y坐标和N-2个节点向量。个体编码时，采用随机方法产生4个Bezier曲线控制点，包括起点和终点，范围为0～200。依据给定的路径点数目产生N-2个节点向量，用于比较Bezier曲线上的点和实际需要追踪的路径点的误差。N-2个节点向量是0～1之间的随机小数，按递增顺序排列，但不包括边界。依据上述设计，并编写FieldD矩阵。

2.2 遗传适应度函数

在遗传算法中，适应度越大的个体被遗传的可能就越大，故需要编写适应度函数来计算每个个体的适应度。本文的适应度函数为

2.3 遗传交叉因子与遗传变异

与自然进化一样，子女拥有父母的一部分染色体特征，集成父母的遗传因子。本文采用多点交叉的方式，形成新的染色体。

虽然在下一代染色体中含有一部分的父母染色体，但是自然界中还存在一定数量小概率的基因突变，变异是一种随机事件。本文中，当误差比较大时，取变异率为1.5，这样能变化出更多样化的染色体；而当误差小于一定数值后，变异率改为0.5，以更加精确地逼近目标值，使最终的数值更接近原曲线。

2.4 遗传算法结束条件

当Bezier曲线形成的误差小于指定误差后，算法终止；当遗传代数大于最大遗传代数之后，算法还无法收敛，则自动终止，并返回当前种群中的最优解。

2.5 遗传算法改进

遗传算法中存在大量的不确定因素，故在以往生成曲线顶点时，不考虑初始种群中本身具有的先天缺陷，如顶点围成的多边形本身不是凸多边形而造成绘制的曲线具有尖点曲线、不平滑等。因此，在计算过程中，增加校验环节，使初始种群中的数据都符合凸多边形特性，这样绘制出的Bezier曲线更加的平滑。

3 轨迹规划算法具体步骤

（1）手动输入N个型值比较点。算法随机生成Bezier曲线控制点，且同时产生N个时间节点提供比较，时间节点为0～1的随机数，按由大到小顺序排列。

（2）按遗传算法个体编码产生初始种群，并校验初始种群中先天不足的个体，补充符合标准的个体。计算初始种群的个体适应度，计算其中最优秀的基因进行继承重插。

（3）选择适应度高的个体进行重组。计算种群中最优解的误差率，并按照误差的大小选择变异率。若种群中最优个体误差小于指定误差，则变异率为0.5；若最优个体误差大于最大误差，则变异率为1.5，再产生新的种群。

（4）返回（2），进行个体基因适应度计算，重新计算误差度。判断是否小于指定误差。

（5）若种群中具有个体小于误差，则遗传计算终止，返回最优个体；若计算无法收敛，则当遗传代数大于最大遗传代数后自动停止，最大遗传代数为用户指定，若无特殊指定，则默认最大遗传代数为Gmax＝1 000。

（6）绘制Bezier曲线，按照t＝0.5s的时间间隔，利用Matlab对机器人进行示教点的仿真运行，观察机器人的平面运行轨迹。

4 算法实验

实验计算机环境为Windows XP系统，CPU为Inter Core2，2GB内存。使用汉字笔画中比较难实现的弯折笔画字库模型，利用MatLab 7.1软件进行计算机字模分析。

实验中，提取型值点（20，80；40，80；60，80；50，60；40，30；40，20；60，20；80，20），利用 MatLab的遗传基因工具箱对改进后的遗传算法和传统遗传算法进行仿真模拟。图1所示为弯折笔画字库模型与仿真结果的比较。其中，图1（a）为弯折笔画模型，图1（b）为利用改进后的遗传算法在G＝30时得到的计算结果；图1（c）为利用传统遗传算法在G＝30得到的计算结果。

利用改进后的遗传算法，在算法初期就去除不必要的曲线的尖点，取默认4个控制点的Bezier曲线进行笛卡尔空间曲线逼近。计算出最优的Bezier控制顶点为（20，80；85.249 0，86.813 2；8.603 1，25.809 3；80，20），最 优 时 间 节 点 为（0.906 6，0.463 0，0.323 0，0.723 7，0.319 1，0.747 1）。由图可见，计算结果收敛明显，算法优化效果显著。

而利用传统遗传算法计算[10]不仅计算迭代次数增加，而且还导致Bezier曲线的尖点，由图1（c）可见，计算结果收敛性差。

图1 弯折笔画字库模型与仿真结果的比较Fig.1 Comparison of bending font model simulation results

5 结 语

本文针对笛卡尔空间轨迹计算量大、算法复杂等缺点，设计了一种改进的遗传算法，分段跟踪Bezier曲线的各部分，使机器人运行平衡，路经圆滑平顺。通过实验测试表明，选用遗传算法计算机器人路径进行笛卡尔空间规划不仅精度提高，计算过程也相对简单，对于需要精确跟踪轨迹的场合非常合适。但是遗传算法本身随机性比较大，导致每次计算的路径结果都不相同，在需要重复路径的场合还需要进行路径存储来节省更多的计算时间，减少不确定性。

[1] 蔡自兴.机器人学[M] .2版.北京：清华大学出版社，2009.

[2] 马晓花，孔庆忠，马为民，等，四自由度写字机器人轨迹规划研究[J] .机械工程与自动化，2010（5）：161-163.

[3] 李东洁，邱江艳，尤 波.一种机器人轨迹规划的优化算法[J] .电机与控制学报，2009，13（1）：123-127.

[4] 陈 丹.基于遗传算法的B样条曲线优化在机器人轨迹规划中的应用[D] .武汉：武汉科技大学，2007：3-4.

[5] Kim B K，Shin K G.Minimum-time path planning for robot arms and their dynamics[J] .IEEE Transactions on Systems，Man，and Cybernetics，1985，15（2）：213-223.

[6] Dubowsky S，Blubaugh T D.Planning time-optimal robotic manipulator motions and work places for point-to-point tasks[J] .IEEE Transactions on Robotics and Automation，1989，5（3）：377-381.

[7] Gasparetto A，Zanotto V.A technique for timejerk optimal planning of robot trajectories[J] .Robotics Computer Integrated Manufacturing，2008，24（3）：415-426.

[8] Gasparetto A，Zanotto V.Optimal trajectory planning for industrial robots[J] .Advances in Engineering Software，2010，41（4）：548-556.

[9] 周红梅，王燕铭，刘志刚，等.基于最少控制点的非均匀有理B样条曲线拟合[J] .西安交通大学学报，2008，42（1）：73-77.

[10] 刘 彬，张仁津.基于退火遗传算法的NURBS曲线逼近[J] .山东大学学报：工学版，2010，40（5），96-100.

[11] 张银娟，王永科.遗传算法在 NURBS曲线拟合精度的研究应用[J] .自动化仪表，2012，33（1）：9-11.

[12] 张聚梅，王洪伦.基于遗传算法和模拟退火算法的B样条曲线拟合[J] .计算机工程与科学，2011，33（3）：191-193.

[13] 王幼民，徐蔚鸿.机械臂关节空间Bezier曲线轨迹规划[J] .安徽机电学院学报，2000，15（3）：59-64.

[14] 王幼民.机器人关节空间Bezier曲线轨迹优化设计[J] .机械科学与技术，2001，20（3）：350-352.

[15] 王春武，刘春玲，姜文龙.基于VB 6.0的点阵字模信息提取方法[J] .计算机工程，2010，36（11）：283-284.