Understanding the Role of Exploration in Search and Planning

点击翻译按钮获取中文摘要

1. Background********As a researcher in Computing Science, my goal is to make progress towards solving ever more complex real-world problems. Intelligent automated decision-making requires modelling an application domain, and processing a potentially huge space of possible future alternatives, sometimes offline but more and more often in a real-time setting. With my research group I study efficient search algorithms for solving hard problems. Powerful solution techniques include abstraction, divide and conquer strategies, and many types of systematic and heuristic search. While my research agenda involves work on many aspects of these approaches, the current proposal focuses on the topic of exploration in heuristic search, which has emerged as the common theme that drives much of my recent work.******For a computer program, exploration is a way of getting experience about its (simulated or real) environment. Such exploration can be used to correct errors, gaps and uncertainty in a model of the world. Examples include board games, where exploration of possible future move sequences can find winning strategies, and automated planning, where exploration can be used to discover promising action sequences.******2. Objectives of the Proposed Research Program********My main objective is to better understand the issues of using exploration in heuristic search. Exploration techniques are vital ingredients of a large and growing number of search algorithms. Monte Carlo sampling methods have been extremely successful in applications including game-playing and probabilistic planning. Yet despite all these successes, many important questions remain about when, how, and why exploration methods work.******3. Summary of Scientific Approach*******To study exploration methods in heuristic search, I plan to continue working on concrete applications which pose significant research challenges, such as the game of Go, domain-independent planning and motion planning. With my students and colleagues, I want to continue building complete high performance systems, and test them on standard benchmarks as well as in competitions.*******This work will require many angles of attack, from in-depth analysis of successful deployed systems to synthesizing the experience from different exploration-based algorithms, and leading towards generic frameworks and adaptive models for controlling exploration. A deeper understanding of exploration-based methods will likely lead to algorithmic improvements or even brand-new algorithms. It should also lead to significantly improved computer programs, which can find better solutions to difficult heuristic search problems, can scale to larger problems, and are fast enough for real-time use.**