RI-Small: Structured Duplicate Detection: A New Approach to External-Memory and Parallel Graph Search

点击翻译按钮获取中文摘要

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.