Decentralized Master-Mind: Joint Action Refinement through Iterative Intent Denoising in Multi-Agent Pathfinding
Valeriy Vyaltsev, Anton Andreychuk, Taisia Zlotnikova, Konstantin Yakovlev, Aleksandr Panov, Alexey Skrynnik
cs.AI, cs.MA
2026-09-26
DMM 把每步一次性动作采样改成多轮通信里迭代去噪动作意图,MovingAI 1600 任务解出 1598 个,并扩到百万智能体。
去中心化 MAPF(多智能体路径规划,多个 agent 在共享地图上各自走到目标且互不相撞)的学习型策略有个共同收尾动作:每个 agent 输出自己的动作分布,然后各自独立采样。窄走廊里两个 agent 要互换位置时,四种动作组合只有两种能协调收场,同时走相撞、同时等僵持。LC-MAPF、MAGAT+、HMAGAT 只在这条走廊上训练后采样,四种结果各占约 25%,一半直接无效。
论文证明这不是学习不充分的问题。只要专家的联合动作在给定上下文后仍有相互依赖,任何 per-agent 分布的乘积与专家联合分布之间就存在抹不掉的 KL 差距,下界是条件总相关(度量这种残余依赖),还要叠加每个 agent 看不到邻居上下文带来的信息缺失。论证借自非自回归序列模型的多模态问题:每个位置的边缘分布全学对,乘起来仍会拼出非法序列。
DMM(Decentralized Master-Mind)把采样换成去噪,机制上像离散版扩散:
关键在「被精修的意图本身就是通信内容」。既有的学习通信传的是上下文信息,传完照样独立采样;DMM 让 agent 看得见邻居正在形成的随机选择,提交前互相耦合,而单个 agent 的计算量不随团队规模增长。同为扩散路线的 DiffLNS 集中式精修全体 agent 的整段计划,DMM 是逐步的、去中心化的精修。
训练分两段。先用专家解做模仿,监督每一轮的投票,并以 teacher forcing 按概率把专家动作注入初始意图和各轮投票,注入概率从 1.0 退火到 0.8 的保留下限。再用 MICPO 做免 critic 的强化学习微调:同一场景的一组 rollout 共享相同的采样初始意图,组内比较算优势;团队回报由离目标时长和被挡动作数构成;重要性比率按 agent 按轮计算并截断,外加对冻结模仿策略的 KL 约束。
走廊实验先验证机制:DMM 在歧义状态把 94.8% 的采样压在两个有效解上,三个基线约 50%;测试时把精修轮数从 4 加到 8、12,不重训就升到 99.6% 和 99.9%。把 teacher forcing 下限设为 0,DMM 退化到接近均匀分布。
POGEMA 上做纯策略对比(不带碰撞修正,后两类地图属训练外分布),最大团队规模处:
| 方法 | 设置 | 成功率 |
| DMM-MICPO-3M | Warehouse,192 agents | 1.000 |
| LC-MAPF-3M(最强基线) | Warehouse,192 agents | 0.938 |
| DMM-MICPO-3M | Cities-Tiles,256 agents | 0.922 |
| LC-MAPF-3M | Cities-Tiles,256 agents | 0.805 |
已解实例的 SoC(sum of costs,全体 agent 步数总和)中位数相对 LaCAM 的比值,DMM-MICPO-3M 在四类地图全部最低(1.006–1.102),MAGAT+ 与 HMAGAT 为 1.063–1.892。
MovingAI 1600 个任务,学习策略挂 CS-PIBT 碰撞屏蔽后的求解器级对比:
| 方法 | 解出数 | SoC 中位数 | 中位耗时 |
| DMM-MICPO-3M | 1598 | 100.1% | 8.27 s |
| DMM-MICPO-0.8M | 1593 | — | 2.33 s |
| HMAGAT | 1576 | — | 48.10 s |
| LG-LaCAM | 1569 | 100.3%(q95 达 164.0%) | 5.61 s |
| MAPF-LNS2 | 1411 | — | 8.43 s |
DMM-MICPO-3M 还在 736 个任务上取得不劣于任何对手的 SoC,这一计数同样居首。规模化实验里,DMM-0.8M 在 2304×2304 迷宫(约 29.1% 障碍)解掉全部 16 个实例,agent 数从 131,072 到 1,048,576;百万级场景全部到达目标,单趟 16,345–29,508 步,4 张 H100 约 4.4 小时,agent 数增 8 倍单步耗时只增 1.73 倍。对照 GPU-PIBT 全部撞到步数上限,最高密度下只有 89.15% 的 agent 到达。论文称这是首个在含障碍环境完全解掉百万级同时行动 agent 的学习型 MAPF 策略。
「独立采样重组出非法联合动作」这个病不限于寻路,凡去中心化多智能体策略,机器人编队、游戏 AI、多 agent LLM 系统都一样,在多模态联合决策上都会犯。DMM 的修法很便宜:架构不动,把中间样本放进通信内容。测试时加深精修轮数就能提升协调,与扩散模型加采样步同一道理。0.8M 版本只有 76 万参数,两段训练合计约 114 GPU 小时,2.33 秒的中位耗时给下游 LNS 精修留出 99% 以上的预算,代码已开源。
论文自己承认最重的一条:DMM 不硬约束联合动作可行性,MovingAI 与百万级实验都要靠 CS-PIBT 碰撞屏蔽兜底,而屏蔽用到全局信息,属于集中式组件,纯去中心的证据只在 POGEMA 那组。走廊消融显示 teacher forcing 下限归零后协调能力崩掉,说明相关行为有一部分靠训练时注入的专家信号撑着,机制脱离这招能泛化多远没有验证。MovingAI 的耗时对比也不在同一预算口径(搜索法 600 秒墙钟,学习法 5000 步),速度优势要打折看;百万级一趟 4.4 小时里,屏蔽本身占了不小开销。