Optimal Search with Inadmissible Heuristics

Authors

  • Erez Karpas Technion - Israel Institute of Technology
  • Carmel Domshlak Technion - Israel Institute of Technology

DOI:

https://doi.org/10.1609/icaps.v22i1.13499

Keywords:

heuristic, search, planning

Abstract

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.

Downloads

Published

2012-05-14

How to Cite

Karpas, E., & Domshlak, C. (2012). Optimal Search with Inadmissible Heuristics. Proceedings of the International Conference on Automated Planning and Scheduling, 22(1), 92-100. https://doi.org/10.1609/icaps.v22i1.13499