The compression power of symbolic pattern databases

The heuristics used for planning and search often take the form of pattern databases generated from abstracted versions of the given state space. Pattern databases are typically stored space, which limits the size of the abstract state space and therefore the quality of the heuristic that can be used with a given amount of memory. In the AIPS-2002 conference Ste-fan Edelkamp introduced an alternative representation, called symbolic pattern databases, which, for the Blocks World, re-quired two orders of magnitude less memory than a lookup table to store a pattern database. This paper presents experi-mental evidence that Edelkamp’s result is not restricted to a single domain. Symbolic pattern databases, in the form of Al-gebraic Decision Diagrams, are one or more orders of magni-tude smaller than lookup tables on a wide variety of problem domains and abstractions