A Formalism for Optimal Search with Dynamic Heuristics

Abstract

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. Multiple existing approaches use such dynamic heuristics in A*-like algorithms and appeal to classic results for A* to show that they return optimal solutions. However, doing so disregards the intricacies of searching with a mutable heuristic. We treat dynamic heuristics formally and propose a framework that defines how the information dynamic heuristics rely on can be modified. We use these transformations in a generic search algorithm and an instantiation that models A* with dynamic heuristics, allowing us to provide general conditions for optimality. We show that existing approaches fit our framework and apply our results. Doing so for future applications of dynamic heuristics may simplify formal arguments for optimality.