《综述：多智能体系统（MAS）中的任务分配技术》美国空军项目支持

多Agent系统，尤其是无人驾驶系统，是解决很多现实问题的关键部分，因此必须改进任务分配技术。在这篇综述中，我们介绍了用于任务分配算法的主要技术，并根据所使用的技术对其进行了分类，主要侧重于最近的工作。我们还分析了这些方法，主要集中在它们的复杂性、优化性和可扩展性上。我们还提到了任务分配方法中使用的常见通信方案，以及任务分配中不确定性的作用。最后，我们根据上述标准对它们进行了比较，试图找到文献中的差距，并提出最有希望的方法。

关键词：任务分配、MAS、优化、学习、博弈论、元启发式方法

I. 简介

众所周知，自然界中的大多数系统都是复杂的分布式系统。这样的系统主要需要沟通和合作，以实现一个共同的目标，如改善群体内每个人的表现，旨在实现最佳的整体表现[1]。因此，由于受到自然界的启发，许多复杂的工程系统也采用了同样的原则。特别是在过去的15年里，很多研究工作都集中在多智能体系统上，这些系统可以更好地完成很多单一智能体有时无法完成的任务。智能体可以是一个物理实体，如UAVs、UGVs或UUVs，一般类型的机器人，但甚至是计算机资源，如处理器，或一个计算机程序[2]。

科学界将注意力集中在MAS上的原因有很多。一些任务，特别是分布式任务，由于其复杂性和前提条件，可能无法由单个智能体来完成。此外，多个智能体的存在提高了执行任务的性能和可信度，因为更多的智能体可以合作更快地完成相同的任务，而且系统对智能体的损失或故障更加强大。另外，成本可能会降低，因为可以使用许多便宜的、有时是一次性的智能体，而不是一个昂贵的智能体[3]。

但是，在使用多智能体系统完成多项任务时，出现了分工的问题，即哪项任务将被分配给哪个智能体，智能体将有什么类型的通信，一般来说，每个智能体的行为将被定义，以便有一个最佳和强大的性能[3], [4]。所有这些问题的答案就是任务分配技术。为MAS中的任务分配问题找到一个最优或接近最优的解决方案是一个相当困难的过程，在一般情况下已被证明是NP困难的[5], [6]。任务分配的一些主要目标，除了实现整体最优的系统性能外，还可以是任务执行时间的最小化，一些智能体保持不活动的时间最小化，在特定的时间内完成的任务数量最大化，任务分配程序的可靠性最大化，即任务的成功完成，等等。[7]. 由于最佳整体性能是一个模糊的概念，难以量化，而且可能取决于每个智能体的感知，因此使用了效用的概念，即对任务分配程序对系统性能的价值或成本进行估计[4]。

任务分配的第一步是静态的，但由于现实环境是动态环境，动态任务分配领域在过去几年中已经成为一个很大的研究领域。在动态任务分配中，系统可以处理任务或环境的在线变化，具有更强大的性能[8]。使用的算法可以是集中式的，也可以是分散式的，取决于智能体的通信结构，也可以使用同质或异质的智能体。在任务分配技术的最初应用中，主要是假设同质智能体，因为相应算法的计算负担较小。但是，在现实世界的应用中，经常需要异质的智能体。例如，在机器人系统中可能存在不同类型的传感器，或者同一问题的不同任务可能需要不同类型的机器人。尽管异质性增加了计算成本，但它在许多应用中的必要性，促使研究人员为异质MAS开发了大量的任务分配算法[9], [10]。

用于解决MAS中任务分配问题的主要技术是基于拍卖（或市场）的方法、基于博弈论的方法、基于优化的方法（启发式算法、元启发式算法等），以及机器学习技术。根据所使用的技术，可以找到一个最佳的，或者几乎总是一个近似的解决方案，而且问题的可扩展性、复杂性和适应性也会存在不同程度。MAS中的任务或任务分配的应用包括搜索和救援任务（SAR）[11]-[14]，军事行动，如攻击或监视[15]-[18]，物理灾害管理[11]，[12]，[19]-[22]，其中主要使用无人驾驶系统，也包括众包平台的使用，云计算[23]-[28]，智能电网，制造业的资源分配[29]-[32]和其他。

II. 任务分配技术的不同通信方案

解决任务分配问题的算法主要有两大类，即集中式算法和分布式算法。

A. 集中式任务分配

集中式算法是过去研究较多的一类算法。其主要概念是，有一个中央协调者智能体，它与所有其他智能体有通信渠道。这个智能体管理其他智能体的谈判，并决定分配给其他智能体的任务。在这些情况下，大多数时候，会考虑全局效用函数[14]，[33]，[3]，[34]。

图1. 一个集中式系统，智能体A7是中央协调人

这些方法的优点是使用较少的系统资源，可能有较低的实施成本，但由于计算成本高，它们只能用于少量的智能体，而且它们不能适应动态环境，因此它们主要用于静态任务分配。任务集中分配的事实避免了任务分配的冲突，因此不需要共识阶段，也可以找到分配问题的最优解。它们也缺乏稳健性，因为它们很容易受到智能体，特别是中央智能体的损失，导致整体性能的恶化。此外，所有的智能体与中央智能体进行通信的事实，限制了它们的可扩展性[17]，[35]。

B. 分布式任务分配

分布式算法克服了集中式算法的一些缺点，因此它们在过去几年中吸引了研究人员的注意。在这种类型的算法中，没有中央协调者，智能体对环境有一个局部的感知，并可能相互协商。因此，任务分配的决定是以分布式方式在局部做出的。每个智能体也可能有自己的效用函数，总体效用函数可能是近似的[14]、[33]、[3]、[34]。

图2. 一个分布式系统

这些方法的优点是它们具有稳健性，因为智能体的失败对整体性能的影响很小，而且由于智能体之间的通信水平较低，所以也是可扩展的。此外，它们的计算成本比集中式方法小，使它们成为大规模系统的理想选择，即使通信带宽很小。权衡之下，它们找到了任务分配问题的次优（近似）解决方案，而且可能需要一种共识算法，因为局部任务分配可能导致任务之间发生冲突[17]，[35]。

III. MAS任务分配中的不同算法

在MAS中，有很多用于任务分配的技术。下面对所使用的方法进行分类介绍（见图3）。

A. 基于拍卖的算法

在MAS中用于任务分配的一大类算法是基于拍卖的算法。这类算法以经济学为基础，智能体使用谈判协议，根据他们对环境的局部感知，在拍卖中为任务投标。这就是为什么有时这些方法也被称为基于市场的原因。智能体根据他们计算的效用或成本出价，他们的目标是为分配的任务完成最高的效用或最低的成本。基于智能体的效用函数，一个全局目标函数被优化。拍卖者可能是一个中央智能体，也可能由系统的智能体以分布式方式进行拍卖，拍卖可能需要几轮，可以考虑一个或几个任务[10], [14], [36], [37]。

基于拍卖的算法有很多优点，例如，即使找到了次优的解决方案，也有很高的解决效率，因为它们同时使用了集中式和分布式的方法及稳健性。它们也是可扩展的，因为它们有适度的计算成本或通信负担，不是完全集中式的算法，它们对动态任务分配很好，因为它们可以从拍卖程序中增加或删除新任务[3]。

图3. 任务分配技术分类

a) 基于CBBA的算法：基于共识的捆绑算法（CBBA）是一种分布式的算法，它为多目标优化问题提供解决方案，与智能体态势感知的不一致无关，其成本函数是每个智能体对执行捆绑任务所感知的效用。在第一阶段，该算法使用带有贪婪启发式的拍卖来选择任务，在第二阶段，该算法应用基于共识的程序来解开任何重叠的任务。该算法被证明可以为单机器人单任务的任务分配问题提供次优解（完整的分类法见[4]），并且具有高度的可扩展性，使其适用于动态任务分配应用，因为它具有多项式时间竞标[38] [39]。

最近发现的方法包括PI（性能影响）算法的改进，如PI-MaxAss[14]和[35]。此外，其他技术是CBBA算法的改进，如修改的CCBBA[38]，G-CBBA[40]和[41]。

b) 基于CNP的技术：Smith[42]开发的合约网协议（CNP）是第一个用于任务分配问题的谈判平台，构成了众多任务分配算法的基础。它是一个标准化的协议，可以将任务分配给最合适的智能体，同时它能够在需要时进行任务重新分配[43]。另一方面，CNP有信息拥塞的问题，有时会使智能体之间的谈判程序变得不方便。与其他方法不同，如基于信息素的方法，CNP在很大程度上依赖于智能体之间的信息通信，这些信息的计算成本可能非常高，从而降低了通信效率和系统性能[44]。

最近一些基于CNP的方法包括[45]、[46]、[11]、[27]、[44]。此外，一种不属于上述类别的基于拍卖的方法是（FMC TA）[47]。

B. 基于博弈论的方法

在基于博弈论的方法中，假定智能体是采取特定行动的玩家，任务分配方案是他们应该遵循的策略。在博弈结束时，玩家根据他们的行动所获得的回报被称为报酬。当玩家选择了最佳策略，那么他们就不会希望改变他们的策略，因为这是他们能够完成的最佳结果，达到纳什均衡[48]。

博弈可以分为两大类，合作博弈和非合作博弈。在合作博弈中，智能体在采取具体行动之前进行合作或形成联盟，影响他们的一般战略和效用。合作博弈的一个例子是联盟形成博弈。在非合作博弈中，智能体单独选择他们的行动和策略，这意味着智能体是自私的，希望达到最高的回报。一些例子包括贝叶斯博弈、非合作性差分博弈、子模态博弈等。[49].

最近一些基于博弈论的方法包括[50]、[20]、[51]、[52]、[53]、[54]、[55]。

C. 基于优化的技术

优化是应用数学的一个领域，旨在从一组可能的解决方案中找到一个特定问题的解决方案，使某一成本或目标函数的成本最小或利润最大。这个成本函数根据一些约束条件进行优化，决定了系统的目标。有很多优化技术可以是确定性的或随机性的[3], [56]。确定性方法不考虑随机性，也就是说，如果使用相同的起点，通往解决方案的路径将是相同的。确定性方法包括诸如图形方法、基于图形的方法、顺序规划、线性规划、混合整数线性规划（MILP）等技术。随机方法或元启发式方法是指在计算过程中包含随机性的方法。元启发法包括进化算法、蜂群智能、模拟退火等。此外，启发式算法是用来寻找快速和高质量的解决方案的算法，以解决确定性方法会有难以承受的计算成本的困难优化问题。这些方法虽然提供了近似的解决方案[57]。

a) 基于确定性的优化：一个经常被用作开发新任务分配算法的基础的优化算法是匈牙利算法[58]。匈牙利算法将任务分配问题视为一个组合优化问题，使用图论并在多项式时间内解决该问题。该算法计算每个智能体效用的估计值，从而使整体效用最大化。但这在计算上是很昂贵的，而且当系统存在高不确定性时，有时价值较低，因此对该算法提出了很多改进[59]。最近的一些方法包括[60]、[61]和[62]。

b) 元启发式算法：元启发式算法包括几种方法，如蜂群智能、遗传算法、模拟退火和其他。蜂群智能已被广泛用于MAS的任务分配，它是一类受生物启发的算法，主要来自具有社会行为的动物，如昆虫群、鱼群、鸟群等[63]。 这些动物表现出高效的分工，由于团队成员的专业化，导致了群体的高效率[64]。即使智能体可能相当简单，但由于他们的合作，他们可以作为一个整体完成复杂的任务，导致强大、高效和低成本的解决方案[65]。另一方面，这些算法有时会给智能体分配不必要的任务，导致冲突，并对环境变化有缓慢的整体反应[63]。主要使用的方法分为基于阈值和概率的方法。

在基于阈值的方法中，如响应阈值法[66]，智能体决定其关于任务的行动，取决于一些监测量的值和阈值的值。阈值可以是固定的，也可以是可变的，智能体可能只有关于该数量的局部或整体信息。在概率方法中，智能体根据环境观察或历史数据计算出的概率，随机地改变任务。另外，可能会使用一个刺激物，当刺激物对特定的任务来说是高的时候，可能会选择一个任务[67]。

最近一些基于元启发式的任务分配方法包括改进的分布式蜜蜂算法[63]、动态蚁群的分工[17]、分布式免疫多Agent算法[68]、改进的QPSO[69]、分层任务分配和路径寻找方法[70]、多目标多类人机器人任务分配[71]和其他技术如[72]、[73]、[15]。

c) 启发式方法：最近基于启发式的方法包括Lazy max-sum算法[19]、平均Hamilton分区--多个旅行推销员算法[74]、One-To-Many Bipartite Matching[75]、基于最近邻的聚类和路由方法[76]和[77]。

D. 基于学习的方法

要预测一个智能体必须处理的未来干扰是非常困难的，特别是在没有具体的数学模型来描述环境行为的情况下，这对实际应用来说是动态的。因此，一个解决方案是智能体学习如何面对这种干扰，考虑到他们过去的行动和其他智能体的行动，从而提高系统效率[78], [79], [80]。

一个典型的机器学习技术是强化学习，其中智能体使用他们的经验来学习如何在环境的不同状态下采取行动。环境通常是以马尔科夫决策过程（MDP）的形式形成的，智能体优化成本或奖励函数，以便从环境中学习。经常使用的RL方法是Q-learning，它是一种无模型的RL方法，帮助智能体找到MDP的最优解。[78], [79]. RL有很多优点，包括处理环境中的不确定性、实时实施（对于训练有素的网络）和处理不同的任务[16]。另一方面，特别是在大规模的复杂系统中，大多数RL算法需要高计算能力[81]。

已发现的基于学习的方法包括[82]中的分布式自组织地图方法、[12]中的随机强化学习算法、基于图的多智能体强化学习方法[83]、带有增强爬坡搜索方法的MARL[84]、基于Q-学习的快速任务分配算法[16]、使用合作深度强化学习策略的任务分配过程[79]和基于MARL软Q-学习方法[85]。

E. 混合方法

除了上述解决任务分配问题的方法外，还有一些结合了上述一些方法的其他方法，它们被称为混合方法。

在[86]中，优化和基于拍卖的方法被结合起来，而在[87]中，基于市场的方法与基于博弈论的方法被结合起来。此外，[88]、[89]和[13]是基于市场和元启发式的结合，[90]是基于市场和学习的结合。在[91]中，进化算法与贪婪算法相结合，而在[92]中，基于博弈论的方法与学习算法相结合。

IV. 任务分配程序的关键因素

评价MAS中的任务分配程序的一些基本标准是所使用的算法的计算复杂性、解决方案的最优性和所使用方法的可扩展性。此外，算法处理不确定性的能力，以及通信程序的有效性，对整个系统的性能起着重要作用。

A. 复杂性、最优性和可扩展性

影响任务分配计算成本的因素是所使用的算法的复杂性，这些算法的使用频率，以及智能体之间需要的通信方法的计算成本（智能体为实现成功的任务分配需要交换的信息比特）[93], [94]。

另一个关键因素是找到的解决方案的最优性。当我们提到任务分配程序的最优性时，我们的意思是所找到的解决方案具有可能的最高总体效用，受到系统特性的限制，如提供给智能体的信息的噪声、不确定性和不准确性。为了找到动态而非静态的解决方案而执行算法的频率，以及可以重新分配的任务的比例，都会影响解决方案的质量[4]。此外，随着越来越多的复杂任务和更多的智能体被用于任务分配方案，算法的可扩展性对其有效性至关重要。

表一 一些有代表性的任务分配算法的复杂性

a) 基于CBBA的方法：所提出的基于CBBA的方法，是CBBA和PI算法的改进，比基线CBBA方法有更好的效率和可扩展性，但缺点是计算成本较高。具体来说，PI-MaxAss[14]算法的计算复杂性相当于 ，其中 是任务数。此外，改进的CCBBA算法[38]的复杂度为 ，其中Θ是收敛前需要的最大迭代次数， 是每个任务的最大传感器数量， 是智能体数量， 是任务数量，M是规划范围。

b) 基于CNP的方法：一般来说，基于CNP的技术在重新分配任务方面非常好，但高度依赖于智能体之间的通信程序，通常造成高计算成本。此外，CNP的另一个问题是观察到的信息拥堵。所提出的改进的CNP算法，比基线CNP有更高的效率和更小的计算成本。但是，即使有一些方法试图解决消息拥塞的问题，例如[44]，这仍然是一个开放的研究领域。

c) 基于博弈论的方法：所提出的博弈论方法，比基线方法更有效，有更好的次优（近优）解决方案。此外，一些博弈论的算法比基于市场的方法有更好的效率。至于复杂度，基于Apollonius圈的主动追击者检查（AAPC）[52]，其复杂度为 其中 为追击者的数量。基于匿名享乐博弈[50]的GRAPE算法的复杂度由 约束，尽管在大多数情况下要小得多，其中 是网络的图径， 是任务数， 是智能体的数量。至于每个智能体的通信复杂度是 ，其中 是智能体i所通信的智能体数量。

d) 启发式方法:有很多解决DCOP问题的技术。提供最优解决方案的技术通常具有指数级的协调负担，而基于启发式的技术具有较低的协调成本，但提供次优的解决方案。一些提议的技术显示了比一些基于遗传和市场的方法更高的效率和更小的计算成本[19]。懒惰的最大和方法[19]的信息传递复杂性为 但如果我们考虑所有智能体对所有任务的分配，复杂度会上升到 对于找到次优解的AHP-mTSP算法[74]（平均哈密尔顿分区，多个旅行销售人员问题），对于 个智能体和 个任务，每个迭代的复杂度为 平均运行时间为 。此外，集中式启发式基于最近邻的聚类和路由（ncar）方法[76]的计算成本为 ，其中 是智能体的数量。OTMaM技术[75]适用于大规模的系统，其时间复杂度为 ，其中 是智能体的数量， 是任务的数量。

e) 元启发法：元启发式技术成本低、稳健、高效，但有时会造成任务间的冲突，为智能体分配不必要的任务，对环境变化的反应也很慢。与基线算法相比，所提出的算法具有较低的复杂性和更好的可扩展性。但是，其中一些算法是次优的，或者假设通信程序没有故障。此外，其中一些算法比一些贪婪的和基于市场的（如CNP）方法具有更高的可扩展性和更好的性能。对于MOMHTA算法[71]，总体最坏情况下的复杂度是 ，其中 是任务的数量，H是超平面上参考点的数量，L是目标的数量，K是创建集群的数量。

f) 基于学习的方法：基于学习的方法，特别是强化学习的方法，通常具有很高的效率，可以在线实施，并对环境干扰有很好的表现。我们注意到，很多技术比基线模拟退火、爬坡和贪婪算法有更好的性能。此外，我们还注意到比基于边界的方法和匈牙利方法的效率更高。尽管一些方法的计算成本比基于拍卖的方法小，但计算成本和维度的增加仍然是其他强化学习方法的一个问题。

表二 一些有代表性的任务分配算法的通信类型

g) 混合方法：使用混合方法是一个非常好的解决方案，因为两种技术可以结合起来，利用它们的优势，实现比基线方法或只使用一种方法更高的效率或更小的计算成本。在[86]中，使用了简化的MILP程序和多智能体投标的迭代调度算法，迭代调度器的计算复杂度为 ，其中 是智能体的子集。此外，在这个调度器的低级阶段，使用了GSTP算法，增加了整体的复杂性。在[89]中，基于CBBA的方法与蚁群系统（ACS）算法相结合，并且在CBBA的包含阶段使用了基于贪婪的策略，最坏情况下的计算复杂性是 ，其中 是幸存者（任务）的数量。

表一中列出了上述算法的复杂度摘要。我们可以看到大多数方法都有多项式的时间复杂度。计算成本较高的是基于CBBA的算法，以及一些混合方法。另一方面，基于启发式的方法和基于博弈论的方法的复杂性较低。

B. 通信

智能体之间的通信是其协调性能的一个非常重要的因素。目标是智能体使用最小的可用带宽，在不使通信网络过载的情况下，交换有关其状态以及周围环境的重要信息[12]。智能体的通信可以是明确的或隐含的。显性或直接通信，是指智能体之间使用通信网络和专用网络协议交换信息。大多数现有的协调方法都使用这种类型的通信。隐式方法是指通过环境，使用智能体配备的传感器，获得关于多智能体系统中其他智能体的信息。如果智能体利用其他智能体在环境中留下的信息进行交流，那么隐式交流是主动的（生物学启发技术），如果智能体使用他们的传感器来感知环境发生的变化，那么隐式交流是被动的[96]。

显式通信方式通常比隐式情况有更高的准确性，缺点是通信负荷较高，特别是对于大规模的系统。隐式的情况下，即使缺乏准确性，也有更好的稳定性和更强的容错性。因此，混合使用这些方法是一个非常好的主意，可以利用它们的优势，导致更好的整体系统性能[96]。在表二中列出了一些任务分配的特征算法的通信技术。我们看到，一些经常使用的技术是社会网络技术、黑板计划、信息素图和一般基于图的技术。

表三 主要任务分配方法的比较

C. 不确定性

考虑到不确定性的任务分配技术，对于在现实生活中实现高效和稳健的任务分配非常有用。到目前为止，大多数技术，特别是分布式技术，比集中式技术更难融入不确定性。不确定性可以考虑到传感器的不准确性、智能体的失败、环境干扰等[97] [98]。根据以前的研究，应该把可靠性作为优先考虑的因素，因为如果忽略了失败的可能性，性能就会下降（次优性能）[99]。例如，在[100]中，作者发现在通信程序不确定的环境中使用基于异步共识的捆绑算法（ACBBA）（现实的有损网络环境），会产生低效的任务分配，特别是对于大量的智能体。因此，该算法的性能与理论上的预期性能相比是不同的。

在[99]中，使用启发式方法和非马尔科夫状态，研究了多智能体系统中的不确定性问题（通常是任务分配程序中的元素失效）。他们的结论是，做出简化的假设，如马尔科夫状态，会导致结果不能公平地反映系统的性能。此外，他们证明了在某些类别的问题中，使用更复杂的启发式方法，更好地描述物理环境和发生的不确定性，导致了性能的提高。在[97]中，作者通过处理不确定的环境，开发了性能影响（PI）算法的改进版本，提高了鲁棒性。提出了三种稳健的PI变体，使用蒙特卡洛抽样从高斯分布中抽取不确定的变量。与基线CBBA和PI相比，所提出的方法降低了不确定情况下的故障率和未分配任务的数量，但增加了计算的复杂性，使得它们对时间关键型应用不可靠。

因此，纳入不确定性在很多应用中是非常有用的，可以带来更好的性能。但是，总是存在着计算复杂度较高的危险，因此在效率、稳健性和收敛时间之间应该有一个平衡，这取决于可用的计算能力和每个应用的具体需求。

V. 结论

表三是主要任务分配技术的一些主要性能特征的总结，从1（低值）到4（非常高的值）进行了分类。我们看到，基于CBBA和CNP的技术通常具有较高的计算成本，使它们不适合大规模的系统。此外，确定性优化技术也有极高的成本和低可扩展性，使得它们也不适合于中到大规模的系统，尽管它们有非常好的效率。另一方面，启发式和博弈论方法具有非常低的成本，使它们成为提供具有中等和良好效率的快速解决方案的理想选择。这些方法也可以用于大规模的系统，因为它们具有非常好的可扩展性。元启发式方法和学习方法具有适度的成本、良好的效率和可扩展性，可用于中等规模，有时也可用于大规模环境，这取决于具体问题。特别是学习技术在动态任务分配和动态环境中非常好。

随着MAS系统技术的发展和计算能力的逐年提高，在实际环境中实施改进的任务分配算法的需求势在必行。这样的环境有很高的不确定性，复杂的任务，并且可能需要实时实现所用的算法。由于对这种环境的适应性，RL方法是一个很有前途的任务分配研究领域，在过去的几年里被科学界广泛研究。此外，博弈论和元启发式方法对这类系统也很有前途。如[101]所述，基于RL和博弈论的技术的结合改善了多Agent情况下的RL（MARL），因此基于博弈论和RL的技术的结合对于任务分配方法来说也是非常有前途的。