Portal-Based True-Distance Heuristics for Path Finding

Authors

  • Meir Goldenberg Ben-Gurion University
  • Ariel Felner Ben-Gurion University
  • Nathan Sturtevant University of Alberta
  • Jonathan Schaeffer University of Alberta

DOI:

https://doi.org/10.1609/socs.v1i1.18169

Abstract

True distance memory-based heuristics (TDHs) were recently introduced as a way to obtain admissible heuristics for explicit state spaces. In this paper, we introduce a new TDH, the portal-based heuristic. The domain is partitioned into regions and portals between regions are identified. True distances between all pairs of portals are stored and used to obtain admissible heuristics throughout the search. We introduce an A*-based algorithm that takes advantage of the special properties of the new heuristic. We study the advantages and limitations of the new heuristic. Our experimental results show large performance improvements over previously-reported TDHs for commonly used classes of maps.

Downloads

Published

2010-08-25