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.