Coordinated Route Planning of Multiple Fuel-constrained Unmanned Aerial Systems with Recharging on an Unmanned Ground Vehicle for Mission Coverage

Small Unmanned Aerial Systems (sUAS) such as quadcopters are ideal for aerial surveillance because of their runway independence, terrain-agnostic maneuverability, low cost, and simple hardware. However, battery capacity constraints limit the effective range and endurance of sUASs, requiring human intervention to replace batteries or perform manual recharging for longer operations. To increase their range, an Unmanned Ground Vehicle (UGV) may provide recharging depot as needed. The problem is then to find optimal paths for the UGV and sUASs to visit mission points and sUAS-UGV rendezvous points for recharging. We present a three-tiered heuristics to solve this computationally hard combinatorial optimization problem: (1) K-means clustering is used to find UGV waypoints, (2) a traveling salesman formulation (TSP) is used to solve the optimal UGV route, and (3) vehicle routing problem formulation (VRP) with capacity constraints, time windows, and dropped visits is used to solve for sUAS routes. We use constraint programming for optimization of the TSP and VRP, achieving a solution for 25 mission points and up to 4 sUASs in about a minute on a standard desktop computer. We also found that constraint programming solvers are 7 - 30 times faster, but 4 - 15% sub-optimal compared to mixed-integer solvers, which provide exact solutions. Further, we used constraint programming solvers in a Monte-Carlo approach to evaluate the role of mission spread, number of clusters, and number of sUASs on the optimal solution. Our contribution is the development of heuristics for route selection of sUAS-UGVs that produces high quality solutions as more mission points and sUASs are added without substantially increasing the computational time.