Optimal Search with Inadmissible Heuristics
DOI:
https://doi.org/10.1609/icaps.v22i1.13499Keywords:
heuristic, search, planningAbstract
Considering cost-optimal heuristic search, we introduce the notion of global admissibility of a heuristic, a property weaker than standard admissibility, yet sufficient for guaranteeing solution optimality within forward search. We describe a concrete approach for creating globally admissible heuristics for domain independent planning; it is based on exploiting information gradually gathered by the search via a new form of reasoning about what we call existential optimal-plan landmarks. We evaluate our approach on some state-of-the-art heuristic search tools for cost-optimal planning, and discuss the results of this evaluation.