EAGER: Large-Scale Bidirectional Search

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

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.