---
title: "Memory-Based Heuristics for Explicit State Spaces"
authors:
  - "Nathan R. Sturtevant"
  - "Ariel Felner"
  - "Max Barer"
  - "Jonathan Schaeffer"
  - "Neil Burch"
doi: ""
url: "https://ijcai.org/proceedings/2009/107"
pdf: "https://ijcai.org/proceedings/2009/0107.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "609-613"
track: ""
keywords:
---

# Memory-Based Heuristics for Explicit State Spaces

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

*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