多机器人任务分配调度的克隆选择算法

全燕鸣 何一明

(华南理工大学 机械与汽车工程学院，广东 广州 510640)

近年来,随着“中国制造2025”的不断深入开展,智能制造行业和机器人行业获得了快速发展,有关机器人的企业如雨后春笋般涌现。机器人由于可以代替人做一些重复而繁琐的任务,具有工作效率高及工作成本小的优点,正广泛用于各行各业,且需求量不断增大[1]。多机器人任务分配调度方法是多机器人稳定运行的关键技术,通过改进多机器人任务分配调度方法有利于节省机器人的工作成本,延长机器人的工作寿命,提高机器人的工作效率,且易于多机器人的进一步推广应用[2]。

多机器人任务分配调度研究是大势所趋,国内外学者已经对此展开了较多研究,但很多研究都偏向某个方面,难以做到全局统筹。Trigui等[3]提出了分布式市场化算法来解决多机器人任务分配问题,通过交换任务的方法进行分配优化,但其为局部调度,缺少考虑全局规划的最优性;David等[4]提出一种基于贝叶斯学习的多机器人协同方法,增强了多机器人局部的自适应能力,但其偏向局部条件的应对,欠缺全局优化效果;夏田等[5]建立了路径调节的模型,并用蚁群算法去解决多AGV(一种移动机器人)调度作业全局优化问题,但蚁群算法相对其它算法来说计算速度慢、效率偏低且搜索过程容易出现“早熟”,欠缺稳定性;徐海军等[6]提出了一种改进的A*算法来解决多AGV的冲突及调度问题,但A*算法计算量大,且局限于小规模计算,随着任务数量的增加,此算法难以满足全局调度的需求;Kala等[7]先用遗传算法寻找最优单路径,再用进化算法将最优多路径进行整体优化，从而实现多机器人的整体最优调度;Tuncer等[8]提出一种改进的遗传算法,通过引进新的变异算子,解决了动态环境下多机器人调度的全局优化问题;孟冲等[9]将多种群遗传算法引入到两阶段路径规划策略,实现了多AGV全局路径规划的效果，他们在机器人全局规划方面做出了创新,但是也存在对单机器人的利用率方面考虑不足等问题。

针对多机器人多任务分配及调度优化问题,本文提出一种应用于多机器人任务分配调度的克隆选择算法。此算法在一定条件下,建立多机器人、多工件及多工位并行作业的数学模型,分析约束条件和目标函数,使用克隆选择算法进行迭代计算,直到结果符合算法终止条件,最后输出最优调度结果,从而实现同一时间段内多机器人完成多任务分配调度。文中还通过实验,对比分析克隆选择算法及遗传算法在相同条件下对各项计算指标(算法收敛时间、系统持续时间、单机器人最大消耗、多机器人总消耗)的优化程度,从而验证克隆选择算法的优势。

1 问题描述

在智能制造系统中,工位并行协同加工工件,并按照不同加工流程完成多种不同工件的加工。工件的生产需要多工序,并通过多工位配合完成，而机器人则通过调度和运输功能使多工件和多工位建立联系。多工位、多工件和多机器人组成智能制造系统的重要部分[10]。本文研究是基于智能制造系统中多机器人的任务分配及调度优化问题，智能制造系统(下文简称为系统)示意图如图1所示。

图1 智能制造系统示意图

系统中,主要研究对象的设定如表1所示。

表1 研究对象设定Table 1 Research object setting

当系统下达一组任务时,R1先从H1将毛坯运输到M1进行J11,运输需要消耗10 s,运输完成后,R1解除占用状态,然后等待其他调度任务,如果没有其他调度任务，R1在M1等待J11完成，J11需要消耗30 s,然后R1将W1从M1运输到M2，运输需要消耗25 s,工件在M2完成J12，J12需要消耗35 s，此时W1加工完毕,整个过程消耗100 s。在此实例中,系统的甘特图如图2所示。

图2 实例中的甘特图

通过甘特图可以很直观看出各工位和各机器人在连续时间下的工作状态[11]。

在多任务条件下,多机器人运输多工件且按照各工件加工顺序完成加工的任务分配调度优化问题,这是本文的研究基础。

2 数学模型的建立

2.1 初始条件

给定机器人集合为

R={R1,R2,…，Rn1}

(1)

给定工位集合为

M={M1,M2,…，Mn2}

(2)

给定工件集合为

W={W1,W2,…，Wn3}

(3)

所有目标任务集合为

T={T1,T2,…，Tn4}

(4)

代价矩阵为

C=[cij]

(5)

式中,矩阵C中的元素cij表示机器人R从目标i运动到目标点j(i,j=1,2,…，m)的消耗值[12]。

2.2 约束条件

(Ⅰ)工位约束:工件W的相应工序J由指定的工位M加工,工位M在同一时刻不能同时进行多工序J的加工。

(Ⅱ)时间约束:工件的前一工序Ji1加工完成才能进行后一工序Ji2,设此任务过程中的时间点为tA,工序J完成的时间点为tA(J),即

tA(Jia)

(6)

工位要完成前一加工任务T1才能进行后一加工任务T2,即

{∀tA=a

∀Mi∈M

count(TMi)≤1

(7)

式中,count(·)为统计个数函数。

工件Wi在工位M的工序Jij完成前,不允许被机器人R运输,即

{∀tA

∀Ri∈R

count(TRi)=0

(8)

(Ⅲ)任务约束:完成所有任务T,相同的任务T不能重复执行,即

(9)

(∀i,j∈{1,2,…，m},i≠j)

∪Ri∈RTRi=T

(10)

Ti∩Tj=∅, ∀i≠j∈R

(11)

2.3 目标函数

(Ⅰ)设各工位作业时间为t(x),系统持续时间由最大工位作业时间决定。使系统持续时间最小,则目标函数为

min ɡ1=min[maxt(x)]

(12)

(Ⅱ)计算各机器人R执行运输任务的消耗,使得单机器人最大消耗最小,则目标函数为

min ɡ2=min{max[f(R1,TR1),…，f(Rn,TRn)]}

(13)

(14)

式中,chk是机器人Ri沿规划好的路径从目标h移动到目标k的消耗值,消耗值与运输时间正相关,可以用运输时间代表。

(Ⅲ)设总消耗值为cost(x),使所有机器人R的总消耗最少,则目标函数为

(15)

考虑上述3个优化因素,总的目标函数为

min ɡ=min(C1ɡ1+C2ɡ2+C3ɡ3)

(16)

式中,C1、C2、C3均为权重系数,反映ɡ1、ɡ2、ɡ3的相对重要性。

3 克隆选择算法的任务分配调度方法

3.1 克隆选择算法的总体流程

克隆选择算法受生物系统克隆选择原理启发而诞生,其计算思想是通过对候选解产生克隆、变异等操作,产生一个候选解的领域解,通过扩大搜索范围强化局部搜索,通过领域解和候选解的竞争进行选择以提高算法快速全局搜索能力[13]。其计算流程如图3所示。

图3 克隆选择算法的计算流程

3.2 初始化种群

设定当前种群代数k=0,随机产生一个规模N=n的初始染色体种群P(0)={p1,p2,…，pn},采用整数编码方法进行染色体编码[14]。

染色体由u个基因(下文用英文G表示)组成,每个基因长度为v，则染色体长度为

L=uv

(17)

一个染色体代表一个调度方案。基因按从左到右的执行顺序排列,本文每个基因从左到右由3部分编码组成,分别为工件类型、工序编号及机器人编号;染色体长度等于任务总数。一种基因编码例子如表2所示,此为9工序、4工位、1机器人(编号为z)的基因编码。

表2 基因编码例子Table 2 Example of gene coding

表2中,G11z表示Rz把毛坯运输到M1进行J11；G12z表示Rz到M1运输完成J11的W1，到M2进行G12;其他基因G的意义以此类推。当以上8个任务均完成时,意味着3种工件全部加工完毕,系统任务完成。

由于在染色体中,基因按执行顺序排列,基因顺序代表着执行顺序,所以工序编号可以由程序进行解析,而不需要在基因中标出。例如染色体中第1次出现的G1X代表RX运输W1去进行J11，第2次出现的G1Y代表RY运输W1去进行J12。图4是一个基于上述条件的染色体编码例子。

图4 染色体编码例子

3.3计算亲和度

亲和度源于免疫系统中抗原与抗体的亲和力概念,表示抗体对抗原的匹配程度。克隆选择算法中,亲和度是指个体相对于结果的期望值。亲和度越高,个体越优秀。文中算法致力于提高个体亲和度[15]。计算亲和度前,要对染色体进行解析,以计算系统持续时间ɡ1、单机器人最大消耗g2及多机器人总消耗ɡ3。

考虑数学模型的目标函数,亲和度计算公式为

f(x)=B-ɡ=B-C1ɡ1-C2ɡ2-C3ɡ3

(18)

式中,参数B为亲和度总值,取用一个较大值的正整数,目的是使得个体亲和度值越高,个体品质越好。

计算各个体亲和度f(p1),f(p2),…，f(pn),将种群P(k)按亲和度降序排列。为了防止“早熟”并提高算法的全局搜索能力,根据排列顺序按比例2:5:3划分种群P(i)为优Pr(i)、中Ps(i)、差Pt(i)3个种群,即

P(i)={Pr(i),Ps(i),Pt(i)}

(19)

(r:s:t=2:5:3)

式中,参数r、s、t分别为3个种群中的个体数目。

计算个体间相似度S(0≤S≤1),用于表示两个体px和py间的相似程度:

(20)

式中，axk为个体px的染色体编码第k位数值。

采用个体浓度D反映种群多样性,定义个体px的浓度为

(21)

式中,n为种群规模。式(21)表明,个体间相似度越小,则个体浓度D越小。个体浓度主要用于调整克隆规模,保持种群多样性。

3.4 克隆

根据各个体亲和度大小,计算其相应克隆次数,进行克隆复制操作。

对P(i)中的个体pj(j=1,2,…，ni),按照个体克隆规模qj进行复制:

(22)

式中,ni为第i代种群规模,ceil(·)为向上取整函数,Nc为种群克隆规模。其中,

(23)

式中,pj(i)为第i代个体pj。

克隆产生子代种群Pc(i)。式(22)和(23)表明:克隆规模依赖于个体亲和度和个体浓度,个体亲和度越大,个体克隆规模越大;个体浓度越大,个体克隆规模越小。

3.5 变异

对克隆个体采取变异操作。按式(24)分配克隆个体pj(j=1,2,…，ni)的变异概率:

(24)

式(24)表明,变异概率取决于个体亲和度大小,个体亲和度越大,个体变异概率越小。

变异包含突变和交换两个过程。突变过程是对个体中基因的第2位进行变更,变更后整数编码要限定在合理范围内,如图5所示。

图5 基因突变过程

交换过程是对个体中任意两个基因进行交换,如图6所示。

图6 基因交换过程

子代优秀种群Pcr(i)和子代中等种群Pcs(i)通过变异分别转化为种群P′cr(i)和P′cs(i)。

3.6 选择

选择是算法的重要搜索过程,目的在于筛选出优秀个体,从而产生新种群[16]。

Pdr(i+1)={P′cr(i),Pr(i)}

(25)

根据式(25),从种群Pdr(i+1)中选出亲和度最高的r个个体组成P′dr(i+1)。

Pds(i+1)={P′cs(i),Ps(i)}

(26)

根据式(26),从种群Pds(i+1)中选出亲和度最高的s个个体组成P′ds(i+1)。

为了防止“早熟”,再次随机生成规模大小为n的种群Pdt(i+1),取其中亲和度最高的t个个体组成P′dt(i+1)。

新一代种群产生,此种群集合为

P(i+1)={P′dr(i+1),P′ds(i+1),P′dt(i+1)}

(27)

3.7 终止条件

本文算法不预设固定期望值和最大迭代次数,而是通过判断连续多个子代最大亲和度值是否相等作为算法收敛判断依据,当连续20代子代最大亲和度值和父代最大亲和度值相等时,算法收敛,即符合算法终止条件。

当新一代种群产生时,需要判断是否符合算法终止条件。若符合算法终止条件,则算法停止,选择亲和度最高的个体作为结果输出;否则,转到图3 的选择步骤,继续进行迭代循环运算[17]。

4 实验与分析

构建仿真场景模型,考虑条件:机器人数量count(R)=3，任务数量count(T)=45。零件加工时间如表3所示，为了避免不同含义的基因编码混淆,大于1位的整数编码用逗号隔开。

机器人从各工位起点将工件运输到各工位终点消耗的时间如表4所示。

计算前要初始化算法参数:设置种群规模N=80,种群克隆规模Nc=80,亲和度总值B=500,权重系数C1=0.80,C2=0.10,C3=0.10。在Matlab 2016a环境下进行克隆选择算法程序编程,在配置为Intel Core i5处理器、8 GB RAM内存的计算机上运行,通过232次迭代计算,算法收敛,输出结果为G411,G711,G911,G11,11,G10,11,G12,12,G212,G312,G512,G113,G613,G813,G13,13,G14,13,G15,13,G321,G521,G14,21,G10,21,G15,21,G622,G122,G922,G11,22,G723,G423,G823,G13,23,G12,23,G223,G631,G431,G831,G15,31,G10,31,G732,G332,G13,32,G12,32,G232,G133,G533,G933,G14,33,G11,33。

表3 零件加工时间Table 3 Workpiece processing time

表4 机器人运输消耗的时间Table 4 Time spent in robot transportation s

根据上述结果,画出此系统的甘特图,如图7所示。

图7 系统的甘特图

由图7可得,最后完成加工的工位是M6,系统持续时间ɡ1(x)=635 s,运输时间最长的机器人是R2,单机器人最大消耗ɡ2(x)=523 s,多机器人总消耗ɡ3(x)=1 519 s。实验表明,此多机器人任务分配调度方法合理,达到了任务分配调度优化目的。

单条件下单次实验偶然性大,因此,在考虑不同实验条件的基础上,分别用克隆选择算法(下文简称CSA)和遗传算法(下文简称GA)进行求解,以对CSA和GA进行对比。

使用GA求解此问题时,为了提高可比性,GA的初始参数需要和CSA的初始参数保持一致,GA的选择、交叉、变异概率使用CSA返回的初代概率。可得CSA的初代参数值为:种群规模N=n1,选择概率a=a1,交叉概率b=b1,变异概率c=c1。则设置GA参数为:种群规模N′=n1,选择概率a′=a1,交叉概率b′=b1,变异概率c′=c1,进行Matlab编程。

对每个不同条件分别进行10次独立重复的Matlab仿真实验,获取最终输出结果,并计算其各项指标平均值。将CSA和GA各项平均值指标对比,比较的指标分为两个方面:一是算法的计算性能,包括迭代次数和收敛时间,即达到稳定的迭代时间;二是算法的优化能力,包括系统持续时间、单机器人最大消耗和多机器人总消耗。比较结果如图8和9所示。

图8和9中,实验编号1到20是在相同机器人数量(count(R)=3)基础上,对任务数量从12到69进行逐渐增加来进行实验;实验编号21到30是在相同任务数量(count(T)=45)基础上,对机器人数量从1到10进行逐渐增加来进行实验的。

图8 CSA和GA计算性能比较柱状图

图9 CSA和GA优化能力比较柱状图

由图8可知,CSA在迭代次数和收敛时间方面的表现均优于GA。CSA明显减少了迭代次数,虽然CSA增加了每代计算时间,但是CSA的平均收敛时间也比GA少,且随着实验条件复杂化,CSA的收敛时间更有优势。由此可见,CSA的计算性能优于GA。

由图9可知,无论在相同机器人数量、不同任务数量下还是在相同任务数量、不同机器人数量下对各项优化能力指标(包括系统持续时间、单机器人最大消耗和多机器人总消耗)进行比较,CSA的表现均优于GA,即CSA的优化能力强于GA。可以看出:当机器人数量相同时,随着任务数量增加,调度条件复杂化,相比于GA,尤其在单机器人最大消耗和多机器人总消耗方面,CSA的优势逐渐变大；当任务数量相同时,随着机器人数量的增加,CSA和GA各项优化能力指标间的差异逐渐变小；当机器人数量增加到一定程度并使其达到饱和状态时,即使继续增加机器人数量,CSA和GA的系统持续时间、单机器人最大消耗和多机器人总消耗也不会下降。

使用GA时,事先要设定好交叉、变异和选择概率等参数,采用适应度评估的方法进行优秀子代的选择[18]。为了改进GA收敛速度偏慢的缺点,CSA引入亲和度函数,目的在于动态修改CSA的控制参数,将原本在GA中保持固定的参数设置成随着迭代变化,并利用亲和度函数所提供的信息对克隆、变异及选择操作方式进行校准,从而引导算法向提高亲和度的搜索方向进行,进而使种群朝着全局最优的方向进化,最终减少了冗余的搜索过程,所以能有效降低迭代次数并提高收敛速度。

此外,CSA在提高收敛速度的同时可能会产生收敛过快以及无法进行足够探索的问题。收敛过快的特征表现在:种群中个体间相似度高,种群多样性急剧减少,缺乏有效等位基因,在决策算子作用下不能生成高阶竞争模式,即“早熟”[19]。此现象会使算法过早收敛于局部最优,而非全局最优。尤其是处于迭代后期时,经过算法的多代筛选,优秀个体已经在种群中占据大部分,此时,交叉操作对于相同优秀个体几乎不产生影响。虽然变异操作能够为算法补充新个体,但是此操作对算法影响相对较小。如果增大算法的变异概率会破坏种群中的优良个体,导致算法继承能力及优化能力降低。

防止“早熟”是搜索算法设计的重点。为了在提高收敛速度的同时防止“早熟”现象,本文通过增大种群规模和克隆规模,将种群分为优、中、差3种类型分别进行选择操作,同时在选择步骤中随机引入新种群的方法以提高种群基因多样性,从而在一定程度上防止“早熟”。实验结果表明,CSA表现优良,并未出现明显“早熟”现象。

5 结论

文中基于智能制造系统中多机器人任务分配调度问题,分析多机器人在智能制造系统中的调度条件,构建合理的数学模型,并基于多机器人任务分配调度应用CSA。在迭代过程中引入适当的亲和度函数,动态改变克隆、变异、选择参数,从而加快算法的收敛速度;同时通过增大种群规模和克隆规模,进行种群分类筛选和随机引入新种群的方法防止“早熟”,使算法性能得到提高。最后，文中通过实验证明其可行性,分析CSA相对于GA的优势。相比于GA,CSA的计算性能和优化能力具有优势,对收敛时间、系统持续时间、单机器人最大消耗、多机器人总消耗等指标优化较好。随着调度任务增加,调度条件复杂化,CSA相比于GA在计算性能和优化能力方面优势更加明显。当任务数量相同时,随着机器人数量增加,CSA和GA各项优化能力指标间的差异逐渐变小。当机器人数量增加到一定程度并使其达到饱和状态时,即使继续增加机器人数量,CSA和GA的系统持续时间、单机器人最大消耗和多机器人总消耗也不会下降。

本文所用模型还存在如下不足:多机器人运动过程中路径冲突和避碰问题并没有在调度过程中加以考虑;在复杂调度情况下,本文在调度优化过程中机器人出现故障时的容错处理没有加以考虑。因此，在后续相关研究中会进行这些问题的仔细探究。