The Compressed Differential Heuristic

Authors

  • Meir Goldenberg Ben-Gurion University
  • Nathan Sturtevant University of Denver
  • Ariel Felner Ben-Gurion University
  • Jonathan Schaeffer University of Alberta

DOI:

https://doi.org/10.1609/socs.v2i1.18213

Keywords:

Search, path finding, memory based, compression

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) can be tuned to fit any size of memory, even smaller than the size of the state space.Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompress

SoCS 2011 Proceedings Cover

Downloads

Published

2021-08-19

How to Cite

Goldenberg, M., Sturtevant, N., Felner, A., & Schaeffer, J. (2021). The Compressed Differential Heuristic. Proceedings of the International Symposium on Combinatorial Search, 2(1), 191–192. https://doi.org/10.1609/socs.v2i1.18213

Issue

Vol. 2 No. 1 (2011): Fourth Annual Symposium on Combinatorial Search

Section

Short Papers