Proceedings:
Book One
Volume
Issue:
Proceedings of the International Conference on Automated Planning and Scheduling, 26
Track:
Main Track
Downloads:
Abstract:
A popular way to create domain-independent heuristic functions is by using abstraction, where an abstract (coarse) version of the state space is derived from the original state space. An 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 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 planning problem domains and provides a good trade-off between space usage and lookup time. Thus, it is suitable to be a standard efficient representation for pattern databases and a benchmark method for other pattern database representation/compression methods.
DOI:
10.1609/icaps.v26i1.13752
ICAPS
Proceedings of the International Conference on Automated Planning and Scheduling, 26