Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Alberta

$24,000.00

Synthesizing Programmatic Knowledge with Heuristic Search

EF 2022-23

Résumé
We have recently witnessed tremendous achievements of machine learning systems in decision-making problems. Artificial intelligence (AI) algorithms achieved superhuman performance on Go, Chess, and Shogi, and strong performance in StarCraft. While these systems are able to solve complex problems, the generated solution is encoded in black-box models (e.g., neural networks), which result in solutions that are hard to interpret. Lack of interpretability hinders the application of these systems in domains where trust and reliability are important, as it can be hard to predict how such systems will act in production. Instead of encoding solutions to decision-making problems in black-box models, in this research program we will develop algorithms for encoding solutions in human-readable computer programs, as the latter are more amenable to interpretation, verification, and were shown to generalize better to problems not seen during training. The challenge here is that one needs to solve hard combinatorial search problems to be able to encode strong solutions to complex decision-making problems in human-readable programs. We refer to programs encoding solutions to decision-making problems as programmatic knowledge. Our long-term objective is to develop algorithms for solving the combinatorial search problems that arise in the synthesis of programmatic knowledge as a means of attaining interpretable and robust intelligent systems. We seek to advance the state-of-the-art of systems for synthesizing programmatic knowledge to eventually allow for the replacement of existing black-box models with interpretable ones of similar strength. In the next five years we will focus the following objectives, which will contribute to the synthesis of stronger programmatic knowledge: develop algorithms that search for program space representations (Aim A); develop action abstractions for speeding up the synthesis process (Aim B); develop evaluation functions for guiding search algorithms for synthesizing programmatic knowledge (Aim C). In this research program we will reduce the gap between non-interpretable and interpretable machine-generated knowledge through the development of novel heuristic search algorithms. The results of this research program will contribute to the development of systems able to collaborate effectively with us. For example, we will be able to find flaws in programs written by game-AI programmers by synthesizing a program that defeats the program written by the programmer. Our synthesized programs could be used to instruct the programmer of the weaknesses of their implementation. We are starting to work with local games companies and our goal is to eventually have the technology developed in this project deployed in commercial products.
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-2021-02886
Name nom
Santana de Lelis, Levi
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
2022
Competition year année de concours
2021
Award amount
24000
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)
Installment
inst:2
Partie
1
Nb partie
5
Application title
Synthesizing Programmatic Knowledge with Heuristic Search
Application summary
We have recently witnessed tremendous achievements of machine learning systems in decision-making problems. Artificial intelligence (AI) algorithms achieved superhuman performance on Go, Chess, and Shogi, and strong performance in StarCraft. While these systems are able to solve complex problems, the generated solution is encoded in black-box models (e.g., neural networks), which result in solutions that are hard to interpret. Lack of interpretability hinders the application of these systems in domains where trust and reliability are important, as it can be hard to predict how such systems will act in production. Instead of encoding solutions to decision-making problems in black-box models, in this research program we will develop algorithms for encoding solutions in human-readable computer programs, as the latter are more amenable to interpretation, verification, and were shown to generalize better to problems not seen during training. The challenge here is that one needs to solve hard combinatorial search problems to be able to encode strong solutions to complex decision-making problems in human-readable programs. We refer to programs encoding solutions to decision-making problems as programmatic knowledge. Our long-term objective is to develop algorithms for solving the combinatorial search problems that arise in the synthesis of programmatic knowledge as a means of attaining interpretable and robust intelligent systems. We seek to advance the state-of-the-art of systems for synthesizing programmatic knowledge to eventually allow for the replacement of existing black-box models with interpretable ones of similar strength. In the next five years we will focus the following objectives, which will contribute to the synthesis of stronger programmatic knowledge: develop algorithms that search for program space representations (Aim A); develop action abstractions for speeding up the synthesis process (Aim B); develop evaluation functions for guiding search algorithms for synthesizing programmatic knowledge (Aim C). In this research program we will reduce the gap between non-interpretable and interpretable machine-generated knowledge through the development of novel heuristic search algorithms. The results of this research program will contribute to the development of systems able to collaborate effectively with us. For example, we will be able to find flaws in programs written by game-AI programmers by synthesizing a program that defeats the program written by the programmer. Our synthesized programs could be used to instruct the programmer of the weaknesses of their implementation. We are starting to work with local games companies and our goal is to eventually have the technology developed in this project deployed in commercial products.