Representing Pattern Databases with Succinct Data Structures

Tim Schmidt; Rong Zhou

AAAI Publications, Fourth Annual Symposium on Combinatorial Search

Tim Schmidt, Rong Zhou

Last modified: 2011-07-05

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.

Keywords

memoization; heuristic search; pattern databases; state set representation

Full Text: PDF