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

在加拿大，每年有数千起搜救案件和数千起失踪人口案件。应急搜索和监视行动的调度和路径规划是一项时间紧迫的任务。基于优化的决策支持系统(OBDSS)可以帮助决策者在这样的情况下找到有效的计划或调度，避免生命损失和伤害。然而，目前还没有一刀切的OBDSS用于监视和搜索。应急决策支持系统通常是由研究人员和开发人员白手起家建立的。我们最近与魁北克和加拿大海岸警卫队(CCG)的研究人员共同开发了这样一个用于海上SAR作业调度的OBDSS。尽管OBDSS有助于DM对可用资源进行任务分配，但为了找到最佳建议而要评估的可能建议的组合爆炸，或者仅仅是实际评估可能建议的质量所需的冗长模拟，阻碍了OBDSS的效率。此外，DM经常需要在短时间内评估多个场景，从而导致推荐模块的多次重启和次优响应。我们的研究主要应用于海上SAR、陆上SAR和应急监视(覆盖)。在这种情况下，生命往往岌岌可危。因此，我们认识到有必要改进在这方面使用的系统的质量和响应时间。在形式上，我们将上述应用视为调度和路径规划问题。解决这类问题的一种方法是运用运筹学，将它们表述为优化问题。优化问题通常分两步求解：建模步骤和求解步骤。在建模过程中，以形式语言描述问题的约束条件，例如搜索者数量和搜索持续时间，以及其目标函数，例如最大化找到幸存者的概率。该模型可由我们称为求解器的计算机程序读取。在求解步骤中，求解器搜索在约束条件下优化目标函数的推荐。这导致了OBDSS推荐模块中可能存在的两个瓶颈：建模(或模型生成)和求解。作为对此的回应，该计划中解决的项目被分成两个互补的主题，利用人工智能和运筹学的多种组合。第一个主题包括促进和加速问题形成(建模)阶段的项目。这是通过使用人工智能来取代或简化对问题建模或评估建议所需的昂贵模拟来实现的。第二个主题涉及新的方法，也是基于人工智能，通过简化优化模型或为求解器提供良好的起点来提高求解器在给定问题或反复出现的问题上的性能。

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.