Paper  abstract   bibtex   2 downloads  

@inproceedings {icaps16-126,
    track    = {​Main Track},
    title    = {Efficient Representation of Pattern Databases Using Acyclic Random Hypergraphs},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13093},
    author   = {Mehdi Sadeqi and  Howard Hamilton},
    abstract = {A popular way for creating domain-independent heuristic functions is by using abstraction, an abstract (coarse) version of the state space. Abstraction-based heuristic is usually implemented using a pattern database, a lookup table of (abstract state, heuristic value) pairs. Efficient representation and compression of pattern databases has been the topic of substantial amount of ongoing research. In this paper, we present a novel domain-independent algorithm for this purpose using acyclic $r$-partite random hypergraphs. The theoretical and experimental results show that our proposed algorithm provides a consistent representation that works well across many planning problem domains and provides a very good trade-off for space usage and lookup time. This makes it suitable as a standard efficient representation for pattern databases and a benchmark method for other pattern database representation/compression methods.},
    keywords = {Search techniques}
}