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.
This project has primarily addressed computer algorithms for planning problems: what is the best sequence of actions to achieve a desired outcome? It is widely understood that finding optimal plans is intractable for many practical problems. This project has provided the basic research for a new generation of suboptimal planning methods - methods that can quickly find useful plans, but that do so in a way that still provides guarantees that plan cost is close to optimal. The central insight of the project is to focus on the information that is available to the planning algorithm - either provided by the user or acquired by the algorithm itself during the solving process. The project has shown that it can be as important for the solving process to estimate plan length as to estimate plan cost. It has also shown that modifying algorithms that were designed for optimal search is not nearly as effective as designing a new class of algorithms specifically for suboptimal search. Luckily, the suboptimal search framework developed in this project has turned out to be easily adaptable to many different suboptimal search settings. The project has also trained a large cohort of graduate and undergraduate students at the University of New Hampshire, the state's only public research university. Many of these students have graduated and are directly contributing to the high technology economy of the region and country.
