基于势博弈的异构多智能体系统任务分配和重分配

鞠锴 冒泽慧 姜斌 马亚杰

近年来,多智能体系统在一致性安全控制、健康管理、编队跟踪等多个领域得到广泛应用[1−3].得益于智能体之间的分工与合作,多智能体系统在执行大规模任务时可以提供比单个智能体更好的性能.通过采用任务分配算法,将具有不同要求的任务分配给最合适的异构智能体,多智能体系统可以在能耗、任务效用等方面获得最佳的整体性能.因此,任务分配问题在多智能体系统的研究中引起了更多关注[4−6].

日益复杂的任务需求对任务分配问题提出新的挑战.一方面,需要多种资源的任务通常无法由缺乏足够配置的单个智能体处理,因此这些任务各自需要多个智能体协同执行.在任务分配问题的标准分类法中[7],这类任务称为MR (Multi-robot)任务,且对任务分配算法提出智能体间合作的要求.另一方面,任务价值的动态变化和任务执行时间限制等所施加的多重约束,使得任务分配问题的求解更加困难.MR 需求和多重约束将大大扩展可选分配方案的数量,因此算法需要在解质量和计算时间之间找到平衡.此外,任务数量变化或智能体故障等突发情况对算法的实时性能提出考验.面对这一系列难点,传统的任务分配算法,如蚁群算法[8]、粒子群算法[9]等不再适合复杂约束下的重规划环境,特别受限于在大规模可行解空间内寻优难度几何倍数递增的问题.因此,设计多重约束下更为实时、高效的任务分配算法具有重要意义.

针对MR 任务分配问题,现有的一类编队联盟方法注重于任务的拆分、智能体联盟的形成和将任务分配给合适的联盟[10−12].在这些工作中,联盟根据任务需求的拆分而形成,但是若任务之间的耦合足够强,拆分将无法进行.通过设计按序分配任务的策略,基于市场的算法[13−15]可以用来分配MR 任务.不幸的是,决定分配顺序的过程通常取决于智能体对任务的效用,而这一值同样来源于对任务的拆分.近年来,博弈方法为智能体之间的合作与协商提供了良好的性能,因此广泛应用于优化问题[16−18].作为博弈方法的一种,势博弈的特征为具有能够将智能体策略的变化同等地反映在系统整体性能上的势函数[19−21],这一特征为各智能体自主决策是否参与合作提供了便利.受到这一启发,本文致力于通过智能体间的通信协商,从整体的角度来分配强耦合的MR 任务,从而能够避免编队联盟方法与市场算法需要拆分任务的缺陷.因此,如何设计智能体博弈机制成为算法的重点和难点.

在执行之前将每项已知任务分配给合适智能体的过程称为初始分配,之后智能体根据分配结果执行任务.任务需求的增加和工作环境的恶化,使得智能体在执行任务过程中更容易出现故障.本文仅考虑永久故障,即故障智能体无法自恢复,从而无法再执行其剩余任务,导致这些任务需要重新分配.在任务分配问题中,任务需及时执行以避免其效用严重下降,因此实时的容错能力对于任务重分配算法至关重要.Xu等[22]提出一种具有容错能力的动态资源供应方法,用以恢复云计算工作流的失败任务.Paul等[23]通过采用改进的容错调度算法来减轻永久处理器故障对实时应用程序的影响.

智能体故障可以通过硬件和软件方法解决.硬件方法使用额外智能体替换故障智能体以供后续任务执行,但在智能体数量或资源有限的情况下不可行.软件方法使被故障终止的任务在健康智能体上恢复执行,这一思想类似于在初始分配的基础上处理任务数量的动态变化,如Das等[24]通过并行分配和执行来处理新任务或智能体的加入.由于方案调整的灵活性,拍卖方法在动态环境中得到全面研究[25].然而,这些工作并没有在任务分配问题模型中嵌入智能体故障.为此,一些学者为多处理器系统解决了容错策略分配问题,使得失败的任务被迁移到不同的处理器上恢复执行[26−27].这些工作考虑了智能体故障并以尽可能提高系统可靠性作为主要目标,但它们缺乏对任务执行质量的实质性关注.

本文提出一种将具有多重约束的任务最优地分配给异构多智能体系统,并且具有快速有效地处理突发智能体故障能力的新算法.势博弈思想贯穿于算法的整体设计,主要贡献总结如下.

1) 建立考虑多重约束和智能体故障率的MR任务分配问题模型.建立基于势博弈的框架,其中智能体是完全分布式的,且能独立地作出影响全局任务效用的决策.

2) 基于势博弈为无故障环境设计初始分配算法,之后将其推广到针对永久智能体故障的任务重分配算法.智能体策略总是迭代地向纳什均衡移动,且在纳什均衡处获得近似全局最优分配.

3) 构建与本文建立的任务分配问题模型符合程度高的现实场景,并通过仿真结果验证所提出算法的有效性.

本文的剩余部分安排如下: 在第1 节中,给出问题描述和优化目标;在第2 节中,设计基于势博弈的算法以完成无故障情况下所有已知任务的整体最优分配,称为初始分配;并在第3 节中将其推广为重分配算法来处理任务执行过程中的永久性智能体故障;在第4 节中,给出仿真结果来分析所提出算法的有效性;最后在第5 节中给出结论.

1 问题描述

考虑最优地将m项任务分配给n个异构智能体的任务分配问题.每个智能体在某一时刻至多参与一项任务的执行,且每项任务需要由多个智能体同时执行.智能体集合编号为A={A1,A2,···,An},任务集合编号为T={T1,T2,···,Tm}.任务之间相互独立,且执行任务Tj所需要的智能体数量定义为Nj,满足 1≤Nj ≤n,j=1,2,···,m.忽略执行任务所消耗的时间,即一旦所有Nj个参与执行的智能体均到达任务Tj,则认为该任务已完成.智能体之间在类型、资源等方面都可以是异构的,表现为若执行同一任务Tj则将提供不同的性能,且可以通过为各智能体Ai,i=1,2,···,n定义一个经归一化后值在0 到1 之间的变量λij,i=1,2,···,n,j=1,2,···,m来量化.任务Tj更可能由λij更大的智能体执行,若λij等于0,则表示智能体Ai无法执行任务Tj.智能体在执行任务过程中可能遭受不可恢复的永久故障,且一旦发生,故障智能体无法再执行后续任务,从而产生任务的重分配需求.每项任务Tj都有一个效用函数uj,j=1,2,···,m,与任务分配方案、各智能体对该任务的贡献、任务执行时间等多种因素有关.下面将分别量化这些因素对任务效用的影响,并建立任务分配问题模型.

基于每项任务需要多个智能体合作执行的需求,模型进一步引入同步性约束,用来描述单个智能体的努力不足以启动单项任务的情况.在此约束下,仅当所有参与执行任务的智能体均到达时,任务才视为完成.因此,任务的开始执行时间由所有参与执行的智能体中最晚的到达时间主导,即

其中,tj为任务Tj的开始执行时间;tij为智能体Ai到达任务Tj的时间;χij定义为二进制决策变量,若智能体Ai参与执行任务Tj,则χij设为1,否则设为0.鉴于此,智能体之间需要合作与协商,以关于任务执行时间达成共识.

因而,任务效用uj来源于所有参与执行的智能体的贡献.贡献随着各智能体能力而不同,且计算为任务执行的奖励和资源成本的线性组合[7].在本工作中,智能体Ai对任务Tj的贡献定义为rij,表示为

其中,rj为任务Tj的基础效用;dij为智能体Ai当前位置与任务Tj的距离;α和β分别为智能体能力和距离的权重系数,取值取决于各自的相对重要性.

进一步引入时效性约束来强调随时间不断提升抵抗智能体行为能力,导致智能体的可获得效用不断衰减的任务类型.在此约束下,每项任务限制在其出现和截止时间之间的时间窗内执行.任务Tj的出现时间定义为,对于起始存在的任务该值为0.利用以任务执行时间为变量的指数函数来表征时效性约束对任务效用的影响.当一项任务尚未被执行但其基础效用已经随时间衰减到固定阈值时,该任务宣告失败,相应时间称为任务截止时间,即

其中,折扣系数µj决定时效性约束对任务效用的影响程度;δ为决定任务能否被成功执行的阈值.

由于各项任务均需求多个智能体和尽可能早的执行时间,时效性约束使得一项任务的分配对智能体和可用执行时间的占用会导致竞争失败的任务被迫推迟其执行时间,从而导致个体乃至全局效用的衰减,这一耦合特性使得分配每项任务时均需要考虑其他任务所受的影响.两项约束式(1)和式(3)的引入,将从任务的执行顺序和执行时间方面大大增加可选任务分配方案的数量,使得对最优解的搜索更加困难.

注 1.以空地协同作战、火灾救援、流水线工作等复杂任务为代表的任务分配问题,均受到单项任务由多种类型的智能体协同执行的同步性约束和任务价值随时间衰减的时效性约束的限制.因此,考虑在模型中同时引入这两项约束具有现实意义.

根据同步性约束式(1)和时效性约束式(3),任务Tj的效用计算为

其中,tj在分配中要求不超过.

此外,对智能体故障率建模来提升系统可靠性和期望任务执行质量.永久故障发生的可能性会被智能体已执行任务的特性加剧.定义智能体Ai执行任务Tj时发生永久故障的可能性为fij,与Tj和智能体Ai已经完成的任务有关.利用Guo等[26]给出的通用可靠性模型,fij表示为

其中,ωi为智能体Ai的可靠性系数;σf为给定正常数;(Tj) 为智能体Ai在执行任务Tj前已经完成的任务集合.如果任意参与智能体在执行一项任务时故障,则将该任务终止且将其效用式(4)置0.尽管后续将通过重分配严格保证该任务的成功执行,但建模中的这一处理将尽可能地提升系统可靠性.因此,任务Tj的期望效用计算为

根据式(4)～式(6),任务分配问题模型写为

式(10)保证执行每项任务的智能体数量满足要求,式(11)保证每项任务能在截止时间前成功执行.式(12)、式(13)用以确保任意智能体到达待执行任务的时间足够覆盖所需的路程,其中τi(l1,l2)代表智能体Ai从l1到l2的位置所需的时间.至此,异构多智能体系统的任务分配问题转化为在同步性约束式(1)和时效性约束式(3)下,考虑故障率式(5),以最大化式(8),即全局最优分配为目标的问题.

由式(7)～式(13)可见,该任务分配问题是一个多重约束下的优化问题,很少有找到最优解的方法,即使有,也需要承担大量的计算资源成本.因此,本文追求式(7)的近似全局最优,使得算法能够在分配方案解质量和计算时间之间取得平衡.

2 无故障初始环境下的任务分配

在无故障情况下,将所有任务T最优地分配给处于起始位置的智能体集合A的过程称为初始分配.初始分配完成后,每项任务将由负责它的智能体执行.对于多智能体系统任务分配问题,算法大多在健康情况下进行设计和实现.在故障发生后,若能根据健康情况下的算法进行容错的重分配,则算法的工作量和计算量将大大减少,效率更会提高.因此,本文将首先研究无故障情况下的任务分配算法,后续将其推广到故障情况,以表明所提出的算法具有很好的普适性.

定义U ⊆T为未分配任务集合.所有m项任务最初都标记为未分配,即U=T,且所有智能体均未被分配任务.算法每轮将从U中选择一项任务以最大化式(6)为目标完成最优分配,并将该任务添加到所分配智能体的任务包中,直到U为空集,则通过m轮将最终确定使式(8)近似最大的全局最优分配.

2.1 单项任务最优分配搜索

首先,算法将设计智能体间针对单项任务的博弈方法,以为每项未分配任务Tj∈U寻找最优分配,即从智能体集合A中选择如式(10)要求的Nj个对应能力λij不为0 的智能体,使得它们合作执行Tj所能获得的期望任务效用式(6)最大.

从博弈论角度而言,智能体为博弈参与者,基于其位置、运动状态、能力、时间戳等信息参与任务博弈.要求每个智能体博弈所依据的到达任务时间tij均满足约束式(11)～式(13),以确保经由同步性约束式(1)得到的任务执行时间tj同样满足式(11)～式(13).此外,要求任意两个智能体之间的通信可达且稳定,以确保博弈能够随时进行.

定 义博 弈Γ=(A,S,{uij}) ,A仍然为第1节定义的智能体集合.S=S1×S2×···×Sn表示策略空间,其中Si ⊆2T,i=1,2,···,n为智能体Ai关于是否执行T中各项任务的所有可选策略集合[28].si∈Si,i=1,2,···,n为其中一项可选策略,对应分配给智能体Ai的一组任务.当且仅当式(8)中的任务分配决策变量χij为1 时,有Tj∈si,即si={Tj|Tj∈T,χij=1},i=1,2,···,n. s=(s1,s2,···,sn) 代表所有智能体策略的集合,也可写为s=(si,s−i),其中s−i表示除Ai之外其他所有智能体的策略集合.s对应唯一的决策变量矩阵χ,从而代表唯一的全局任务分配,决定期望全局效用式(8)的值.据此,式(6) 所描述的期望任务效用也可表示为(si,s−i).uij表示智能体Ai执行其策略si中任务Tj的效用函数,其值依赖于合作智能体到达该任务的时间,因此uij与所有智能体的策略相关,可写为uij(si,s−i).uij(si,s−i) 来源于任务Tj的期望效用,但由于如式(1)和式(4)所示其与合作智能体效用的耦合特性,uij(si,s−i) 的值不能直接计算为贡献rij占的比例.根据单个智能体对任务的边际贡献[15],uij(si,s−i) 定义为

其中,si,0表示智能体Ai不参与执行任何任务.显然若Tjsi,有uij(si,s−i)=0.

效用函数uij(si,s−i) 的定义为智能体的独立决策提供基础.根据式(14),单个智能体对任务的边际贡献仅和该智能体以及参与该任务的其他智能体相关,因此单个智能体在对一项任务博弈时仅需要少量邻居智能体的信息,并能据此作出是否参与任务的决策,这使得系统能在分布式结构下工作.算法将寻求利用势博弈搭建uij(si,s−i)与期望任务效用(si,s−i) 之间的联系,使得(si,s−i) 能通过寻找各智能体Ai的最优策略si,以uij(si,s−i)为媒介达到最大化.如下给出势博弈的定义.

则Γ为势博弈,P为相应的势函数.

根据定义1,在势博弈中,每个智能体由策略变化引起的效用函数变化会等量地反映在势函数上.如果能利用智能体效用函数构造势博弈,使得势函数P为期望任务效用式(6),则各智能体能通过仅改变自身策略来不断提高式(6).在这一框架下,个体智能体的目标能够与全局目标保持一致.具体地,所有智能体的策略均被随机初始化.每个智能体Ai∈A在其他智能体的策略s−i保持不变的条件下,总是朝着提升自身智能体效用uij(si,s−i) 的方向迭代调整策略si.若没有智能体能作出更好的策略选择,则作为势函数的期望任务效用式(6)达到最大化.这意味着当所有智能体的策略迭代完成时,任何智能体都无法再通过独自调整自身策略来获取更高的效用,称此时的策略集合s为纳什均衡,如下给出其定义.

应用势博弈的关键在于,当任意智能体Ai∈A的策略si迭代时,其他智能体的策略s−i必须保持不变.然而,在第1 节所搭建的MR 任务分配问题模型中,每项任务都需要固定数量的智能体合作执行,这导致一个智能体的策略变化必然会要求另一个智能体的策略同步变化以维持任务所需智能体数量.为此,在迭代时令策略中包含该任务的智能体与所有策略中不包含该任务的智能体一一替换,将两个策略改变的智能体视为一个整体考虑,以便其他智能体的策略能够视为不变.据此如下定理成立.

定理 1.针对目标任务Tj∈U,考虑由智能体集合A为最大化式(6)所描述的期望任务效用所进行的博弈Γ.如果将某次迭代中具有替换关系的两个智能体视为一个整体参与博弈,则可以将博弈Γ构造为势博弈,且势函数推导为期望任务效用.经过有限次迭代,所有智能体执行任务Tj的策略将收敛到使最大的纳什均衡.

根据定义1,博弈Γ为势博弈,且为势函数.

因此,在所构造的博弈Γ中,算法只需要朝着提升智能体效用之和式(19)的方向成对地迭代调整各智能体的策略,就能实现期望任务效用式(6)的增加.由于智能体效用随着策略的调整呈现单调变化,且势博弈必然存在纳什均衡点[28],算法会使得各智能体的策略必然收敛为使式(6)最大的纳什均衡策略.根据势博弈的有限递增属性[19],任何单方面改进的序列都会在有限时间内收敛于纳什均衡,则本算法所设计的迭代过程一定会在有限的迭代步内实现收敛. □

注 2.在一致性联盟算法[29]中,各智能体仅根据个体收益以贪婪算法思想将任务添加到自身策略中,从而导致分配到该任务的智能体数大于实际所需数量的冲突.虽然后续设计该智能体间冲突的消除方法,但也重复消耗算法资源.而本节所设计的算法则利用智能体间博弈始终维持分配到任务的智能体数量,从而在分配过程中避免这类冲突现象.

每项未分配任务Tj∈U的最优分配能最大化其期望效用式(6),但与所有其他任务的成功执行之间可能存在冲突.任务的允许执行时间受时效性约束式(3)限制,因此应用一项任务的最优分配后,其他任务可能缺乏足够式(10)要求数量的能在截止时间前到达任务的智能体,从而无法满足式(11).第2.2 节将设计消除这类冲突的方法.

2.2 冲突消除

线性表用来存储所有待定次优解,选择次优解的过程一般化为线性表中结点的添加和删除.添加的方案要求不与表中现存的方案或曾删除的方案重复.最初,线性表为空.在某一轮得到一项任务的最优分配后,将其添加入线性表并进行检测.如果应用该最优分配后会存在冲突,则删除该方案并将其分支下的势博弈待定次优解添加入线性表.从表中选取对应期望任务效用最大的方案作为次优解,并检测冲突是否消除.若已消除,则用其替换最优分配,否则重复此过程,直到搜索到可行方案.如果直到线性表再次为空也没有找到合适的方案,则意味着对该被检测任务的任何分配都会导致与其他未分配任务的冲突.在这种情况下,被检测任务在这一轮中不允许被分配,而是在下一轮重新考虑.图1描述了利用线性表选择势博弈次优解的过程,其中不会引发冲突的最终可行分配被标记为.

图1 势博弈次优解的选择过程Fig.1 The process of selecting the suboptimal solution of the potential game

2.3 全局最优分配搜索

基于第2.1 节和第2.2 节的结果,本节将定义各项任务的优先级来描述一项任务的最优分配趋向于全局最优的程度,并分配具有最高优先级的未分配任务.一项任务的分配对多个智能体的占用,会导致其他任务在时效性约束下所能获得最大期望效用的衰减.值得一提的是,智能体的故障率与其曾经执行的任务有关,随分配过程动态变化,其影响同样包含在这一衰减中.因此,该任务的优先级取决于其他任务受到该任务分配的影响程度,那么为尽可能最大化式(8),应当首先分配所导致衰减最小的任务.实际上,这表示该任务的最优分配相比于其他任务更趋近于全局最优.针对某一轮中的任意未分配任务Tj∈U,令其通过第2.1 节和第2.2节得到的最大期望效用为.假设任务Tj按其个体的最优方案完成分配,且方案中参与智能体的位置、速度、加速度和时间戳得到更新,在此基础上计算所有其他未分配任务Tk∈U,kj在下一轮所能获得的最大期望效用的变化量化了任务Tk受到任务Tj分配影响的程度,据此,任务Tj的优先级权值定义为其对所有其他未分配任务所造成的最严重影响,即

算法2.优先级权值计算

健康环境下整体初始分配的流程图如图2 所示.算法每轮通过第2.1 节～第2.3 节这3 个步骤完成一项优先级最大的任务Tp的分配.所有参与该任务执行的智能体的状态与时间戳信息应当被更新,以进行下一轮博弈.任务Tp标记为已分配并且不会参与后续计算.将未分配任务集合U迭代为UTp,智能体集合A针对U中所有剩余任务重复这3 个步骤.经过m轮最终得到所有任务的全局近似最优分配,此时U为空.

图2 健康环境下的初始任务分配流程图Fig.2 The flow chart of the initial task allocation in the healthy environment

注 3.从整个初始分配算法的设计过程中可以总结出所提出算法的优越性.一方面,智能体作为整体对单项MR 任务进行博弈,从而避免编队联盟方法[10−12]和市场算法[13−15]所面对的任务难以拆分的问题.另一方面,算法根据博弈过程对分配方案进行优劣排序,从而确定任务优先级,解决任务间的耦合.与传统群体智能算法[8−9]寻优方向的随机性相比,所提出算法等效为在一定程度上对寻优方向具有导向性,因此具有较低的寻优难度.

至此,算法完成健康环境下所有任务的初始分配.算法的设计追求包含全局效用最大化和所有任务成功执行的目标,同时能够在解质量和计算时间之间取得较好的平衡.通过循环由这3 个步骤构成的算法,全局最优式(7)由分布式结构中智能体之间的合作与协商来近似实现.

3 故障情况下的任务重分配

在无故障情况下已经完成所有任务的初始分配,随后每个智能体根据其策略执行任务.智能体在任务执行过程中可能会发生永久故障,以致故障智能体无法再执行剩余任务.因此,这些任务需要重分配,即智能体需要实时调整策略.特别地,当协同执行具有多重约束式(1)和式(3)的MR 任务时,单个智能体策略的改变可能会导致整个系统策略的改变.如果每发生故障就对所有任务重新分配,则尽管结果会更优,但所有智能体策略的动态重置将导致分配方案解空间的非线性剧增,消耗大量的算法资源,降低重分配的实时性能和效率.因此,本节将健康环境下的任务分配算法推广到故障情况下,同时将健康环境下的分配结果作为重分配的依据,以减少工作量和计算量.算法推广的基础是在健康情况下,一项任务只能在紧跟着前一项任务的位置之后被添加到智能体策略中,而在故障情况下,重分配任务将被提供若干个可添加位置供其选择.

如下给出一些服务于算法的准备和说明.所有任务Tj∈T按照初始分配方案下的任务执行时间tj从小到大进行排序,依次重新编号为∈T,其中任务的执行时间写作,k=1,2,···,m.

待重分配的任务需要从初始分配下的智能体策略中移除.如式(4)所示,任务效用与执行时间有关.移除由智能体故障终止的任务后,剩余未执行任务的执行时间需要进行调整以最大化期望全局效用式(8).具体地,调整方法是以排序后执行时间的顺序依次决定剩余任务能否被提前执行.

待重分配的任务被全部移除后,应当各自重插入到智能体策略中.与初始分配时智能体始终将任务放置在其策略末尾来参与博弈不同,待重分配任务的可重插入位置并不唯一.考虑重插入一项任务,其按执行时间排序后的编号为.若将插入至一个智能体的策略中,算法需要决定其插入位置.通过拆分任务的可执行时间窗来讨论可选重插入位置.若距离故障时刻tf最近的已执行任务其排序后的编号为,则有p=m−mr−c+1种位置使得任务执行的顺序不同,其中mr为待重插入任务数.

如果重插入不会推迟任何任务的执行,则期望全局效用式(8)不会减少,否则会导致由时效性约束式(3)引起的效用衰减.任务总是包含在多个智能体的策略中,因此在被推迟的任务数量方面影响可能较为严重.那么,重插入所引起的期望全局效用变化量不仅与自身的效用有关,还与后续任务被推迟执行的程度有关,计算为

图3 故障情况下的任务重分配流程图Fig.3 The flow chart of the task reallocation in the faulty case

仍然讨论上例.给定智能体A4在执行后永久故障,则和需要重新分配.重分配方案为判断和是否可以提前执行,之后依次重插入和.移除和重插入任务的具体过程已在上文分析,这里不再赘述.可以发现在此例中,算法仅需要调整、的执行时间和、的分配.这表明通过推广健康环境下的分配算法并结合故障信息,重分配问题被简化为对少量任务的调整,而不需要重启所有任务的分配.从这种意义上说,算法能够避免不必要的时间消耗.至此,本节已经完成具有容错能力的任务重分配算法设计,同时算法解质量和实时性能得到保证.

4 仿真结果

构建一个多个智能体攻击多个任务目标的军事场景,以验证所提出算法的可行性和有效性.每个任务目标具有针对智能体行为的初始防御能力,防御能力越弱对应该任务的基础效用越高.防御工事随时间加强,因此智能体攻击目标越晚,则可获得的效用越低.如果超过截止时间,则来自智能体的攻击无法穿透防御,该任务宣告失败.每个目标都由所需数量的智能体同时攻击以确保火力的集中程度,且完成攻击后这些智能体立刻各自前往下一个目标.所构建的场景显然非常契合本文所建立的任务分配问题模型.任务目标为最大化期望全局效用,且确保所有任务成功完成.算法仅在XOY平面上进行仿真,且表1、表2 给出了某次仿真中智能体和任务的参数.这样的设定和参数选择仅是为了使实验结果中智能体的轨迹清晰,实际上智能体和任务可在场景中随机分布,且数量和所有参数均可调.

表1 智能体初始信息Table 1 Initial information of agents

表2 任务初始信息Table 2 Initial information of tasks

图4 给出了无故障情况下的初始最优分配和相应的智能体轨迹.以Minimum snap 为目标[30],基于贝塞尔曲线优化智能体轨迹[31],使其保持光滑和连续.在任务分配和重分配阶段,轨迹规划均在完成一项任务的分配或重分配后进行.以分配完成上一项任务时智能体的位置、速度、加速度为起点约束,同时以新分配任务的执行时间为终点约束,结合最大速度和加速度约束,轨迹优化问题实质上被转化为能用MATLAB 直接求解的凸二次规划问题,因此不再赘述.每项任务的执行时间在任务点旁边标注.由图4 易得各智能体的最优策略分别为s1={T3,T4},s2={T2,T1},s3={T2,T3},s4={T1,T4}. 以A2的轨迹为例说明任务执行的同步性.A2首先在282.0 s 时与A3同时到达T2并合作攻击T2,相似地随后在408.0 s 时与A4共同攻击T1.可以看出,每组合作智能体都满足同步性约束,且智能体的轨迹连续光滑.

任务分配算法第2.1 节的目标是获得所有未分配任务的最优分配,首先考虑第2.1 节分配单项任务的性能.对于某个需要两个智能体执行的单项任务,图5、图6 分别给出了在不同智能体数量n下采用势博弈算法和枚举法的可得最大期望任务效用和所需迭代次数.针对每种情况进行50 次重复实验并取平均值,其中智能体和任务的位置随机分布.可以看出,基于势博弈的算法能提供与枚举法相同的性能,也就是说,所提出算法的第1 步可以获得任意单项任务的最优分配.相反,算法复杂度的差异很大.枚举法和势博弈算法的复杂度分别为O(n2)和O (n),因此势博弈算法的复杂度显著减少.此外,随着智能体数量的增加,可能会出现能力更强或距离更近的智能体,从而导致可获得的任务效用增加.

图6 分配单项任务的所需迭代次数对比Fig.6 Comparison of the required number of iterations for allocating a single task

考虑第2 节中完整的无故障情况下的任务分配算法.仍然用枚举法作为比较,图7、图8 分别给出了在不同任务数量m和不同智能体数量n下通过使用势博弈算法所能获得的最大期望全局效用相对于枚举法的衰减量.两个实验分别在m=4和n=4的条件下进行,每个实验重复50 次取平均值,其中智能体和任务的位置随机分布.由图可见,所提出算法仍然可以提供与枚举法相似的性能.随着任务数量增加,所提出算法的性能相对降低,这是由于每轮在计算每项任务的优先级时,只考虑分配该任务将造成的下一轮效用衰减量,而未考虑后续轮次的效用同样会受到影响.特别地,如果任务分配的总轮数为1 或2,则算法等同于已经考虑所有轮次的影响.因此,由图7 可见,当任务数量为1 或2 时,所提出算法能够获得与枚举法相同的最佳效用.可以推断,若在计算优先级时考虑某一轮分配对更多后续轮次的影响,所提出算法会提供更好的性能,而代价是计算复杂度的提升.相反,随着智能体数量的增加,所提出的算法将提供更好的性能.这是因为可用于任务执行的智能体越多,在相邻两轮中选择的两项任务就越有可能由完全不同的智能体执行,则基于优先级的框架带来的效用衰减越低.

图7 不同任务数量下的最大期望全局效用衰减Fig.7 Reductions of the maximum expected global utility under different number of tasks

图8 不同智能体数量下的最大期望全局效用衰减Fig.8 Reductions of the maximum expected global utility under different number of agents

图9 给出了第2 节提出的任务分配算法与枚举法的迭代次数的比值随智能体数量和任务数量的变化图.可以总结出当任务数量满足m ≥4 时,势博弈算法的迭代次数已不足枚举法迭代次数的1%.考虑在无故障情况下将均需要两个智能体协同执行的m项任务分配给n个智能体的初始分配问题,枚举法的算法复杂度为,而所提出势博弈算法的复杂度为综上所述,所提出的算法在能有效获得令人满意的任务效用的同时具有较低的复杂度.

图9 所提出算法与枚举法迭代次数的比值Fig.9 The ratio of the number of iterations between the proposed algorithm and the enumeration method

为验证重分配算法的容错能力,在故障情况下进行仿真.如图4 所示无故障情况下任务分配算法的仿真结果被用作初始条件.给定A2在300 s 时故障并且无法从故障中恢复运行,此时A2已经执行完T2,则T1需要重新分配.重分配方案和相应的智能体轨迹如图10 所示,其中用虚线表示无故障情况下的仿真结果作为参考.

图10 故障情况下的最优任务重分配方案Fig.10 The optimal task reallocation scheme in the faulty case

5 结论

基于势博弈解决异构多智能体系统的任务分配问题.多重约束和智能体故障率同时被建模,这给任务执行时间带来严格的限制.所构建的势博弈框架允许合作和协商,从而为无故障和故障情况下的分布式任务分配和重分配算法设计奠定基础.然后,在保证所有任务成功执行的前提下,通过较少次迭代达到近似全局最优,并且可以在健康的智能体上恢复被智能体故障终止的任务,这表明所提出算法具有容错性能.针对能够模拟所研究模型特征的攻击任务场景进行仿真,与枚举法的比较结果表明所提出算法在期望全局效用和算法复杂度方面的有效性.算法的一个局限是需要持续通信,这在大规模系统或恶劣环境中可能不可行,从而导致博弈无法以最佳方式进行.智能体在通信范围受限和通信故障时进行博弈的方法,将在以后的工作中讨论.