Memory-based heuristics for explicit state spaces Conference Paper uri icon

abstract

  • Abstract In many scenarios, quickly solving a relatively small search problem with an arbitrary start and arbitrary goal state is important (eg, GPS navigation). In order to speed this process, we introduce a new class of memorybased 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.

publication date

  • January 1, 2009