基于遗传算法的分拣机器人最优路径规划

（华南理工大学 聚合物新型成型装备国家工程研究中心 聚合物成型加工工程教育部重点实验室，广州 510640）

近年来，工业机器人技术发展迅速，广泛应用于工业生产的各个方面，具有较大的发展空间[1-2]。机器人抓取技术是指工业生产中实现不同物体的分拣，并且将其快速准确地放在指定位置。如果让工人长时间从事重复的分拣工作易产生疲劳且效率不高。因此，采用机器人完成分拣工作不仅可以提高工作效率和准确性，更能节省人力资源成本，增加工厂的效益。机器人分拣物体的路径优化问题是生产中常见的实际难题，如果路径设计不合理，将会增加系统的运行时间。分拣顺序优化是一个组合优化问题，而组合优化问题是一个复杂的问题，得到了广泛的研究[3-7]，但对并联机器人路径优化的研究还比较少。本文运用遗传算法对多约束条件的并联机器人分拣顺序进行了仿真研究并在贝加莱公司最新的Tripod机器人上进行实验，验证了该方法的有效性。

1 问题描述

Tripod机器人是贝加莱工业自动化有限公司和奥地利HTL Wels大学共同设计的四轴并行机器人，具有3个机械手臂。在3台相同电机的配合控制下，工具中心可以在X，Y，Z工作空间中进行平移运动，并通过一个步进电机实现旋转。

模拟工件分拣平台如图1所示，由外圆环和内圆圈2部分组成。外圆环上随机放置9个几何体，三角形、五角形、圆形各有3片，分别为红色、蓝色和橙色；内圆圈上有9个不同形状的槽位。几何体放置的朝向与内圆圈槽位的朝向一致。机械手依次从外圆环上抓取9个几何体放置在对应的内圆槽位，要求颜色相同的几何体放置在一起，并且总路径最短。

图1 分拣平台Fig.1 Sorting platform

2 模型建立

Tripod机器人在分拣过程中，对每个分拣工件都只允许抓取一次，这可以等效为一个带约束条件的旅行商问题。旅行商问题（TSP）是指给定n个城市的点的坐标，遍历所有城市以最短距离路线，即搜索自然子集X=｛1，2，…，n｝（X的元素表示n个城市的编号）的一个排列π（X）=（V1，V2，…，Vn），使其满足：

取最小值，其中 d（Vi，Vi+1）表示城市 Vi到 Vi+1的距离[8]。

本文采用遗传算法进行TSP问题的求解。遗传算法是一种借鉴生物进化过程中“物竞天择，适者生存”规则的智能算法，可以由1个8元组组成[9]：

式中：C为个体编码方法；E为个体适应度评价函数；P0为初始群体；M为群大小；Φ为选择算子；Γ为交叉算子；Ψ为变异算子；T为遗传算法终止条件。

设机器人分拣的工件为n个，V=｛V1，V2，…，Vn｝是n个工件的集合，［Dij］n×n（i，j=1，2，3，…，n）为物体Vi与物体Vj之间距离所组成的距离矩阵，计算出通过V中所有工件最短路径矩阵D1。建立约束矩阵D2，D1与D2是同维矩阵。将D1与D2进行组合，寻找F=min（Td）的抓取顺序。这样就建立了机器人分拣顺序的数学模型，将机器人分拣顺序最优化问题抽象成图论中TSP来求解。

3 最优路径规划问题遗传算法实现

3.1 遗传算法流程

通过遗传算法进行机器人分拣最优路径规划，并在其中加入约束矩阵完成目标。算法的流程如图2所示。

图2 遗传算法流程Fig.2 Flow chart of genetic algorithm

3.2 遗传算法实现步骤

1）编码：采用符号编码方法，内圆上9个点的顺序与序号是固定的，依次标记为｛1，2，3，4，5，6，7，8，9｝。外环上9个点的顺序是可以变化的，设定10代表橙三角形，11代表橙五角星，12代表橙圆，13代表黄三角形，14代表黄五角星，15代表黄圆，16代表蓝三角形，17代表蓝五角星，18代表蓝圆，如图3所示。

图3 对象编号Fig.3 Object code

分拣台上18个中心坐标，可以由Tripod机器人上的摄像机拍照求得，本文主要研究该机器人的路径规划问题，对图像处理部分不作介绍。18个目标的坐标值如表1所示。

表1 18个编号的坐标表Tab.1 18 number coordinates

2）多约束条件矩阵化：根据模型，在生成的距离矩阵的基础上添加一个对应的约束矩阵为

约束矩阵中inf代表无限大数值，左上角的9×9部分限制内环上9个几何体之间不能相互在抓取的相邻次序，右上角部分的9×9部分是从外环上抓取放入内环上的几何体的形状必须是一样的，且相同颜色放一起，左下角9×9部分是从内环可以到外环上任何一个几何体处抓取，右下角的9×9部分代表外环上9个几何体之间不能是抓取的相邻次序。约束矩阵的构造是本遗传算法中一个关键的步骤，约束条件矩阵化的实质是对适应度函数进行调整，对不符合约束条件的增加适应度函数值，从而减少被选中的概率。

3）种群初始化：考虑到满足约束条件，在约束矩阵的限制下通过一个随机函数对种群进行初始化。

其中，n=18。

5）选择操作：采用联赛选择机制，从群体中任意选择一定数目的个体，其中适应度最高的个体保存到下一代，反复执行，直到保存到下一代的个体数达到预先设定的数目为止。

6）交叉操作：采用部分匹配交叉法（PMX），依据均匀随机分布产生2个位串交叉点，定义这2点之间的区域为一匹配区域，并使用位置交换操作交换2个父串的匹配区域。

7）变异操作：采取随机在18个目标中选取2个点，将其对换位置。

8）进化逆转操作：为提高遗传算法的局部搜索能力，引进多次连续的单方向进化逆转操作，只有经逆转后，适应度值有提高的才接受下来，否则逆转无效。

对于每一个目标体进行交叉变异，代入适应度函数中进行评估，选出适应度最大的个体进行下一代的交叉、变异以及进化逆变操作，直到满足设定的最大遗传代数。

4 仿真与实验结果

在MATLAB7.1环境下编写与运行。种群数为100，交叉率为0.9，变异率为0.05，代沟为0.9，最大迭代次数为250。在MATLAB中用遗传算法最优抓取顺序 15-＞6-＞18-＞9-＞12-＞3-＞14-＞5-＞10-＞1-＞13-＞4-＞17-＞8-＞16-＞7-＞11-＞2-＞15，总距离：3009.5752 mm，如图4所示。

图4 最优路径Fig.4 Optimal path

根据仿真结果得到的最优路径，利用TCPUDP Socket调试工具将最优路径数据通过TCP/IP发送给Tripod机器人，进行试验。试验结果表明机器人能够按照最优路径准确抓取物体并放入内圆相应位置，如图5所示。

图5 实验结果Fig.5 Result of test

5 结语

通过添加约束矩阵的遗传算法进行路径的最优化，可以有效减少机器计算运行的时间，提高抓取的准确性，在工业生产中能有效降低生产成本。提出的将多约束条件变成约束矩阵的方法，对于带约束条件的TSP问题具有适用性，能够在以后的TSP及机械手抓取物体的工程应用中有较好的适用性、移植性。

[1] 王田苗，陶永.我国工业机器人技术现状与产业化发展战略[J].机械工程学报，2014，50（9）：1-13.

[2] 谭民，王硕.机器人技术研究进展[J].自动化学报，2013，39（7）：963-972.

[3] 田贵超，黎明，韦雪洁.旅行商问题（TSP）的几种求解方法[J].计算机仿真，2006，23（8）：153-157.

[4] 朱玲湘，廖芹，邹亮.运用遗传算法求解有约束条件的旅行商问题[J].华南理工大学学报：自然科学版，2004，32（4）：97-100.

[5] Moon Chiung，Kim Jongsoo，Choi Gyunghyun，et al.An efficient genetic algorithm forthe traveling salesman problem with precedence constraint[J].European Journal of Operational Research，2002，140（3）：606-617.

[6] 张永德，姜金刚，唐伟，等.基于遗传算法的直角坐标式排牙机器人路径规划[J].哈尔滨理工大学学报，2013，18（1）：22-26.

[7] 陈冰梅，樊晓平，周志明，等.求解旅行商问题的Matlab蚁群仿真研究[J].计算机测量与控制，2011，19（4）：990-992

[8] 史峰，王辉，郁磊，等.MATLAB智能算法30个案例分析[M].北京：北京航空航天大学出版社，2011.

[9] 牟衔臣，谢东来，闫威，等.基于遗传算法航路规划TSP问题的研究[J].系统仿真学报，2013，25（8）：86-89.