Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Alberta

$70,000.00

Exploration and Learning in Heuristic Search

FY 2024-25

Summary
Research in Computing Science progresses towards the goal of solving ever more complex, difficult real-world problems. Intelligent automated decision-making requires modelling an application domain, and processing a potentially huge space of possible future alternatives. With my research group and my colleagues I study efficient search algorithms for solving hard decision-making problems. The current proposal focuses on two topics: the question of efficient exploration in large search spaces, and the use of machine learning methods. These topics have emerged as big common themes that drive much of my group's recent work in a diverse set of application areas. My research area has radically changed over the last five years. Systems that combine deep reinforcement learning with Monte Carlo Tree Search have achieved super-human performance in complex games such as Go, chess and shogi. DeepMind's Alpha Zero system has learned to play such games from scratch, without any human input regarding playing strategy. A beautiful aspect of these systems is the way in which they combine learning and search. They create a virtuous cycle where machine learning improves the search process, and the search also improves the learning. Despite the impressive successes of these algorithms, a number of problems of both practical and fundamental nature currently limits their more widespread use. A major practical problem is posed by the massive resources required to train the large and deep neural networks which encode the learned knowledge. More fundamental questions include: how to control the search process? And how to generalize such approaches when we don't have a perfect and efficient model of a problem? In future work with my students and colleagues, I want to study the following topics in depth: 1. Continue the study of exploration in heuristic search 2. Extend our methods to problems beyond games, which are less well specified 3. Study learning and search in cases where we know the "true result" due to their special mathematical structure To study these research questions, I plan to continue working on concrete applications which pose significant challenges. I want to continue building complete high performance systems, and test them on standard benchmarks as well as in competitions. A deeper understanding of these methods will likely lead to further significantly improved decision-making systems, which can search and learn better and faster, and can be used for less well-defined problems.
Program
Discovery Grants Program - Individual
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2020-04048
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
2024
Competition year année de concours
2020
Award amount
70000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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)
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Exploration and Learning in Heuristic Search
Keywords
heuristic search; game tree search; reinforcement learning; monte carlo tree search; exploration; domain-independent planning
Application summary
Research in Computing Science progresses towards the goal of solving ever more complex, difficult real-world problems. Intelligent automated decision-making requires modelling an application domain, and processing a potentially huge space of possible future alternatives. With my research group and my colleagues I study efficient search algorithms for solving hard decision-making problems. The current proposal focuses on two topics: the question of efficient exploration in large search spaces, and the use of machine learning methods. These topics have emerged as big common themes that drive much of my group's recent work in a diverse set of application areas. My research area has radically changed over the last five years. Systems that combine deep reinforcement learning with Monte Carlo Tree Search have achieved super-human performance in complex games such as Go, chess and shogi. DeepMind's Alpha Zero system has learned to play such games from scratch, without any human input regarding playing strategy. A beautiful aspect of these systems is the way in which they combine learning and search. They create a virtuous cycle where machine learning improves the search process, and the search also improves the learning. Despite the impressive successes of these algorithms, a number of problems of both practical and fundamental nature currently limits their more widespread use. A major practical problem is posed by the massive resources required to train the large and deep neural networks which encode the learned knowledge. More fundamental questions include: how to control the search process? And how to generalize such approaches when we don't have a perfect and efficient model of a problem? In future work with my students and colleagues, I want to study the following topics in depth: 1. Continue the study of exploration in heuristic search 2. Extend our methods to problems beyond games, which are less well specified 3. Study learning and search in cases where we know the "true result" due to their special mathematical structure To study these research questions, I plan to continue working on concrete applications which pose significant challenges. I want to continue building complete high performance systems, and test them on standard benchmarks as well as in competitions. A deeper understanding of these methods will likely lead to further significantly improved decision-making systems, which can search and learn better and faster, and can be used for less well-defined problems.