Domain-Independent Structured Duplicate Detection

Abstract

The scalability of graph-search algorithms can be greatly extended by using external memory, such as disk, to store generated nodes. We consider structured duplicate detec-tion, an approach to external-memory graph search that limits the number of slow disk I/O operations needed to access search nodes stored on disk by using an abstract represen-tation of the graph to localize memory references. For graphs with sufficient locality, structured duplicate detection outper-forms other approaches to external-memory graph search. We develop an automatic method for creating an abstract repre-sentation that reveals the local structure of a graph. We then integrate this approach into a domain-independent STRIPS planner and show that it dramatically improves scalability for a wide range of planning problems. The success of this ap-proach strongly suggests that similar local structure can be found in many other graph-search problems.