《Artificial Intelligence》：Factored Planning in Partially Observable and Deterministic Multi-Agent Domains
编辑推荐：
在多智能体协同规划领域，尤其是在信息部分可观且行动具有确定性的复杂场景下，如何高效协调多个智能体以实现共同目标是一项极具挑战性的任务。针对此问题，Shashank Shekhar、Ronen I. Brafman和Guy Shani开展了一项主题为“部分可观与确定性多智能体领域的因式规划”的研究。他们创新性地将完全可观测多智能体规划中的“因式规划”思想扩展至部分可观场景，提出了一种三步求解框架。该方法首先将多智能体规划问题简化为一个单智能体规划问题，然后利用其解作为骨架计划，由各智能体独立完成，并最终同步处理形成分布式策略。实验评估表明，该算法在规模扩展性和求解质量上均取得了显著提升，为解决大规模确定性QDec-POMDP问题提供了新的高效方案。
在物联网、自动驾驶、无人机集群等智能系统日益普及的今天，多智能体协同工作以完成共同任务已成为常态。然而，现实世界往往是“雾里看花”——每个智能体通常只能通过有限的传感器感知其周围环境，获得局部的、不完整的信息。例如，一辆自动驾驶汽车无法直接“看到”被建筑物阻挡的另一辆车的位置，而家庭中的智能设备也仅能监测其所在房间的状况。这种“部分可观性”使得每个智能体的知识状态各不相同，形成了分布式信息格局。当多个智能体需要紧密协作，例如同时执行动作或按特定顺序行动时，这种信息的不对称和局限性就给目标的达成带来了巨大挑战。
为了应对这一挑战，研究者们建立了多种数学模型，其中分散式部分可观马尔可夫决策过程是描述此类协同多智能体规划问题的经典框架。然而，寻找最优解的计算复杂度极高，属于NEXP-难问题，难以应用于实际规模的问题。为此，研究者们引入了其定性版本——定性分散式POMDP。QDec-POMDP采用命题式（或称因式）的状态表示，更便于描述，并且能更有效地利用现有的强大经典规划方法，在确定性多智能体问题上已展现出比传统Dec-POMDP求解器更好的可扩展性。
尽管如此，求解QDec-PDPOMP的规模和效率仍有提升空间。由Shashank Shekhar、Ronen I. Brafman和Guy Shani共同完成，发表在《Artificial Intelligence》上的这项研究，正是为了突破这一瓶颈。他们聚焦于确定性的QDec-POMDP问题，提出了一种创新的“因式规划”方法。该方法的核心思想是将复杂的多智能体协调问题“分解”为一系列更易处理的单智能体子问题，从而显著降低了求解难度，并能够处理更大规模、更多智能体的规划实例。
为开展研究，作者主要运用了以下关键技术方法：首先，基于QDec-POMDP的形式化模型，定义了智能体的私有与公有变量、动作及协同动作。其次，提出了核心的“三步走”算法框架：（1）构造团队问题：将原多智能体问题松弛为一个单智能体应急规划问题，其解称为“团队策略”。（2）个体模仿规划：为每个智能体构建一个单智能体规划问题，目标是在仅依靠自身观察的前提下，模仿其在团队策略中的行为（特别是影响其他智能体的行为）。(3)策略后处理与同步：对生成的个体策略进行后处理，确保它们能良好同步，形成可执行的分布式联合计划。此外，研究还引入了“信号传递”的概念，建模了动作对其他智能体信念状态的影响，以实现隐式通信。算法在包含新旧领域的多种基准问题上进行了广泛的实证评估。
1. 方法框架与变体
研究提出的因式规划方法包含三个主要步骤。首先，通过将所有智能体视为一个能够即时共享所有信息的“元智能体”，将原QDec-POMDP问题转化为一个单智能体应急规划问题（即“团队问题”）并求解。其次，为每个智能体构建一个“模仿”问题，要求其仅基于自身观察来复现在团队策略中分配给自己的行动序列。若对所有智能体都能找到这样的模仿策略，则进行第三步，将这些策略同步后处理，形成最终的可执行分布式联合计划。作者研究了该方法的两种主要变体：第一种是基本的团队问题建模；第二种则在团队问题中加入了关于各子智能体知识状态的信息，使得每个智能体动作的前提条件依赖于其自身的知识，这促使规划器添加感知动作来增加相关智能体的知识。第二种变体的优势在于可以建模“信号传递”机制，即智能体可以通过执行某个动作（其唯一目的）来改变世界状态，从而向能观察到该状态变化的另一个智能体传递信息。
2. 理论性质
研究讨论了所提算法的理论性质。关键在于，在满足一定条件时，原问题解在某个变量子集上的“投影”可以构成该投影问题的解。这保证了将复杂问题抽象简化为只关注公共变量等关键子集的问题是合理且保守的，为后续的因式分解和求解提供了理论基础。
3. 信号传递
研究深入探讨了“信号传递”这一核心概念。这是指一个智能体执行某个动作，其主要或唯一目的是影响环境中的某个公共变量，从而将信息传递给能够观察该变量的其他智能体。显式通信是信号传递的一种特殊形式，但信号传递也允许隐式通信。例如，一个缺乏直接通信能力的智能体可以打开一扇门，并不是因为任何智能体需要通过它，而是为了向另一个能观察到门状态的智能体“信号”其应该向左而不是向右移动。这种机制极大地增强了智能体在缺乏直接通信渠道下的协调能力。
4. 实证评估
研究在多个基准领域上对新算法进行了实证评估，包括经典的4x4 Wumpus领域、论文设计的运行示例（一个简单的推箱-子领域）以及其他新旧领域。评估指标涵盖了可解决的问题规模（对象数量和智能体数量）以及求解质量。结果表明，无论是相比之前的IMAP算法还是编译方法，新提出的因式规划方法都实现了显著的可扩展性提升，能够解决更大规模的问题，并且通常能产生更好的解。
研究结论与意义
本研究成功地将适用于完全可观测多智能体规划的“因式规划”思想，扩展并应用于处理部分可观的确定性多智能体规划问题。所提出的方法通过“分解-协调”的思想，将复杂的多智能体QDec-POMDP问题转化为一系列更易处理的单智能体规划子问题，并最终整合为协调一致的联合策略。该方法不仅包含基础的团队问题抽象，还进一步发展了能建模各智能体知识状态和“信号传递”机制的增强变体，从而能够发现并利用智能体间的隐式通信来达成协作。
这项研究的重要意义在于，它为解决大规模、部分可观的协同多智能体规划问题提供了一条高效的新途径。理论分析确保了方法的可靠性，而广泛的实验验证则充分证明了其卓越的可扩展性和实用性。该方法能够处理包含更多对象和更多智能体的复杂场景，为自动驾驶车队协调、多机器人协同搜索与救援、分布式传感器网络优化等实际应用提供了强大的算法基础。此外，研究中形式化的“信号传递”概念，为理解和发展多智能体系统中的隐式协调机制提供了重要的理论框架。这项工作标志着在破解部分可观多智能体规划计算难题的道路上迈出了坚实的一步。
