跳转至

Efficient Multiagent Planning via Shared Action Suggestions

会议: AAAI 2026
arXiv: 2412.11430
代码: github.com/sisl/MCAS
领域: 强化学习
关键词: Dec-POMDP, 多智能体规划, 动作建议通信, 信念推断, 联合信念估计

一句话总结

提出MCAS算法，通过在Dec-POMDP中仅通信建议的联合动作（而非共享观测），利用动作信息推断其他智能体的信念状态，实现接近集中式方法的协调性能，同时大幅降低计算复杂度。

研究背景与动机

问题背景

多智能体系统在复杂工程项目和应急响应等场景中至关重要。Dec-POMDP（分布式部分可观测马尔可夫决策过程）是处理多智能体不确定性决策的标准框架，但其有限视界问题的复杂度为NEXP-complete，实际应用中几乎不可解。

现有方法的局限性

  • 无通信的Dec-POMDP：智能体必须独立推理环境和其他智能体的行为，复杂度极高
  • 完全通信（MPOMDP）：共享所有观测和动作可将问题降至PSPACE-complete，但完全信息共享在实际中往往不可行
  • 有通信的Dec-POMDP-Com：当通信非无损且非免费时，有限视界问题仍然是NEXP-complete

核心动机

人类协作的启发：人类自然地通过动作建议进行协作，例如"我们去那家餐厅吧"——这隐含了对餐厅营业状态、适合性和价格的判断，将复杂推理封装在简单的动作提议中。本文将这种直觉形式化：仅通过共享建议的联合动作，就能在不共享观测的情况下推断其他智能体的信念，实现有效协调。

方法详解

整体框架

MCAS（Multiagent Control via Action Suggestions）算法的核心思路分三步： 1. 离线求解 \(n+1\) 个MPOMDP策略（每个智能体一个 + 一个联合策略） 2. 在线执行时，智能体通过共享建议的联合动作进行通信 3. 利用动作建议推断信念空间，进行信念剪枝，估计联合信念，选择最优动作

关键设计

1. 信念子空间推断（Belief Subspace Inference）

核心洞察：一个动作建议隐含了建议者的信念位于信念空间中特定子空间的信息。

假设智能体 \(i\) 收到智能体 \(j\) 建议的动作 \(a_s\)，且 \(j\) 使用策略 \(\pi^j\)，则：

\[\mathcal{B}^j_{a_s} = \{b \mid \pi^j(b) = a_s, \forall b \in \mathcal{B}^j\}\]

在alpha向量策略中，这对应于被特定alpha向量主导的信念子空间：

\[\mathcal{B}^j_{a_s} = \{\mathbf{b} \mid (\boldsymbol{\alpha}_i - \boldsymbol{\alpha}_j) \cdot \mathbf{b} \geq 0, \forall \boldsymbol{\alpha}_i \in \Gamma_{a_s}, \forall \boldsymbol{\alpha}_j \in \Gamma\}\]

这一设计的动机是：既然我们假设智能体是合作且最优的，那么它的动作建议直接反映了其对环境的信念判断。

2. 信念剪枝（Belief Pruning）

每个时间步后，智能体\(i\)对智能体\(j\)的可达信念集大小为 \(|\hat{\mathcal{B}}^{i,j}_{t-1}| \cdot |\mathcal{O}^j| \cdot \prod_{j \neq i} |\mathcal{A}^j|\)，随时间指数增长。MCAS通过两种方式管理增长：

动作一致性剪枝：移除与收到的动作建议不一致的信念： $\(\hat{\mathcal{B}}^{i,j}_t \leftarrow \{b \in \hat{\mathcal{B}}^{i,j}_t \mid \hat{\pi}^{i,j}(b) = \sigma^{j,i}\}\)$

相似性合并：利用Lee等人证明的POMDP值函数Lipschitz条件，当两个信念的L1距离小于 \(\delta\) 时，它们的值函数差异有界：\(|V(b) - V(b')| \leq \frac{\|R\|_\infty}{1-\gamma}\delta\)。因此可安全合并相近信念。

此外设置最大信念集大小上限 \(\bar{B}_{max} = 200\)，通过迭代移除最近信念对中较低权重的信念来控制集合大小。

3. 联合信念估计（Joint Belief Estimation）

提出两种联合信念估计方法：

精确重构（理论可行但计算开销大）：利用推断的观测和动作直接更新联合信念： $\(\hat{\tilde{b}}^i_t(s') \propto O(\hat{\mathbf{o}} \mid \hat{\mathbf{a}}, s') \sum_s T(s' \mid s, \hat{\mathbf{a}}) \hat{\tilde{b}}^i_{t^-}(s)\)$

但内存需求为 \(\prod_{j \neq i} |\hat{\mathcal{B}}^{i,j}|\) 个联合信念组合，随智能体数指数增长。

Conflation近似（实际采用）：利用Hill提出的conflation方法合并概率分布： $\(\hat{\tilde{b}}^i(s) = \frac{b^i(s) \prod_{j \neq i} \hat{b}^{i,j}(s)}{\sum_{s' \in \mathcal{S}} b^i(s') \prod_{j \neq i} \hat{b}^{i,j}(s')}\)$

Conflation的优势在于：最小化合并时的Shannon信息损失、自动优先选择更确信的信念、无需人为设定权重。

损失函数 / 训练策略

MCAS不涉及传统意义上的训练损失，而是通过以下离线-在线流程实现：

离线阶段：使用SARSOP求解器为每个智能体生成MPOMDP策略（alpha向量表示），以及一个假设集中式执行的联合策略。

在线阶段： - MCAS变体：共享动作作为消息，基于动作一致性剪枝 - MCAS-α变体：共享alpha向量索引（更精确的信念子空间信息），实现更有效的剪枝 - 使用基于计数的启发式方法选择联合信念：维护每个估计信念的访问频次，选择最高频次的联合信念 - 协调智能体基于估计的联合信念使用联合策略选择动作并广播

实验关键数据

主实验

在多个标准Dec-POMDP基准上评估，每个场景运行2000次，使用95%置信区间：

问题 智能体数 MPOMDP（上界） MCAS-α MCAS MPOMDP-I Independent Dec-POMDP最优
Dec-Tiger (2) 2 59.5±0.9 58.5±0.9 58.5±0.8 34.3±1.7 -68.1±3.5 13.5
Dec-Tiger (3) 3 108.5±1.0 108.5±1.0 108.5±1.0 82.1±1.5 -95.5±4.1 —
Broadcast (2) 2 9.4±0.0 9.4±0.0 9.4±0.0 9.4±0.0 7.6±0.1 9.3
Meet 3×3 (2) 2 5.8±0.1 5.8±0.1 5.7±0.1 3.6±0.1 3.7±0.1 5.8
Box Push (2) 2 222.9±2.2 223.4±2.1 223.0±2.2 199.6±2.6 163.6±3.4 224.4
Mars Rover-UI (2) 2 23.9±0.1 23.9±0.1 19.8±0.2 16.4±0.2 15.3±0.2 —
Mars Rover-UI (3) 3 25.2±0.1 25.2±0.1 23.8±0.2 19.7±0.1 16.6±0.1 —

消融实验

信念集大小分析（MCAS vs MCAS-α的最大估计信念集大小）：

问题 MCAS-α MCAS
Meet 3×3 1.0±0.0 2.5±0.0
Meet 27 (UI,WP) 1.5±0.0 16.8±1.6
Box Push (SO) 4.8±0.1 192.1±1.2
Wireless 1.0±0.0 18.0±0.9
Mars Rover (UI) 1.0±0.0 2.0±0.0
Mars Rover (55G,UI) 1.0±0.0 3.0±0.0

关键发现

  1. MCAS-α近乎匹敌MPOMDP-C：在所有问题上，通过alpha向量索引的精确子空间剪枝几乎恢复了集中式性能
  2. 动作级剪枝也很有效：MCAS仅使用动作信息就能维持良好的联合信念估计，性能损失很小
  3. 信念剪枝效率高：87.8%的Box Push-SO运行中信念集达到上限，但其余问题中仅3.2%（Meet 27）的运行超限
  4. 某些问题中单智能体观测已足够：Broadcast和Wireless问题中MPOMDP-I与MPOMDP性能相当，说明一个智能体的观测足够做出好决策
  5. Conflation是有效的信念融合方法：MPOMDP-C在所有问题上与MPOMDP表现相似

亮点与洞察

  • 以人类协作方式为灵感的通信机制：动作建议是人类最自然的协作方式，将其形式化为Dec-POMDP的通信策略非常优雅
  • 从动作到信念的反向推断：通过假设最优行为，将动作建议转化为信念空间的约束，这一思路具有普适性
  • 计算复杂度的实质降低：从NEXP-complete降低到求解n+1个MPOMDP（每个都是PSPACE-complete），实际运行可在标准笔记本上完成
  • MCAS-α与MCAS的对比揭示了信息粒度的价值：共享alpha向量索引提供比动作更细粒度的信念子空间信息，在复杂问题中差异显著

局限与展望

  1. 依赖离线策略生成：MPOMDP求解规模仍随智能体数指数增长，限制了大规模应用
  2. 强假设条件：假设所有智能体具有相同的代理策略、消息无噪声无成本，实际中难以满足
  3. 仅适用于离线策略：尚未与在线求解器（如AdaOPS、BetaZero）集成
  4. 信念选择启发式的局限：基于计数的选择方法在某些问题上并非最优，未来可探索遗憾最小化等更优策略
  5. 需要更深入的理论分析：缺乏信念估计收敛性和相对集中式方法的性能界

相关工作与启发

  • 与occupancy state方法（Dibangoye 2016）互补：前者将Dec-POMDP转化为连续状态MDP，本文则通过通信降低复杂度
  • TCAS/ACAS X航空防撞系统是动作建议通信的实际应用案例：通过"禁止下降"等动作建议实现协调
  • 为人机混合团队提供了自然的通信框架，比共享观测或信念更符合人类交互习惯

评分

  • 新颖性: ⭐⭐⭐⭐ （动作建议通信的思路虽有前人探索，但信念推断和剪枝的形式化是新贡献）
  • 实验充分度: ⭐⭐⭐⭐ （7个基准问题的多种变体，比较全面，但缺乏大规模实际应用验证）
  • 写作质量: ⭐⭐⭐⭐⭐ （符号定义清晰，算法描述详细，餐厅隐喻贯穿始终）
  • 价值: ⭐⭐⭐⭐ （为可扩展的多智能体规划和人机协作提供了有价值的框架）

相关论文