Memory-Based Heuristics for Explicit State Spaces

Sturtevant, Nathan R.; Felner, Ariel; Barer, Max; Schaeffer, Jonathan; Burch, Neil

Memory-Based Heuristics for Explicit State Spaces

Nathan R. Sturtevant, Ariel Felner, Max Barer, Jonathan Schaeffer, Neil Burch

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 609-613.

Abstract

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.Nathan R. Sturtevant, Ariel Felner, Max Barrer, Jonathan Schaeffer, Neil Burch

Nathan R. Sturtevant, Ariel Felner, Max Barer, Jonathan Schaeffer, and Neil Burch. 2009. Memory-Based Heuristics for Explicit State Spaces. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09. IJCAI, 609–613. https://ijcai.org/proceedings/2009/107

@inproceedings{ijcai2009p107,
  title     = {Memory-Based Heuristics for Explicit State Spaces},
  author    = {Sturtevant, Nathan R. and Felner, Ariel and Barer, Max and Schaeffer, Jonathan and Burch, Neil},
  booktitle = {Proceedings of the Twenty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-09}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Hiroaki Kitano},
  pages     = {609--613},
  year      = {2009},
  url       = {https://ijcai.org/proceedings/2009/107},
}

TY  - CPAPER
TI  - Memory-Based Heuristics for Explicit State Spaces
AU  - Sturtevant, Nathan R.
AU  - Felner, Ariel
AU  - Barer, Max
AU  - Schaeffer, Jonathan
AU  - Burch, Neil
T2  - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2009
SP  - 609
EP  - 613
UR  - https://ijcai.org/proceedings/2009/107
ER  -