AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Memory-Based Heuristics for Explicit State Spaces
Nathan R. Sturtevant, Ariel Felner, Max Barrer, Jonathan Schaeffer, Neil Burch

Last modified: 2009-06-25


In many scenarios, quickly solving a relatively small search problem with an arbitrary start and arbitrary goal state is important (e.g., GPS navigation). In order to speed this process, we introduce a new class of memory-based heuristics, called true distance heuristics, that store true distances between some pairs of states in the original state space can be used for a heuristic between any pair of states. We provide a number of techniques for using and improving true distance heuristics such that most of the benefits of the all-pairs shortest-path computation can be gained with less than 1% of the memory. Experimental results on a number of domains show a 6-14 fold improvement in search speed compared to traditional heuristics.


heuristic; distance; pathfinding; pdb; puzzle

Full Text: PDF