通过成本分配学习可接纳启发式函数

背景

在最优规划（Optimal Planning）领域，可接纳启发式函数（Admissible Heuristics）扮演着至关重要的角色。可接纳性意味着启发式函数给出的估计代价永远不会超过从当前状态到目标状态的实际最小代价。这一性质保证了基于 A* 等算法的规划器能够找到全局最优解。

然而，学习高质量的启发式函数一直是一个极具挑战性的问题。传统的机器学习方法在尝试预测启发式值时，往往面临“高估”的风险。一旦启发式函数高估了实际代价，算法将失去可接纳性，进而无法保证解的最优性。

为了解决多启发式函数的组合问题，成本分配（Cost Partitioning） 技术被广泛采用。它通过将动作的代价分配给不同的抽象启发式函数（Abstraction Heuristics），从而在保持整体可接纳性的前提下，利用多个启发式的优势。尽管成本分配在理论上很完美，但在在线规划过程中计算最优的成本分配方案计算开销巨大，难以实时应用。

核心内容

本文提出了一种全新的框架，旨在通过机器学习自动推断可接纳的成本分配方案。该研究的核心创新在于建立了成本分配与乘数预测（Multiplier Prediction）之间的拉格朗日对偶等价关系（Lagrangian dual equivalence），并利用深度学习来学习这一过程。

1. 状态编码与特征提取

为了将规划问题输入到神经网络中，作者首先将规划状态和模式（Patterns）编码为带标签的图（Labelled Graphs）。随后，采用一种以动作为中心的 Weisfeiler-Leman (WL) 算法变体来提取图的结构特征向量。WL 算法是图同构测试中的经典算法，以其强大的结构表达能力著称，能够有效地捕捉状态空间的拓扑特征。

2. 深度架构设计

提取出的结构特征向量被输入到一个深度神经网络中。该网络架构包含两个关键组件：

• 轴向自注意力机制（Axial Self-attention）：用于处理高维特征空间中的长距离依赖关系，增强模型对复杂状态结构的理解能力。
• Softmax 输出层：这是确保可接纳性的关键设计。网络输出的不是直接的启发式值，而是满足成本分配约束的成本权重。由于 Softmax 函数的性质，其输出天然满足非负且总和为 1 的约束，从而在构造上保证了成本分配的可接纳性。

3. 方法论优势

通过这种设计，模型不再直接预测可能高估的启发式值，而是预测一组合法的权重，这些权重将多个抽象启发式的代价进行加权组合。这种方法从根本上规避了传统监督学习中常见的过估计问题，确保了最终生成的启发式函数严格满足可接纳性条件。

关键要点

• 首创性保证：据作者所知，这是首个被证明具有严格可接纳性的机器学习启发式函数。
• 理论基础：利用成本分配与乘数预测之间的拉格朗日对偶等价关系，将组合优化问题转化为可学习的参数预测问题。
• 图神经网络应用：采用以动作为中心的 Weisfeiler-Leman 算法变体，将规划状态编码为图结构并提取特征，有效捕捉了状态间的结构相似性。
• 架构创新：结合轴向自注意力机制与 Softmax 输出层，既提升了特征提取的深度，又通过输出层的数学性质从结构上强制保证了成本分配的合法性（即非负且归一化）。
• 实验效果：与次优分配基线相比，该方法显著减少了搜索过程中的节点扩展数量（Node Expansions），同时严格维持了可接纳性，证明了其在提升搜索效率方面的有效性。

意义与影响

这项研究在自动规划与人工智能领域具有重要的理论和实践意义。

首先，它解决了机器学习应用于最优规划时的一个核心痛点：如何在利用数据驱动模型强大泛化能力的同时，严格保持数学上的可接纳性约束。 以往的研究往往需要在“性能”和“最优性保证”之间做妥协，而本文提出的框架通过架构设计实现了两者的统一。

其次，该方法为高效求解复杂规划问题提供了新的思路。通过自动学习成本分配权重，避免了在线计算最优分配的高昂开销，使得基于抽象启发式的搜索算法在实际应用中更加可行和高效。

最后，这一工作拓展了图神经网络在组合优化问题中的应用边界，展示了 WL 算法变体与自注意力机制结合在处理结构化规划状态时的潜力，为后续研究如何通过深度学习解决其他带有严格约束的优化问题提供了借鉴。