Grant: Alliance Grants
University of Toronto
$100,000.00
Problem Solving with Domain-Independent Dynamic Programming: Theory and Practice
FY 2024-25
Summary
Domain-independent dynamic programming (DIDP) is a recently proposed framework for modeling combinatorial optimization problems using dynamic programming and solving them with a general purpose solver. Initial results show strong performance using a heuristic state-based search solver, thus demonstrating the success of problem solving approaches developed in Artificial Intelligence (AI) on problems traditionally studied in Operations Research (OR). This proposal seeks to develop the theory and practice of DIDP-based problem solving by characterizing DIDP from computational and knowledge representation perspectives; by understanding its relationship to the problem solving paradigms embodied in constraint programming, satisfiability, and AI planning; and by developing novel domain-independent heuristics for DIDP through the adaptation and extension of techniques from AI planning, state abstraction in OR, and decision diagram-based optimization.
Program
Alliance Grants
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
597431-2024
Name nom
Beck, Christopher JC
Department département
Mechanical and Industrial Engineering
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
100000
Program id
ALLRP
Program name en
Alliance Grants
Program name fr
Subventions Alliance
Group en
RESEARCH PARTNERSHIPS
Group fr
PARTENARIATS DE RECHERCHE
Committee code
96
Committee name en
RPP Internal Decision Cttee
Committee name fr
Cté de décision interne - PPR
Area of application code
802
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
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
Problem Solving with Domain-Independent Dynamic Programming: Theory and Practice
Keywords
artificial intelligence; dynamic programming; mathematical modeling; operations research; optimization; planning
Application summary
Domain-independent dynamic programming (DIDP) is a recently proposed framework for modeling combinatorial optimization problems using dynamic programming and solving them with a general purpose solver. Initial results show strong performance using a heuristic state-based search solver, thus demonstrating the success of problem solving approaches developed in Artificial Intelligence (AI) on problems traditionally studied in Operations Research (OR). This proposal seeks to develop the theory and practice of DIDP-based problem solving by characterizing DIDP from computational and knowledge representation perspectives; by understanding its relationship to the problem solving paradigms embodied in constraint programming, satisfiability, and AI planning; and by developing novel domain-independent heuristics for DIDP through the adaptation and extension of techniques from AI planning, state abstraction in OR, and decision diagram-based optimization.