曹宗华，吴 斌，黄玉清，邓春艳

(西南科技大学 信息工程学院，四川 绵阳 621010)

0 引言

随着社会的发展，由于机器人应用的领域和范围在不断扩展，虽然单个机器人的能力在提高，但是对于一些复杂的任务，单个机器人并不能满足人们的要求，因此，多机器人系统(MRS，Multi－Robot System)成为主要发展方向。MRTA(MRTA，Multi－Robot Task Allocate)是MRS 的研究方向中之一，MRTA 是指将多个任务分配给在最短时间内完成任务的机器人。MRS的研究起源于1980 年，MRTA 的研究是为了提高多机器人系统的性能，确保多机器人在执行任务过程中的协同性。MRTA 问题本质是最优分配问题，最初是在博弈论中提出的，相继在组合优化、调度、经济学、运筹学、群体智能等学科进行了深入研究。MRS 的结构可分为两大类:集中式分配和分布式分配。早期的多机器人系统任务分配多采用集中式的，由一个管理者负责任务的分配，这种方法不适合机器人规模较大的系统;分布式任务分配方法可以发挥系统的分布计算性能，相比集中式它具有高效性和鲁棒性。MRTA 算法主要包括基于行为的分配方法、基于市场机制方法及群体智能的分配方法等，这些分配算法都有各自的优点。基于行为的分配方法［1］，实时性和稳定性较好，只能求解局部最优;基于市场机制的分配方法［2-3］，实时性差和系统开销大，适用于小规模系统，能够实现全局最优;群体智能方法［4-6］，主要方法包括阈值法和蚁群方法，系统具有鲁棒性、实时性及高效性，适用于分布式MRTA;在MRTA 的研究中，群体智能方法是解决MRTA 的主要发展方向，文中采用改进的蚁群算法研究MRTA。

本文首先研究了多机器人系统及任务分配问题;然后叙述了蚁群算法;在此基础上设计了改进的蚁群算法来解决MRTA 问题;通过实验数据对算法仿真并分析;实验表明，本文算法能很好的解决大规模机器人系统任务分配问题。

1 多机器人系统描述

多机器人系统由单个具备多种不同功能的机器人构成，如智能感知、搬运能力、智能决策、通信能力等。且每个机器人都是自立的，对于简单的任务，单个机器就能完成。对于复杂任务，分成多个单个机器人可完成的原子任务，多机器人系统根据这些任务形成特定的联盟，从而适应任务需求。MRS 常采用Ad-hoc 网络，机器人之间可以进行信息交互，从而可实现分布式计算。

随机分布的MRS 分布结构。多机器人系统包括任务发布系统、通信系统及多个智能机器人。任务发布系统具备通信、复杂任务分解等功能;通信系统具备路由、点对点及广播等通信功能;智能机器人具备通信、任务规划及任务执行等功能。

1.1 机器人能力描述

多机器人系统包含n 个异构机器人R={Ri，1≤i≤n}，对于机器人Ri其能力向量ARi=diag{ai1，ai2…，ain}，ain定义为机器人Ri的第n 种能力强弱，若不具备能力n 则ain=0;C =［c1，c2，…cn］T，其中cn为机器人基本单项能力如移动能力、搬运能力、通信能力及各种传感能力等。

综上可得，单个机器人的能力可表示为E(Ri)=ARi×C。

1.2 任务描述

假设有m(m≥1)个任务，可表示为T ={Tk，1≤k≤m}，任务Tk对机器人的单项能力要求BTk=diag{bk1，bk2，…，bkn}。任务Tk所需能力E(Tk)=BTk×C，若机器人Ri能够完成任务Tk，则要求ain≥bkn，可以记为E(Tk)≤E(Ri)。

任务的约束条件主要包括时序约束、任务时间约束及多机器人协同约束等。时序约束是指不同任务Tk之间存在执行顺序。任务时间约束是指某个任务必须在指定的时间内完成。

1.3 机器人完成任务的代价

在多机器人系统中，由于机器人个体的能力存在差异，在完成相同的任务时，不同机器人所花费的代价也会存在差异。机器人Ri的能力向量为E(Ri)，机器人的各项能力在完成任务过程中有能量消耗，针对各项能力，所花代价向量表示为cost(ARi)=［costai1，costai2…，costain］T，因此，机器人Ri完成任务Tk所花代价可以定义为costi(Tk)=E(Tk)×cost(ARi)。

1.4 MRTA 问题描述

MRTA 是多机器人系统动态环境下协作完成任务的一个基本问题。对于多机器人系统执行给定的系统级任务，需要解决的是如何把任务分解给多个机器人及在何时执行该任务的问题，即MRTA。机器人Ri和任务Tk的分布如图1 所示。

图1 机器人及任务分布

多机器人系统的任务分配由协作规划层完成，协作规划层可以是一台或几台移动机器人甚至包括不可移动的计算处理平台或人类共同组成，要求有较强的通讯能力、计算能力和存储能力，可称之为指挥者。协作规划层为整个团队的最高控制中心，负责系统的全局规划、任务分配、角色任命，对协调层直接管理。

分布式任务分配的具体步骤如下:首先，任务规划，通过控制中心向多机器人系统的中央机器人下达任务，任务进入任务规划模块，协作规划模块取得任务后，运用知识把任务分解成多个子任务;第二步，将多个子任务随机发布给MRS 中的多个机器人;第三步，MRS 中的机器人运用群体智能算法求解最优分配，从而确定任务的接收者，接收任务的同时发送信息反馈其它机器人;最后，机器人接收任后会根据自己的角色和所要完成的任务，利用传感器采集的周围环境信息等，采用基于行为的控制方法规划自己的路径，确定机器人运动的速度和角度。

2 改进的蚁群算法

蚁群算法具有问题求解的快速性、全局最优特性及在优化过程初期解的合理性等特点，可以解决任务分配问题，在任务分配过程，主要考虑如何发挥系统的性能，将任务最优分配，实现系统最小代价。

2.1 算法思想

本文采用蚁群算法实现任务分配，用蚂蚁代表任务，机器人为任务的接收者。假设任务的个数为m，机器人的数目为n，PTkij(t)表示在t 时刻任务Tk由机器人i 转移到机器人j 的状态转移概率:

式中，Rc为任务i 的候选机器人集合;α 为信息启发式因子，表示轨迹的相对重要性，反映了任务在转移过程中所积累的信息对任务的转移所起的作用;β 为期望启发式因子，表示能见度的相对重要性，反映了任务在转移过程中启发信息在任务转移路径的选择中受重视程度。ηj(t)为启发函数:

式中Dj(Tk)表示机器人j 与任务Tk之间距离。τij(t)表示t 时刻在i 和j 连线上残留的信息素值;所有任务都完成一次求解，即完成一次循坏，从而可寻找出任务的最优执行者，并按下式更新信息素值:

式(3)中Δτij(t)(Q 为常数表示信息强度)表示Tk和Rj之间的信息素增强。其中:

根据上述计算公式，计算出任务Tk与机器人之间的信息素，信息素强度表示着机器人与任务间的适应度，信息素与机器人完成任务的代价及距离有关。因此，多个任务可根据信息素值进行分配。

2.2 算法的改进

上述算法中，只考虑了机器人到任务之间的距离，从而导致了分配结果出现“就近”问题。本文所考虑的任务分配要避免该问题，因此需对基本算法进行改进。

基于蚁群算法的多机器人任务分配中，转移概率仅决定了机器人接收任务的优先顺序，由于机器人的能力在计算转移概率时是未知的，而机器人与任务的距离是已知的，因此转移概率的启发函数仅与距离有关;任务分配的直接影响因素是信息素，因此在对信息素更新时应加入机器人能力的影响。也就是改进Δτij(t)表达式，写成如下形式:

式(5)中costj(Tk)表示的是机器人完成任务所花代价;Q1，Q2表示完成任务的代价和所行走距离在信息素中所占的比例。

采用改进后的信息素更新规则，需要从计算的结果的寻找最优分配方案，当机器人数目为N 时，任务数目为M(M ＜N)，时间复杂度为O(N!)，因此，当机器人和任务数目较多时，机器人在搜索过程将非常耗时，以至于算法不够高效。面对这种局面，提出一种快速高效搜索算法，在分布式多机器人系统中，任务的最后一个接收者负责计算任务的分配最优搜索，从而实现最优分配。最优搜索算法思想如下:

(1)为每个任务选取最优分配的机器人，时间复杂度为O(M* N);

(2)检查是否有多个任务分配给了同一个机器人，若否则转第(4)步;时间复杂度为O(M);

(3)对于多个任务分配给了同一个机器人，将这些任务的次优分配纳入搜索，综合考虑这些任务的最优和次优来分配。转第(2)步;时间复杂度最大为O(M!);

(4)通知任务的最终接收者完成任务。

改进的算法时间复杂度较小。因此该算法比普通算法更适合用于搜索最优的多任务分配方案。

2.3 算法实现

综上所述，基于蚁群算法的任务分配具体实现步骤如下:

(1)参数初始化。令时间t =0，循环次数N =0，将m 个任务随机置于n 个机器人上，令初始信息量τij(0)为常数，Δτk

ij(0)=0;(2)接收到任务的机器人i 根据任务Tk所需的能力Etk及约束条件计算代价costk(Tk)及收益值，然后根据转移概率PTkij(t)从Rc中选择一个机器人，重复该步骤，直到Rc中机器人都计算出相应的代价及收益值;

(3)根据任务Tk对应的分配方案，计算最大收益值及最小代价分配方案;

(4)根据全局信息素更新规则式(3)更新分配方案对应的信息素的强度;

(5)选择当前任务分配计划与全局最优分配计划进行比较，若优于全局最优分配计划，则用当前任务分配计划更新全局最优分配计划;令t=t+1，N=N+1;

(6)当N≤Nmax时，继续从(2)执行;

(7)查找计算结果，输出最优分配方案。

3 仿真结果及分析

基于上述算法思想，采用Matlab 仿真平台进行算法验证。仿真环境设定在一个100 ×100m 的区域，随机分布着20 个机器人，以及10 个任务。机器人均拥有完成任务的能力，约定每个任务均由单机器人来完成。对机器人的描述(表1)主要是位置、能力及完成任务所花代价;任务的描述(表2)主要是任务的位置及对机器人最小能力要求。

表1 机器人描述

表2 任务描述

表1 的数据中，多个机器人存在差异;表2 的数据中，任务对机器人的能力要求不同。基于以上数据，编写程序进行仿真，基本算法参数设置为α=1，β=3，Q=2，NC_max =300;改进的算法参数设置为α=1，β=3，Q1=2，Q2=5，NC_max =300，算法仿真结果如图2 所示。

图2 基本算法分配结果(a)及改进算法分配结果(b)

图2a 可以很直观地看到基本蚁群算法任务的分配，分配结果如表3 所示;图2b 可以很直观地看到改进的蚁群算法任务分配，分配结果如表4 所示。

表3 基本蚁群算法的多机器人任务分配结果

表4 改进蚁群算法的多机器人任务分配结果

通过对表3 和表4 的数据进行分析，可以得出，采用基本算法完成设定的任务所花的代价为892;改进的蚁群算法完成设定的作务所花的代价为806;由此可知完成相同的任务，文中改进的蚁群算法所花总的代价较小，实现了全局近似最优分配。

4 结论

文中对多机器人任务分配系统进行了描述，针对多机器任务分配问题，提出了一种对基本蚁群算法的改进算法，编写算法代码，运用Matlab 平台仿真，对比基本算法和改进算法的仿真结果，改进的蚁群算法在多任务分配中所花代价最小。从而得出文中改进的任务分配算法实现了全局近似最优的多任务分配。

［1］柳林，季秀才，郑志强. 基于市场法及能力分类的MRTA方法［J］. 机器人，2006(3):337.

［2］张嵛，刘淑华. MRTA 的研究与进展［J］. 智能系统学报，2008(2):115.

［3］齐心跃，田彦涛，杨茂，等. 基于市场机制的多机器人救火任务分配策略［J］. 吉林大学学报:信息科学版，2009，27(5):506.

［4］姜健，闫继宏，臧希喆，等. 基于信息素的多机器人协作任务分配［J］. 计算机工程与应用，2008(2):19.

［5］M.Dias and A.Stentz，"Opportunistic optimization for market-based multi robot control"［J］，IEEE International Conference on Intelligent Robots and Systems，2002:2714.

［6］Y.Y.DING，Y.HE，and J.P. JIANG，"Multi-Robot Cooperation Method Based on the Ant Algorithm"［J］，ROBOT，2003，25(5):414.