Improving Optimization-Based Scheduling and Path Planning Decision Support: An Artificial Intelligence and Operations Research Approach With Applications to Surveillance and Search

点击翻译按钮获取中文摘要

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.