Grant: Discovery Grants Program - Individual
University of Alberta
$50,000.00
Understanding the Role of Exploration in Search and Planning
EF 2017-18
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Alberta, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2015-04466
Name nom
Müller, Martin
Department département
Computing Science - Computing Science
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2015
Award amount
50000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2800
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Artificial intelligence (computer vision, use2603)
Research subject fr
Intelligence artificielle (vision artificielle, utiliser 2603)
Partie
3
Nb partie
5
Application title
Understanding the Role of Exploration in Search and Planning
Keyword
NSERC
Application summary
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.