This project will develop a new approach to scaling up state-space heuristic search based on structured duplicate detection, which leverages graph locality and structure to improve the effciency of duplicate detection. Structured duplicate detection provides a foundation for (a) a new approach to external-memory graph search which aligns the memory hierarchy with the search space, so that for example, only a small fraction of already-explored nodes need to be stored in RAM at any time in order to perform duplicate detection, (b) a new approach to parallel graph search in which an abstract representation of the state space that preserves graph locality is used to partition stored nodes among processors, and (c) a new approach to creating and learning larger and more accurate pattern database heuristics by storing part of the pattern databases on disk and distributing them among multiple processors.
The search algorithms developed in this project will be tested on two challenging applications of practical importance: domain-independent planning and explicit-state model checking. But because state-space graph search is a pervasive technique in AI and other branches of computer science, the new techniques developed under this project have the potential to benefit many applications areas, including bioinformatics and computational group theory. Finally, this research project integrates AI and high-performance computing, thus providing an excellent opportunity to train students in both areas.
Graph-search algorithms play a key role in solving many real-world optimization problems, but their scalability is limited by time and especially memory complexity. In this project, new techniques for external-memory and parallel graph search were developed that leverage problem structure to significantly improve the efficiency and scalability of graph-search algorithms. The effectiveness of these techniques was successfully demonstrated in several applications, including model checking, domain-independent planning, inference in Bayesian networks, and speech recognition. The techniques developed in this project improve the scalability of external-memory and parallel graph-search algorithms by leveraging various forms of graph structure to achieve locality of reference. The layered structure of a breadth-first graph provides the simplest form of graph structure. More complex forms of graph structure are identified by an approach that partitions the nodes of a graph into subsets such that all the successors of nodes in one subset are contained in a very small number of other subsets – an approach called structured duplicate detection. In this project, algorithms were developed that automatically construct a partition function that captures graph structure that can improve the efficiency of external-memory and parallel search. The improved scalability that results from this approach allowed development of the state-of-the art algorithm for optimal domain-independent planning and the state-of-the-art algorithm for learning the optimal structure of a Bayesian network. It also led to implementation of an external-memory model checking algorithm and the parallelization of the decoder of a speech-recognition system. The project partially supported the research of two PhD students and four MS students, and the contributions are described in thirteen published conference papers. Two participants in the project are presently working in industry positions where they are applying some of the techniques developed in this project.
