Optimal Path Planning Among Mobile Sources of Threat in Complex Environments

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

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.