Robust Sequential Trajectory Planning under Disturbances and Adversarial Intruder

Provably safe and scalable multivehicle trajectory planning is an important and urgent problem. 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, which has been successfully applied to many small-scale problems; however, its direct application 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 provided by HJ reachability and eliminate the computation burden by assigning a strict priority ordering to vehicles under consideration. Under this sequential trajectory planning (STP) scheme, vehicles reserve 'space-time' portions in the airspace. The space-time portions guarantee dynamic feasibility, collision avoidance, and optimality of trajectories 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, the STP can tractably solve the multivehicle trajectory planning problem for vehicles with general nonlinear dynamics in a practical setting. We demonstrate our theory in representative simulations.