Optimal Search with Inadmissible Heuristics

Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling

Volume

Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling

Full Technical Papers

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.

10.1609/icaps.v22i1.13499