A Formalism for Optimal Search with Dynamic Heuristics (Extended Version)
Remo Christen, Florian Pommerening, Clemens Büchner, Malte Helmert · 2025
Read A Formalism for Optimal Search with Dynamic Heuristics (Extended Version) by Remo Christen, Florian Pommerening, Clemens Büchner, Malte Helmert (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-21131.txt.
Description
Remo Christen and co-authors formalize optimal search with heuristics that change as the search proceeds, published in 2025. Most search heuristics depend only on the current state, but some gather information during the search and so depend on its history too. Existing methods use such dynamic heuristics inside A-star-like algorithms and cite classic results for their optimality.
That appeal skips the complications of a mutable heuristic, the authors argue. They define dynamic heuristics precisely and place them in a generic algorithm framework. For the A-star-like instantiation, they prove general optimality results. Several existing approaches from classical planning then appear as special cases, so the new results apply to them directly. The paper is an extended version, giving the full formalism and proofs.
Catalog record
| CREATOR | Remo Christen, Florian Pommerening, Clemens Büchner, Malte Helmert |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-21131