Proceedings of the International Symposium on Combinatorial Search · 2010 · 26 citations · 9 references
ComputingComputer ScienceAlgorithmsGeographic Information SystemsPath PlanningHeuristic OptimizationHeuristic SearchSearching AlgorithmsShortest Path AlgorithmsAdmissible HeuristicsHeuristicsShortest Path HeuristicsShortest Path MapsState Space Search
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.
9
Predicting Internet network distance with coordinates-based approaches
T. S. Eugene Ng, Hui Zhang · 2003 · 1.1K citations
Computing the shortest path: A search meets graph theory
Andrew V. Goldberg, Chris Harrelson · 2005 · 728 citations
Near Optimal Hierarchical Path-Finding.
Adi Botea, Martin Müller, Jonathan Schaeffer · 2004 · 327 citations
Memory-based heuristics for explicit state spaces
Nathan Sturtevant, Ariel Felner, Max Barrer et al. · 2009 · 91 citations