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

本项目将开发一种基于结构化重复检测的扩展状态空间启发式搜索的新方法，该方法利用图的局部性和结构来提高重复检测的效率。结构化重复检测提供了一个基础(一)外部内存图搜索的新方法,将搜索空间的内存层次结构,例如,只有一小部分already-explored节点需要存储在RAM中随时为了执行重复检测,(b)的并行图搜索的新方法的抽象表示状态空间保存图形位置用于分区存储节点之间的处理器,(c)通过将部分模式数据库存储在磁盘上并将其分布在多个处理器上，从而创建和学习更大、更准确的模式数据库启发式方法。本项目中开发的搜索算法将在两个具有实际重要性的具有挑战性的应用中进行测试：领域独立规划和显式状态模型检查。但是，由于状态空间图搜索在人工智能和计算机科学的其他分支中是一种普遍的技术，因此在该项目下开发的新技术有可能使许多应用领域受益，包括生物信息学和计算群论。最后，这个研究项目将人工智能和高性能计算相结合，为培养这两个领域的学生提供了一个很好的机会。

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.