多目标优化算法在冗余机械手逆解中的应用.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 第 38卷增刊 1 8月中南大学学报(自然科学版)J. Cent. South Univ. (Science and Technology)Vol.38Suppl.1Aug. 多目标优化算法在冗余机械手逆解中的应用李 胜, 申晓宁, 陈庆伟, 胡维礼(南京理工大学自动化学院, 江苏南京, 210094)摘 要: 针对带有 N个关节的冗余机械手运动学逆解问题, 提出了一种改进的多目标优化遗传算法。与传统的机械手逆解方法相比, 所提算法不但考虑了使终端执行器精确地到达期望位置的目标, 而且同时优化了关节转动角、 机械手柔顺性、 与障碍物之间的距离 3个目标。在算法群体的初始化及子代群体的生成中, 采用了一种新型的个体生成方式以满足约束条件的限制; 在选择算子中, 引入了防止算法早熟收敛的机制。仿真结果表明, 所提算法能够有效地求解具有多个优化目标的机械手运动学逆解问题。关键词: 多目标优化; 遗传算法; 冗余机械手; 运动学逆解中图分类号: TP24文献标识码: A文章编号: 1672-7207( )S1059805Application of multi-objective optimal algorithm inkinematical inverse of hyper redundant manipulatorLI Sheng, SHEN Xiao-ning, CHEN Qing-wei, HU Wei-li(School of Automation, Nanjing University of Science and Technology, Nanjing 210094, China)Abstract: An improved multi-objective optimization genetic algorithm was proposed for solving kinematical inversesolutions of the redundant manipulator. Compared with the traditional methods, the proposed algorithm not only made theend-effector reach the desired position precisely, but also optimized three objectives that were turning angles of joints,flexibility of the manipulator and the distance to obstacles. A new method to create individuals satisfying the constraintswas proposed in the initialization of the algorithm and in generating child population, and a mechanism that preventedpremature of the algorithm was incorporated in the selection operator. Simulation results indicate that the proposedalgorithm can solve kinematical inverse solutions of the manipulator with multiple optimization objectives effectively.Key words: multi-objective optimization; genetic algorithm; redundant manipulator; kinematic inverse solution机械手运动学逆解问题是机械手控制中研究的基本问题之一。当前求解机械手运动学逆解问题的方法主要有以下 3类1: 代数法2、 几何法34、 数值迭代法56。已有的这些方法虽然均能够较有效地解决冗余机械手的逆解问题, 但大多数算法在求解时, 只考虑了一个目标, 即如何使末端执行器较为精确地到达给定位置, 而没有考虑机械手的柔顺性、 安全性等性能指标。为国内外学术界的一个研究热点7。MOEAs对问题的多个目标同时优化, 算法运行一次便能够并行得到问题的一组 Pareto最优解。决策者能够依据问题的当前需要, 从中挑选出一个或一些”足够满意”的解作为多目标优化问题的最终解。SPEA28是瑞士学者 Zitzler在 年提出的一种高效的多目标优化遗传算法, 它基于 Pareto支配的概念进行适应值分配和选择操作, 并采用小生境法和精英保留的机制。本文作者针对冗余机械手运动学逆解多目标优化进化算法 (简称 MOEAs)近年来已成收稿日期: 0420基金项目: 国家自然科学基金资助项目(60474034); 江苏省博士后科研基金资助项目(0502027B)作者简介: 李 胜(1976), 男, 江苏徐州人, 博士, 从事机器人系统的开发与研究通讯作者: 李 胜, 男, 博士; 电话: ; E-mail: 增刊 1李 胜, 等: 多目标优化算法在冗余机械手逆解中的应用599问题具有较强的约束条件的特点, 采用了一种新型的个体生成方式; 并在 SPEA2的选择算子中加入了防止算法早熟收敛的策略。与已有冗余机械手逆解算法相比, 本文作者提出的算法在求解时, 不但考虑了使其终端执行器精确地到达给定位置, 而且同时优化了冗余机械手的关节转动角度、 柔顺性、 安全性等目标。置为 Pgoal = xgoal, ygoal T, 求取一组满意的*, 使得: * = arg min f1(), f 2 (),., f m ()(2)且*对目标位置 Pgoal = xgoal , ygoal T满足冗余机械手的运动学正解方程式(1), *对应的机械手位置与障碍物无交点。式(2)中, = 0,1, N1; fi()表示目标函1 问题描述数, j=1, 2, , m。考虑冗余机械手自身的一些特点和真实环境中可能出现的一些情况, 选取如下几个性能指标作为上述多目标优化问题的目标函数:1.1 数学模型本文主要研究一类平面型冗余机械手的运动学逆解问题。此类机械手在电子制造、 生物制药和食品加工等场合得到大量应用, 较常见的主要有三关节和四关节平面型冗余机械手 2类。1) 各关节转动角度 f1(): N1f1() =(0 ini 2 +( ) (i1 )i ini ini 2i i1(3)0i=1为使本文提出的算法更具有通用性, 在研究时, 以图 1 所示的带有 N 个转动关节的平面型机械手为例。为了减少能量的消耗, 当机械手从初始位置运动到目标位置时, 各关节连杆转动的角度应尽可能小。2) 机械手柔顺性 f 2 (): N1以机械手基底位置作为坐标原点, 其运动学正解方程如下: f 2 () =i (i i1) 2(4)i=1其中, 1 =1; N1x =y =li+1 cosiC(t) , if (i i1)(i1 i2) 0, i=2, , N1i=0(1)i = 1,N1otherwiseli+1 sinii=0为了便于机械手更好地工作, 应尽可能保持各相邻关节转角的偏转方向一致, 如图 2所示, 偏转角度q1和 q2的方向应尽量一致, 且 q1和 q2的绝对值越小越好( qi =i i1, i =1,2, qi , ), 以保证机式中: x,yT 表示终端执行器的位置; li+1 表示各连杆的长度, i表示各关节的转角, i, , i=0, 1, ,N1。械手具有较好的柔顺性。当第i ( i = 2, N 1)个关节转角的偏转方向与它前一个关节转角的偏转方向不一致时, 即 (i i1)(i1 i2) 0。对 f2()的第 i项施加惩罚因子 C(t)=t1/2, 其中 t为算法的进化代数, 随着 t的增加, 惩罚项增大。3) 机械手整体安全性 f3(): f3() =1 ds(5)式中: ds表示整个机械手距离所有障碍物的最短距离。当关节转角 对应的机械手位置与障碍物有交点, 即 不可行时, 应对它的目标函数值进行惩罚。记 fi,worst (i =1,2,3)为当前群体中所有可行解在目标函数 fi上的最差值, 则对不可行解 , 令图 1带有 N个转动关节的平面型冗余机械手Fig.1 Redundant planar manipulator with n jointsfi ( ) = fi,worst + n Di, i =1, 2, 3(6)本文冗余机械手运动学逆解问题的数学模型可表述为: 设机械手的工作环境为二维平面, 其中存在若干个障碍物。已知机械手各关节的初始转角为iini (i=0, 1, , N-1), 要求终端执行器到达的目标位其中: n 为 对应的机械手位置与障碍物交点的个数; Di为一个适当的正数。式(6)保证了不可行解的所有目标函数值均差于可行解。 600中南大学学报(自然科学版)第 38卷的 N2、 N1, 组成完整的个体 。若对某个向量0,1, N3, 式(1)无解, 则重新随机生成一个N 2维的向量, 直到式(1)有解为止。2.2 适应值评价和选择算子依据其相应的 3个目标函数值, 为当前群体中的每个个体分配一个适当地反映其优劣程度的适应值, 然后从中选择出若干个适应值较优的个体, 进行遗传算子的操作。图 2关节转角的偏转方向示意图本文使用 SPEA2的适应值分配策略。设置一个外部存储器保存算法在进化过程中搜索到的 Pareto支配解。在为每个个体分配适应值时, 综合考虑群体和外部存储器中支配该个体及受该个体支配的其余个体的数目, 该方法体现了基于 Pareto支配概念的小生境机制9, 避免了以往基于距离的小生境法中小生境范围(距离参数)难以确定的问题。当两个个体的适应值相同时, 引入密度信息(第 k个最近邻居估计法9)对它们的优劣进行区分。Fig.2Schema of joint rotators direction1.2Pareto最优解多目标优化问题的多个目标之间往往是相互矛盾的, 因而不存在一个最优解能够使得所有的目标同时达到最优。求解多目标优化问题一般使用 Pareto最优解的概念。定义 (Pareto 最优解): 假设求解最小化问题, F = ( f1, f 2, f m )为目标向量, X 为问题的决策空间。如果不存在任何 x X , 使得 fi (x) fi (x*), SPEA2 的选择算子分为交配选择和环境选择两种。交配选择采用二进制联赛法。环境选择用来确定新一代外部存储器中保存的个体。本文对 SPEA2的环境选择算子做了改进: 在判断某个解是否应加入外部存储器中时, 需考察当前外部存储器中是否已存在与之相同的解, 若存在, 则阻止该解进入外部存储器。这样做的目的是防止某个适应值较好的个体在后代群体中迅速繁殖和扩张, 从而避免了早熟收敛。2.3 遗传算子i(1, m), 而且 f j (x) f j (x*), j (1, m), 则 x*是多目标优化问题的一个 Pareto最优解。一个多目标优化问题一般存在多个 Pareto 最优解, 这些解共同构成了问题的 Pareto最优解集。2 算法描述 本文采用模拟二进制交叉算子 (SBX)和多项式变异算子10。文献10的结果表明上述两种算子能够有效地对实数编码的个体进行操作。针对上述多目标优化问题, 对经典的多目标优化遗传算法 SPEA2进行了改进。在群体的初始化及子代群体的生成中, 采用一种新型的个体生成方式以满足约束条件的限制; 在选择算子中 , 加入了避免外部存储器中出现相似个体的机制, 以防止早熟收敛。2.1 个体的编码和群体的初始化2.4 算法的步骤本文算法的步骤如下: 1) 初始化:生成规模为 np的初始群体 O(0), 设置一个初始为空的外部存储器 A(0), 设进化过程中外部存储器的大小固定为 M, 最大进化代数为 T, 计数器t=0; 冗余机械手的运动学正解方程式 (1)是一个很强的约束条件, 如果直接对个体 = 0,1, N1进2) 适应值评价: 对 O(t)和 A(t)中的所有个体计算行编码并实施遗传算子的操作, 算法难以求得满足式(1) 的 可 行 解 。 本 文 取 的 前 N 2 个 元 素0,1, N3作为自由参数进行实数编码, 参与进化操作; 而的后两个元素 N2、 N1由0,1, N3适应值; 3) 环境选择: 把 O(t)和 A(t)中所有的非支配解加入 A(t+1)。如果 A(t+1)的规模超过 M, 则采用基于密度信息的”裁减”法 6移除多余的非支配解; 反之, 则再选取若干个适应值最优的支配解添入 A(t+1), 直到它保存的解的个数达到 M为止; 根据式(1)采用解析法求得。这种方法能够保证每个个体均满足式(1)的约束。群体的初始化采用随机生成法。设算法的群体规模为 np, 则在, 内随机生成 np个 N 2维的向量0,1, N3, 把每个向量分别代入式(1)求得相应4) 交配选择: 采用二进制联赛法从 A(t+1)中选择出部分较优解组成交配池; 增刊 1李 胜, 等: 多目标优化算法在冗余机械手逆解中的应用6011.8,2.6T。机械手的工作环境中存在3个障碍物。本文算法的运行参数为: 群体规模np与外部存储器的大小M均取30, 交配选择中的联赛规模取为2, 最大进化代数T取50, 交叉概率为0.9, 变异概率为1/3。5) 遗传操作: 在交配池中, 对所有个体的前 N2个元素构成的参数群体进行遗传算子的操作, 把生成的每个参数向量依次代入式 (1)求取相应的另两个元素, 以构成完整的子代个体。若对生成的某个参数向量, 式(1)无解, 则从交配池中随机选取两个个体重新进行交叉和变异操作, 直到产生的参数向量代入式(1)有解为止。把生成的子代群体作为新一代的群体O(t+1); 本文算法只需运行一次, 便能够得到上述问题的一组非支配解(近似 Pareto最优解)。从这组解中挑选 4个具有代表性的解作为示例, 如图 3所示(图中实线表示机械手的初始位置, 虚线表示终端执行器到达目标位置时机械手所处的位置)。6) 终止准则: 如果 tT, 则把 A(t)中所有非支配解组成的集合作为问题最终的 Pareto最优解集输出, 算法终止; 否则, t=t+1, 转到第 2)步。从图 3能够看出, 图(a)对应的解其转动角度 f1性能很好, 柔顺性 f2 也较好, 但安全性 f3 却很差; (b)对应的解柔顺性 f2很好, 转动角度 f1和安全性 f3一般; (c)对应的解安全性 f3很好, 但转动角度 f1和柔顺性 f2较差; (d)表示的解在 3个目标上的性能比较平均, 都不是最好也不是最差。表 1分别给出了图 3各子图所对应的解在 3个优化目标上的值。3 示例分析为了验证本文算法的有效性, 以带有 5个转动关节的平面型机械手运动学逆解问题作为示例。机械手的连杆长度分别为: l1=1.2, l2=1, l3=0.8, l4=0.6, l5=0.4, 总 长 度 为 4 ; 机 械 手 各 关 节 的 初 始 转 角 为 = 6, 3,11 18,5 6,17 18; 终端执行器的初由此可见, 利用本文给出的冗余机械手多目标优化逆解算法, 决策者能够较容易地搜索到一组多样性较好的非支配解。这组解在给定的目标函数上各有侧重, 决策者能够根据当前的需求, 从这组非支配解中挑选出一个足够满意的解作为最终解, 即机械手终端始位置为 Pini=0.325 ,2.44 8T, 目标位置为 Pgoal=(a) 转动角指标 f1很好, 柔顺性指标 f2较好, 安全性指标 f3一般; (b)柔顺性指标 f2很好, 转动角指标 f1和安全性指标 f3一般;(c) 安全性指标 f3很好, 转动角指标 f1和柔顺性指标 f2较差; (d)转动角指标 f1、 柔顺性指标 f2, 安全性指标 f3较为平均图 3冗余机械手逆解问题非支配解的示例Fig.3Example of non-dominated resolutions of redundant manipulators kinematical inverse 602中南大学学报(自然科学版)第 38卷执行器到达目标位置时各关节的转角。与文献9中所给出的同类型冗余机械手逆解算法相比, 本文给出的算法不但考虑机械手终端执行器如何到达给定位置, 而且同时考虑了机械手自身的柔顺性与安全性等指标, 较大程度上提高了计算结果的多样性。2 Manocha D, Canny J F. Real time inverse kinematics for general 6R manipulatorsC/ Proc 1992 IEEE Intl Conf Robotics & Automation. Los Alamitos: IEEE, 383389. 3 祖 迪, 吴镇炜, 谈大龙. 一种冗余机器人逆运动学求解的有效方法J. 机械工程学报, , 41(6): 7175. ZU Di, WU Zhen-wei, TAN Da-long. Efficent inverse kinematic solution for redundant manipulatorsJ. Chinese Journal of Mechanical Engineering, , 41(6): 7175. 表 1图 3中各运动学逆解的目标函数值Table 1 Objective functions values of every kinematicalinverse in Fig.34 Chung W J, Youm Y, Chung W K. Inverse kinematics of planar redundant manipulators via virtual links with configuration indexJ. Journal of Robotic Systems, 1994, 11(2): 117128. 图形编号转动角 f10.88754.51108.00612.8953柔顺性 f2 安全性 f3(a)(b)(c)(d)1.11940.95963.89581.312425.55616.32023.03884.74375 周友行, 何清华, 邓伯禄. 一种改进的爬山法优化求解冗余机械手运动学逆解J. 机器人, , 25(1): 3538. Zhou You-xing, HE Qing-hua, ZHENG Bo-lu. An ameliorative ”Mountain Climbing” arithmetic to solve inverse kinematics of redundant manipulatorJ. Robot, , 25(1): 3538. 4 结 论6 LU Bao-liang, Ito K. Regularization of inverse kinematics for redundant manipulators using neural network inversionsC/ Proc of IEEE International Conference on Neural Networks, New York: IEEE, 1995, 5: 27262731. 针对多关节冗余机械手的逆解问题, 在 SPEA2算法的基础上, 提出了一种适用于冗余机械手运动学逆解问题的多目标优化遗传算法。该算法采用的新型的个体生成方式有效地处理了冗余机械手运动学正解方程这一较强的约束条件; 在选择算子中引入基于密度信息的”裁减”策略, 剔除外部存储器中出现的相同个体, 有效地防止了算法早熟收敛。仿真结果表明, 本文算法经过较少的迭代次数, 便可产生一组多样性较好的非支配解, 供决策者根据不同的工作目标与实际情况进行选择。由此可见, 本文算法适用于求解具有多个(2)目标的冗余机械手运动学逆解问题。7 8 Abraham A, Jain L, Goldberg R. Evolutionary multiobjective optimizationC/ Theoretical Advances and Applications. USA: Springer, . Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength pareto evolutionary algorithmC/ Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Athens, Greece, : 95100. Zitzler E, Laumanns M, Bleuler S. A tutorial on evolutionary multiobjective optimizationJ. Metaheuristics for Multiobjective Optimisation, , 2(1): 337. 9 参考文献: 10 Deb K, Agrawal R B. Simulated binary crossover for continuous search spaceJ. Complex Systems, 1995, 9(2): 115148. 1 Krieger C, Hosticka B J. Inverse kinematics computations with modified CORDIC iterationsJ. IEE Proc Computer Digital Techniques, 1996, 143(1): 8792. (编辑 彭超群)