EAGER: Large-Scale Bidirectional Search

EAGER：大规模双向搜索

• 批准号: 1551406
• 负责人: Nathan Sturtevant
• 金额: $ 14万
• 依托单位: University of Denver
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1551406&HistoricalAwards=false
• 关键词: EAGER; Large; Scale; Bidirectional; Search

A large variety of real-world problems are combinatorial in nature: doubling the length of the best solution doesn't double the problem difficulty, it makes it exponentially harder. A classic approach to reducing this complexity is to look for solutions in a bidirectional manner - beginning both from the start and the goal and meeting in the middle. In theory this approach can result in an exponential reduction in the time required to find the best solution, because the two searches are each half the length of the full solution. But, in practice, bidirectional methods haven't been able to compete with the best heuristic approaches. Our work, suggests, however, that scaling the difficulty of problems solved will give the advantage back to bidirectional search approaches. The proposed exploratory research could lead to a new wave of applications of search algorithms to tasks ranging from weather prediction to robotics.This project studies how current computational resources can be used to scale the performance of bidirectional search. This includes the full use of parallel computation and external memory, such as solid state drives. Almost all current devices support parallel computation, so high performance algorithms must exploit parallel computation. Solid state drives have different performance characteristics than traditional hard disk drives with lower latency reads, but a limited number of writes before they wear out. Large-scale heuristics, stored in external memory, can also be used to improve the performance of search. But, in external-memory bidirectional search algorithms there is a tension in how internal memory is allocated: Using it to store large heuristics can prune states and improve the quality of the search, but performance is degraded if memory is not used for other tasks like duplicate detection. Taken together, there is significant room for new research on large-scale bidirectional search algorithms. To improve the applicability and performance of large-scale bidirectional search we will (1) design and implement efficient parallel and external memory search algorithms that (2) are designed to maximize the performance and lifetime of external memory resources and (3) efficiently use external-memory resources such as large-scale heuristics to maximize performance.

现实世界中的许多问题本质上都是组合问题：最佳解的长度加倍并不会使问题的难度加倍，而是使问题的难度呈指数级增加。减少这种复杂性的一个经典方法是以双向的方式寻找解决方案-从开始和目标开始，在中间相遇。理论上，这种方法可以导致找到最佳解所需的时间呈指数级减少，因为两次搜索的长度都是完整解的一半。但是，在实践中，双向方法无法与最好的启发式方法竞争。然而，我们的工作表明，解决问题的难度将使双向搜索方法重新获得优势。这项探索性研究可能会引发搜索算法在从天气预报到机器人等任务中的新一轮应用。该项目研究如何利用当前的计算资源来扩展双向搜索的性能。这包括充分利用并行计算和外部存储器，如固态驱动器。目前几乎所有的设备都支持并行计算，因此高性能算法必须采用并行计算。固态硬盘具有与传统硬盘不同的性能特征，具有较低的读取延迟，但在磨损之前写入次数有限。存储在外部存储器中的大规模搜索也可以用于提高搜索性能。但是，在外部存储器双向搜索算法中，内部存储器的分配方式存在紧张关系：使用它来存储大型的搜索可以修剪状态并提高搜索质量，但如果存储器不用于重复检测等其他任务，则性能会下降。总的来说，大规模双向搜索算法的新研究有很大的空间。为了提高大规模双向搜索的适用性和性能，我们将（1）设计和实现高效的并行和外部存储器搜索算法，（2）旨在最大限度地提高外部存储器资源的性能和生命周期，（3）有效地使用外部存储器资源，如大规模并行计算，以最大限度地提高性能。