Leveraging graph locality via abstraction

The use of abstraction to speedup problem solving is ubiquitous in AI, especially in the field of heuristic search where abstraction has proven a crucial technique for creating highly accurate memory-based heuristics known as pattern databases (PDBs). While PDBs are intrinsically based on problem abstractions, the converse is not necessarily true, and this suggests that abstraction should play a much bigger role than simply improving the quality of the heuristic. This has inspired the development of a technique called structured duplicate detection, which uses abstraction to reveal as well as leverage the local structure of a search problem. Unlike PDBs, structured duplicate detection considers the neighborhood of an abstract state in the final search, and uses this information to localize memory references in duplicate detection. Using a locality-preserving abstraction function, structure duplicate detection can (i) limit the number of slow disk I/O operations in external-memory graph search, and (ii) reduce the synchronization (or communication) overhead in parallel graph search. The success of structured duplicate detection in areas such as disk-based search, external-memory heuristics, domain-independent STRIPS planning, and parallel graph search speaks for the generality and effectiveness of using abstraction beyond its application to regular pattern databases.

Citation

Zhou, R. Leveraging graph locality via abstraction. 7th International Symposium on Abstraction, Reformulation, and Approximation (SARA 2007).; 2007 July 18-21; Whistler, Ontario, Canada.