Grant: Discovery Grants Program - Individual
University of Toronto
$50,000.00
AI Planning and Mathematical Programming
EF 2019-20
Résumé
Many of the day-to-day activities of people and organizations require planning and scheduling: deciding what actions to do to achieve a set of goals and deciding when actions should be done and with what resources. A daily commute might consist of deciding the latest time one can leave home to arrive in time for an important meeting while taking into account different ways to travel (bike, car, public transit), the time each one will take, and the interaction with other goals (e.g., if I drive I won't be able to have a drink with colleagues after work). As another example, a company such as Amazon must use labour, warehouse space, trucks, and fuel to coordinate the reception, storage, order-taking, packing, and delivery of goods. ****Artificial Intelligence planning has made substantial strides over the past 15 years, primarily addressing the problem of what actions to take. In contrast, the most successful technology to deal with choices about the timing and resource choices for actions arises from the mathematical programming and constraint programming disciplines. As AI planning technology is being increasingly used for real-world applications, it must increasingly make decisions about time and resources.***The proposed research program attacks the challenges of reasoning about what to do, when to do it, and what resources to use. Three proposed research themes are unified under the hypothesis that mathematical programming encompasses a suite of problem solving techniques and theoretical foundations that can be extended and integrated with AI planning to address these challenges.***Theme 1 will seek to unify and extend existing mixed integer linear programming (MILP) approaches to solving the AI planning problem with time and resources and to develop new planning technology based on Constraint Integer Programming (CIP).***Theme 2 will focus on the fundamental AI technique of A* search and develop it to solve planning problems with resources and time in three ways: focusing on solving simple scheduling problems; using LP relaxations to compute A* heuristics; and developing the relationship among A* search, dynamic programming, and multi-valued decision diagrams.***Theme 3 will take a principled approach to the application of problem decomposition to AI planning problems, focusing on the mathematical programming patterns of lazy constraint generation and column generation.***This research program is focused on fundamental advances in solving AI planning problems that require reasoning about time and resources. To ground the research, the program will be conducted in parallel with an externally-funded, collaborative robotics project that is placing robots in long-term care homes. This application embodies the challenges we address in this program. While it is separate from what is being proposed here, the robot planning application will serve as an inspiration and test-bed.**
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2015-05072
Name nom
Beck, Chris
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
2019
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 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
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
2803
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Knowledge representation
Research subject fr
Répresentation des connaissances
Installment
inst:5 - 5
Partie
5
Nb partie
5
Application title
AI Planning and Mathematical Programming
Keyword
NSERC
Application summary
Many of the day-to-day activities of people and organizations require planning and scheduling: deciding what actions to do to achieve a set of goals and deciding when actions should be done and with what resources. A daily commute might consist of deciding the latest time one can leave home to arrive in time for an important meeting while taking into account different ways to travel (bike, car, public transit), the time each one will take, and the interaction with other goals (e.g., if I drive I won't be able to have a drink with colleagues after work). As another example, a company such as Amazon must use labour, warehouse space, trucks, and fuel to coordinate the reception, storage, order-taking, packing, and delivery of goods. ****Artificial Intelligence planning has made substantial strides over the past 15 years, primarily addressing the problem of what actions to take. In contrast, the most successful technology to deal with choices about the timing and resource choices for actions arises from the mathematical programming and constraint programming disciplines. As AI planning technology is being increasingly used for real-world applications, it must increasingly make decisions about time and resources.***The proposed research program attacks the challenges of reasoning about what to do, when to do it, and what resources to use. Three proposed research themes are unified under the hypothesis that mathematical programming encompasses a suite of problem solving techniques and theoretical foundations that can be extended and integrated with AI planning to address these challenges.***Theme 1 will seek to unify and extend existing mixed integer linear programming (MILP) approaches to solving the AI planning problem with time and resources and to develop new planning technology based on Constraint Integer Programming (CIP).***Theme 2 will focus on the fundamental AI technique of A* search and develop it to solve planning problems with resources and time in three ways: focusing on solving simple scheduling problems; using LP relaxations to compute A* heuristics; and developing the relationship among A* search, dynamic programming, and multi-valued decision diagrams.***Theme 3 will take a principled approach to the application of problem decomposition to AI planning problems, focusing on the mathematical programming patterns of lazy constraint generation and column generation.***This research program is focused on fundamental advances in solving AI planning problems that require reasoning about time and resources. To ground the research, the program will be conducted in parallel with an externally-funded, collaborative robotics project that is placing robots in long-term care homes. This application embodies the challenges we address in this program. While it is separate from what is being proposed here, the robot planning application will serve as an inspiration and test-bed.**