Realtime, Parallel Heuristic Search

启发式搜索是人工智能中的一种基本问题求解方法。然而，目前的算法，如A*和IDA*，由于它们专注于寻找最优解，不能扩展到大问题。去除最优性约束应该允许开发启发式搜索算法，可以有效地解决任意大的问题。原因是启发式评估函数捕获了问题解决方案的长期战略组成部分，而启发式估计和实际成本之间的差异主要是一种短期或战术现象。因此，具有足够宽的搜索范围的算法应该能够处理启发式函数中的误差。提出了一种双管齐下的方法来解决这个问题。首先是实时搜索算法的发展，这种算法可以在恒定的时间内运行，并且可以基于有限的信息或计算来执行操作。第二是并行搜索算法的发展，试图显著扩展这种算法可以实现的搜索范围。并行树搜索算法应该推广到任意的树递归程序，例如那些由分治算法生成的程序。

Heuristic search is a fundamental problem solving method in artificial intelligence. Current algorithm such as A* and IDA*, however, do not scale up to large problems, due to their focus on finding optimal solutions. Removing the optimality constraint should allow the development of heuristic search algorithms that can effectively solve arbitrarily large problems. The reason is that heuristic evaluation functions capture the long-range strategic component of problem solutions, while the discrepancy between heuristic estimates and actual costs is primarily a short-range or tactical phenomenon. Thus, an algorithm with a sufficiently wide search horizon should be able to cope with error in the heuristic function. A two-pronged attach on this problem is proposed. The first is the development of real-time search algorithms that run in constant time and can commit to actions based on limited information or computation. The second is the development of parallel search algorithms in an attempt to significantly extend the search horizons achievable by such algorithms. Parallel tree-search algorithms should generalize to arbitrary tree- recursive programs, such as those generated by divide-and-conquer algorithms.