RI-Small: Combinatorial Search Algorithms as Rational Agents

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

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.