Grant: Discovery Grants Program - Individual
University of Alberta
$82,000.00
Real-time Heuristic Search for Cooperative and Explainable Autonomous Agents
EF 2023-24
Résumé
Real-time heuristic search (RTHS) allows Artificial Intelligence (AI) agents to make decisions in real time, with incomplete information. Since 2003 my research group has produced a series of state-of-the-art RTHS algorithms. We accomplished that by introducing several key ideas to the field. However, even contemporary heuristic search methods still face several challenges. First, RTHS algorithms and their parameters are typically manually designed/optimized for each type of search problem. Thus applying RTHS techniques to a new search problem usually requires an RTHS expert, restricting applicability of RTHS. Second, while our recent work showed that RTHS algorithms can sometimes be automatically formed from a set of building blocks, the blocks themselves are manually engineered limiting their variety and injecting human bias. Third, an RTHS agent typically learns only from its own individual experience. Fourth, an agent's reasoning can be difficult to express in a compact human-comprehensible way. This is detrimental for AI agents embedded in human society where the ability to explain one's actions is key to trust and collaboration. My research program will address these shortcomings as follows. We will start by extending our recent work on automated search in the space of RTHS algorithms as well as automated per-problem algorithm selection. We recently used deep learning techniques to map a description of a search problem to the most suitable RTHS algorithm, obtaining promising results. Thus, the short-term objective of this research program is to further investigate cross-domain portability of such mapping and its applicability to broader algorithm spaces. We will address the second shortcoming by adding deep neural networks as a new building block to be incorporated into RTHS. We will evolve the networks in a simulated neuroevolution where survival is linked to search performance. Depending on the evolution setting, RTHS agents may replace some/all of their traditional parts (e.g., lookahead search) with evolved deep networks. As RTHS agents form a population, the ability to communicate and explain their reasoning/knowledge to each other will be an evolutionary adaptation as it would allow them to share learned knowledge among themselves, complementing each agent's individual learning experience. Furthermore, by situating the simulation in a video-game-like environment, we will involve humans in the evolution process and set up a survival structure to encourage RTHS agents to explain their actions to humans as well. Thus, high-performing RTHS agents will not only search well but also be able to explain their search strategy to humans. Finally, we will develop machine-learned detectors to recognize emergence of novel RTHS algorithms automatically. Benefits of this research program include new high performance autonomous agents that can learn collectively and explain their reasoning to humans.
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-2019-06132
Name nom
Bulitko, Vadim
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
2023
Competition year année de concours
2019
Award amount
82000
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
2803
Research subject group en
Artificial intelligence
Research subject group fr
Knowledge representation
Research subject en
Intelligence artificielle
Research subject fr
Répresentation des connaissances
Application title
Real-time Heuristic Search for Cooperative and Explainable Autonomous Agents
Keyword
agent-centered search; artificial life; autonomous agents; deep learning; machine learning; real-time heuristic search
Application summary
Real-time heuristic search (RTHS) allows Artificial Intelligence (AI) agents to make decisions in real time, with incomplete information. Since 2003 my research group has produced a series of state-of-the-art RTHS algorithms. We accomplished that by introducing several key ideas to the field. However, even contemporary heuristic search methods still face several challenges. First, RTHS algorithms and their parameters are typically manually designed/optimized for each type of search problem. Thus applying RTHS techniques to a new search problem usually requires an RTHS expert, restricting applicability of RTHS. Second, while our recent work showed that RTHS algorithms can sometimes be automatically formed from a set of building blocks, the blocks themselves are manually engineered limiting their variety and injecting human bias. Third, an RTHS agent typically learns only from its own individual experience. Fourth, an agent's reasoning can be difficult to express in a compact human-comprehensible way. This is detrimental for AI agents embedded in human society where the ability to explain one's actions is key to trust and collaboration. My research program will address these shortcomings as follows. We will start by extending our recent work on automated search in the space of RTHS algorithms as well as automated per-problem algorithm selection. We recently used deep learning techniques to map a description of a search problem to the most suitable RTHS algorithm, obtaining promising results. Thus, the short-term objective of this research program is to further investigate cross-domain portability of such mapping and its applicability to broader algorithm spaces. We will address the second shortcoming by adding deep neural networks as a new building block to be incorporated into RTHS. We will evolve the networks in a simulated neuroevolution where survival is linked to search performance. Depending on the evolution setting, RTHS agents may replace some/all of their traditional parts (e.g., lookahead search) with evolved deep networks. As RTHS agents form a population, the ability to communicate and explain their reasoning/knowledge to each other will be an evolutionary adaptation as it would allow them to share learned knowledge among themselves, complementing each agent's individual learning experience. Furthermore, by situating the simulation in a video-game-like environment, we will involve humans in the evolution process and set up a survival structure to encourage RTHS agents to explain their actions to humans as well. Thus, high-performing RTHS agents will not only search well but also be able to explain their search strategy to humans. Finally, we will develop machine-learned detectors to recognize emergence of novel RTHS algorithms automatically. Benefits of this research program include new high performance autonomous agents that can learn collectively and explain their reasoning to humans.