Ben-Gurion University

True distance memory-based heuristics (TDHs) were recently introduced as a way to obtain admissible heuristics for ex-plicit 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 be-tween all pairs of portals are stored and used to obtain admis-sible 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 per-formance improvements over previously-reported TDHs for commonly used classes of maps.