Grant: Discovery Grants Program - Individual
Université Laval
$26,000.00
Improving Optimization-Based Scheduling and Path Planning Decision Support: An Artificial Intelligence and Operations Research Approach With Applications to Surveillance and Search
FY 2021-22
Summary
In Canada, there are thousands of search and rescue (SAR) cases and thousands of missing person cases each year. Scheduling and path planning of search and surveillance operations for emergency response is a time-critical task. Optimization-based decision support systems (OBDSS) can help decision makers (DM) to find a valid and efficient plan or schedule in such situations and avoid life loss and injuries. However, at this time, there is no one-size fits all OBDSS for surveillance and search. OBDSS for emergency response are often built from scratch by researchers and developers. We recently worked on such an OBDSS for maritime SAR operations scheduling with researchers from Québec and the Canadian Coast Guard (CCG). Although an OBDSS helps a DM to task the available resources, the combinatorial explosion of possible recommendations to evaluate in order to find the best, or simply the lengthy simulations required to realistically assess the quality of possible recommendations, hinder the OBDSS efficiency. Furthermore, a DM often needs to evaluate multiple scenarios in a short time leading to multiple restarts of the recommendation module and to a suboptimal response. The main applications of our research are maritime SAR, land SAR, and surveillance (coverage) for emergency response. In such contexts, lives are often at stake. Therefore, we identified a need to improve both the quality and response time of the systems used in this context. Formally, we see the aforementioned applications as scheduling and path planning problems. One way to tackle such problems, using operations research, is to formulate them as optimization problems. Optimization problems are often solved in two steps: a modeling step and a solving step. During modeling, the problem is described in a formal language in terms of its constraints, e.g. number of searchers and search duration, and of its objective function, e.g. maximize the probability of finding survivors. The model is readable by a computer program we call a solver. The solver, during the solving step, search a recommendation that optimizes the objective function subject to the constraints. This leads to two possible bottlenecks in an OBDSS recommendation modules: modeling (or model generation) and solving. As a response to this, the projects tackled in this program are grouped in two complementary themes leveraging multiple combinations of artificial intelligence and operations research. The first theme encompasses projects to facilitate and accelerate the problem formulation (modeling) phase. This is done by using artificial intelligence to replace or simplify the expensive simulations needed to model a problem or evaluate a recommendation. The second theme concerns novel approaches, also based on artificial intelligence, to improve the performance of the solver on a given problem or on recurring problems either by simplifying the optimization models or by providing good starting points for the solver.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2021-03495
Name nom
Morin, Michael
Department département
Département d'opérations et systèmes de décision
Organization id
51
Institution établissement
Université Laval
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2021
Competition year année de concours
2021
Award amount
26000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
800
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 and communication services
Area of application fr
Services d'information et de télécommunications
Research subject code
2715
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Optimization
Research subject fr
Optimisation
Installment
inst:1
Partie
1
Nb partie
5
Application title
Improving Optimization-Based Scheduling and Path Planning Decision Support: An Artificial Intelligence and Operations Research Approach With Applications to Surveillance and Search
Keyword
NSERC
Application summary
In Canada, there are thousands of search and rescue (SAR) cases and thousands of missing person cases each year. Scheduling and path planning of search and surveillance operations for emergency response is a time-critical task. Optimization-based decision support systems (OBDSS) can help decision makers (DM) to find a valid and efficient plan or schedule in such situations and avoid life loss and injuries. However, at this time, there is no one-size fits all OBDSS for surveillance and search. OBDSS for emergency response are often built from scratch by researchers and developers. We recently worked on such an OBDSS for maritime SAR operations scheduling with researchers from Québec and the Canadian Coast Guard (CCG). Although an OBDSS helps a DM to task the available resources, the combinatorial explosion of possible recommendations to evaluate in order to find the best, or simply the lengthy simulations required to realistically assess the quality of possible recommendations, hinder the OBDSS efficiency. Furthermore, a DM often needs to evaluate multiple scenarios in a short time leading to multiple restarts of the recommendation module and to a suboptimal response. The main applications of our research are maritime SAR, land SAR, and surveillance (coverage) for emergency response. In such contexts, lives are often at stake. Therefore, we identified a need to improve both the quality and response time of the systems used in this context. Formally, we see the aforementioned applications as scheduling and path planning problems. One way to tackle such problems, using operations research, is to formulate them as optimization problems. Optimization problems are often solved in two steps: a modeling step and a solving step. During modeling, the problem is described in a formal language in terms of its constraints, e.g. number of searchers and search duration, and of its objective function, e.g. maximize the probability of finding survivors. The model is readable by a computer program we call a solver. The solver, during the solving step, search a recommendation that optimizes the objective function subject to the constraints. This leads to two possible bottlenecks in an OBDSS recommendation modules: modeling (or model generation) and solving. As a response to this, the projects tackled in this program are grouped in two complementary themes leveraging multiple combinations of artificial intelligence and operations research. The first theme encompasses projects to facilitate and accelerate the problem formulation (modeling) phase. This is done by using artificial intelligence to replace or simplify the expensive simulations needed to model a problem or evaluate a recommendation. The second theme concerns novel approaches, also based on artificial intelligence, to improve the performance of the solver on a given problem or on recurring problems either by simplifying the optimization models or by providing good starting points for the solver.