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

改进基于优化的调度和路径规划决策支持：一种应用于监视和搜索的人工智能和运筹学方法

• 批准号: RGPIN-2021-03495
• 负责人: Morin, Michael
• 金额: $ 1.89万
• 依托单位: Université Laval
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=742584
• 关键词: Improving; Optimization; Based; Scheduling; Path

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.

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