文摘

与传统分布式多重代理系统的扩张,协调战略成为一个严重的瓶颈,当系统规模数以百计的代理。关键的挑战是在典型的大型可替换主体系统,稀疏分布式代理只能很少直接与别人交流和网络通常是建模为一个自适应复杂的网络。在本文中,我们目前的模拟实验CoordSim建立网络中心多重代理系统的协调模型。基于口令策略,可以建立协调沟通决策问题,代理决策目标通信和通过他们的代理能力可能会团队最受益。我们从理论上分析了复杂网络的特点做一个显著差异与随机和智能协调策略,这可能会导致未来的可替换主体算法设计。

1。介绍

多重代理系统范式的分布式人工智能一直在流行的领域,如军事、航空、灾难救援。例如,大型异构multirobot团队应对大规模自然灾害(1),执行未来的建设和管理大型市政基础设施(2),部署大批不做作的飞行器和地面车辆在军事行动3]。在这些系统中,关键是要构建实际协调算法能够控制他们异构代理向共同的目标。尽管有许多流行的研究工作对这个问题(4),在最先进的应用程序时需要越来越多的代理商,现有的协调方法不能解决控制数百名特工的新挑战。

首先,网络结构已经成功的一个关键属性协调算法设计。例如,当机器人部署的大型团队,他们总是稀疏分布的。无线通信覆盖范围的限制,代理可能只能与其他的一些直接沟通。因此,类似于人类社会动态的基础设施,每一次,代理只密切配合几个队友通过通信网络在逻辑上或身体上,当他们与其他多次反射的重传。

其次,可替换主体系统需要应对动态和部分可观测的环境与代理商的独立决策。因为应用程序域的性质,代理总是在一个复杂的、动态变化的,在某些情况下,充满敌意的环境。关键域事件作出反应,他们智力适应动态变化和协调自己与自己的观察和知识。在这个过程中,网络是至关重要的代理协议的联合活动或接收信息支持代理商的决策时不能完全观察到。

第三,协调是一个复杂的过程,因为几个分布式算法需要进行交互产生敏捷,有凝聚力,有效协调的行为。典型的协调需要不同方面的子任务之间的相互作用网络代理、信息共享等外部环境事件(5为联合行动[],分配个人任务6),和分享独家资源(7]。

通信网络的一个主要瓶颈是一个有效的和可伸缩的协调。现有的算法对于小团队协作,黑板上(8)或特定的集中代理(9],依靠过度的通信协议是不可行的,不受欢迎的,或者太贵了在大型团队。减少沟通,使分散的协调,代理应该尝试目标通信。然而,这是一个的鸡与蛋问题,沟通是分享知识而丰富的本地化所需目标通信知识是必不可少的。

总之,扩张的多重代理系统,网络是一个关键因素模型团队协调。指出,在相关工作(11),不同的拓扑可能大大改变了表现在同一控制协议。模拟可替换主体协调的关键是解决问题分散代理是如何交互的通信网络,以便协调任务的不同方面可以实现达到共同的目标。尽管流行的网络仿真工具NS2等(12同时采用OPNET[]和13)能够模拟典型的分布式系统应用程序的表现,他们无法模拟大规模系统的可替换主体协调。我们总结的原因如下。

(1)代理使用积极的与他人互动决策模型和动态选择沟通,而不是传统的预定义的被动的通信协议。

(2)代理需要构建本地知识库推理的动态模型,从而使分散协调决策,不可能编码的网络仿真工具。

(3)代理需要很多复杂的语义数据通信域信息等任务,并与他人分享资源。但这些数据无法统一抽象和大多数网络模拟器一样通信包。

尽管有现有的可替换主体团队协调模拟器,其中大部分是不能模拟大规模网络化多重代理系统。例如,Machinetta [14),模拟了可替换主体协调在现实领域,忽视了网络结构的复杂性,只有模仿代理在一个小团队与一个完整的网络。任务分析框架、环境建模和仿真(TAEMS) [15)使用部分全局规划(PGP)框架(16为特定领域决策环境中处理不确定性。它是建立基于层次网络体系结构。等分散协调模拟器LA-DCOP [17),只有部分协调子任务的能力。在这篇文章中,我们将分析复杂网络的特点可替换主体将显著差异的协调,并根据这些观察结果,我们提出了一个新颖的方法来建模和模拟协调网络可替换主体系统。模拟器能够模拟协调的主要方面包括信息共享、任务分配和资源分配。关键是要模拟代理通过网络互动,这样代理如何执行他们的联合活动向共同的目标。模拟器的最突出的优点是它允许大量的参数协调调整的关键,也允许数据被记录;特别是,它能够启动代理在不同的网络拓扑,考虑到复杂的网络效应。这些变化并记录有助于验证协调大规模的网络可替换主体系统的效率。

2。多重代理系统协调

多重代理系统的协调可以描述如下。网络代理共享一个顶级共同目标的目标(如[18])和实现需要实现一个数量的子目标。当子目标满意,团队将获得奖励。例如,高水平目标的子目标来应对灾难可能扑灭火灾,提供医疗照顾受伤的平民。为了满足子目标,团队遵循一组代表在图书馆(19]。每一个计划包括四个部分,写成。第一个元素是子目标;第二个是它适用的条件,;第三个元素是单个任务哪些是需要实现最后一部分,收到的,是团队成功的满足感。每个任务是由它的子目标由一个单一的代理与所需的特定类型的和(下面会介绍),也就是说,实际的描述为代理实现子目标。

例如,一个消防计划可以被建模如下:。这个计划需要在启动前两个条件:火灾报警和烟雾。这个计划启动后,三个任务,需要分配和奖励100年将是归功于团队。的三个任务计划驾驶消防车,救火和寻找受害者;也就是说,(熟练的驾驶卡车),,(有消防培训),,(没有),。执行,需要一个代理能够驱动和获得一辆消防车独家资源。

在异构的多重代理系统中,每个代理可能有不同的能力来执行不同的任务。例如,在火灾救援,能够代理可以把消防车,扑灭火灾,或者寻找伤员。然而,当执行相同的任务,代理有不同的功能做出不同的表现;例如,一个消防队员能够比一个没有经验的公民消防。因此,我们定义一个函数表示代理的能力执行任务。如果代理的功能多的阈值,它可以执行的任务。奖励将会收到由系统当代理人完成一个任务。它是一个代理的函数的功能和任务,以及资源代理。具体地说, 这个函数如果代理是分配给的任务;否则等于0。在任何时候,一个任务最多只能分配给一个代理;也就是说,。

网络代理总是需要共享资源来执行任务。这些资源,离散和非自耗的。代理独占地访问资源。只有一个代理可能持有资源在任何的时间点;也就是说,。

协调问题是最大化回报的团队,同时最小化成本的协调。整个奖励很简单 协调的成本可能非常一般,在某些情况下很难定义。我们特别关心的唯一的交流。

3所示。网络代理

根据网络代理的角色,他们只能直接交流或与他人很少在网络上交流,可替换主体的组织系统可以抽象为无向网络如图1(20.]。在这个模型中,代理设置,边的设置如果吗,和可以直接相互通信。此外,被定义为一组的的邻居,它可以直接沟通。

可以组织为不同的网络拓扑基于社交网络的不同的属性。在我们的模拟中,我们感兴趣的主要是四个:随机网络、网格网络、小世界网络和无标度网络。初步研究[21)发现,每个拓扑编码以下不同的基本属性。(1)平均度:。(2)度分布:。(3)平均距离:。定义了最少的啤酒花之间进行通信和。

不同的网络拓扑结构可以根据上面的属性进行描述。在我们的方法中,我们主要考虑的影响小世界和无标度网络和使用程度分布表达无尺度效应和他们的平均距离来表达小世界效应。

4所示。网络协调模型

协调问题建模的部分2代理商的交互在网络进行子任务的不同方面协调,达到共同的目标包括信息共享,任务分配,和资源共享。是所有可能的领域事件的集合,是潜在的可用的集合联合活动,所有可用的独家资源团队吗。被定义为可替换主体协调。在每一个时间,一双代理之间的协调互动元素可以定义为通过网络要么是一个域的事件,联合活动,或独家资源。通过封装tc,我们可以定义的数据结构之间的交互网络代理。

如果我们假设代理会处理好自己的工作,通过网络代理沟通令牌的目的是寻找代理商可以执行所需任务能力,使用资源,或获取信息,这子目标将会实现。任何标记的结构被编写为。我们假设令牌不能被复制。当一个代理,它需要控制。tc并将释放。tc如果是过去了。.path记录序列的代理已经过去了。.path也被用作信息和任务令牌如果停止条件.path。是预定义的可以被传递给其他人拦住了他。

概括一个阈值对资源和任务令牌,可以接受任何代理。只有当计算能力或代理高于的欲望.threshold,它可以被接受。可以动态地调整来平衡整个系统的需求和生产改进分配的性能。例如,如果一个资源是高度竞争的,它将提高阈值穿越网络找到一个“更好”的接受器。否则,如果在网络上已经走了很长的路,应该降低阈值有助于发现任何人都可以使用它,即使它可能不是最好的。

5。可替换主体沟通决定

节中解释4,沟通令牌的目的是找到代理商可以执行所需任务能力,使用资源,或获取信息如果自己不能够利用它。类似于人类社会,代理总是向前的无能任务和资源通过网络找到最好的接受者。协调的关键是优化他们的交互,所以,最好的代理能力可以达到尽快沟通成本和最少的作业延迟。

算法1(22]描述的一般决策过程分散的网络代理。在该算法中,代理首先检查是否新任务已成为适用。如果是这样的话,代理将嵌入任务令牌并将其添加到标记列表处理,其中包含令牌(3 - 7行)。接下来,代理将收到的所有令牌通过其他代理(第8行)。然后流程中的所有标记。如果一个令牌代表一个任务,代理会接受这个任务的能力来执行这个任务比牌的阈值(11 - 14行);否则,代理将选择一个邻居,令牌(17行)。如果令牌是一个资源令牌和代理执行他的等待任务对资源的需求高于牌目前的阈值,将举行这个资源;否则,它传递给一个邻居(19-27行)。注意,当发送令牌时,它将被删除从代理的名单。最后,代理将检查是否附加现在可以执行任何任务(30行)和释放任何资源从完成任务(32-37行)。

关键的决定过程的功能,这是通过一个令牌的邻居需要它或者知道谁。在我们的仿真模型中,我们主要使用两种算法标记路由智能或随机。通过构建一个本地代理的决策矩阵一个令牌作为。代表的决定令牌传递的概率到邻居。在随机路由算法,为每一个,是统一的。然而,当代理建立了知识库的收到令牌,代理商吗可以路由也不失为一种聪明的办法。通过令牌的优势可能相关的领域知识,以前收到令牌可以用来更新本地概率模型,获得令牌预测,发送方可以请求一个相关的令牌。例如,信息的发送方令牌“我饿了”表示,它可能会感兴趣的一个资源令牌“披萨”给一个饥饿的代理。因此,每个令牌是用于改善其他标记的路由将导致显著的性能改进。(描述的详细和关键算法23),编码在我们的模拟器。

6。复杂的网络效应在协调效率

在本节中,我们简要地分析复杂网络效应会改变团队的协调性能。我们模拟令牌作为有限马尔可夫链的随机漫步,是时候可逆(24]。为一个特定的令牌运动,我们可以定义不同的州。

因为它是图所示2,国家将国家定义的令牌移动到一个代理的最短的距离从水槽代理。具体来说,概率定义的令牌传递状态的概率来。因为令牌只能为每个地平线上一步,除了。因此,对于一个国家,令牌可能接近目标,保持在同一水平,或移动的遥远。当牌达到的状态,它会停在目的地和概率。例如,假设是初始状态概率分布的令牌。根据马尔可夫链理论,我们可以计算的概率令牌后到达沉剂步骤。

作为代理传播令牌随机人的邻居,会有不同的源和目的地之间的距离。图3显示的相对速度(标记为“关闭”),(标记为“相同”),(标记为“进一步”)无标度和随机网络。请注意,我们平均在每个节点的距离,虽然这从节点到节点会有所不同。的设在显示了从一个节点到目标节点的距离,也就是说,目标代理。的设在美国的比例显示“进一步”“一样”和“近”,不同的颜色代表了相应的比例,和它们的总和是1。注意,令牌到目标越近,越有可能将随机通过进一步的目标。相应地,进一步令牌从目标,就越有可能会通过接近目标随机运动。此外,由于数据显示不同的发行版,令牌运动特征可能是不同的。

图3(一个)显示了一个典型的无标度网络。状态概率转移矩阵在这个网络拓扑

图3 (b)显示了一个典型的随机网络。状态转移概率矩阵是

假设同样的初始分布令牌随机运动1000步之后,无标度网络的状态概率分布0.8287 0.0030 0.0198 0.0605 0.0675 0.0194 0.0011 0.0000,在83%的情况下,这个令牌已经达到目的地代理。另一方面,随机网络的状态概率分布0.0171 0.0084 0.0575 0.3337 0.4904 0.0920 0.0009 0.0000,只有约1.7%的情况下,这个令牌已经达到目的地代理。它证明了我们观察数据。无标度网络中信息传输的效率高于随机网络。

另一方面,在团队中,令牌不只是随机移动时从代理,代理代理可以建立一个更好的决策模型(23]。因此,令牌可以更快得到公认的基于代理的本地知识。这样的运动模型不是完全随机的,而是偏向于目标,我们使用一个参数为了使大,小。然而,这种偏见应该更强的令牌也渐渐靠近目标位置,因为代理如他们的邻居更容易知道目标。我们通过使用模型。非正式地,一个能想到的的总学习团队的团队和状态多少代理“附近”代理知道它比代理“远”。使用和马尔可夫链状态转换,可以写成 此外,一个值为0.97时用于偏见对向目标代理的联系。数据3 (c)和3 (d)显示,分别对无标度的影响和随机分布。令牌尤其接近目标时,他们更容易接近目标和代理将更有效的传递令牌。

无标度和随机网络相比随机游走,如果令牌的初始分布是一样的在上一节(即,0.25 0.25 0.15 0.15 0.1 0.05 0.04 0.011000运动)后,我们会发现状态概率分布1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000这令牌肯定会到达目的地。此外,100年以后动作,状态概率分布0.9290 0.0029 0.0094 0.0242 0.0262 0.0078 0.0005 0.0000。这意味着,在93%的情况下,令牌已经到达目的地,这是比牌的随机移动超过1000步骤相同的网络拓扑。上述理论分析验证可替换主体协调将会有一个显著的差异在不同的网络拓扑与随机和智能协调策略,因此它将模拟器设计中我们将考虑的一个重要因素。

7所示。模拟器的设计

在本节中,我们描述我们的模拟器的设计称为CoordSim,如图所示4。这个模拟器可以模拟协调的主要方面,包括信息共享、任务分配和资源分配。CoordSim抽象环境通过模拟只对系统的影响。代理商不能接受任何领域知识,除非他们感觉自己或被队友“告诉”网络。任务是模拟所需的物理资源,允许只有一个代理来访问它们在任何给定的时间。没有成本转移资源,资源不能使用或丢失。随机分布的任务在一个开放的环境。所有代理允许“思考”和“行为”在每个时间步,虽然他们的“行动”抽象模拟的影响,他们只需要一个时间步。

奖励团队收到的模拟是当一个任务分配给一个代理。CoordSim的最突出的优点是它允许大量的参数调整,也允许将数据记录,如奖励的数量和象征性的动作。有20多个参数,可以多种多样,包括大型异构的主要方面协调,和这些配置和记录有助于验证我们的方法的验证。

7.1。系统架构

CoordSim的系统架构如图所示5。主要包括五个模块:环境、代理、通信决策模型,以及监测、统计模型和用户界面,已被描述在黑暗的盒子里。在环境模块,它启动代理部署在环境,计划模板,可以激活模型代理商的联合活动,最初的网络代理连接,和可用的资源代理。根据协调的复杂网络效应的分析,在我们的模拟中,考虑不同的拓扑结构,允许用户模拟和分析网络结构的影响。网络代理组织为四个典型的网络结构:随机的,网格,小世界和无标度网络。请注意,尽管我们采取代理的移动性方面考虑,移动速度远低于通信速度。

代理模块,基于知识的初始环境,协调过程包括感知环境、网络互动、和执行自己的任务。特别是通过协调封装到令牌,决策模型构建的网络通信有两个算法:随机路由和智能路由。创建代理还包括异质性的初始化。仿真的关键在于代理启动计划如果他们获得了足够的信息,感觉或共享,他们可能需要不同的任务和获取所需的资源来实现系统的共同目标。因此,如果令牌封装资源、任务或信息接受代理,他们可以执行的任务所需的资源,并将信贷系统与回报。否则,令牌将不会停止,和代理将提出了令牌的邻居通信成本。

7.2。模拟网络的

在CoodSim,网络设计是网络中心代理最重要的部分。类似于人类群体成员通常保持少量的伙伴,当系统规模,网络显示了复杂网络的属性。在本文中,我们主要是对表演感兴趣当网络代理组织四个受欢迎的复杂的网络结构:ER随机网络(25)、网格网络WS小型网络(26),和BA无标度网络21]。的网络建设过程建立的组织网络代理的平均邻居(算法设计,总是一个偶数)如图6。网络链接的总数。(我)ER随机网络:网络从节点与空链接。对于每一个时间步,两个节点是随机拿起和与一个预定义的概率。(2)网格网络:每个节点只与相邻的邻居。网格网络的建设过程是直接的27]。(3)WS小世界网络:网络是基于规则的网格,WS小世界网络构建一个重新编译的过程。在这个过程中,网络中的每一个链接被选中的概率。如果选择的,一个节点的链接保存但其他节点将被替换为一个随机网络中的节点。(iv)BA无标度网络:网络始于一个完全连接节点。如果每个现有节点的程度是的概率,对于每一个待添加节点,连接到现有的节点是。

一般来说,网格网络聚类的特点但不呈现小世界效应(28]。ER随机网络平均路径长度小,但它不是集群相对。小世界网络的过渡网格网络ER随机网络,它有一个小的平均距离和高度的集群(29日]。因为主要的中心,无标度网络表现出很强的健壮性失败,但有时它可能削弱无标度网络的性能30.]。

除了网络设计,我们用一个简单的显示网络代理之间的交互方式如图所示7。

7.3。绩效评估和统计

因为scalable-team协调的复杂性问题,有许多参数可以调整和测试。在我们的仿真,通过改变20多个参数和可伸缩的主要方面协调,我们评估系统性能与奖励和沟通成本。具体而言,在本文中,我们主要感兴趣的参数最有助于网络中心代理。(我)如果沟通成本高,团队将获得更低的回报当达到相同的团队目标。(2)通信处理速度的令牌数量一个代理可以通过每秒。如果有更多的令牌,他们必须在接下来的第二次发送。(3)实时控制意味着一个任务或一个计划必须在很短的时间内进行的。(iv)任务重要性描述如何计算奖励。例如,无人机团队的目标是摧毁尽可能多的敌人车辆,缺少一个不是一个大问题。然而,城市搜救失踪一个受害者意味着团队失败了,所以必须分配的每项任务和计划。(v)团队规模是代理的数量的团队。(vi)异构团队描述了团队成员之间的功能类型的数量。(七)独家资源需求描述所需的资源类型的数量。(八)计划的复杂性定义的先决条件激活每一个计划。

8。仿真和结果

在本节中,根据我们的模拟器设计,我们简要介绍网络多重代理系统的仿真。目的是验证我们的模型能够模拟几百的协调网络代理。

8.1。多重代理系统协调

因为大规模的可替换主体协调的复杂性,我们通常会选择四个典型的应用领域:城市搜救(城市搜救),控制大范围搜索弹药(WASMs) [31日],“机器人足球世界杯”[32),和大型代理团队战略游戏和调度33]。例如,在城市搜救、协调主要集中在异构团队和只有一个或两个任务的计划模板。这些领域根据表中列出的特性进行了总结1。

实验证明是否不同的复杂网络特性可能影响可替换主体系统与智能标记路由算法的性能在不同的应用领域。四个复杂网络拓扑已经测试,我们提出了两组实验。在第一组,我们每个域的多重代理系统大小范围从50到500年,平均4邻居为每个代理。在第二个,我们修复系统大小为100,平均每个代理的同事数量从2到10不等。

第一个实验的结果如图8。在大多数领域,因为小世界效应的性质,基本随机网络,小世界网络优于基于网格的网络。在某些领域,由于无尺度效应的财产,无标度网络可能比其他三个网络拓扑。原因是几个代理可以作为中心节点和获得更多的知识如何明智地通过一个给定的令牌在正确的方向上。另一方面,在一些领域如机器人世界杯赛,无标度网络产生更多的令牌和接收更少的回报。原因是,中心节点维护许多邻居,但平均令牌从每个邻居可能会减少。因此,中心节点无法建立一个更好的模型基于前面的令牌,他们已经收到了。

第二个实验的结果如图所示9。平均而言,所有的网络拓扑时提高性能代理商保持平均四个邻居而不是两个的平均值。但当邻居的平均数量增加,除了电网网络,其他网络拓扑的性能变得更糟。因此,当邻居每剂数量的增加,平均每个邻居的令牌数量减少和代理不能保持更好的决策模型基于之前收到令牌。这是最突出的中心节点在无标度网络的无标度网络的性能下降得如此之快。相反,基于网格的网络增强了它的表现在两个方面。首先,邻居的数量为每个代理是一个常数。没有代理会有大量的邻居。随着越来越多的邻居,基于网格的网络平均距离是大大降低了。通过这种方式,它更容易智能通过令牌很快到目的地。 Therefore, the small world effect is important on system efficiency.

8.2。通信传输网络

在第二个仿真,分析和模拟通信传导机制基于我们的设计概率决策模型。在这些实验中,我们使用一个系统拥有400保险代理人,平均而言,每个代理有四个邻居。一个代理是随机选择一个令牌的来源,另一个是随机挑选的下沉。水槽代理将首先发送20个相关的令牌与和每一个将。接下来,源代理发送令牌和我们测量有多少令牌(通信成本)发送水槽代理。

在图10 (),我们首先不同从0.5到1。令牌传输效率的提高在所有与智能路由网络模型,而不是随机()与无标度网络的最佳性能。

在图10 (b),我们不同的数量相关的令牌从水槽代理从5到45岁。设置为0.9。它表明,通信将成为稳定后相关的令牌的数量超过15。这个结果也告诉我们,一些令牌足够为当地代理商建立决策模型。无标度网络需要更少的通信。

在图10 (c),我们运行实验和每个代理平均2 - 8的邻居。这表明更多的邻居可能不会有助于改善网络运输部分相同的结论7.1。

在过去的实验如图10 (d)大小,我们设计了不同的实验系统。网络传输效率测量作为令牌传递代理参与的比例: 实验的结果表明,不同大小的系统效率保持稳定。随机网络的比例略有变化及其通信保持高而无标度网络保持沟通。

9。总结和未来工作

在本文中,我们提出了一个新颖的方法来建模和模拟复杂网络属性在网络与代理数以百计的多重代理系统。关键是在典型的大型可替换主体系统中,稀疏分布式代理只能直接与很少的别人交流和网络可以建模为一个自适应复杂网络。通过抽象协调和封装成令牌,我们可以网络代理之间的交互模型和模拟他们在网络上。通过构建一个简单的局部决策模型如何转播协调封装在令牌,我们可以实现一个集成算法分散代理进行协调的主要方面,包括共享信息,分配任务,和共享资源;此外,我们考虑一个完整的复杂网络效应和提供不同的拓扑。所有的设计都编码成我们的模拟器CoordSim测试网络结构如何影响性能的协调。我们发现在一个典型的网络系统,小世界效应一致帮助网络协调,而无尺度效应通过引入节点高度可以减少网络的平均距离,以帮助提高性能,但它也可能导致网络拥塞的枢纽节点加剧协调效率。

虽然这个工作代表一个重要一步模拟大型分散网络化的多重代理系统协调,许多工作有待完成。批判性的模拟中,我们使用最简单的实例化的算法,忽略了许多性能增强技术提出了在文献中这可能是重要的模拟真实的应用程序域。我们打算扩展CoordSim实现其中的一些扩展,例如,个人的失败和代理商的不同的流动性,这可能影响性能在大型复杂网络可替换主体系统。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项研究已经得到了中国国家自然科学基金的资助。61370151,61202211,60905042和中央大学的基础研究基金。ZYGX2011X013。