基于群体智能的多机器人任务分配

第40卷第1期2010年1月

吉林大学学报(工学版)

Journal o f Jilin U niv ersity (Engineering and T echnolo gy Edition)

Vol. 40 No. 1 Jan. 2010

基于群体智能的多机器人任务分配

刘淑华, 张嵛, 吴洪岩, 刘杰

(东北师范大学计算机学院, 长春130017)

摘要:针对具有松散和紧密耦合型任务的大规模多机器人系统, 研究了基于群体智能的任务分配方法。系统采用层次结构, 高层用蚁群算法实现松散耦合型任务分配的寻优, 提出逆转分配思想让蚂蚁代表任务, 为每个任务选择任务的承担者。底层分别提出了基于蚁群、粒子群蚁群和量子蚁群实现机器人联盟的形成产生紧耦合型任务解, 并进行仿真。仿真结果表明, 基本蚁群算法得到的解质量最差; 粒子群蚁群算法得到的分配解最好, 但是运算时间最长; 量子蚁群算法得到的解稍次于粒子群蚁群算法, 但分配时间比另两种算法减少了一半。因此, 在大规模的多机器人任务分配中, 量子蚁群算法具有更强的适用性。

关键词:自动控制技术; 任务分配; 机器人联盟形成; 蚁群优化; 粒子群蚁群优化; 量子蚁群优化中图分类号:T P242 文献标志码:A 文章编号:1671 5497(2010) 01 0123 07

Multi robot task allocation based on swarm intelligence

LIU Shu hua, ZH ANG Yu, WU H ong yan, LIU Jie

(S chool of Comp uter Science , N or theas t N or mal Univer sity , Changchun 130117, China)

Abstract:The task allocation w as studied based on the sw arm inteeligence for the larg e scale multi robot system w ith loo se and tight coupled tasks adopting the hierarchial architecture. In the high lev el, the ant colony algo rithm w as em ploy ed to find the optimal allocation of the loo se coupled tasks, namely, based o n the reverse distribution idea, taking each ant to form a task, an undertaker w as chosen for every task. In the low lev el, the coalitio n fo rmation algo rithms based on the ant co lony optimization(ACO ) , the particle sw arm and ant colom y optim ization (PSACO) , o r the quantum inspised ant colony optimization (QA CO ) w as pr opo sed respectively fo r perform in a tig ht coupled task. Sim ulations w ere perfo rmed and results show ed that PSACO prov ides the best so lution, but its running time is the largest; QACO is a little inferior in solution quality to PSACO, how ever, it needs only a half time of the 2o ther methods. T herefo re, QACO appears mo re suitable for the task allocation of the larg e scale multi robot system.

Key words:autom atic control technolog y; task allocation; robot coalition form ation; ant co lony optimization; particle sw arm and ant colony optimization; quantum inspired ant co lony optimizatio n 多机器人任务分配问题M RT A(M ulti robot task allocation) 是多机器人系统研究的一个基础问题, 体现了系统高层组织形式与运行机制, 是多

收稿日期:2008 08 30.

基金项目:国家自然科学基金项目(60573067).

, . . edu. 机器人系统实现目标的基础。随着系统中机器人数目和任务难度的增加, 任务分配问题就显得越来越重要[1]。目前, 多机器人任务分配方法主要

%124%

吉林大学学报(工学版) 第40卷

包括以下几种:基于行为的分配方法, 如ALLCANCE 、BLE 和ASyM TRe , 这种方法虽然实时性、容错性和鲁棒性好, 但只能求得局部最优解。基于市场机制的方法是目前主流的任务分配方法, 如First pr ice auctio ns 、Dy namic role assig nm ent [6]、T raderbo ts [7]、M +系统[8]、MU RDOCH [9]和DEMiR CF [10]等, 该方法因具有良好的可扩展性而特别适合于分布式机器人领域, 而且理论上能够保证得到任务的最优分配, 但任务分配过程中通讯开销大, 一旦通讯中断, 性能将明显下降[11], 所以它较适合于中小规模的任务分配问题。基于群体智能的方法是受到社会性昆虫行为的启发, 通过对社会性昆虫觅食任务等的模拟产生的任务分配方法。由于群体中相互合作的个体是分布的, 不会由于某一个或者某几个个体的故障而影响整个问题的求解, 而且个体之间通过非直接通信进行合作, 使系统具有更好的可扩充性。因此群体智能方法非常适合于分布式多机器人系统, 而且也有越来越多的研究者将群体智能方法应用到多机器人任务分配中, 其典型代表是蚁群算法[12 14]。但是在应用中都是让蚂蚁代表机器人去选择任务, 这样就局限其只能用于松散型任务(单个机器人可独立完成的任务) 分配中。

作者提出逆转分配思想使蚁群算法可应用于求解大规模机器人松散耦合型任务分配问题中。让蚂蚁代表任务, 为每个任务选择任务的承担者。对于紧耦合型任务(必须由多个机器人合作才能完成的任务) , 蚂蚁分别采用基本蚁群算法、粒子群蚁群算法和量子蚁群算法求解相应的机器人联盟产生紧耦合型任务解。

[5]

[2]

[3]

[4]

相应的联盟形成算法, 产生紧耦合任务解, 即该任务的承担者。

图1 系统层次图

Fig. 1 Hierarchy architecture of system

2 机器人联盟形成的关键问题

2. 1 机器人联盟问题描述

(1) 机器人的能力描述

系统中所有机器人构成一个多机器人集合R ={R 1, R 2, , R N }, R i 的能力向量为B R i =(b i 1, b i 2, , b im ) , 对应的能力代价向量为cos t R i =(cos t i 1, cos t i 2, , cos t im ) , 其中cos t ij 表示R i 完成能力b ij 需要花费的代价。当b ij =0表示R i 不具备能力b ij , R i 具有m 种能力的代价定义为

j =1

! cos t

b ij 。

(2) 机器人联盟的能力描述

机器人联盟C 是一组合作的、能共同完成某一任务的机器人集合。一个联盟C 是R 的一个非空子集。根据机器人的能力属性不同, 联盟C 的能力向量也不同。对于可加能力(如搬运等) , 联盟C 的能力为B C =

R ∀C

! B

[15]

, 而可并能力(如

[15]

1 系统结构

为实现松散耦合型任务分配过程, 本文采用层次结构, 如图1所示。图1中, R i 表示机器人, Task i 表示任务。在底层, 对于多机器人任务Task i , 采用相应的联盟形成算法形成机器人联盟。高层采用蚁群算法进行任务分配。高层蚁群算法实现任务分配的寻优, 并让蚂蚁代表任务, 为每个任务选择任务的承担者。底层用于形成机器人联盟产生紧耦合型任务解。

系统的整体工作流程如下:首先蚂蚁处于高层, 从第一个任务出发, 为其选择适合的承担者;

可视距离等) 联盟C 的能力为B C =R #B R i

∀C

。

根据机器人的能力描述, 联盟能力的折合代价定义为

可加能力:D(C) =

R ∀C j =1

! ! cos t

j=1

b ij

可并能力:D(C) =R #∀C

! co s t

b ij

(3) 任务能力需求描述

设有k 个任务T ={t 1, t 2, , t k }, 求解任务t 需要的能力表示为向量B t =(b 1, b 2, , b m ) T 。

机器人联盟C 能完成任务t 的条件是:B C ∃t

第1期

(4) 联盟收益定义

刘淑华, 等:基于群体智能的多机器人任务分配

-! n

%125%

定义联盟完成任务的回报函数为reward :T &R , 是从任务集合到正实数集合的一个映射, 依赖于需要完成的任务及其他要求。定义联盟完

成任务的代价函数为co st :C &R +, 是从联盟集合到正实数集合的一个映射。本文考虑两种代价:∋联盟固有代价C _cost:如能量消耗或计算需求等。这里主要考虑机器人为完成任务的能力消耗, 包括联盟中机器人间的通信代价和联盟能力的折合代价; (任务代价T _cost :如任务完成时间或距离等, 这里主要考虑完成任务的距离代价。因此本文定义代价函数为:

Co st (C, t) = 1C _cost + 1T _cost, 1、 2为固有代价和任务代价的权重, 1>0, 2>0。根据Robot 联盟与Ag ent 联盟的差别, Ro bot 联盟收益定义为:

Inc (C) =FT C ) [rew (t) -Cost (C, t) ]

(1)

式中:FT C 为容错因子; rew (t) 为机器人完成任务t 得到的回报。2. 2 机器人联盟评价标准

由于机器人间不可以重新分配资源, 联盟中可能会有一个或几个机器人是资源的主要贡献者, 任务能否执行主要依赖于它们, 它们就成了联盟不可缺少的重要成员。考虑到这些重要机器人成员可能发生故障导致任务执行失败, 所以这样的联盟应该避免。联盟失衡(co alition imbalance) 是指联盟中各个成员资源分布的不均衡程度。完全平衡联盟是指联盟中每个成员对任务产生相同的贡献。平衡因子BC (Balance coefficient) 量化联盟的失衡程度, 即评价联盟偏离完全平衡联盟的程度。BC 定义为[16]

BC =

12n

(2)

式中: + =1; f (n) =1-e 是联盟大小的函数。当n 到达某一点后, 函数值不会有明显的增加, 即继续增加机器人数目并不能提高系统性能, 这与实际情况相符。

3 底层机器人联盟的求解

3. 1 基于基本蚁群算法求解机器人联盟

将m 只蚂蚁随机置于n 个机器人上, 对于任意一只蚂蚁k 选择机器人盟友j 的概率为[17]

#∃

ij ij k p ij =, j ∀J k (4) #∃[∀iu (t) ][1/d iu ]

u ∀J

ij (t) 式中:J k 为蚂蚁k 没有选择的机器人集合; ∀

表示t 时刻在i , j 连线上残留的信息素量; d ij (i, j =1, 2, , n) 表示Robot i 与Ro bot j 之间的距

离, 即通信开销; 参数#、∃分别为路径积累的信息素强度和通信开销的权重。

当蚂蚁选择一个机器人后发现当前联盟已能完成任务时, 则停止寻径。当所有蚂蚁都完成一次求解, 则完成一次循环。将本次循环找到的联盟收益最大的解作为当前最优解, 并按下面的公式更新信息素的强度

[17]

∀ij (t +1) ∗%∀ij (t) +

k =1

式中:&∀ij 表示第k 只蚂蚁在本次循环中对Robot i 、Robot j 之间熟悉度的增量

&∀ij

(5)

ij =&∀

k 如果机器人k 形成的联盟

, m

包含机器人i 和j

! C k

k=1

0, 其他

(6)

式中:Inc (C k ) 是蚂蚁k 形成联盟的收益。

算法中参数#、∃、%用实验方法确定其最优组合, 停止条件用固定进化代数或者当进化趋势不明显时停止计算。算法的时间复杂度为O(NC %m %n 2) , 其中N C 表示迭代次数。

3. 2 基于粒子群算法求解机器人联盟

粒子群算法(PSO ) 是由Eber hart 和Kennedy 等[18]于1995年提出的一种进化计算算法, 其基本思想来源于对鸟群觅食过程的研究及行为模拟。PSO 首先初始化一群随机粒子(随机解) , 然后通过迭代找到最优解. 在每次迭代中, 每个粒子根据以下公式更新自己的速度和新的位置[18]

v k+1=c 0v k +c 1(pbest k -x k ) +c 2(gbest k -x k )

(1, 2, , n ) 是联盟C 的资源分布; 式中:(

taskv alue 是完成任务的回报。对于相同大小的

联盟, BC 越大, 则联盟越平衡。

联盟越大其容错性越好, 平衡性也越好, 但是由于越大的联盟代价越大(能力折合代价、通信代价等) , 所以要在联盟平衡和联盟大小之间找到一个折中, 即容错因子FT C (Fault tolerance coefficient) 。FTC 定义为

[16]

%126%

x k +1=x k +v k+1

吉林大学学报(工学版)

(8)

第40卷

得到C −1(k) , C −1(k ) 与pcbest 交叉得到C . 1(k) , C . 1(k ) 以一定的概率变异到C 1(k ) 。如果当前联盟C 1(k) 能完成任务, 则根据式(3) 计算适应值Income1, 若Incom e1>Inco me0, 接受新值; 否则就拒绝, 第j 只蚂蚁形成的联盟仍然为C 0(k) , 重新找出各只蚂蚁的个体极值ptbest 和极值联盟pcbest, 找出全局极值gtbest 和全局极值联盟gcbest 。

Step5根据式(1) 计算各蚂蚁形成联盟的收益Inc (C k ) , 记录当前的最好解。

Step6按式(5) (6) 更新信息素。

Step7Set t =t +1, N C=NC+1, &∀ij =0Step8if(NC

Step9输出最优联盟及其收益。3. 3 基于量子蚁群算法求解机器人联盟

2002年Kuk H yun H an 提出量子进化算法

[20]

式中:pbest 表示粒子本身找到的最优解的位置;

gbest 表示整个种群目前找到的最优解的位置; v k 是粒子的速度向量; x k 是当前粒子的位置; c 0、c 1和c 2是权重系数; x k+1是x k 、pbest -x k 和gbest -x k 矢量的加权和。

(1) 粒子群蚁群算法(PSOACO)

基本PSO 算法擅长解决连续优化问题, 对于离散优化问题, 其速度难以表达。故借鉴遗传算法的思想:式(7) 中:c 0v k 项可以看作变异操作, c 1(pbest k -x k ) +c 2(g best k -x k ) 可以看作交叉操作, 将当前解与个体极值和全局极值分别作交叉操作[19]。

粒子群蚁群算法的思想是让蚂蚁具有+粒子, 的特性, 利用+粒子, 本身信息、个体极值信息和全局信息来指导蚂蚁选择盟友, 形成最优联盟。当前联盟为基本联盟, 让当前联盟与个体极值联盟和全局极值联盟分别作交叉操作, 产生的解为新联盟, 再作变异操作。

本文采取的交叉策略是在第二个串中随机选择一个交叉区域, 然后将o ld2的交叉区域加到old1对应的位置。变异策略是在当前串中随机选择一个变异位置, 如果为-1(表示机器人未选中) , 则将其置为1(表示机器人选中) , 反之亦然。

(2) PSOACO 算法描述

Step1初始化:NC=0(NC 为迭代次数) , J k

={1, 2, , n}。利用蚁群算法, 完成一次遍历(形成m 个联盟) 。按式(3) 计算适应值(各个初始联盟的收益) Income0, 设置当前适应值为个体极值ptbest, 当前联盟为个体极值联盟pcbest, 根据各个粒子的个体极值ptbest, 找出全局极值gtbest 和全局极值联盟gcbest 。

Step2将m 只蚂蚁随机置于n 个机器人上。

for k =1to m

{将各蚂蚁的初始出发点的机器人置于当前联盟中, 即初始联盟。从J 中删除该机器人的标号, 计算各初始联盟的能力向量B C k }

, 该算法体现出卓越的性能, 不仅具有很好

的搜索寻优能力, 有效避免早熟收敛, 并且以较小规模的种群就能获得最优解。因此本文将量子进化思想融合到基本ACO 算法中, 提出一种新颖的量子蚁群算法(Quantum inspired ant co lony optimization, QACO) 。

(1) 量子蚁群算法(QACO)

量子蚁群算法的基本思想是使蚂蚁量子化, 每只蚂蚁为一个量子个体, 使其具有量子特性, 并且用蚂蚁选择盟友的概率P 代替量子位编码, 直接采用概率位编码。由于引入了量子计算思想, 与基本ACO 算法相比, QACO 算法需要添加相应的测量过程和修正过程, 本文采用文献[20]中提出的测量和修正算法框架。

概率位编码表示为:

P 0P , 其中P 0+P 1=

1。因此本文采用概率位编码的个体表示为:q k =P k 10P k 20P k j 0P k m 0P k 11P k 21P k j 1P k m 1

, 其中k =1, 2, , n; j =

Step3for k =1to m w hile(B C k

{按式(4) 中的p ij 选择下一个盟友机器人j ,

将机器人j 置于当前联盟中。Delete j from J k 。累加联盟能力向量}

Step4for k =1to m

C (k) 与k

1, 2, , m; P k j 1=P ij ; P k j 0=1-P k j 1。设Q(t) ={q t 1, q t 2, , q t n }表示QACO 第t 代时的种群, P(t) ={X 1, X 2, , X n }, 其中X k 为对第k 个个体测量得到的状态, X t k ={x t k 1, x t k 2, , x t km }, x t kj 或者为0, 或者为1, 为0时表示机器人j 未被选, t

第1期

(2) QACO 算法描述

刘淑华, 等:基于群体智能的多机器人任务分配

&∀k ij =

%127%

Step1初始化t =0, NC =0, NC max =N , &∀ij =0, ∀ij (0) =∀0。

Step2将m 只蚂蚁随机置于n 个机器人上for k =1to m for j =1to n

{若蚂蚁k 的出发点为机器人j , 则P k j 1=1。然后根据式(4) 计算选择盟友的概率, P k j 1=P k ij , P k j 0=1-P k ij }

Step3对种群Q(t) 中各个体实施测量, 得到一组状态P (t) 。

Step4检查P(t) 中每个状态是否都为解, 不是则进行修正, go to Step10。

Step5根据式(1) 计算各状态(联盟) X 的收益Inc(X ) 。

Step6记录下最优联盟b 及其收益Inc(b) 。Step7根据式(5) 和(6) 更新信息素浓度。Step8Set t =t +1, NC=NC+1, &∀ij =0。Step9if (NC

else 输出最优联盟及其收益。Step10调用修正算法, 对不是解的状态进行修正。If P(t) 的状态都是问题的解then go to Step5。

t j

k=1

! cos t

, Q 为常数(10)

算法流程如下:

Step0Set t =0, NC=0(N C 为迭代次数) ,

ij (0) =∀0, &∀∀ij =0, numTask=s , numA nt=m , numRobot=n , 设置任务的能力需求, 每个机器人

具有的能力和相应的能力代价。

Step1

for i =1to s

fo r k =1to m do

{蚂蚁k 从第一个任务出发, 判断当前任务i 是否为紧耦合型任务, 如果是, 则转Step6, 否则根据式(9) 的概率p k ij 从J i 中选择一个任务承担者, 计算该承担者完成任务的收益, 然后蚂蚁k 移动到下一个任务, 重复上述判断直到为所有任务都分配一个承担者}

Step2 计算每只蚂蚁所对应任务分配方案的总收益, 更新最大收益及相应的分配方案。

Step3 根据式(5) (10) 更新信息素的强度∀ij (t +1) 。

Step4 Set t=t+1, N C=NC+1, &∀ij =0。 Step5If(N C

else 输出收益最大的任务分配方案。

Step6调用相应的联盟形成算法ACO 、PSOACO 和QACO 形成任务i 的一个机器人联盟。然后返回Step1。

经过上述6个步骤, 高层的蚁群算法通过调用低层的蚁群算法、粒子群蚁群算法和量子蚁群算法完成整个系统的任务分配。

4 高层任务分配过程

设蚂蚁个数为m , 每个任务为节点0, 其候选机器人或机器人联盟为节点1~n, 对于任意一只蚂蚁k 从节点0出发选择节点j 的概率为

#∃

ij ij p =, j ∀J k

#∃

[∀iu (t) ][1/cos t iu ]k

u ∀J

(9)

5 仿真实验

在TeamBots 仿真平台上进行了算法实现。以搬运问题为背景, 在环境中分布着若干个任务, 有松散型任务, 即单个机器人可独立完成的任务, 也有紧耦合型任务, 即必须由多个机器人合作才能完成的任务。机器人和任务的数目可根据需要设置, 每个任务和机器人都具有一个对应的能力向量。表1和表2给出了机器人和任务的相应信息。由表1和表2可以看出, 任务T 1、T 3、T 6和T 9必须由多个机器人合作才能完成。实验参数设置如下:蚂蚁数m =10, 最大迭代次数NC max =500, rew (T i ) =1000, 1= 2=1, = =! =0. 5, Q =1, #=1. 5, ∃=2, %=0. 9。

式中:J i 为任务i 的候选机器人或机器人联盟的集合; co s t ij 为机器人或机器人联盟完成任务i 的代价, 对于单个机器人完成任务的代价为它到任务的距离和它的能力消耗, 而机器人联盟完成任务的代价为Cost (C, t) 。对于任意一只蚂蚁k , 待分配任务列表中的第一个任务节点为寻优的起点, 蚂蚁k 为其选择一个任务承担者后, 便移

动到下一个任务, 然后为该任务选择一个任务承担者。当蚂蚁k 为所有任务选择完任务承担者后, 则完成一次任务分配。当所有蚂蚁都完成一次求解, 则完成一次循环, 将本次循环找到的收益最大的解作为当前最优解。然后, 按照式(5) 更新,

表1 机器人能力向量和相应能力代价(3种能力) Table 1 C apacity and cost vector of robots

机器人R 0R 1R 2R 3R 4R 5R 6R 7

能力[***********]001221

代价[***********]323321

机器人R 8R 9R 10R 11R 12R 13R 14

能力[***********]021

代价[***********]312

在200代左右、QACO 算法在300代左右才收敛到最优解, 但是由于PSOA CO 算法中每只蚂蚁完成一次的周游时间较长, 所以相同迭代次数的情况下, Q ACO 算法运行时间比PSOACO 算法缩短了一半。综合比较, QACO 可快速得到一个较优分配方案。

6 结束语

针对多机器人松散耦合型任务分配问题, 采用逆转分配思想提出一种基于蚁群算法的任务分配机制。并且深入探讨了机器人联盟形成中的关键问题, 提出3种求解机器人联盟的算法蚁群算法、粒子群蚁群算法和量子蚁群算法。最后, 在TeamBots 仿真平台上对本文算法进行了实现。仿真结果表明, 基本ACO 算法和PSOACO 算法分配时间较长, 而QACO 算法分配时间要比前两者缩短了一半, PSOACO 算法得出的分配解最好, 基本A CO 算法最差。因此, 如果想要快速得到一个较优的任务分配方案, QACO 算法是比较好的选择。参考文献:

[1]张嵛, 刘淑华. 多机器人任务分配的研究与进展

[J].智能系统学报, 2008, 3(2) :115 120.

Zhang Yu, L iu Shu hua. Sur vey of multi robot task allocatio n [J]. CA AI T ransact ions o n Intellig ent Systems, 2008, 3(2) :115 120.

[2]Parker L E. AL L IA N CE:an architecture for fault

tolerant multirobot coo per atio n[J].IEEE T ransac tions on R obotics and Auto mation, 1998, 14(2) :220 240.

[3]Werg er B, M ata ric M J. Bro adcast of local elig ibili

ty :behav ior based contro l fo r str ongly co operativ e

表2 任务信息(3种能力需求) Table 2 Information of tasks

任务T 0T 1T 2T 3T 4

需求[**************]

位置(13, 10) (0, 0) (10, -10) (-10, 10) (-8, -3)

任务T 5T 6T 7T 8T 9

需求[**************]

位置(15, 0) (

0, -10) (20, -10) (20, 20) (20, 0)

分别对ACO 、PSOA CO 和QACO 算法做10次实验, 计算机主要配置为:Intel Pentium M CPU 750, 1. 86GH z, 512MB 内存。对比结果

如图2和表3。

图2 平均进化曲线

Fig. 2 Average solution evolving curve 表3 A CO 、PSOACO 和QAC O 算法对比实验结果Table 3 Results comparison among AC O,

PSOACO and QAC O

算法ACO PSOACO QACO

最优解[1**********]0

最差解[1**********]5

平均解[1**********]4

运行时间/s

7. 378. 523. 75

multi r obot teams[C]/Pr oceeding s of A ut onomous Ag ent s, 2000:21 22.

[4]F ang T ang , L ynne E P. ASy M T Re:automated syn

thesis of multi robot task solut ion thr ough so ftwar e r eco nfigurat ion [C]/Pr oc of IEEE Internatio nal Conference o n Ro bo tics and A uto mation, Barcelo na, Spain, 2005:1501 1508.

[5]Zlo t R, Stentz A , Dias M B, et al. M ulti r obot ex

plo rat ion contro lled by a mar ket eco no my[C]/Pr oc of the IEEE intl Conf o n R obotics and A uto matio n, 2002:3016 3023.

[6]L uiz Chaimow icz, M ar io F M Campos, Vijay Ku

Dy fo r co r

从图2和表3可以看出, 基本ACO 算法寻优能力较差, 出现了早熟现象, 容易陷入局部最优,

bo ts[C]/P ro c o f the I EEE Intl Conf on Ro bo tics and A ut omatio n, 2002:293 298.

[7]Dias M B. T raderBots:a new par adigm for robust

and efficient mult iro bo t coo rdinatio n in dynamic en v iro nments [D ].

Pit tsburg h:R obotics I nstit ute,

Car neg ie M ello n U niv ersity , 2004.

[8]Bo telho S, A lami R. M +:a scheme fo r multi ro bo t

cooperation t hr ough neg otiated task allocation and a chiev ement[C]/P ro c I EEE Int Co nf R obot A uto mat , 1999:1234 1239.

[9]Gerkey B P, M atar ic M J. Sold! :auction methods

for multir obot coo rdination[C]/IEEE T ransact ions on Robotics and A utomation, 2002:758 786. [10]Sanem Sar iel, T ucker Balch. A distr ibuted multi r o

bot coo per atio n framew or k fo r real time task a chievement [C ]/Distr ibuted A utonomo us Robot ic Sy st ems, T oky o:Spr ing er, 2006:187 196.

[11]Kalra N , M a rtinoli A. A comparative study o f mar

ket based and thresho ld based t ask allocatio n[C]/Distributed A utonomo us Ro botic Sy st ems, T o ky o:Spr inger, 2006:1 11.

[12]杨冬, 王正欧. 改进的蚂蚁算法求解任务分配问题

[J].天津大学学报, 2004, 37(4) :373 376. Yang D ong, W ang Zhang ou. Impro ved ant alg o r ithm for assig nment pro blem[J].Jo ur na l of T ianjin U niversit y, 2004, 37(4) :373 376.

[13]丁潆颖, 何衍, 蒋静坪. 基于蚁群算法的多机器人协

作策略[J].机器人, 2003, 25(5) :414 418. Ding Y ing y ing , H e Y an, Jiang Jing ping. M ulti r o bot coo per atio n method based o n the ant alg or ithm [J].Robot, 2003, 25(5) :414 418.

[14]Zhang Dan dan, Xie G uang ming, Y u Jun zhi, et al.

Adaptive task assignment for multiple mo bile ro bo ts via swar m intelligence appr oach [J ].R obotics and Auto no mous Sy st ems, 2007, 55(7) :572 588. [15]柳林, 季秀才, 郑志强. 基于市场法及能力分类的多

机器人任务分配方法[J].机器人, 2006, 28(3) :337 343.

Liu L in, Ji X iu cai, Z heng Zhi qiang. M ulti ro bo t task allocation based on market and capability classi ficat ion[J].Ro bo t, 2006, 28(3) :337 343. [16]Lo vekesh V ig , Julie A A. M ulti ro bot coalitio n fo r

mation[J]. IEEE T r ansactio n on Ro bo tics, 2006, 22(4) :1 13.

[17]Xia N a, Jiang Jian guo, H u Y a ling. Solut ion to a

g ent co alit ion pr oblem using impro ved ant co lony o p timization algo rithm[C]/Pr oceeding s of the IEEE/WIC/A CM Internatio nal Conference o n Intellig ent Ag ent T echnolog y, 2004.

[18]Eberhar t R C, Kennedy J. A new o ptimizer using

par ticles swar m theor y[C]/Pr oc Sixth Int Sympo sium on M icro M achine and H uman Science, Nag o y a, 1995:39 43.

[19]高尚, 韩斌, 吴小俊, 等. 求解旅行商问题的混合粒

子群优化算法[J]. 控制与决策, 2004, 19(11) :1286 1289.

Gao Shang, Han Bin, Wu Xiao jin, et al. Solving trav eling salesman pr oblem by hy brid par ticle swar m optimizatio n alg or ithm [J ].Co nt rol and Decisio n, 2004, 19(11) :1286 1289.

[20]H an Kuk H yun. Q uantum inspired evo lutio nar y al

go rit hm fo r a class of combinato rial optimization[C]/IEEE T ransact ions on Ev olutionary Computatio n, 2002:580 593.

第40卷第1期2010年1月

吉林大学学报(工学版)

Journal o f Jilin U niv ersity (Engineering and T echnolo gy Edition)

Vol. 40 No. 1 Jan. 2010

基于群体智能的多机器人任务分配

刘淑华, 张嵛, 吴洪岩, 刘杰

(东北师范大学计算机学院, 长春130017)

Multi robot task allocation based on swarm intelligence

LIU Shu hua, ZH ANG Yu, WU H ong yan, LIU Jie

(S chool of Comp uter Science , N or theas t N or mal Univer sity , Changchun 130117, China)

收稿日期:2008 08 30.

基金项目:国家自然科学基金项目(60573067).

, . . edu. 机器人系统实现目标的基础。随着系统中机器人数目和任务难度的增加, 任务分配问题就显得越来越重要[1]。目前, 多机器人任务分配方法主要

%124%

吉林大学学报(工学版) 第40卷

[5]

[2]

[3]

[4]

相应的联盟形成算法, 产生紧耦合任务解, 即该任务的承担者。

图1 系统层次图

Fig. 1 Hierarchy architecture of system

2 机器人联盟形成的关键问题

2. 1 机器人联盟问题描述

(1) 机器人的能力描述

j =1

! cos t

b ij 。

(2) 机器人联盟的能力描述

R ∀C

! B

[15]

, 而可并能力(如

[15]

1 系统结构

系统的整体工作流程如下:首先蚂蚁处于高层, 从第一个任务出发, 为其选择适合的承担者;

可视距离等) 联盟C 的能力为B C =R #B R i

∀C

。

根据机器人的能力描述, 联盟能力的折合代价定义为

可加能力:D(C) =

R ∀C j =1

! ! cos t

j=1

b ij

可并能力:D(C) =R #∀C

! co s t

b ij

(3) 任务能力需求描述

设有k 个任务T ={t 1, t 2, , t k }, 求解任务t 需要的能力表示为向量B t =(b 1, b 2, , b m ) T 。

机器人联盟C 能完成任务t 的条件是:B C ∃t

第1期

(4) 联盟收益定义

刘淑华, 等:基于群体智能的多机器人任务分配

-! n

%125%

定义联盟完成任务的回报函数为reward :T &R , 是从任务集合到正实数集合的一个映射, 依赖于需要完成的任务及其他要求。定义联盟完

Co st (C, t) = 1C _cost + 1T _cost, 1、 2为固有代价和任务代价的权重, 1>0, 2>0。根据Robot 联盟与Ag ent 联盟的差别, Ro bot 联盟收益定义为:

Inc (C) =FT C ) [rew (t) -Cost (C, t) ]

(1)

式中:FT C 为容错因子; rew (t) 为机器人完成任务t 得到的回报。2. 2 机器人联盟评价标准

BC =

12n

(2)

式中: + =1; f (n) =1-e 是联盟大小的函数。当n 到达某一点后, 函数值不会有明显的增加, 即继续增加机器人数目并不能提高系统性能, 这与实际情况相符。

3 底层机器人联盟的求解

3. 1 基于基本蚁群算法求解机器人联盟

将m 只蚂蚁随机置于n 个机器人上, 对于任意一只蚂蚁k 选择机器人盟友j 的概率为[17]

#∃

ij ij k p ij =, j ∀J k (4) #∃[∀iu (t) ][1/d iu ]

u ∀J

ij (t) 式中:J k 为蚂蚁k 没有选择的机器人集合; ∀

表示t 时刻在i , j 连线上残留的信息素量; d ij (i, j =1, 2, , n) 表示Robot i 与Ro bot j 之间的距

离, 即通信开销; 参数#、∃分别为路径积累的信息素强度和通信开销的权重。

[17]

∀ij (t +1) ∗%∀ij (t) +

k =1

式中:&∀ij 表示第k 只蚂蚁在本次循环中对Robot i 、Robot j 之间熟悉度的增量

&∀ij

(5)

ij =&∀

k 如果机器人k 形成的联盟

, m

包含机器人i 和j

! C k

k=1

0, 其他

(6)

式中:Inc (C k ) 是蚂蚁k 形成联盟的收益。

3. 2 基于粒子群算法求解机器人联盟

v k+1=c 0v k +c 1(pbest k -x k ) +c 2(gbest k -x k )

(1, 2, , n ) 是联盟C 的资源分布; 式中:(

taskv alue 是完成任务的回报。对于相同大小的

联盟, BC 越大, 则联盟越平衡。

[16]

%126%

x k +1=x k +v k+1

吉林大学学报(工学版)

(8)

第40卷

Step5根据式(1) 计算各蚂蚁形成联盟的收益Inc (C k ) , 记录当前的最好解。

Step6按式(5) (6) 更新信息素。

Step7Set t =t +1, N C=NC+1, &∀ij =0Step8if(NC

Step9输出最优联盟及其收益。3. 3 基于量子蚁群算法求解机器人联盟

2002年Kuk H yun H an 提出量子进化算法

[20]

式中:pbest 表示粒子本身找到的最优解的位置;

(1) 粒子群蚁群算法(PSOACO)

(2) PSOACO 算法描述

Step1初始化:NC=0(NC 为迭代次数) , J k

Step2将m 只蚂蚁随机置于n 个机器人上。

for k =1to m

{将各蚂蚁的初始出发点的机器人置于当前联盟中, 即初始联盟。从J 中删除该机器人的标号, 计算各初始联盟的能力向量B C k }

, 该算法体现出卓越的性能, 不仅具有很好

(1) 量子蚁群算法(QACO)

概率位编码表示为:

P 0P , 其中P 0+P 1=

1。因此本文采用概率位编码的个体表示为:q k =P k 10P k 20P k j 0P k m 0P k 11P k 21P k j 1P k m 1

, 其中k =1, 2, , n; j =

Step3for k =1to m w hile(B C k

{按式(4) 中的p ij 选择下一个盟友机器人j ,

将机器人j 置于当前联盟中。Delete j from J k 。累加联盟能力向量}

Step4for k =1to m

C (k) 与k

第1期

(2) QACO 算法描述

刘淑华, 等:基于群体智能的多机器人任务分配

&∀k ij =

%127%

Step1初始化t =0, NC =0, NC max =N , &∀ij =0, ∀ij (0) =∀0。

Step2将m 只蚂蚁随机置于n 个机器人上for k =1to m for j =1to n

{若蚂蚁k 的出发点为机器人j , 则P k j 1=1。然后根据式(4) 计算选择盟友的概率, P k j 1=P k ij , P k j 0=1-P k ij }

Step3对种群Q(t) 中各个体实施测量, 得到一组状态P (t) 。

Step4检查P(t) 中每个状态是否都为解, 不是则进行修正, go to Step10。

Step5根据式(1) 计算各状态(联盟) X 的收益Inc(X ) 。

Step6记录下最优联盟b 及其收益Inc(b) 。Step7根据式(5) 和(6) 更新信息素浓度。Step8Set t =t +1, NC=NC+1, &∀ij =0。Step9if (NC

else 输出最优联盟及其收益。Step10调用修正算法, 对不是解的状态进行修正。If P(t) 的状态都是问题的解then go to Step5。

t j

k=1

! cos t

, Q 为常数(10)

算法流程如下:

Step0Set t =0, NC=0(N C 为迭代次数) ,

ij (0) =∀0, &∀∀ij =0, numTask=s , numA nt=m , numRobot=n , 设置任务的能力需求, 每个机器人

具有的能力和相应的能力代价。

Step1

for i =1to s

fo r k =1to m do

Step2 计算每只蚂蚁所对应任务分配方案的总收益, 更新最大收益及相应的分配方案。

Step3 根据式(5) (10) 更新信息素的强度∀ij (t +1) 。

Step4 Set t=t+1, N C=NC+1, &∀ij =0。 Step5If(N C

else 输出收益最大的任务分配方案。

Step6调用相应的联盟形成算法ACO 、PSOACO 和QACO 形成任务i 的一个机器人联盟。然后返回Step1。

经过上述6个步骤, 高层的蚁群算法通过调用低层的蚁群算法、粒子群蚁群算法和量子蚁群算法完成整个系统的任务分配。

4 高层任务分配过程

设蚂蚁个数为m , 每个任务为节点0, 其候选机器人或机器人联盟为节点1~n, 对于任意一只蚂蚁k 从节点0出发选择节点j 的概率为

#∃

ij ij p =, j ∀J k

#∃

[∀iu (t) ][1/cos t iu ]k

u ∀J

(9)

5 仿真实验

表1 机器人能力向量和相应能力代价(3种能力) Table 1 C apacity and cost vector of robots

机器人R 0R 1R 2R 3R 4R 5R 6R 7

能力[***********]001221

代价[***********]323321

机器人R 8R 9R 10R 11R 12R 13R 14

能力[***********]021

代价[***********]312

6 结束语

[1]张嵛, 刘淑华. 多机器人任务分配的研究与进展

[J].智能系统学报, 2008, 3(2) :115 120.

Zhang Yu, L iu Shu hua. Sur vey of multi robot task allocatio n [J]. CA AI T ransact ions o n Intellig ent Systems, 2008, 3(2) :115 120.

[2]Parker L E. AL L IA N CE:an architecture for fault

tolerant multirobot coo per atio n[J].IEEE T ransac tions on R obotics and Auto mation, 1998, 14(2) :220 240.

[3]Werg er B, M ata ric M J. Bro adcast of local elig ibili

ty :behav ior based contro l fo r str ongly co operativ e

表2 任务信息(3种能力需求) Table 2 Information of tasks

任务T 0T 1T 2T 3T 4

需求[**************]

位置(13, 10) (0, 0) (10, -10) (-10, 10) (-8, -3)

任务T 5T 6T 7T 8T 9

需求[**************]

位置(15, 0) (

0, -10) (20, -10) (20, 20) (20, 0)

分别对ACO 、PSOA CO 和QACO 算法做10次实验, 计算机主要配置为:Intel Pentium M CPU 750, 1. 86GH z, 512MB 内存。对比结果

如图2和表3。

图2 平均进化曲线

Fig. 2 Average solution evolving curve 表3 A CO 、PSOACO 和QAC O 算法对比实验结果Table 3 Results comparison among AC O,

PSOACO and QAC O

算法ACO PSOACO QACO

最优解[1**********]0

最差解[1**********]5

平均解[1**********]4

运行时间/s

7. 378. 523. 75

multi r obot teams[C]/Pr oceeding s of A ut onomous Ag ent s, 2000:21 22.

[4]F ang T ang , L ynne E P. ASy M T Re:automated syn

thesis of multi robot task solut ion thr ough so ftwar e r eco nfigurat ion [C]/Pr oc of IEEE Internatio nal Conference o n Ro bo tics and A uto mation, Barcelo na, Spain, 2005:1501 1508.

[5]Zlo t R, Stentz A , Dias M B, et al. M ulti r obot ex

plo rat ion contro lled by a mar ket eco no my[C]/Pr oc of the IEEE intl Conf o n R obotics and A uto matio n, 2002:3016 3023.

[6]L uiz Chaimow icz, M ar io F M Campos, Vijay Ku

Dy fo r co r

从图2和表3可以看出, 基本ACO 算法寻优能力较差, 出现了早熟现象, 容易陷入局部最优,

bo ts[C]/P ro c o f the I EEE Intl Conf on Ro bo tics and A ut omatio n, 2002:293 298.

[7]Dias M B. T raderBots:a new par adigm for robust

and efficient mult iro bo t coo rdinatio n in dynamic en v iro nments [D ].

Pit tsburg h:R obotics I nstit ute,

Car neg ie M ello n U niv ersity , 2004.

[8]Bo telho S, A lami R. M +:a scheme fo r multi ro bo t

cooperation t hr ough neg otiated task allocation and a chiev ement[C]/P ro c I EEE Int Co nf R obot A uto mat , 1999:1234 1239.

[9]Gerkey B P, M atar ic M J. Sold! :auction methods

for multir obot coo rdination[C]/IEEE T ransact ions on Robotics and A utomation, 2002:758 786. [10]Sanem Sar iel, T ucker Balch. A distr ibuted multi r o

bot coo per atio n framew or k fo r real time task a chievement [C ]/Distr ibuted A utonomo us Robot ic Sy st ems, T oky o:Spr ing er, 2006:187 196.

[11]Kalra N , M a rtinoli A. A comparative study o f mar

ket based and thresho ld based t ask allocatio n[C]/Distributed A utonomo us Ro botic Sy st ems, T o ky o:Spr inger, 2006:1 11.

[12]杨冬, 王正欧. 改进的蚂蚁算法求解任务分配问题

[J].天津大学学报, 2004, 37(4) :373 376. Yang D ong, W ang Zhang ou. Impro ved ant alg o r ithm for assig nment pro blem[J].Jo ur na l of T ianjin U niversit y, 2004, 37(4) :373 376.

[13]丁潆颖, 何衍, 蒋静坪. 基于蚁群算法的多机器人协

作策略[J].机器人, 2003, 25(5) :414 418. Ding Y ing y ing , H e Y an, Jiang Jing ping. M ulti r o bot coo per atio n method based o n the ant alg or ithm [J].Robot, 2003, 25(5) :414 418.

[14]Zhang Dan dan, Xie G uang ming, Y u Jun zhi, et al.

机器人任务分配方法[J].机器人, 2006, 28(3) :337 343.

mation[J]. IEEE T r ansactio n on Ro bo tics, 2006, 22(4) :1 13.

[17]Xia N a, Jiang Jian guo, H u Y a ling. Solut ion to a

g ent co alit ion pr oblem using impro ved ant co lony o p timization algo rithm[C]/Pr oceeding s of the IEEE/WIC/A CM Internatio nal Conference o n Intellig ent Ag ent T echnolog y, 2004.

[18]Eberhar t R C, Kennedy J. A new o ptimizer using

par ticles swar m theor y[C]/Pr oc Sixth Int Sympo sium on M icro M achine and H uman Science, Nag o y a, 1995:39 43.

[19]高尚, 韩斌, 吴小俊, 等. 求解旅行商问题的混合粒

子群优化算法[J]. 控制与决策, 2004, 19(11) :1286 1289.

Gao Shang, Han Bin, Wu Xiao jin, et al. Solving trav eling salesman pr oblem by hy brid par ticle swar m optimizatio n alg or ithm [J ].Co nt rol and Decisio n, 2004, 19(11) :1286 1289.

[20]H an Kuk H yun. Q uantum inspired evo lutio nar y al

go rit hm fo r a class of combinato rial optimization[C]/IEEE T ransact ions on Ev olutionary Computatio n, 2002:580 593.

基于群体智能的多机器人任务分配

相关内容

热门内容

标签