Optimization of waterspace management and scheduling for multiple unmanned vehicles

We describe an approach for accomplishing the high-level mission planning required for a heterogeneous team of autonomous vehicles performing surveys in multiple areas, such as required for mine countermeasure (MCM) missions. The high-level mission scheduling and waterspace management require sequencing the order and location of lower-level tasks to be completed by each vehicle in the heterogeneous team: unmanned surface vessels (USVs) and unmanned underwater vehicles (UUVs). In this context, the USVs serve as transport vehicles while the UUVs perform the actual surveys and execute any other local actions. We develop a solution to this complex sequencing operation by leveraging unique information processing, communication, refueling, and planning windows that form constraints within the system within a formal scheduling optimization framework. We use mixed-integer linear programming (MILP) as a solution method for the associated optimization problem. By using such a standard optimization approach, we both take advantage of optimality guarantees on the solution and extensive commercial numerical solvers. In addition to developing the numerical optimization problem, we also include methods to account for risks due to schedule slip for the individual tasks. We conclude with an example of joint USV/UUV planning using the optimization algorithm