用机器学习方法自动学习可保证最优的启发式函数。
Learning Admissible Heuristics via Cost Partitioning
- 通过拉格朗日对偶性将代价划分转化为乘子预测，构建可保证可接纳性的学习框架。
- 在多个规划任务上减少节点扩展次数，性能优于非最优基线方法。
- 适合需要严格保证最优解的自动化规划场景，如机器人路径规划。
可接纳启发式对最优规划至关重要，但学习过程面临高估风险。代价划分通过组合多个抽象启发式保持可接纳性，但在线计算最优划分代价高昂。本文提出一种学习框架，利用代价划分与乘子预测之间的拉格朗日对偶等价性，推断可接纳的代价划分。将规划状态和模式编码为带标签图，采用以动作为中心的Weisfeiler-Leman算法提取结构特征向量。一个基于轴向自注意力和softmax输出层的深度架构，将特征映射为满足划分约束的代价权重，从构造上保证可接纳性。实验表明，相比次优划分基线，该方法显著减少节点扩展次数，同时严格维持可接纳性。据我们所知，这是首个被机器学习保证可接纳的启发式方法。
原文摘要 · Abstract (English)
Admissible heuristics are essential for optimal planning, yet learning them remains challenging due to the risk of overestimation. Cost partitioning combines multiple abstraction heuristics while preserving admissibility, but computing optimal partitions online is expensive. We propose a framework that learns to infer admissible cost partitions by leveraging the Lagrangian dual equivalence between cost partitioning and multiplier prediction. Planning states and patterns are encoded as labelled graphs, and an action-centric variant of the Weisfeiler-Leman algorithm extracts structural feature vectors. A deep architecture with axial self-attention and a softmax output layer maps these features to cost weights that satisfy the partition constraints by construction, ensuring admissibility. Experiments demonstrate reduced node expansions compared to suboptimal partitioning baselines while maintaining strict admissibility. To our knowledge, this is the first machine-learned heuristic guaranteed to be admissible.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。