Realtime, Parallel Heuristic Search

实时、并行启发式搜索

• 批准号: 8801939
• 负责人: Richard Korf
• 金额: $ 12.29万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-07-01 至 1990-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8801939&HistoricalAwards=false
• 关键词: 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.

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