用大模型生成可保证最优性的启发式函数，提升规划效率。
LLM-Evolved Pattern Generators for Optimal Classical Planning
- 通过大模型演化生成抽象模式，构建可解释的领域专用启发式。
- 在多个领域上达到顶尖无领域启发式覆盖率，状态评估速度更快。
- 适合需要最优解保障的智能规划场景，如机器人路径规划。
学习型启发式近年来已成为满足性规划中传统无领域启发式的一种有力替代方案。然而，现有方法主要关注提升搜索引导能力，而非保证可接纳性，因此不适用于最优经典规划。本文提出首个通过设计确保可接纳性的领域依赖启发式学习方法，从而保持A*搜索的最优性保证。不同于直接从状态映射到启发值，我们学习构造能诱导出可接纳启发式的抽象。采用大模型驱动的进化程序合成框架，为每个领域生成一个程序，该程序可为该领域任意任务生成模式集合，并通过饱和代价划分方式可接纳地组合这些模式。实验表明，所学程序编码了可解释的领域特定洞察，在测试时开销极小，且在多个领域上实现了与最先进无领域基线相当的覆盖范围，同时显著加快了每个状态的评估速度。
原文摘要 · Abstract (English)
Learned heuristics have recently become a competitive alternative to traditional domain-independent heuristics for satisficing planning. Existing approaches, however, focus on improving search guidance rather than guaranteeing admissibility, which makes them unsuitable for optimal classical planning. We present the first method for learning domain-dependent heuristics that are admissible by design and thus preserve the optimality guarantees of A* search. Instead of learning a direct mapping from states to heuristic values, we learn to construct abstractions that induce admissible heuristics. We use an LLM-driven evolutionary program-synthesis framework to obtain, for each domain, a program that produces a pattern collection for any task in that domain, and we combine the resulting patterns admissibly via saturated cost partitioning. Empirically, the learned programs encode interpretable domain-specific insights, run with negligible overhead at test time and yield heuristics that match the coverage of state-of-the-art domain-independent baselines on several domains while evaluating each state substantially faster.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。