Representing Pattern Databases with Succinct Data Structures

Authors

  • Tim Schmidt Palo Alto Research Center, Inc.
  • Rong Zhou Palo Alto Research Center, Inc.

DOI:

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

Keywords:

memoization, heuristic search, pattern databases, state set representation

Abstract

In this paper we describe novel representations for precomputed heuristics based on Level-Ordered Edge Sequence (LOES) encodings. We introduce compressed LOES, an extension to LOES that enables more aggressive compression of the state-set representation. We evaluate the novel repre- sentations against the respective perfect-hash and binary decision diagram (BDD) representations of pattern databases in a variety of STRIPS domains.

SoCS 2011 Proceedings Cover

Downloads

Published

2021-08-19

Issue

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

Section

Full Papers