Safe and Resilient Multi-vehicle Trajectory Planning Under Adversarial Intruder
For multi-vehicle systems requiring safety guarantees, this work provides a scalable replanning method under adversarial intrusions, though it is an incremental improvement over existing STP.
The paper addresses safe multi-vehicle trajectory planning under adversarial intruders by extending sequential trajectory planning (STP) to require replanning for only a fixed number of vehicles, independent of total fleet size, demonstrated in urban airspace simulations.
Provably safe and scalable multi-vehicle trajectory planning is an important and urgent problem. Hamilton-Jacobi (HJ) reachability is an ideal tool for analyzing such safety-critical systems and has been successfully applied to several small-scale problems. However, a direct application of HJ reachability to multi-vehicle trajectory planning is often intractable due to the "curse of dimensionality." To overcome this problem, the sequential trajectory planning (STP) method, which assigns strict priorities to vehicles, was proposed, STP allows multi-vehicle trajectory planning to be done with a linearly-scaling computation complexity. However, if a vehicle not in the set of STP vehicles enters the system, or even worse, if this vehicle is an adversarial intruder, the previous formulation requires the entire system to perform replanning, an intractable task for large-scale systems. In this paper, we make STP more practical by providing a new algorithm where replanning is only needed only for a fixed number of vehicles, irrespective of the total number of STP vehicles. Moreover, this number is a design parameter, which can be chosen based on the computational resources available during run time. We demonstrate this algorithm in a representative simulation of an urban airspace environment.