RI-Small: Combinatorial Search Algorithms as Rational Agents

University Of New Hampshire, Durham NH

Investigators

Abstract

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 focusing attention 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.