| Cooperative Unmanned Aerial Vehicles (UAV) teams are anticipated to provide much needed support for human intelligence, measurement and signature intelligence, signals intelligence, imagery intelligence, and open source intelligence through algorithms, software, and automation. Therefore, it is necessary to have autonomous algorithms that route multiple UAVs effectively and efficiently throughout missions and that these are realizable in the real-world given the associated uncertainties. Current routing strategies ignore communication constraints altogether. In reality, communication can be restricted by bandwidth, line-of-sight, maximum communication ranges, or a need for uninterrupted transmission. Generating autonomous algorithms that work effectively around these communication constraints is key for the future of UAV surveillance applications.;In this work, both current and new routing strategies for UAVS are analyzed to determine how communications impact efficiency of information return. It is shown that under certain communication conditions, a new approach on routing can be more efficient than typically adopted strategies. This new approach defines and presents a new formulation based on a minimum delivery latency objective function. The problem is formulated such that information is not considered delivered until it is returned back to a high-bandwidth connection (depot) which is common when communication is restricted. The size of the region is shown to be dependent upon distance between requests, UAV bandwidth, UAV velocity, and data size, but it was shown that for large-sized data, long distances, and low bandwidth, it is generally better to route UAVs with this new minimum latency objective.;With the added decision of when to deliver information to a high-bandwidth connection, an already computationally complex problem grows even faster. Because of scaling issues, a heuristic algorithm was developed that was constructed by analyzing the optimal solution. The algorithm is a cluster-first, route-second approach, but differs from conventional Vehicle Routing Problem (VRP) solutions in that the number of clusters is not necessarily equal to the number of vehicles. Because of this, a unique approach to clustering is adopted to form clusters using hierarchical agglomerative clustering and fuzzy logic. Based on a detailed Monte Carlo analysis, the heuristic algorithm showed near-optimal (within ∼5%) results calculable in real-time (allowing it to be used in dynamic scenarios too) and scaled to much larger problem sizes. Furthermore, the performance was analyzed under varying degrees of dynamism and arrival rates. Results showed good performance, and found the boundaries for the regions of light and heavy load cases for a single vehicle to be about 0.3 and 4 requests an hour, respectively. Finally, both static and dynamic cases were validated in flight testing, highlighting the usability of this approach. |
