ML Anthology

The Compressed Differential Heuristic

Meir Goldenberg, Nathan R. Sturtevant, Ariel Felner, Jonathan Schaeffer
AAAI 2011 pp. 24-29
doi:10.1609/AAAI.V25I1.7823 /aaai/2011/goldenberg2011aaai-compressed/

Abstract

The differential heuristic (DH) is an effective memory-based heuristic for explicit state spaces. In this paper we aim to improve its performance and memory usage. We introduce a compression method for DHs which stores only a portion of the original uncompressed DH, while preserving enough information to enable efficient search. Compressed DHs (CDH) are flexible and can be tuned to fit any size of memory, even smaller than the size of the state space. Furthermore, CDHs can be built without the need to create and store the entire uncompressed DH. Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompressed DH.

PDF AAAI Semantic Scholar

Cite

Text

Goldenberg et al. "The Compressed Differential Heuristic." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.7823

Markdown

[Goldenberg et al. "The Compressed Differential Heuristic." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/goldenberg2011aaai-compressed/) doi:10.1609/AAAI.V25I1.7823

BibTeX

@inproceedings{goldenberg2011aaai-compressed,
  title     = {{The Compressed Differential Heuristic}},
  author    = {Goldenberg, Meir and Sturtevant, Nathan R. and Felner, Ariel and Schaeffer, Jonathan},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {24-29},
  doi       = {10.1609/AAAI.V25I1.7823},
  url       = {https://mlanthology.org/aaai/2011/goldenberg2011aaai-compressed/}
}