  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. 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 large scale systems is often intractable because of its
exponentially-scaling computation complexity with respect to system dimension,
also known as the "curse of dimensionality". To overcome this problem, the
sequential path planning (SPP) method, which assigns strict priorities to
vehicles, was previously proposed; SPP allows multi-vehicle path planning to be
done with a linearly-scaling computation complexity. In this work, we
demonstrate the potential of SPP algorithm for large-scale systems. In
particular, we simulate large-scale multi-vehicle systems in two different
urban environments, a city environment and a multi-city environment, and use
the SPP algorithm for trajectory planning. SPP is able to efficiently design
collision-free trajectories in both environments despite the presence of
disturbances in vehicles' dynamics. To ensure a safe transition of vehicles to
their destinations, our method automatically allocates space-time reservations
to vehicles while accounting for the magnitude of disturbances such as wind in
a provably safe way. Our simulation results show an intuitive multi-lane
structure in airspace, where the number of lanes and the distance between the
lanes depend on the size of disturbances and other problem parameters.
