  We present a method for optimal coordination of multiple vehicle teams when
multiple endpoint configurations are equally desirable, such as seen in the
autonomous assembly of formation flight. The individual vehicles' positions in
the formation are not assigned a priori and a key challenge is to find the
optimal configuration assignment along with the optimal control and trajectory.
Commonly, assignment and trajectory planning problems are solved separately. We
introduce a new multi-vehicle coordination paradigm, where the optimal goal
assignment and optimal vehicle trajectories are found simultaneously from a
viscosity solution of a single Hamilton-Jacobi (HJ) partial differential
equation (PDE), which provides a necessary and sufficient condition for global
optimality. Intrinsic in this approach is that individual vehicle dynamic
models need not be the same, and therefore can be applied to heterogeneous
systems. Numerical methods to solve the HJ equation have historically relied on
a discrete grid of the solution space and exhibits exponential scaling with
system dimension, preventing their applicability to multiple vehicle systems.
By utilizing a generalization of the Hopf formula, we avoid the use of grids
and present a method that exhibits polynomial scaling in the number of
vehicles.
