Realtime, Parallel Heuristic Search

点击翻译按钮获取中文摘要

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.