基于改进遗传算法的并联机器人分拣路径优化*

张好剑 苏婷婷 吴少泓 郑军 王云宽

(中国科学院 自动化研究所∥中国科学院大学, 北京 100190)

Delta并联机器人[1]是应用最为成功的并联机构之一[2].近年来，工业需求的巨大刺激使得Delta并联机器人的研究与应用呈现轻量化、高速、高灵活性等趋势[3]，特别是在筛检、装箱等重复性劳动的流水线应用中最为常见，所以提高其工作效率是提高产业效益的重要途径.结合机器视觉的Delta并联机器人分拣系统比传统的分拣流水线更能适应多变的作业环境，显著地提高生产效率，增强机器人的环境适应能力.但是目前其分拣路径的策略普遍采用固定的模式，即并联机器人一直分拣传送带方向最前方的物料，未能充分发挥自动化生产的优势.随着智能控制技术的发展，很多智能算法逐步地应用于工业控制领域，并充分挖掘系统的性能、提高生产效率，因此引进了机器视觉和智能控制算法的并联机器人分拣系统具有广阔的应用前景.

为了满足当前高速化的生产需求，提高生产效率，国内外许多学者对最优时间轨迹规划进行了深入研究，大多采用三次多项式、高阶多项式及B样条曲线等方法在操作空间或关节空间对机器人进行轨迹规划，得到了速度、加速度及转矩连续的运行曲线，保证了机器人运行的稳定，减少了对机械的刚性冲击，相关研究工作见文献[4- 8].但是从文献中可以看出，学者们所做的研究都集中在对单个分拣轨迹的优化，如单个门形轨迹的平滑处理等，而在分拣系统中,Delta并联机器人的工作流程是分拣连续不断的物料，是由无数个拾取轨迹组成的，但当前对整个分拣路径的优化还鲜有报道.

针对以上问题，对于分布密集的对排布方向无要求的物料(比如圆饼型锂电池)实时分拣系统.文中把分拣流水线按照节拍进行分组处理，以装满一个包装盒托盘为基准节拍，提出了一种基于改进遗传算法的分拣路径优化方法，在保证每个分拣门形轨迹进行最优化处理的同时，对处于每一个节拍中的所有物料进行基于改进遗传算法的动态目标最短分拣路径的整体路径规划，以易于理解和实现，并保证实时性；建立并联机器人与周围模型的紧密联系，旨在实时快速抓取操作，增强系统的适应能力，提高并联机器人系统的作业效率.

1 单个分拣轨迹的优化

1.1 问题背景

如图1所示，Delta并联机器人分拣系统由视觉模块、机器人模块、传送带模块以及控制系统组成.随机分布的无排列方向要求的物料随传送带匀速进入到视觉采集区时，工业相机以频率f采集物料的图像信息，然后采用文献[9]中单目视觉系统摄像机快速标定方法，解决视觉系统的精度问题，同时利用不重复识别跟踪算法，获得全局坐标系下精确的物料坐标信息，传送给控制系统，控制系统根据物料的位置信息并结合相机触发的时间信息，再对这一节拍内物料的分拣路径进行规划优化，然后向 Delta机器人发送运动指令，拾取零散的物料并整齐地放置到指定托盘上，完成分拣操作.

图1 并联机器人分拣系统结构图Fig.1 Structure diagram of parallel robot sorting system

平面模型如图2所示，下方虚线框区域是并联机器人的最大工作区间，建立全局坐标系BASE，原点位于并联机器人最大工作区间右边中点，X、Y方向如图所示，传送带位于图2的左半部分，传送带上端的虚线框内为工业相机的图像采集区域；下半部分穿过并联机器人的工作区域，且以速度vcov由上向下传输物料(图2中圆圈表示分布的物料)，图的右边为目标托盘，目标托盘必须位于工作区域内.

1.2 轨迹优化

由于分拣流水线要求Delta并联机器人的高速运行，因此高速运动的机器人在外力与惯性力作用下，其构件的弹性变形等因素不仅影响了机构的精度、破坏系统运行的稳定性和可靠性,同时降低了工作效率和整机的使用寿命.为了保证运行的平稳，减少振动和冲击，必须对并联机器人的运行空间轨迹进行优化.针对分拣系统的动作特点，文中采用文献[10]的方法，将Delta并联机器人末端执行器的运动轨迹近似门形，采用圆弧连接直线规划.将门形抓取动作拆分为5个部分(如图3所示)，其中Q0—Q1、Q2—Q3和Q4—Q5采用直线插值，长度分别为S01、S23、S45,Q1—Q2、Q3—Q4采用圆弧插值，长度为S12和S34，总的行程用Stotal表示.

图2 平面布局图Fig.2 Layout plan

图3 笛卡尔空间轨迹规划Fig.3 Trajectory planning in Cartesian space

在确定了使用圆弧平滑直角过渡区域后，下一步的工作就是沿着轨迹采样获得插补点的位置、速度、加速度序列.从减少加减速时间、运动平稳等指标出发，必须使用专门的柔性加减速控制方法.目前常见的直线加减速、直线加抛物线加减速、指数型加减速等方法在初始和结束阶段的加速度突变不连续，都不满足高速Delta并联机器人的控制要求；七段式S曲线加速度连续，加加速度有上界，在高速数控系统中应用广泛[11]，但加加速度在切换时有突变，并且对于段数的确定及时间的计算较为复杂.为了减少刚性冲击，文中选用加减速更为柔顺、计算更为简单的修正梯形加减速算法[12]，此算法是以正余弦函数为过渡段的加减速曲线，其加速度规划如下:

(1)

式中：amax为Delta并联机器人终端执行器的最大加速度，t为减速度表达式的时间自变量，T为加、减速阶段时间总和.

该算法加速度曲线变化柔顺，对加速度求导可知其加加速度无突变.式(1)两侧对时间连续 2 次积分并代入边界条件可得位移表达式：

(2)

从式(2)可以看出，当t=T/2时速度达到最大，即终端执行器在前T/2的时间处于加速过程，后T/2的时间处于减速过程，远远不能满足高速生产的需求；并联机器人在高速运行过程中，加减速的时间很短，其余阶段都以最大的速度vmax运行，所以必须继续对式(2)进行改进，中间增加匀速运行的阶段，速度为vmax.改进后加减速的时间周期仍为T，可以得出加减速的时间为

(3)

总的运行时间Ts1为

(4)

式中，Ss1为轨迹S1的行程长度.

2 整体分拣路径优化

2.1 问题描述

如前文所述，虽然国内外的学者和企业针对Delta并联机器人做了比较全面的研究[13]，但是在提高效率方面，研究的焦点基本上集中在对单个分拣轨迹的优化上，忽略了对整体分拣路径的规划，导致目前分拣流水线上的分拣路径方法单一，因此效率的提升空间很大，缩短分拣的总体行程就是关键的技术之一.而且基于最短路径的分拣路径规划的研究比较常见，但Delta并联机器人的分拣路径优化有很大的不同，此路径规划与作业环境联系紧密，如传送带速度、物料分布密度、相机的拍摄频率等都与其有直接关系.

针对以上问题，结合前文提到的分节拍进行分拣和轨迹优化，提出一种基于改进遗传算法的针对动态变化目标的分拣路径规划方法，以缩短Delta并联机器人的分拣行程、提高拾取效率、增强适应能力，具体流程如下.

2.2 流程分析

寻求分拣的最短路径，建立数学模型，可以看出此模型类似于旅行商(TSP)问题，同时，分拣路径优化具有更多的约束条件.若把传送带上的物料和托盘整齐排列的码放位置当做两大城市群，末端执行器当做旅行商，可以看出：物料城市群位置动态变化，旅行商在两大城市群交替穿行等.而有很多关于TSP问题的研究采用粒子群算法、蚁群算法等，他们都是针对静止的城市群分布进行规划优化，没有分析城市群动态变化对规划的影响等.为分析方便，文中以5个城市为例对分拣流程进行说明.

Delta并联机器人终端执行器起始位置为原点O，如图4所示，按照前文优化的门型轨迹进行分拣，门高为b，抓取动作顺序为O→Ai→Bj→Ai+1→Bj+1，可以看出，拾取和放置动作的行程有所不同.

图4 分拣动作流程图Fig.4 Sorting operation flow

(5)

(6)

则

(7)

放置动作：执行器抓取到物料i+1后，放置到定点位置Bj+1,则有：

(8)

其中，S(i+1)(j+1)为点Ai+1到Bj+1放置动作期间终端执行器运行的距离.

以上两步完成一个分拣动作，如此往复循环完成一个节拍的分拣任务，则总的行程为∑Sij.

2.3 改进遗传算法路径优化

2.3.1 遗传算法概述

遗传算法(GA) 是一种模拟生物遗传和进化过程的计算方法，其原理是利用生物界的“物竞天择，适者生存”的进化法则.首先，将待求解问题的参数编码成染色体，然后采用选择交叉和变异等方式运算，交换种群中染色体的信息，最后生成满足优化目标的染色体.其工作流程如图5所示.

图5 遗传算法工作流程Fig.5 Flow chart of genetic algorithm

根据以上流程分析，以一个节拍的分拣为例，利用改进遗传算法进行分拣优化.

2.3.2 编码改进

已知托盘内各目标位置并进行编号(B0-BM)，对同一节拍内传送带上的物料进行编号(A0-AN)，物料位置由工业相机采集得到,则M=N；采用直观路径表示，将染色体定义为一个线性序列.那么随机列举的一条完整的路径编码为(B3→A3→B7→A9→…→Ai→Bj),可以看出编码中编号B和A是交替出现的，为后续的算法顺利进行，文中提出了一种染色体分裂方法，把存在此约束的编码按照奇偶顺序分裂成两条编码，分别为(B3→B7→…→Bj)和(A3→A9→…→Ai)，则后续操作都是对两条编码同时进行的.

2.3.3 适应度函数

适应度函数值是评价一个染色体好坏的依据，与选择算法密切相关，会对实验结果造成直接的影响[14].而分拣路径优化目标函数为路径值最短，因此直接应用分拣路径长度的倒数作为适应度函数值，计算公式简单、快速，得到适应度函数为

(9)

2.3.4 遗传算子改进

遗传算子的选择交叉和变异操作都直接影响遗传算法的效率和收敛速度，而物料分拣路径的约束条件需要在交叉和变异操作中进行设置，因此需要对算法进行相应改进.

选择操作依据个体适应度值的大小，对每个个体采用优胜劣汰的操作，从而产生新的群体[15]，文中采用轮盘赌选择法实现，适应度大的染色体被选中的可能性也大，每个染色体的适应度除以适应度的总和，以此作为每个染色体的选择概率；交叉操作决定了遗传算法的全局搜索能力，按照某种方式对两个相互配对的染色体相互交换其部分基因，从而形成两个新个体，因分拣操作的流程特点，文中对分裂出的两条短的染色体并行地进行交叉操作；变异操作是遗传算法产生新个体的辅助方法，决定了遗传算法的局部搜索能力，以较小的概率对个体编码串上的某个或某些位值进行改变，形成新的个体，与上一步骤类似，文中对分裂的两条短染色体进行并行的变异操作.

2.3.5 迭代循环及终止

经过遗传算子改进作用后的群体，重复上述2.3.2、2.3.3节步骤，直到满足终止条件.由于设定一个明确的收敛性判别标准较困难，文中在满足每个节拍计算的实时性条件下，采用达到预定的迭代次数为终止条件，输出合并后为最终染色体，即最好的分拣顺序.

3 实验验证

采用上面所述的门形轨迹优化和分拣路径规划算法对分拣作业进行优化；机器人的作业区间为800 mm×800 mm的区域，取门形轨迹垂直高度分别为b=100 mm；最大加速度amax=6g，终端执行器的速度上限为vmax=5 m/s，一个节拍的分拣数量M=N=60，改进遗传算法的初始种群数m=100，迭代次数n=200，连续进行10个节拍的分拣优化，通过 Matlab进行测试，随着迭代次数增加改进遗传算法的优化过程如图6所示.

从表1和图6试验结果分析知，改进遗传算法规划分拣路径较固定顺序法整体要优，10个节拍的分拣试验中终端执行器运行路径平均缩短14.76%，有效地提高了作业效率.

图6 10个节拍分拣优化曲线Fig.6 10 beats sorting optimization curves

序号分拣行程/mm随机分拣路径固定分拣路径优化分拣路径缩短百分比/%166135.7976841.9264858.3915.59265373.9580469.7664263.4820.14368230.1175425.6065361.6413.34465912.5278039.3665795.9515.69565870.5176283.8463755.3616.42666856.0373579.8464160.4812.80764708.2784364.1664189.2123.91864529.6767193.9264276.924.34968733.1471126.4066105.367.061066606.2579420.4864908.3318.27均值66295.6276274.5364767.5114.76

4 结论

文中针对分布密集的无排布方向要求的物料分拣流水线提出了一种分节拍的基于改进遗传算法的动态分拣路径优化方法.该算法模型清晰地描述了流水线上物料随机分布和序列严格要求的分拣路径选择优化问题，计算相对简单，易于编程实现.样机测试中终端执行器运行路径比传统的固定分拣策略效率提升14.76%，证明了该算法能够有效地提升系统的作业效率.同时提出的分节拍处理降低了对硬件(如相机和上位机)的要求，完全满足分拣系统的实时性要求，具有较高的准确性和稳定性，适合工程实际应用.

[1] VISCHER P,CLAVEL R.Kinematic calibration of the parallel Delta robot [J].Robotica,1998,16(2):207- 218.

[2] 郎需林,靳东,张承瑞,等.基于实时以太网的DELTA并联机械手控制系统设计 [J]．机器人,2013,35(5):576- 581．

LANG Xu-lin,JIN Dong,ZHANG Cheng-rui,et al.Control system design of DELTA parallel manipulator based on real-time Ethernet [J].Robot,2013,35(5):576- 581.

[3] 刘辛军,谢福贵,汪劲松.当前中国机构学面临的机遇 [J].机械工程学报,2015,51(13):2- 12.

LIU Xin-jun,XIE Fu-gui,WANG Jin-song.Current opportunities in the field of mechanisms in China [J].Journal of Mechanical Engineering,2015,51(13):2- 12.

[4] GASPARETTO A,ZANOTTO V.A new method for smooth trajectory planning of robot manipulators [J].Mechanism and Machine Theory,2007,42(4):455- 471．

[5] BEHZADIPOUR S,KHAJEPOUR A.Time-optimal trajectory planning in cable-based manipulators [J].IEEE Transactions on Robotics,2006,22(3):559- 563.

[6] CONG Ming,XU Xiao-fei,XU Peter.Time-Jerk synthetic optimal trajectory planning of robot based on fuzzy gene-tic algorithm [C]∥Proceedings of International Confe-rence on Mechatronics and Machine Vision in Practice.[S.l.]:IEEE,2009:274- 279.

[7] 王攀峰,梅江平,黄田.高速并联机械手抓放操作时间最优轨迹规划 [J].天津大学学报,2007,40(10):1139- 1145.

WANG Pan-feng,MEI Jiang-ping,HUANG Tian.Time optimal path planning of a 2-DOF high-speed parallel robot [J].Journal of Tianjin University,2007,40(10):1139- 1145.

[8] 张勇,张宪民,胡俊峰,等.高速并联机械手最优时间轨迹规划及实现 [J].机电工程技术,2010,39(10):42- 45.

ZHANG Yong,ZHANG Xian-min,HU Jun-feng,et al.High-speed parallel manipulator optimal time trajectory planning and implement [J].Mechanical & Electrical Engineering Technology,2010,39(10):42- 45.

[9] 张文昌.Delta高速并联机器人视觉控制技术及视觉标定技术研究 [D].天津:天津大学,2012.

[10] 殷国亮,白瑞林,王永佳,等.一种并联机器人的时间最优轨迹规划方法 [J].计算机工程,2015,41(10):192- 198.

YIN Guo-liang,BAI Rui-lin,WANG Yong-jia,et al.A method of parallel robot time optimal trajectory planning [J].Computer Engineering,2015,41(10):192- 198.

[11] CHEN Youdong,WEI Hongxin,SUN Kai,et al.Algorithm for smooth S-curve feedrate profiling generation [J].Chinese Journal of Mechanical Engineering,2011,24(2):237- 247.

[12] 王云飞,郎需林,张承瑞,等.高速并联机械手最优加减速控制算法研究 [J].机械设计与制造,2014(11):85- 88.

WANG Yun-fei,LANG Xu-lin,ZHANG Cheng-rui,et al.The optimal acceleration-deceleration control research of hign-speed parallel manipulator [J].Machinery Design & Manufacture,2014(11):85- 88.

[13] 冯李航,张为公,龚宗洋,等.Delta 系列并联机器人研究进展与现状 [J].机器人,2014,36(3):375- 384.

FENG Li-hang,ZHANG Wei-gong,GONG Zong-yang,et al.Developments of Delta-like parallel manipulators:a review [J].Robot,2014,36(3):375- 384.

[14] HUANG S C,JIAU M K,LIN C H.A genetic-algorithm-based approach to solve carpool service problems in cloud computing [J].IEEE Transactions on Intelligent Transportation Systems,2015,16(1):352- 364.

[15] 于莹莹,陈燕,李桃迎.改进的遗传算法求解旅行商问题 [J].控制与决策,2014,29(8):1483- 1488.

YU Ying-ying,CHEN Yan,LI Tao-ying.Improved gene-tic algorithm for solving TSP [J].Control and Decision,2014,29(8):1483- 1488.