AAAI Publications, Twenty-Second International Conference on Automated Planning and Scheduling

Font Size: 
Optimal Search with Inadmissible Heuristics
Erez Karpas, Carmel Domshlak

Last modified: 2012-05-14


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.



Full Text: PDF