RI-Small: Combinatorial Search Algorithms as Rational Agents

RI-Small：作为理性智能体的组合搜索算法

• 批准号: 0812141
• 负责人: Wheeler Ruml
• 金额: $ 44.82万
• 依托单位: University of New Hampshire
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0812141&HistoricalAwards=false
• 关键词: RI; Small; Combinatorial; Search; Algorithms

This project pursues three concurrent activities: 1) analysis of common search spaces and previously proposed search strategies to broadly characterize the relevant regularities that can be exploited during search, 2) development of search algorithms that can efficiently learn, update, and exploit models of those parameters on-line during problem-solving, and 3) comprehensive evaluation of the new algorithms across many common benchmarks in terms of actual CPU time, taking into account their increased overhead. Algorithms will be developed for the two most common types of search problems: 1) shortest-path problems, such as task planning or robot navigation, where the depth of the search tree is not usefully bounded, and 2) bounded-depth problems, such as constraint satisfaction or combinatorial optimization problems, where the number of decision variables is known.The rational search approach yields a form of hybrid metareasoning, in which the problem-solver reasons statistically about which combinatorial reasoning to do next. This combination promises significant gains in robustness and performance over the current paradigm in which search algorithms use the numerical information available to them only in simple ways, such as allowing it to directly dictate expansion order or using it only to prune. Rational search will provide a sound basis for moving beyond search strategies motivated by intuition to algorithms that adapt their behavior in unanticipated ways to suit precisely the problem at hand. By focusingattention on optimal use of information, this project will help the field of heuristic search address the question of problem formulation: what problem-specific heuristic information is most useful to guide search, and how can it best be conveyed to the search algorithm? It will also strengthen the nascent links between machine learning and heuristic search, particularly around the issues of exploration vs exploitation and the value of information. Because they form the engines of most AI systems, improvements in heuristic search algorithms yield social benefits wherever such systems are used. Increasing the robustness and generality of search methods also makes industrial adoption of AI technology easier and faster,widening its applicability.

该项目同时开展三项活动：1）分析公共搜索空间和先前提出的搜索策略，以广泛地表征可以在搜索期间利用的相关参数，2）开发搜索算法，其可以在问题求解期间在线有效地学习、更新和利用那些参数的模型，以及3）根据实际CPU时间在许多公共基准测试中对新算法进行综合评估，考虑到它们增加的开销。将为两种最常见的搜索问题开发算法：1）最短路径问题，如任务规划或机器人导航，其中搜索树的深度没有有效的限制，以及2）有界深度问题，如约束满足或组合优化问题，其中决策变量的数量是已知的。理性搜索方法产生一种形式的混合元推理，其中，问题解决者统计地推理出接下来要做的组合推理。这种组合有望在鲁棒性和性能方面获得显着的收益，在当前的范式中，搜索算法仅以简单的方式使用它们可用的数值信息，例如允许它直接指定扩展顺序或仅使用它来修剪。理性搜索将提供一个良好的基础，让我们超越由直觉驱动的搜索策略，转向以意想不到的方式调整其行为以精确地适应手头问题的算法。通过将注意力集中在信息的最佳使用上，这个项目将帮助启发式搜索领域解决问题的问题：什么样的问题特定的启发式信息是最有用的，以指导搜索，以及如何才能最好地传达给搜索算法？它还将加强机器学习和启发式搜索之间的新生联系，特别是围绕探索与利用以及信息价值的问题。因为它们构成了大多数人工智能系统的引擎，所以启发式搜索算法的改进在任何使用这种系统的地方都会产生社会效益。提高搜索方法的鲁棒性和通用性也使人工智能技术的工业应用更容易，更快，扩大了其适用性。