  There is a strong demand for covering a large area autonomously by multiple
UAVs (Unmanned Aerial Vehicles) supported by a ground vehicle. Limited by UAVs'
battery life and communication distance, complete coverage of large areas
typically involves multiple take-offs and landings to recharge batteries, and
the transportation of UAVs between operation areas by a ground vehicle. In this
paper, we introduce a novel large-area-coverage planning framework which
collectively optimizes the paths for aerial and ground vehicles. Our method
first partitions a large area into sub-areas, each of which a given fleet of
UAVs can cover without recharging batteries. UAV operation routes, or trails,
are then generated for each sub-area. Next, the assignment of trials to
different UAVs and the order in which UAVs visit their assigned trails are
simultaneously optimized to minimize the total UAV flight distance. Finally, a
ground vehicle transportation path which visits all sub-areas is found by
solving an asymmetric traveling salesman problem (ATSP). Although finding the
globally optimal trail assignment and transition paths can be formulated as a
Mixed Integer Quadratic Program (MIQP), the MIQP is intractable even for small
problems. We show that the solution time can be reduced to close-to-real-time
levels by first finding a feasible solution using a Random Key Genetic
Algorithm (RKGA), which is then locally optimized by solving a much smaller
MIQP.
