提出动态启发式搜索的统一形式化框架，证明其最优性。
A Formalism for Optimal Search with Dynamic Heuristics (Extended Version)
- 定义动态启发式：依赖搜索历史的状态评估机制
- 构建通用算法框架并证明其在特定实例下的最优性
- 揭示经典规划方法为该框架的特例，可直接复用理论保证
尽管多数启发式仅依赖当前状态，但某些启发式会随搜索过程积累信息，从而依赖搜索历史。现有方法虽将此类动态启发式用于类似A*的算法，并引用A*的经典最优性结果，却忽略了动态启发式带来的复杂性。本文形式化了动态启发式的概念，并将其纳入通用算法框架。我们研究了一个具体实例，即基于动态启发式的A*算法，给出了通用最优性结论。最后，我们表明经典规划中的若干现有方法可视为该实例的特例，因而可直接应用我们的最优性结果。
原文摘要 · Abstract (English)
While most heuristics studied in heuristic search depend only on the state, some accumulate information during search and thus also depend on the search history. Various existing approaches use such dynamic heuristics in $\mathrm{A}^*$-like algorithms and appeal to classic results for $\mathrm{A}^*$ to show optimality. However, doing so ignores the complexities of searching with a mutable heuristic. In this paper we formalize the idea of dynamic heuristics and use them in a generic algorithm framework. We study a particular instantiation that models $\mathrm{A}^*$ with dynamic heuristics and show general optimality results. Finally we show how existing approaches from classical planning can be viewed as special cases of this instantiation, making it possible to directly apply our optimality results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。