Leveraging graph locality via abstraction

Abstract

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.