杨继东 孙兆琦 王飞龙

摘 要：针对元件的抓取路径规划问题，提出一种以最小化时间为目的，结合蚁群算法和禁忌搜索算法的混合优化算法。首先，将基于机器视觉抓取元件的问题确定为有约束的旅行商问题（TSP）;然后，分析了元件大小和抓取放置过程对于路径规划的综合影响，对路径选择概率和禁忌域进行了适应性改进;其次，一方面引入了2-opt局部优化以及信息素惩罚、奖励机制以改善蚂蚁的搜索能力，另一方面对信息挥发因子作适应性改进以提高蚂蚁的自适应能力;

最后，针对基本算法和改进的混合优化算法，仿真实验和平台实验分别进行了性能指標和抓取时间的对比分析。

实验结果表明，仿真环境下，与蚁群优化（ACO）算法和禁忌搜索（TS）算法相比，混合优化算法的平均迭代次数降低了约50%，且其他性能较为优越，平台测试的抓取用时测试结果也说明了混合优化算法较随机结果和基本算法的优越性，可以快速完成元件抓取任务。

关键词：机器视觉;有约束的TSP;最优路径;蚁群算法;混合优化算法

中图分类号： TP273;TP18

文献标志码：A

文章编号：1001-9081（2019）03-0913-05

Abstract： To solve the problem of component grasping path planning， a hybrid optimization algorithm based on ant colony algorithm and tabu search algorithm was proposed to minimize the time. Firstly， the problem of grasping components based on machine vision was defined as Traveling Salesman Problem （TSP） with precedence constraint. Secondly， comprehensive effects of the sizes of components and the grasping and placement process on path planning were analyzed， and the path selection probability and tabu region were improved adaptively. Thirdly， on the one hand， 2-opt local optimization， pheromone punishment and reward mechanism were introduced to improve the search ability of ants; on the other hand， pheromone evaporation factor was improved adaptively to increase the adaptability of ants.

Finally， for the basic algorithm and the improved hybrid optimization algorithm， the performance index and grasping time were compared and analyzed by simulation experiment and platform experiment.

The experimental results show that， compared with Ant Colony Optimization （ACO） algorithm and Tabu Search （TS） algorithm， the average iteration times of the proposed hybrid optimization algorithm is reduced by about 50%， and other performances are superior to the other algorithms. The results of platform test also show that the hybrid optimization algorithm is superior to random results and basic algorithm， and it can realize component grasping task quickly.

Key words： machine vision; Traveling Salesman Problem （TSP） with precedence constraint; optimal path; ant colony algorithm; hybrid optimization algorithm

0 引言

工业摄像机作为工业机器人的视觉传感器，是工业生产需要的柔性制造系统（Flexible Manufacture System， FMS）、自动化工厂（Factory Automation， FA）的重要环节，是实现“中国制造2025”的自动化工具。

目前，机器视觉在工业生产过程中的检测、识别已有较为广泛的应用，同时在定位抓取过程中的研究也有一定的应用，但是对物体抓取路径的控制规划研究较少，优化抓取路径可以有效地提高重复抓取过程中效率，是视觉系统抓取过程中的重要一环。从理论分析来讲，抓取路径可以划归为旅行商问题（Travelling Salesman Problem， TSP），同时该过程为取放过程，因此其属于有约束的旅行商问题（Traveling Salesman Problem with Precedence Constraint， TSPPC）。李尧等[1]提出基于图像识别和遗传算法的最优轨迹控制，但是其抓取模型的约束较多，不具有通用性，且算法未进行优化分析。解决TSP的方法较多，其中：枚举法算法较为简单，但算法效率较低;模拟退火算法、遗传算法、蚁群算法的质量较高，但是优化时间较长，易于陷入局部解;禁忌搜索算法（Tabu Search， TS）局部搜索能力较强，但是依赖初始解。蚁群算法应用于TSP最早是由意大利学者Dorigo等 [2]提出，基本思想是依据蚂蚁寻找食物过程中释放信息素，来引导其他蚂蚁的爬行路径实现正反馈，具有较好的鲁棒性和协作性。叶小勇等[3]引入随机搜索蚁同时增加信息素的奖励惩罚机制，有效地提高全局最优解的搜索能力，但是搜索用时较长，实时性较差。张慕雪等[4]通过该禁忌搜索来加强蚁群算法的全局搜索能力，但是由于是基于蚁群算法的优化算法，搜索用时较长，实时性差，不适用于工业抓取过程。

针对蚁群算法和禁忌搜索算法各自的优缺点，本文提出了一种混合优化算法（Ant Colony Optimization-Tabu Search， ACO-TS），用来取长补短，优化视觉处理后的元件的抓取路径，同时提高算法的收敛速度和算法处理速度。对蚁群算法中的选取概率和禁忌搜索算法的禁忌域作出了适应性修正，同时优化蚁群算法的信息素挥发因子，引入局部2-opt进行优化和信息素奖励惩罚机制，在有效的迭代次数里提高收敛速度，为禁忌搜索算法提供优良的初始解，利用禁忌搜索算法的记忆能力和藐视原则得到路径最优解。

1 相关工作

1.1 实验平台简介

本文中搭建的视觉系统实验平台是基于并联桁架机器人，摄像机采用大恒的MER-125-30GM-PS数字面阵相机，镜头采用Computar的H2Z0414C-MP变焦镜头，采用打背光的打光方式，工控机采用研华IPC-610L，运动控制卡采用雷赛DMC5480板卡。相机的固定方式采用眼在手上（Eyes In Hand）。搭建出的样本的实验平台如图1所示。

为了有效得到实验测试结果，将测试的抓取元件和码盘作了如下简化：

1）抓取元件个数和放置位置个数均为9，抓取的圆形玻璃元件有大中小三种尺寸类型，每种尺寸类型元件各有三个，放置位置个数与之对应。

2）抓取元件在打光区域任意摆放，码盘摆放位置、方向固定，且选取如图码盘的右上角3×3大小的码盘作为放置元件位置。

首先采用Halcon和Visual Studio 2013联合编程的方式对本组进行数字图像处理如图2所示，后通过摄像机传统标定的方法获取摄像机的内参数，借鉴文献[5]的手眼标定方法来确定摄像机坐标到吸盘末端坐标的转化。

经过Halcon对圆形玻璃元件视觉处理后得到不同元件的大小信息和元件的抓取中心特征点的坐标信息，经过标定将结果转为世界坐标信息。根据圆形玻璃元件的大小将其依次进行2～10编号，对于已知坐标的码盘放置元件位置，同样对码盘放置元件位置根据孔洞大小依次进行11～19进行编号，起始点位置确定为1。然后通过与Visual Studio 2013联合编程，便于控制运动控制卡来进行抓取运动的实现。

1.2 问题分析

本文重点研究的内容是并联桁架机器人抓取排放9个圆形玻璃元件的先后顺序问题，以最优的路径实现圆形元件摆放到直径一致的码盘位置。问题描述如下：机械手末端从起始点出发，无重复地到达抓取、放置的每一个点，最终返回原点。与TSP作对比，发现二者有很多相似之处。本文元件抓取和放置位置相当于TSP里的城市，无重复经过每一个点，达到最优路径。但是，本文的最优路径相对于TSP有所约束，

体现如下：

1）末端机械手到达抓取点，完成抓取动作之后，下一步必须到达放置点。

2）抓取和放置过程中，元件的直径和放置位置直径要对应，不能出现直径较小的元件放置在直径较大的码盘位置的情况。

根据问题描述，可以确定该问题为NP问题[6-7]，传统概率算法、并行算法非常复杂，要寻求一个最优的解需要很长的时间，因此本文针对视觉抓取过程提出基于蚁群算法和禁忌搜索算法的混合优化算法。

2 算法介绍

2.1 蚁群优化算法

蚁群优化（Ant Colony Optimization， ACO）算法是一种较为新的模拟进化算法，是从整个蚁群可以找到一条从巢穴到食物源之间的最优路线而启发得到的[8-9]。原因在于蚂蚁在爬行过程中会在路径上释放信息素的物质，随着时间的推移，该物质会挥发，路径上的信息素越浓，蚂蚁选择该路径的机会就越大[10-11]。

其中基本的3個公式如下：

2.2 禁忌搜索算法

禁忌搜索算法是利用禁忌表来记录当前搜索过程中的局部最优点，在下一次的搜索中，对于禁忌表中的信息不再或有选择地搜索，以此来跳出局部最优点。但禁忌搜索算法对初始解的依赖性较强[12-13]，好的初始解有助于搜索很快达到最优解。所以，对禁忌搜索算法的改进一直是人们研究的重点[14]。

3 混合优化算法

3.1 适应性算子的改进

3.1.1 路径选择概率适应性的改进

针对机器人路径上有抓取和放置过程且直径大小对应，本文对路径选择概率作出了如下的适应性改进，蚂蚁由节点i访问节点j的概率为：

其中：概率选取的过程是从抓取位置i到放置位置（用i′表示），然后再从放置位置j再到下一个抓取位置j′这样的抓取、放置、抓取过程为单次循环过程来进行概率选取。根据抓取元件直径大小来选择放置位置（allowsize表示），然后返回下一个抓取位置（allow表示），如此改进可以有效避免单次选取带来的陷入局部最优解。

3.1.2 禁忌域适应性的改进

由于研究问题是有约束的TSP，在禁忌域建立过程中，本文建立交换允许表，在进行禁忌交换时加以利用。交换允许表可以用allowsize表示如表1所示，它是一个二维表，第1行、第1列表示2个元件交换前的序号。

行列节点交叉处的值表示禁忌交换时是否被允许。值为“1”表示允许交换，值为“0”表示不允许交换。产生两个随机交换位置，根据位置对应的初始解的数值在交换允许表中对应的“0”“1”确定该组交换是否可以被接受，且当交换对应的初始解数值在区间[2-10]时，各交换位置的后一位同时进行交换。如初始解为（1-7-16-9-17-2-12-4-13-8-19-10-18-6-14-5-15-3-11-1），如随机产生的交换位置为（2，10），对应的初始解的数值为7，10，在交换允许表的对应数值为“1”，允许交换，且对应的初始解的数值在区间[2，10]，因此初始解数值16，18对应位置同时进行交换。

3.2 蚁群算法优化

3.2.1 2-opt局部优化

将2-opt引入蚁群算法，对于蚂蚁所构建出的路径较短的路径执行2-opt算法来进行当前解的局部优化[15]，这样既可以避免算法陷入局部最优解，又能加快收敛，同时针对路径较优的前n/2个解路径进行2-opt局部优化，减少引入2-opt算法来引起的计算时间过长的现象。过程大致如下：对于节选路径i、i′、i+1、i′+1、…、 j、 j′、 j+1、 j′+1，假设选定i′+1、 j为交换位置、区间内的路径进行抓取位置反向处理，放置位置跟随处理，如下i、i′、 j、 j′、…、i+1、i′+1、 j+1、 j′+1，如图3所示。

3.2.2 引入信息素惩罚、奖励机制

prize为奖励系数，punish为惩罚系数，为设定的固定参数，prize大小影响收敛速度，punish大小影响全局最优解的寻求能力。为了在有限的迭代次数里，为禁忌搜索提供较好的初始解，可以适当地增大punish，减小punish，提高收敛速度，全局最优解搜索能力依靠禁忌搜索来改善。

3.2.3 信息挥发因子适应性优化

蚁群算法的信息素发挥因子ρ设定为固定值，如式（2）所示， ρ设定较小时会造成快速陷入局部最优解，失去全局搜索能力; ρ设定较大时会造成收敛速度过慢，降低工作效率。因此，将ρ设定为与蚁群算法迭代次数相适应的函数，如式（9）所示：

其中：λ为设定参数，NC为蚁群算法搜索的迭代次数，NCmax为最大迭代次数，同时设定上下限为（0.7，0.1），使其值保持在一定的范围。起始时，选择较大的信息素挥发因子，提高蚁群算法搜索全局最优解的能力，动态改变ρ，使其随着迭代次数的增加不断减小，提高其收敛速度，同时算子过程中引入NCmax，提高算子自适应能力。

至此，对机器视觉抓取过程最优路径的规划所需要的实验平台，利用蚁群算法提高收敛速度同时为禁忌搜索提供较优的初始解，通过禁忌搜索求解全局最优解，形成混合优化算法，同时根据抓取路径的具体特点对混合优化算法进行适应性改进。改进的混合优化算法流程如图4所示。

4 实验结果

本文将实验结果分为仿真结果和平台实验，仿真主要是论证本文论述的混合优化算法的实验效果，平台实验旨在说明该算法在机器视觉抓取过程实现最优路径的优化效果，进行整体方案验证。

4.1 仿真结果

本文的仿真环境为Windows 10系统下Matlab R2016b，主要是将本文得到的混合优化算法和蚁群算法、禁忌搜索算法进行对比分析，从而测试改进算法的效果。位置设定如相关工作所描述，各参数根据经验和多次实验得到，初始值设定如表2所示。

在仿真环境下，选取最短路径和平均路径因素，将改进的混合优化算法和蚁群算法、禁忌搜索算法进行对比，混合优化算法生成的途径图、最短路径和平均路径效果如图5所示。

混合优化算法的到的最优路径为： 1-3-13-7-16-10-19-8-18-2-11-6-14-9-17-5-15-4-12-1，最优路径长度为157.991，且根据最短路径对比图看出三种算法不同程度反映了其收敛能力和寻求全局最优路径能力，可以得到以下结论：

1）混合优化算法随着程序的执行，快速收敛，在迭代10次左右陷入死路，在30代左右，用死路作为禁忌搜索的初始解，加强全局搜索能力，在45代左右得到最优解。

2）混合优化算法相比蚁群算法收敛速度明显提高，寻找到的最短路径明显较优。

3）混合优化算法相比禁忌搜索算在30代左右收敛速度提高，之后经历10代左右达到最优解，收敛速度快，得到路径较优。

结合平均距离对比图可以验证以上说法，同时看出混合优化算法得到的路径距离的稳定性较优。

将三种算法同时应用于本文研究的机器视觉抓取圆形玻璃元件问题，选取多组元件进行不同位置的抓取，每组进行20次测试，测试结果如表3所示。

从表3中可以看出，改进的蚁群算法结合禁忌搜索算法的混合优化算法在抓取不同距离位置的元件时均有更好的寻优结果，且寻优结果和距离无关。同组比较，混合优化算法得到较优的最优解且稳定性较好，与ACO和TS相比，混合优化算法的平均迭代次数降低了约50%，且算法用时较短。禁忌搜索算法虽然也可以达到相同的最优解，且算法用时较短，但是得到最优解的稳定性不足，收敛速度不足。蚁群算法得到的最优解过早地收敛，全局搜索能力不足。综上仿真结果来看，混合优化算法寻优能力优于蚁群算法和禁忌搜索算法，且寻优过程中与元件放置位置到码盘位置的距离无关，因此在将该混合优化算法应用于机器视觉抓取元件寻求最优路徑较ACO、TS更优。

4.2 平台实验

将Matlab生成的混合优化算法封装成函数供Visual Studio2013调用，做平台抓取实验。抓取起始点定义在光源中心点，在对现有抓取起始点，元件抓取点以及码盘放置点进行1～19依次排序，得到路径为1-8-19-2-11-3-12-4-13-7-16-10-18-9-17-5-14-6-15-1，完成全部抓取所需要的时间为20.23s，样机取放结果如图6所示。

同时保持起始点、放置位置不变，选取三组较放置位置不同距离的元件进行对比，同样做三种算法的对比实验，每种进行10组，取抓取时间的平均值（单位：秒），得到结果如表4所示。

由距离组之间的对比实验可以看出，距离对于各种算法影响差异不大，说明寻优结果与距离无关，验证仿真实验的结果。算法之间的对比可知，随机路径的用时要优于蚁群算法，其原因在于蚁群算法本身耗时较路径优化节省的时间更长。混合优化算法较蚁群算法和禁忌搜索算法抓取用时更短，且与随机路径相比，混合优化算法平均耗时缩短了6.68%。

5 结语

本研究基于机器视觉定位元件，将元件抓取、放置过程转换为有约束的TSP，通过仿真结果和平台实验表明，结合蚁群优化算法和禁忌搜索算法的混合优化算法在机器视觉定位抓取、放置的过程中，较随机抓取、蚁群算法和禁忌搜索算法来讲，抓取路径得以优化，抓取效率有效提高。

参考文献 （References）

[1] 李尧，石红瑞.基于图像识别和遗传算法的Tripod机器人最优轨迹控制[J].计算机应用，2016， 36（S1）：106-109.（LI Y， SHI H Z. Optimal trajectory control of the Tripod robot based on image recognition and genetic algorithm [J]. Journal of Computer Applications， 2016， 36（S1）：106-109.）

[2] DORIGO M， GAMBARDELLA M L. Ant colonies for the travelling salesman problem [J]. Biosystems， 1997，43（2）：73-81.

[3] 葉小勇，雷勇，侯海军.蚁群算法在全局最优路径寻优中的应用[J].系统仿真学报， 2007，19（24）：5643-5647. （YE X Y， LEI Y， HOU H J. Application of ant colony algorithm in global optimal path searching [J]. Journal of System Simulation， 2007， 19（24）： 5643-5647.）

[4] 张慕雪，张达敏，杨菊蜻，等.基于禁忌搜索的蚁群算法优化算法[J].通信技术，20178， 50（8）：1658-1663. （ZHANG M X， ZHANG D M， YANG J Q， et al. Ant colony optimization algorithm based on tabu search [J]. Communications Technology， 2017， 50（8）：1658-1663.）

[5] 陈丹，白军，石国良.一种新的四自由度SCARA机器人手眼标定方法[J].传感器与微系统，2018，37（2）：72-75.（CHEN D， BAI J，SHI G L. A new method of four DOF SCARA robot hand-eye calibration [J]. Transducer and Microsystem Technologies， 2018， 37（2）： 72-75.）

[6] 高海昌，冯博琴，朱利.智能优化算法求解TSP问题[J].控制与决策，2006，21（3）：241-247.（GAO H C， FENG B Q， ZHU L. Reviews of the meta-heuristic algorithms for TSP [J]. Control and Decision， 2006， 21（3）： 241-247.）

[7] 吴斌，史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报，2001，24（12）：1328-1333.（WU B， SHI Z Z. An ant colony algorithm based partition algorithm for TSP [J]. Chinese Journal of Computers， 2001， 24（12）： 1328-1333.）

[8] MULLEN R J， MONEKOSSO D， BARMAN S， et al. A review of ant algorithms [J]. Expert Systems with Applications， 2009， 36（6）： 9608-9617.

[9] 吴庆洪，张颖，马宗民.蚁群算法综述[J].微计算机信息，2011，27（9）：1-2. （WU Q H， ZHANG Y， MA Z M. Review of ant colony optimization [J]. Microcomputer Information， 2011， 27（9）： 1-2.）

[10] CIORNEI I， KYRIAKIDES E. Hybrid ant clony-genetic algorithm （GAAPI） for global continuous optimization [J]. IEEE Transactions on Systems， Man， and Cybernetics. Part B， Cybernetics： a publication of the IEEE Systems， Man， and Cybernetics Society， 2012， 42（1）： 234-245.

[11] 张鹏，魏云霞，薛宏全，等.基于优胜劣汰规则的异类多种群蚁群算法[J].计算机工程，2012，38（18）：182-185.（ZHANG P， WEI Y X， XUE H Q， et al. Heterogeneous multiple colonies ant colony algorithm based on survival of fittest rules [J]. Computer Engineering， 2012， 38（18）： 182-185.）

[12] 王凌.智能优化算法及其应用[M].北京：清华大学出版社，2001：67-68.（WANG L. Intelligent Optimization Agorithm and Its Application [M]. Beijing： Tsinghua University Press， 2001： 67-68.）

[13] 刘兴，贺国光.车辆路径问题的禁忌搜索算法研究[J].计算机工程与应用，2007，43（24）：179-181. （LIU X， HE G G. Study on tabu search algorithm for stochastic vehicle routing problem [J]. Computer Engineering and Applications， 2007， 43（24）： 179-181.）

[14] 彭茂.一种求解TSP问题的改进禁忌搜索算法[J].计算技术与自动化，2012，31（1）：78-81.（PENG M. Improved tabu search algorithm for solving traveling salesman problem [J]. Computing Technology and Automation， 2012， 31（1）： 78-81.）

[15] 张勇.基于改进蚁群算法物流配送路径优化的研究[J].控制工程，2015，22（2）：252-25.（ZHANG Y. Study of optimizing logistic distribution routing based on improved ant colony algorithm [J]. Control Engineering of China， 2015， 22（2）： 252-256.）