🤖 AI

Scaling Multi-Agent Epistemic Planning through GNN-Derived Heuristics

本文提出了一种可扩展的多智能体认识规划框架，该框架集成了由图神经网络衍生的启发式信息，以有效地引导通过复杂克里普克结构（Kripke structures）的搜索，从而显著提升了求解器相对于现有基准方法的性能。

原作者： Giovanni Briglia, Francesco Fabiano, Stefano Mariani

发布于 2026-02-09

📖 1 分钟阅读☕ 轻松阅读

原作者： Giovanni Briglia, Francesco Fabiano, Stefano Mariani

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在试图解开一个巨大的、多层级的谜题。但这里有一个转折：你不仅仅是在棋盘上移动棋子，你还在试图弄清楚房间里的其他人对这些棋子的看法，他们如何看待你的想法，以及他们如何看待你对他们想法的看法。

这就是**多智能体认识论规划（Multi-Agent Epistemic Planning, MEP）**的世界。这是一种用于计算机规划的类型，当一群智能体（如机器人或软件机器人）需要进行协作，但必须在管理自身信念以及关于彼此心智的认知时，就需要用到这种技术。

问题在于：这种脑力博弈创造了一个极其庞大且复杂的“搜索空间”，让计算机感到不堪重负。这就像是试图在一粒一粒地寻找地球上每一片沙滩上的特定沙粒，而且没有任何地图可以参考。

解决方案：“信念的智能 GPS”

本文的作者 Giovanni Brigia、Francesco Fabiano 和 Stefano Mariani 提出了一种新方法来帮助计算机应对这种混乱。他们构建了一个系统，利用**图神经网络（Graph Neural Networks, GNNs）**来充当这些复杂信念谜题的“智能 GPS”。

他们是如何实现的，以下是简单的步骤分解：

1. 地图是网络，而非列表

在传统的规划中，计算机将世界视为事实的列表。但在这种“认识论”世界中，系统的状态更适合被描述为一个连接的网络（称为 Kripke 结构）。想象一个蜘蛛网，每一个结代表一种可能的现实，而连接它们的丝线则代表不同智能体对彼此的认知。

挑战： 标准的计算机工具不擅长读取这些网络。它们试图计算每一个结，这非常耗时。
对策： 作者使用了 GNN。可以将 GNN 想象成一种特殊的相机，它能同时观察整个网络。它不是在数结的数量，而是通过“感知”网络的形状和结构来理解它距离解决方案有多近。

2. 从经验中学习（训练阶段）

在计算机能够解决新谜题之前，它需要学习什么是“好的”路径。

方法： 研究人员创建了一个“训练健身房”。他们让他们的规划软件运行数千个练习谜题。
教训： 当软件进行探索时，它会记录所走的每一步以及该步距离终点的距离。
结果： 他们将这些数据喂给了 GNN。GNN 学会了观察一个复杂的信念网络并立即猜测：“这看起来离目标还有 5 步，”或者“这看起来像是一个死胡同。”

3. “启发式”（直觉）

在计算机科学中，“启发式”（heuristic）是指帮助你更快做出决策的经验法则或直觉。

旧方法： 计算机会盲目地探索所有可能的路径，直到碰巧成功（就像一个蒙着眼睛在迷宫里摸索墙壁的人）。
新方法： GNN 充当了一个向导。在计算机采取行动之前，它会询问 GNN：“这个方向有希望吗？”GNN 会给出一个分数。如果分数高，计算机就会深入探索；如果分数低，它就会跳过这条路径。这避免了计算机在死胡同里浪费时间。

他们的发现（结果）

团队将他们的新型“智能 GPS”（他们将其命名为 deep）与旧有的盲目方法在几个标准的谜题领域进行了对比测试：

装配线（Assembly Line）： 机器人共同构建物品。
协作（Collaboration）： 智能体移动箱子并相互交流。
小道消息（Grapevine）： 智能体在不同的房间里分享秘密。

结果如下：

步骤更少： 由 GNN 引导的规划器需要查看的各种可能性要少得多。在某些情况下，它探索的“房间”数量比盲目方法少了 10 到 20 倍。
擅长处理难题： 虽然它并非在每个谜题上都完美无缺（有些确实太难了），但它在寻找解决方案的速度和效率方面始终优于旧方法。
泛化能力： 即使他们用一种类型的谜题训练 GNN，并在完全不同类型的谜题上进行测试，它仍然表现良好，这表明它学到的是网络的“逻辑”，而不仅仅是特定的答案。

局限性（不足之处）

作者诚实地指出了目前的限制：

速度： 虽然 GNN 帮助计算机“思考”得更聪明，但 GNN 本身的运行也需要一些时间。目前，“思考”部分比“搜索”部分要慢。这就像拥有一个出色的领航员，他能给出极佳的路线建议，但说话的速度有点慢。
工程实现： 作者指出，如果他们能让 GNN 运行得更快（使用更好的计算机硬件技巧），整个系统将会更加强大。

核心结论

这篇论文并不声称解决了所有的 AI 问题。相反，它证明了利用图神经网络让计算机“看见”信念的结构，是使复杂多智能体规划具备可扩展性的强大方式。它将盲目、精疲力竭的搜索变成了一场有引导、有智能的旅程。

技术摘要：通过 GNN 派生启发式算法实现多智能体认识规划的扩展

问题陈述

多智能体认识规划（Multi-Agent Epistemic Planning, MEP）是一个用于推理物理动作及多个智能体信念的框架。与经典规划不同，MEP 要求将状态表示为 Kripke 结构（有向标号图），以捕捉复杂的信念关系和高阶知识。这种表示法引入了两个主要挑战，阻碍了其可扩展性：

内在复杂度： 在认识状态（e-states）内应用转换并评估公式，比在经典规划中更具计算挑战性。
缺乏有效的启发式算法： 现有的 MEP 求解器通常依赖于无信息搜索（如广度优先搜索），因为有效的启发式算法非常稀缺。随着计划长度的增加，搜索空间呈指数级增长，导致计算不可行。虽然近期的一些工作（例如 H-EFP）尝试使用传统的规划构造（如规划图）来集成启发式算法，但很少有方法通过数据驱动的方法来解决 MEP 的可扩展性问题。

方法论

作者提出了一种利用 图神经网络 (GNN) 为 MEP 生成启发式算法的数据驱动方法。其核心思想是训练一个基于 GNN 的回归器来逼近“完美启发式算法”——即估计从任何给定认识状态到最近目标状态的距离。

1. 状态表示与嵌入

由于 e-states 自然地呈现为图结构（Kripke 模型），因此选择了 GNN，因为它能够捕捉关系结构。论文研究了三种将 Kripke 结构中的“世界”（节点）编码为适用于 GNN 输入的数值向量的策略：

符号 ID 映射 (Symbolic ID Mapping)： 根据生成顺序为世界分配连续整数。这种方法计算成本低，但会丢失世界之间的语义相似性，且在不同运行之间不具备不变性。
基于哈希的编码 (Hash-based Encoding)： 对世界解释和重复索引应用哈希函数。这确保了在不同运行之间具有一致的标识符，并在信息保留与计算效率之间取得了平衡。
位掩码编码 (Bitmask Encoding)： 将世界表示为编码了流（fluents）和重复索引的二进制向量。这保留了逻辑信息，但计算成本较高，且需要更大的模型才能收敛。

为了确保启发式算法能在不同的目标条件下进行泛化，作者将状态嵌入扩展到了包含目标的紧凑编码。这创建了一个统一的图，其中“状态节点”和“目标节点”相互连接，从而使模型能够学习当前状态与特定目标条件之间的依赖关系。

2. 数据生成流水线

训练数据使用 deep 规划器（一种最先进的 EFP 规划器的重新实现）中修改后的深度优先搜索 (DFS) 进行离线生成。

规划器在深度限制内探索状态空间。
当到达目标时，算法进行回溯，为每个访问过的 e-state 分配一个对应于其到最近目标距离的标签。
为了应对组合爆炸问题，生成过程采用了概率分支剪枝、随机动作排序和重复状态检查。
不可达状态被剔除以防止产生伪标签，并且距离类别的分布经过平衡处理，以避免对短计划的偏好。

3. 模型架构

该神经回归器使用 PyTorch 中的 PyTorch Geometric 实现。其架构包括：

位运算嵌入 (Bitwise Embedding)： 通过多层感知器 (MLP) 将节点标识符（位向量）和边属性投影到稠密嵌入中。
关系消息传递 (Relational Message Passing)： 两层 GINEConv（带有边卷积的同构图神经网络）聚合来自邻居的信息，通过显式结合边属性来处理异构模态依赖。
图级汇总 (Graph-Level Summarization)： 通过均值池化将节点嵌入聚合成固定大小的图表示。
深度残差回归头 (Deep Residual Regression Head)： 一系列残差块处理图嵌入，并通过 sigmoid 函数输出归一化的距离估计。

4. 搜索集成

训练好的 GNN 被集成到规划流水线中，以指导启发式优先搜索 (Heuristics-First Search, HFS)。作者还评估了一个变体 HFS*，它借鉴 A* 算法的思想，将预测的启发式值 $h(s)$ 与搜索深度 $d(s)$ 相结合，形成总分 $f(s) = h(s) + d(s)$ 。

核心贡献

本文提出了四个主要贡献：

嵌入对比： 对用于 GNN 输入的三种 Kripke 结构嵌入（符号 ID、哈希、位掩码）进行了形式化定义和实证比较，确定哈希编码是最高效的权衡方案。
自动化流水线： 一个完全自动化的系统，用于生成专门针对 MEP 设置的训练数据（状态-距离对）并训练 GNN 回归器。
集成： 将 GNN 回归器集成到 deep 规划器中，用于评估 e-states 并指导搜索过程。
全面评估： 在多个标准领域下，通过与无信息搜索 (BFS) 和现有的基于启发式的规划器 (H-EFP) 进行深入基准测试。

实验结果

评估在标准 MEP 基准测试（如协作与通信、选择性通信、Grapevine）上进行，设置了 600 秒的超时时间。

可扩展性 vs. 无信息搜索： 在大多数领域中，GNN 引导的搜索显著减少了展开节点的数量，相比于广度优先搜索 (BFS)。例如，在协作与通信 (CC) 领域，在解决相同数量实例的情况下，GNN 方法平均展开约 65 个节点，而 BFS 则为 610 个。
搜索策略： HFS* 变体（结合了启发式和深度）表现优于标准的 HFS，解决了大约 32% 更多的实例，并减少了展开的节点数。
泛化能力： 在多个领域（CC 和 GR）汇总数据训练的模型展示了泛化到未见领域的潜力，在节点展开方面优于 BFS 基准。
与 H-EFP 的比较： GNN 方法的表现与 H-EFP 规划器中的最佳单个启发式算法（特别是 $S\_PG$ 启发式）相当，在测试实例中的解决率为 85.33%，而 H-EFP 的解决率根据具体使用的启发式算法不同，在 49–82% 之间波动。
运行时限制： 论文指出，虽然 GNN 减少了搜索空间（展开节点），但目前的实现缺乏批处理推理优化（例如 CUDA 批处理）。因此，原始求解时间尚未能与传统启发式算法竞争，但作者认为启发式信息的丰富程度是衡量此类背景下可扩展性的主要指标。

意义与主张

作者将这项工作定位为将机器学习与多智能体认识规划相结合的基础性步骤。他们声称：

启发式算法匮乏： 与经典规划相比，MEP 缺乏有效的启发式算法。这项工作证明了 GNN 可以成功学习如何在如此复杂的基于图的设置中逼近完美启发式算法。
数据驱动的效率： 通过将每个 e-state 视为独立的训练信号而非依赖于完整的轨迹，该方法能够高效地生成大型数据集，从而能够从 Kripke 模型的各种关系结构中学习有意义的模式。
互补性： 作者并不声称 GNN 会立即取代现有启发式算法。相反，他们认为 GNN 启发式算法是增强求解器覆盖范围的强大互补工具，特别是在集成到组合式方法中时，不同的启发式算法可以相互补偿各自的弱点。

论文总结道，尽管需要工程优化（如批处理）才能使运行时性能具有竞争力，但减少搜索空间复杂度的结果证明了学习型启发式算法在扩展 MEP 方面的可行性。