Adaptive Unmanned Aerial Vehicle Routing Methods for Tactical Surveillance Operations

We consider a single Unmanned Aerial Vehicle (UAV) routing problem to maximize information fulfillment across an entire mission subject to mission time constraints and a platform's sensor effectiveness resulting in partial collections of information. The UAV routes to discrete waypoints in the area of operation (AO) with corresponding information gain values, representing their value to the mission relative to all other waypoints. This work closely parallels traditional vehicle routing problems such as the traveling salesman, orienteering, and prize-collecting problems but these problems do not adequately represent UAV flight operations by themselves. Three separate problem statements are considered: allocating routing resources for the UAV across a series of partitioned subproblems, generating routes for the UAV in the deterministic environment, and generating routes with the presence of uncertainty.;The first project considers deploying routing methods across a partitioned area of operation by creating a series of independent vehicle routing subproblems to improve global information collection. To solve this problem, we propose a mixed integer allocation model to link the subproblems by identifying the best sequence of ingress and egress points between subgraphs and also determine the time allocation for the subgraph to maximize global information collection. This formulation considers a series of discrete points scored as a function of an all ingress/egress point pairs and time samples for all partitions on the route. To improve overall solve time and solution quality we also present a series of heuristics to generate and score potential ingress and egress points which serve as in input to a mathematical allocation model.;Our second problem we address is to find a path along the transportation network that maximizes total information collection but does not exceed a specified mission cost, representing the vehicle's endurance or the time-sensitivity of improving situational awareness in the AO. The Prize-Collecting Vertex Routing (PCVR) model is first introduced as an exact mixed integer program to generate the prize-collecting route. This is accompanied by a simulated annealing heuristic as a means to efficiently solve larger problem instances without the restrictions of optimization models. These methods are benchmarked alongside each other and provide further insight into solution properties.;Finally, to extend the deterministic routing problem into the real world we introduce uncertainty on the intelligence values and travels costs are considered. To solve this problem we present a variance-constrained PCVR model to maximize the expected information gain across the route while also constraining the route cost and objective variance to predefined variance thresholds to establish confidence in the solution in a stochastic environment. The variance-constrained model is then reformulated to incorporate dependencies in the value of the information gain values, changing the information priority in the entire graph by updating the values upon each realization. Using a covariance approximation as a basis for routing, this model attempts to exhaust the area of any further meaningful information gain without requiring an extensive search of the area. We tested our covariance approximation approach using data from information gain maps generated using normalized geographic elevation data to represent the dependencies between information gain values.;The presented models are capable of maximizing information fulfillments, reducing the impact of uncertainty, and delivering a real-time UAV route with minimal assumptions to facilitate deployment in real-world surveillance applications. A link to our hardware-in-the-loop demo is provided and we finish with remarks and comments regarding the relevance of this work and future research.