多智能体规划

根据在决策中使用的技术，智能体可以分为两类：反应智能体（reactive agents）——仅基于智能体感应器的当前输入作出下一个决定，和规划智能体（planning agents）——该智能体考虑预期的未来情况决定最佳行动方式。

智能体应该如何计划以及应该何时进行反应取决于其所处的特定情况。考虑以下情形：智能体必须规划从一个地方到另一个地方的路线。反应智能体可能会使用指南针来绘制其路线，而规划智能体则会参考地图。显然，在大多数情况下，规划智能体会提出最短的路线，因为它不会遇到不可逾越的河流等障碍物。

在多个智能体都进行规划的情况下（通常是分散的），需要对智能体额外进行协调，并且由于沟通通常有限，结果往往不太理想。智能体规划问题本身已经很难，而多个智能体进行规划则带来额外的困难。因此，区别于一般的智能规划，多智能体规划往往会额外考虑以下问题：

1. 如何在计划之前对智能体施加额外的限制，以便他们的计划可以很容易地协调一致？
2. 如何有效地以分布式方式构建规划？
3. 如果每个智能体都有自己的偏好，那么当有多个选项时如何进行协作决策？
4. 智能体何时应向用户询问更多具体信息？
5. 如何衡量协调计划过程中有多少隐私会被泄露？

一般来说，多智能体规划问题可以定义为由一组多智能体规划的问题。除了一个整体的更集中（多项目）的规划问题外，每个智能体在这个基础上实际上都有个性化的独立的规划问题。典型的智能体个体计划问题包括一系列可以执行的操作（但需要额外附加一些成本，前置和后置条件）、一组目标（带有奖励值）以及当前（初始）状态剂。多智能体规划问题的解决方案是一个计划：一个部分有序的动作序列，当成功执行时，会为一些智能体实现一组已实现的目标。

在智能体之间的合作和通讯是可靠地前提下，在目前大多数技术都可以实现智能体的行为和目标仅仅弱相关的规划问题。但是，多智能体规划问题的范围远不止于此，一般可以将多智能体规划问题按以下三个标准分类：

1. 从独立到强烈相关：
   1. 独立：没有共享资源，没有依赖关系。
   2. 强烈关联：共同行动，共享资源。例如一起举起一个盒子，汽车组装。
2. 从合作到自利的智能体，在某些情况下，参与的智能体只对优化自己的效用(utility)感兴趣。
3. 从不可能的通信到可靠的通信：在执行期间，智能体可能不会或不能进行通信，在这种情况下可能需要在执行开始之前完成所有协调。例如机器人在灾难情况下拯救人员时通信条件会受到严重限制。

多智能体规划技术一般需要将问题分解为不同阶段，对每个阶段分别提供解决方案，一般来说，可以将其分以下几个阶段：

1. 将目标分配给智能体。
2. 将目标细化为子任务。
3. 通过添加资源分配（资源也可能包括智能体）和时间限制来安排子任务。
4. 沟通先前的计划以识别和解决冲突。
5. 执行计划。

[描述来源：de Weerdt, M.;Clement, B. (2009).Introduction to Planning in Multiagent Systems .Multiagent and Grid Systems. 5(4):345-355 .]

下图提供了一个多智能体之间如何协作、进行决策的例子，图中有两个智能体——Agent 1和Agent 2。每个智能体都有自己的噪声传感器以查看是否有火灾。但是，如果他们都打电话，他们的电话可能会互相干扰，则这两个电话都无法工作。Agent 1可以为决策变量Call1选择一个值，并且只能观察变量Alarm1的值。Agent 2可以为决策变量Call2选择一个值，并且只能观察变量Alarm2的值。通话是否有效取决于Call1和Call2的值。消防部门是否来电取决于通话是否有效。Agent 1的效用取决于是否发生火灾、消防部门是否来、以及他们是否有打电话，Agent 2同理。

[图片及描述来源：Poole, D.; Mackworth, A. (2017). Artificial Intelligence: Foundations of Computational Agents, second edition, Cambridge University Press. ]

发展历史

描述

1991年Thomas W. Malone和Kevin Crowston描述了一个新的研究领域，称为协调理论，侧重于协调的跨学科研究。在其中他们明确、简洁地指出了协调是管理活动之间相互依存关系的行为，这也是多智能体规划区别于普通规划的重点——即多智能体规划是规划和协调共存的研究。Thomas W. Malone和Kevin Crowston在1993年将这部分单独发表，再次强调了协调的重要性。此后的许多研究都借用了他们对于协调的定义。1996年，Jennings给出了一个更具体的多智能体规划的定义。

在此期间，Keith S. Decker和Lesser于1994年讨论了可扩展协调机制系列的设计和实现，这即是最著名的多智能体规划框架之一——通用部分全局规划算法（Generalized Partial Global Planning，GPGP），它构成了协作智能体团队的一套基本协调机制。这个框架的重要特征包括一组模块化协调机制（任何子集或全集都可以用于响应特定的任务环境）、涉及检测和响应传入任务结构中的域独立的特定抽象协调关系的一般规范以及协调机制与智能体本地调度程序的分离，使每个协调机制能够更好地完成其设计的工作。

1999年，Edmund H. Durfee提出了多智能体规划的6个阶段，当然，并不是在每一个多智能体规划问题中都一定包含这六个阶段。2001年，Edmund H. Durfee提出了交互环境的三个不同的维度：智能体群体、任务环境和解决方案属性。对于每个维度，他探讨了影响协调策略可用性的三个最明显的属性，以及在该情况下智能体规划的表现。

在多智能体系统中，如何进行任务分配是一个研究重点，早期的方法有使用经典规划框架来构建集中式多智能体规划框架，或拍卖等方法给予智能体更高程度的自主性和隐私性。2002年，Pynadath和Tambe使用马尔可夫决策过程提出了通用多代理团队决策问题（COMmunicative Multiagent Team Decision Problem，COM-MTDP）。COM-MTDP模型结合并扩展了当时的多主体理论，如分散的部分可观察的马尔可夫决策过程和经济团队理论，为处理部分可观察的世界提供了一个有趣的机会。

2003年Clement和Barrett通过使用称为共享活动（shared activities，SHAC）的更加模块化的方法将规划算法与协调行动分开来对PGP框架——PGP（Partial Global Planning）框架即是GPGP框架的基础——进行了改进。

近年来，随着深度学习的流行，不少研究也将神经网络用于多智能体规划中，如来自阿里巴巴和UCL的研究者们把多智能体星际争霸战斗任务设定为零和随机游戏，他们使用了神经网络，不同智能体通过新提出的双向协调网络（BiCNet）来相互交流。研究者们还提出了共享参数与动态分组的概念，以解决扩展性的问题。

主要事件

发展分析

瓶颈

目前多智能体规划的问题仍然对现实世界进行了许多简化，如智能体所处的环境比较稳定，世界的确定性比较高，智能体都是理性的并且有相当程度的一致性，存在一个可行的目标状态以及沟通几乎总是可靠的，并且（几乎）免费。

未来发展方向

多智能体系统实现通用人工可智能的必经之路，可能的方向有如何保证多智能体间的交流与协调顺畅以及多智能体如何集成等。

Contributor: Yuanyuan Li