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

2022 年 10 月 6 日 专知

多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]。