第二部分 分布式规划与优化

2 分布式规划

2.1 研究背景

在典型的多智能体系统中，通常有多个独立行动的智能体参与同环境的交互。环境中的每个智能体是一个独立的决策者，根据从环境中获得的观察和已有的领域信息自动做出决策，并执行相应的行动来达成某些目标。在许多实际的应用问题中，如多机器人系统（例如无人机集群）和多传感器网络（例如天气监测雷达阵列）等，多智能体系统需要完成的是多步决策问题，也就是每个智能体不仅要考虑行为的当前效果，还要考虑该行为对未来决策的影响。多步决策问题同时也被称为序列化决策问题，解决这一问题的过程被称作规划。具体地说，分布式规划的过程就是产生一组行动序列，使得每个智能体独立按照这个行动序列执行时都能够达到某些目标，完成指定的集体任务。也就是说，分布式规划并不意味着规划的过程必须是分布式的，而是要求智能体能够分布式地执行规划的结果。先规划后执行的特点决定了分布式规划的智能体通常都是完全合作的关系，而不是自私或者对抗的关系，因为智能体在执行时需要完全遵从规划结果。

和经典规划问题一样，分布式规划的目标是设计算法，输入问题的模型表示，通过计算自动输出智能体所能执行的行动序列。经典规划问题的模型通常由以下基本元素组成：①问题的状态集；②智能体的行动集；③关于状态转移的描述；④问题的目标函数。在人工智能领域很早就开展了对经典规划问题的研究。为了降低问题的复杂性，经典规划问题通常不考虑状态转移的不确定性。但在许多现实问题中，动作的不确定性无处不在。例如机器人从一点移动到另一点时，可能因为轮子打滑等因素，不能准确地运行到目标点。对于分布式规划来说，由于每个智能体的动作执行都是独立的，智能体之间动作不确定性的问题就尤为突出。在多步决策问题中，每一步行动的不确定性都会被不断地积累放大，最终产生规划外的结果。在经典规划中每一步行动的效果都是确定的，无须系统的反馈就可以准确地获知行动的效果。而在不确定性的环境下，动作可能有多种效果，这就需要反馈信息来预测动作实际产生的效果。因此，分布式规划需要在规划的过程中完整地考虑每个动作产生的各种可能效果；同时在执行阶段，要求从环境中获取动作的反馈，从而指导后续动作的执行。不确定性环境下的分布式规划是目前的主流研究方向。如果环境是确定性的，那每个智能体行动的后果都是可以预测的，这类分布式规划问题在本质上和经典的规划问题一致，只是在状态和动作的维度上扩展为多个智能体。也就是说，确定性的分布式规划问题通常只是“大号”的经典规划问题，在计算复杂度上与传统的经典规划问题相当（例如多智能体的路径规划之于单个智能体的路径规划）。因此，本章内容更多是关于具有更高计算复杂度同时也应用更为广泛的，不确定性环境下的分布式规划问题。

马尔可夫决策理论为不确定性环境下的决策和规划提供了标准的模型表示和丰富的数学基础。它抽象地表示出了智能体决策所需要的关键因素，并用数学语言进行精确的描述。这样就能最大限度地忽略智能体之间的个体差异，同时能体现出不同决策问题间的本质区别，方便对不同类别的决策问题进行理论上的分析和算法设计。对于单智能体的决策问题，可以用马尔可夫决策过程（Markov Decision Process，MDP）以及它的一个重要的扩展即局部可观察的马尔可夫决策过程（Partially Observable MDP，POMDP）来进行建模和求解。在POMDP中，智能体并不能直接获得系统的状态信息，其对于状态的观察来源于传感器收集到的带噪声的局部信息，因此比MDP所要求的“上帝视角”更接近实际情况。在POMDP的决策过程中，智能体不仅需要考虑当前的观察信息，也需要考虑过去的历史信息，从而分析从自身所处状态的一个概率分布。这个关于状态的概率分布也被称为信念状态。由于概率分布是一个连续的空间，所以POMDP的求解要比MDP难得多（POMDP的复杂度是PSPACE，而MDP的复杂度是P）。在分布式规划中，由于智能体之间的相互独立，它们获取的信息也是相互独立的。因此每个智能体只能获得世界状态的某个局部信息，其决策过程更接近POMDP，即需要过去的历史信息而不只是当前的信息。与POMDP不同的是，独立的智能体在分布式执行的时候无法自然形成统一的信念状态，也就是每个智能体不仅要考虑状态的不确定性，还要考虑其他智能体行为的不确定性。

分布式老虎问题（Dec-Tiger Problem）[14]就是这样一个典型的不确定性环境下的分布式规划问题，如图2.1所示。在这个问题中，密室里出现了两个机器人，各自能独立地用自己的机械手打开一扇门，也能独立地用自己的传感器监听老虎的叫声，但它们彼此不能通信，即不能互相交换信息。它们的行为被设定成完全合作的：如果其中一个机器人独自打开有老虎的那扇门，则整个团队得到很大的惩罚；但如果两个机器人同时打开有老虎的门，则得到的惩罚较小。也就是在收益函数的设计上，鼓励两个机器人彼此展开合作。但由于机器人间获得的局部信息不一致，且彼此不能交换信息，所以要完成这样的合作是困难的。在多智能体系统研究领域，这类不确定性环境下的分布式规划问题通常利用分布式局部可观察马尔可夫决策过程（Decentralized POMDP，DEC-POMDP）进行建模和求解。

图2.1 分布式老虎问题