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
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=761853
• 关键词: 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.

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