  Provably safe and scalable multi-vehicle path planning is an important and
urgent problem due to the expected increase of automation in civilian airspace
in the near future. Although this problem has been studied in the past, there
has not been a method that guarantees both goal satisfaction and safety for
vehicles with general nonlinear dynamics while taking into account disturbances
and potential adversarial agents, to the best of our knowledge. Hamilton-Jacobi
(HJ) reachability is the ideal tool for guaranteeing goal satisfaction and
safety under such scenarios, and has been successfully applied to many
small-scale problems. However, a direct application of HJ reachability in most
cases becomes intractable when there are more than two vehicles due to the
exponentially scaling computational complexity with respect to system
dimension. In this paper, we take advantage of the guarantees HJ reachability
provides, and eliminate the computation burden by assigning a strict priority
ordering to the vehicles under consideration. Under this sequential path
planning (SPP) scheme, vehicles reserve "space-time" portions in the airspace,
and the space-time portions guarantee dynamic feasibility, collision avoidance,
and optimality of the paths given the priority ordering. With a computation
complexity that scales quadratically when accounting for both disturbances and
an intruder, and linearly when accounting for only disturbances, SPP can
tractably solve the multi-vehicle path planning problem for vehicles with
general nonlinear dynamics in a practical setting. We demonstrate our theory in
representative simulations.
