多Agent系统(multi-agent system,MAS)是分布式人工智能研究的前沿领域,多个Agent之间在通信的基础上相互协调共同完成系统任务。任务分配是MAS研究的重点^[1],任务分配影响整个系统的效率,也会关系到各个Agent能否最大幅度发挥自身能力,避免资源的占用。

合同网由SMITH R G在研究分布式问题求解过程中提出的^[2],是针对任务和资源分配提出的经典协商策略。合同网被广泛地应用到分布式的Agent任务分配^{[3, 4, 5]}和基于Agent的生产调度中^{[6, 7]},已成为重要的MAS任务分配方法。合同网将系统中的成员角色分为管理者和合同者,通过模仿经济行为中的“招标投标中标”机制实现任务分配。Agent之间通过标值进行相互协作和任务竞争,在局部最优的基础上追求全局的最优,从而以最优的系统配置和最低的代价完成任务。

传统的合同网模型采用广播方式向外界公布任务及其相关信息,收到任务信息的Agent都可以成为合同者进行投标,如果参与投标的Agent数量过多,将会造成系统的通信量过大,也会加重管理者的决策负担。研究者提出了多种形式的扩充和改进方案,包括:接收者限制、集中选择、基于范例的推理(case-based reasoning,CBR)和忽略过期消息等^[8]。在利用基于范例的合同网推理对任务进行分配时,管理者能够充分利用系统中以往的分配方案进行分配,这样可以显著减少传统合同网协议中通信负载较大的问题,也能简化系统中Agent的决策过程。但是,基于范例推理的协议只适用于系统Agent能力不变的静态环境中,当Agent能力动态变化时,过去的范例将不再适用CBR方法。

为了适应Agent能力动态变动的环境,张海俊引入信任度的概念,提出了动态合同网^[9]。文献^[10]通过引入交互信任度、熟人信任度和阈值等策略提高效率。信任是对Agent能够完成任务的相信程度^[11],当Agent在完成任务时可以更新信任度,或者根据熟人推荐的评定信息来更新信任度。通过利用信任度,可以在复杂的Agent环境中实现MAS中的任务合作^{[12, 13]}。当管理者在进行招标时,根据对系统中其他成员的信任度来确定任务的承担者,将招标通知直接发送给这些Agent以减少通讯量。评价投标书时考虑熟人信任度选择中标者。这种模式能让管理者找到最有可能完成任务的Agent,能有效减少通信量。文献^[14]使用任务信任度和任务负载率双重因素对合同网进行改进,并用信任度阈值的策略对任务的发布范围进行弹性选择。

文献^[15]通过分析中标者的选择策略,利用混合策略,从分析Agent的基础上利用概率选择中标者,能在特定环境下避免减少任务浓度,减少系统资源的浪费,从而提高系统性能。文献^[16]将合同网协议与管理者之间的直接谈判相结合,文献^[17]扩展了合同网协议,允许投标Agent互动并同时参与多个拍卖,并更新他们的出价,直到签订合同,这样使得Agent能更灵活地投标,但是Agent的能力是相同的,且系统中投标Agent个数较少。

在动态的环境中,Agent能力的变化不能仅通过调整信任度来反映其对任务的处理能力。招标阶段,管理者选择向信任度较大的Agent发送招标通知,并未考虑此时Agent的能力信息,可能Agent此时的能力不足以满足任务需求,从而导致任务分配的失败。Agent在收到任务招标通知后,会根据自身能力进行评估从而决定是否投标,但是没有考虑Agent自身的潜在能力。

考虑以下场景时,基于信任度的合同网任务分配流程可能导致任务分配不合理。在自动导引车(automatic guilded vehicle,AGV)仓库搬运系统中,AGV可以作为一个Agent接收并处理来自系统产生的任务^{[18, 19]}。AGV在处理搬运任务的过程中的搬运能力是随时变化的。例如,AGV1的最大载质量为500kg,其正在搬运质量为400kg的货物,此时它接收到一个搬运能力需求为300kg的任务时,根据以往合同网协议,它将不具备完成任务的能力。所以它会对该任务进行拒标,拒标之后管理者Agent会降低对该Agent的信任度。然而,这样是不合理的,当AGV完成了之前的任务后,又具备了完成300kg载质量的任务的能力,但是由于管理者Agent对其信任度降低,有可能导致它不在管理者Agent的招标范围内,从而导致任务分配的不合理,影响系统的整体性能。

本研究在考虑Agent能力状态的基础上提出构建Agent的能力模型,提高Agent处理任务的能力,并使Agent在投标阶段在自身能力不足的基础上为了获取更大的收益将自身的任务进行再招标,从而动态改变自身能力以满足任务需求。在合同网的投标阶段,改进Agent的投标策略,利用空标书来表示Agent有潜在能力完成任务,这样来避免错误的信任度评价。

在基于合同网协议的任务分配过程中,Agent在接受到任务招标通知后,会根据自身的状态和对任务的评估选择参与竞标。因此,为了准确评估Agent的自身状态,使Agent能合理的选择参与竞标的任务,本研究建立了Agent能力模型和对简单任务的描述。

能力可以理解为完成特定任务的本能,包括完成任务的方式以及完成的效果^{[20, 21]}。在Agent领域,可以将Agent的能力分为基本能力和行为执行能力两类。Agent的基本能力包括自治能力、社交能力和反应能力,一般Agent所具有的基本特征。Agent的行为执行能力用来认定Agent执行任务资格和决定Agent完成任务效果,可以区分不同Agent之间的个体之间的能力差异,并且能指导任务分配的有效进行^{[22, 23]}。本研究将重点分析Agent的行为执行能力,Agent的行为执行能力元模型如图1所示。

图1(Fig.1)

图1 行为执行能力元模型 Fig.1 Meta-model of behavior executive capability

Agent的行为执行能力由一系列的基本能力(BasicCapability)构成,BasicCapability由〈action,property,status〉构成。其中,action表示执行行为的动作或者处理的某些问题,max_-property表示执行action的属性最大值,cur_-property表示当前值,Status表示执行该action的状态。将Agent的能力模型形式化描述如下:

BasicCapability∈Capability

BasicCapability≡〈action,property,status〉

Property ≡ 〈max-property,cur-property〉

在描述AGV具有的搬运能力时,可以将其描述为:〈“Carry”,〈500kg,200kg〉,“normal”〉,Carry为搬运的动作,500kg表示AGV的最大载质量,200kg表示AGV当前的剩余载质量为200kg,normal表示AGV的搬运能力为正常状态。

在MAS的任务分配问题中,任务是指行为主体所面临的、所需要完成的一项工作,一般表现为一系列的活动。马巧云提出任务是实现特定目标所需完成的工作^[24]。在基于合同网协议的任务分配过程中,由于Agent要对任务和自身能力进行评估,所以要对任务进行正确描述,在描述任务的基础上能更合理的进行任务分配。

由于环境的复杂性和研究对象的多样性,可以将任务作为特定类型的输入转化为特定输出的一种活动,其输入输出是明确的,输入反映任务执行的前提条件,输出反映任务执行的结果。文献^[25]将任务输入和输入集定义为广义资源,资源的属性为存在的时间、位置和数量等特征。记任务的输入集为X=｛x₁,x₂,…,x_i｝,则资源x=(name,dt,p,m,q),name表示资源的名称;dt表示资源有效使用的到期时间;p表示资源的位置属性;m为资源的质量特征;q为资源的数量。此外,在实现任务从输入到输出的转换过程中,任务还应对Agent的能力资格有要求,本研究用Capbility表示任务执行所需求的能力。针对以上描述,任务Task可以用以下元组表示:

Task≡〈TaskID,TaskName,T_R,O_R,Capbility,Ohers〉

Capbility≡〈Action,Property〉

Others≡ 〈Reward,Priority〉

其中:TaskID代表任务的编码标识;TaskName为任务的名称;TaskName代表简单任务的名称;T_R,O_R,分别代表任务的输入集和输出集;Cability代表执行任务需求的能力信息,与上文中建立的Agent能力模型中的Capability对应但是只用〈Action,Property〉表示,其中Action为动作信息,Property为最低的Action属性值;Others表示任务具有的其他属性,其中Reward为完成任务的报酬,Priority为任务的优先级。

在物流仓库中,对Agent执行的一项搬运任务通过上述的描述方法可以表示为:〈TC0001,“CarryTask”,〈“Cargo”,sx,sy〉,〈“Cargo”,dx,dy〉,〈“Carry”,300kg〉〉。根据上述定义,这表示一项编号为TC001,名称为CarryTask的任务,输入为Cargo,Cargo的位置为sx,sy,输出为Cargo,Cargo的位置为dx,dy,该任务需求的能力为值为300kg的Carry动作,对任务的Others没有表示。

MAS系统中动态任务分配问题主要涉及3类Agent:任务分配Agent、任务的执行Agent和环境Agent。环境Agent不参与决策,只充当任务分配的中介,负责管理任务和Agent的信息。任务分配Agent负责任务的分配,任务的执行Agent负责接收和执行任务。在利用合同网方法进行任务分配时,任务的分配Agent和任务的执行Agent分别担任系统中的管理者和合同者角色。其基本的结构如图2所示。

图2(Fig.2)

图2 节点结构 Fig.2 Structure of agent

知识库存储Agent的自身的状态和能力信息,以及任务的相关知识;任务执行器在接受的决策中心的任务执行决策时对任务进行相应的处理^[24];决策中心是Agent的中枢,根据自身的知识库来各项进行决策,包括任务执行、与其他Agent通信、决定签订合同的信息;合同处理器根据不同的任务发送标书或者进行投标并确认合同;通信中心能接收和发送消息,与系统中的其他节点进行通信。

基于扩展合同网动态任务分配的基本框架如图3所示。系统由两个层次构成。第一层为外部的环境Agent,环境Agent主要产生任务,并自动选择一个Agent作为任务的管理者。第二层由管理者Agent和合同者Agent构成。管理者Agent和合同者Agent根据合同网协议进行任务的协商以完成任务分配过程。

图3(Fig.3)

图3 扩展合同网动态任务分配框架 Fig.3 Frame of dynamic task allocation based on extended CNP

本研究在信任度和任务熟人库的基础上使用扩展合同网,通过引入Agent的能力模型以及对任务的完整描述,对合同网协议的招标阶段和投标阶段做了以下改进。

在任务的招标阶段,Agent在从环境Agent接收到新的任务请求时,作为任务的管理者,通过自身的任务熟人库选择招标对象发送招标通知书。若此时Agent的不具备完成任务的能力,则Agent作为合同者发送拒标书,以后将根据这份拒标书来更新任务熟人库。由于对Agent的能力和任务的需求有了定量化的描述,Agent可以根据能力属性的大小选择不同的策略。当Agent具备该能力,且当前的能力属性满足任务能力属性要求时,Agent作为合同者制作标书参与投标。若当前的能力属性不满足任务能力属性要求,但是Agent具备完成完成任务的潜力,即Agent的最大能力属性满足任务需求,若新任务的优先级比管理者正在执行的任务优先级更高,为了获得更好的分配效果,Agent可以选择将优先级低的任务重新分配,根据该任务的完成状态创建新的任务,并对该任务进行招标,以此来寻找系统的最优分配方案。在Agent从环境Agent接收到新的任务请求开始,改进后的招标阶段流程用伪码表述如下所示。

begin

send task notice;

if(!Exist task-capability)

send bid rejection document

if(curproperty_(agent)>property_(task))

calculate task cost;

send bid document;

else if(maxproperty_(agent)>property_(task))

create new task;

send new task notice;

end。

针对招标阶段的运行过程如图4描述。

图4(Fig.4)

图4 招标阶段流程 Fig.4 Diagram of bidding process

系统中的Agent在接收到管理者的投标通知书时,不会考虑自身的任务情况,只考虑当前的能力状态来选择是否进行投标。因此,Agent将根据自身状态将采取三种不同的措施。(1)Agent不具备完成任务的能力,则直接选择拒标;(2)Agent能力满足任务需求,则选择投标。为了减少系统的通信负担,减少任务的处理时间,投标与管理者的策略差别在于,合同者不会将正在处理的任务进行招标。如果Agent的最大能力能满足任务的能力需求,那么Agent向管理者发送空标书。管理者在接收到空标书时不会更改对此Agent的信任度。

本研究利用NetLogo 5.1.0仿真平台来建立MAS的仿真场景,创建了AGV仓库搬运系统的场景。试验仿真的场景如图5所示。在仿真的场景中,模拟了仓库中的AGV处理环境中的搬运任务。不同AGV的载重量的能力不同,搬运任务需求的载重能力也有差异,所以系统中的AGV应用合同网协议进行协商以完成任务分配。

图5(Fig.5)

图5 仿真场景 Fig.5 Scene of simulation

试验开始时,AGV的位置随机分布在道路上,图5中小车代表AGV。试验在运行过程中,系统会随着时间的推移随机产生新任务,任务的信息包括货物的起点、终点和需求的载重量,图中箱子代表任务的起点。系统产生任务时,自动将任务请求发送给距离最近的AGV,接到任务请求的AGV成为任务管理者,然后通过改进后的合同网任务分配流程,对该任务进行任务分配。本实验采用一台1.7GHz AMD CPU和4GB内存的DELL笔记本,在WIN8系统下运行仿真实验,分别采用传统合同网协议和本研究提出的扩展合同网协议进行任务分配,最后比较两种算法的任务总完成时间。仿真结果结果如图6所示。

图6(Fig.6)

图6 仿真结果 Fig.6 Simulation results

图6中a线和b线表示利用传统合同网协议和改进后的合同网协议进行任务分配后的系统总任务完成时间。在任务量较少时,两种方法的总任务完成时间基本一致,但是随着任务数量的增多,改进合同网协议任务分配方法由于Agent动态能力更强,因此会有效减少系统任务完成的总时间。

在动态环境下,基于合同网的MAS任务分配存在着任务分配不合理的情况。本研究提出了建立合理的Agent的能力模型,并对Agent所执行的任务进行描述,在基于Agent能力模型的基础上改进了合同网的招标阶段和投标阶段。该方法通过仿真结果得出在一定程度上能有效减少系统完成任务的总时间,提高了系统的整体效率,从而提高多Agent系统适应动态环境的能力。

然而,本研究所考虑的任务由单个Agent完成,并没有考虑到任务由多个Agent共同完成的情况;其次,由于Agent能够将自身的正在处理的任务进行招标,这将会增加系统的通信量。在未来的工作要考虑更加复杂的任务场景,增强Agent之间的协作,并减小系统的通信量。