  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.
