Optimal Path Planning Among Mobile Sources of Threat in Complex Environments

这项研究工作将为在充满多种移动威胁的环境中运行的受控移动系统创建新的路径规划和轨迹生成算法。这些威胁相当于物体不可预测地移动，或者可能是恶意移动。选择的最坏情况方法将移动威胁建模为主动而智能地寻求碰撞的追踪者。该算法的具体目标是安全地将受控系统引导到其目的地，同时将对所有威胁源的累积风险降至最低。考虑到所有追求者的所有可能行为，很快就会导致一个即使是最强大的计算机也无法解决的问题。为了使计算切实可行，问题分为两部分--第一部分是短期规避策略，只考虑最紧迫的单一威胁；第二部分是长期转向策略，目标是在考虑所有威胁的同时，安全地将受控系统引导到目标目的地。随着航空旅行和汽车交通变得更加自主，这些系统必须容纳一个或多个无法通信、故障或恶意的代理。最后，本科生和代表性不足的学生将有机会在PI的监督下，通过德克萨斯大学奥斯汀分校每年夏季学期提供的两个不同的研究项目，参与与本研究工作范围相关的研究项目。在存在多个威胁来源的情况下，捕获-逃避问题通常在计算上很难处理。该项目采用短期回避战略和长期指导战略相结合的方式来解决这些问题。短期战略基于适当定义的威胁度量，这是一种依赖于状态的度量，用于衡量逃避者与最高风险威胁的接近程度，同时考虑到双方的动态和输入约束。长期战略的主要目的是引导逃避者到达其目标目的地，而其在随后的轨迹上对每一名追赶者的累积风险敞口始终保持在较低水平。本项目分以下几个阶段来研究这些问题：1)将描述多个潜在对抗性决策者的微分对策描述为考虑多个移动威胁源的路径规划问题。2)定义一种易于计算的求解方法。3)利用基于采样的算法等现代技术来解决具有非平凡动态约束和输入约束的路径规划问题，用时变的状态约束来表示移动障碍物。4)通过将捕获-逃避问题的解与蒙特卡罗模拟和其他强大但耗时的数值解技术进行比较，验证捕获-逃避问题的解的有效性。

This research effort will create novel algorithms for path planning and trajectory generation by a controlled mobile system operating in an environment populated by multiple mobile threats. These threats correspond to objects moving unpredictably, or possibly maliciously. The chosen worst-case approach models the mobile threats as pursuers actively and intelligently seeking a collision. The specific objective of the algorithm is to safely steer the controlled system to its destination, while minimizing the cumulative exposure to all threat sources. Accounting for all possible actions by all pursuers quickly results in a problem too large for even the most powerful computer. To make the calculations practical, the problem is divided into two parts -- first a short-term evasion strategy considering only the single most imminent threat, and second a long-term steering strategy with the goal of safely steering the controlled system to its goal destination while accounting for all threats. As air travel and automobile traffic become more autonomous, it becomes imperative for these systems to accommodate one or more uncommunicative, malfunctioning, or malicious agents. Finally, undergraduate and under-represented students will have the opportunity to work under the supervision of the PI in research projects related to the scope of this research effort via two different research programs which are offered every summer semester at the University of Texas at Austin.Problems of capture-evasion in the presence of multiple sources of threat are generally computationally intractable. This project approaches such problems using a combination of a short-term evasion strategy and a long-term steering strategy. The short-term strategy is based on a suitably defined threat metric, which is a state-dependent metric that measures the closeness of an evader from the highest-risk threat, while accounting for the dynamic and input constraints of both parties. The long-term strategy is primarily intended to steer the evader to its goal destination, while its cumulative exposure to every pursuer along its ensuing trajectory is kept low at all times. This project approaches these problems in the following stages: 1) Formulate the differential game describing multiple, potentially adversarial, decision makers as a path planning problem considering multiple mobile sources of threat. 2) Define a computationally tractable solution approach. 3) Leverage modern techniques such as sampling-based algorithms to address the path planning problem subject to non-trivial dynamic and input constraints, with time-varying state constraints to represent mobile obstacle. 4) Validate the solution to the capture-evasion problem by comparing its performance, in terms of the likelihood of the evader safely reaching its destination, against Monte Carlo simulations and other powerful but time-consuming numerical solution techniques.