We consider a single Unmanned Aerial Vehicle (UAV) routing problem where there are multiple depots and the vehicle is allowed to refuel at any depot. The objective of the problem is to find a path for the UAV such that each target is visited at least once by the vehicle, the fuel constraint is never violated along the path for the UAV, and the total fuel required by the UAV is a minimum. We develop an approximation algorithm for the problem, and propose fast construction and improvement heuristics to solve the same. Computational results show that solutions whose costs are on an average within 1.4% of the optimum can be obtained relatively fast for the problem involving five depots and 25 targets.

This paper is about the allocation of tours of m targets to n vehicles. The motion of the vehicles satisfies a nonholonomic constraint (i.e., the yaw rate of the vehicle is bounded). Each target is to be visited by one and only one vehicle. Given a set of targets and the yaw rate constraints on the vehicles, the problem addressed in this paper is 1) to assign each vehicle a sequence of targets to visit, and 2) to find a feasible path for each vehicle that passes through the assigned targets with a requirement that the vehicle returns to its initial position. The heading angle at each target location may not be specified. The objective function is to minimize the sum of the distances traveled by all vehicles. A constant factor approximation algorithm is presented for the above resource allocation problem for both the single and the multiple vehicle case. Note to Practitioners-The motivation for this paper stems from the need to develop resource allocation algorithms for unmanned aerial vehicles (UAVs). Small autonomous UAVs are seen as ideal platforms for many applications, such as searching for targets, mapping a given area, traffic surveillance, fire monitoring, etc. The main advantage of using these small autonomous vehicles is that they can be used in situations where a manned mission is dangerous or not possible. Resource allocation problems naturally arise in these applications where one would want to optimally assign a given set of vehicles to the tasks at hand. The feature that differentiates these resource allocation problems from similar problems previously studied in the literature is that there are constraints on the motion of the vehicle. This paper addresses the constraint that captures the inability of a fixed wing aircraft to turn at any arbitrary yaw rate. The basic problem addressed in this paper is as follows: Given n vehicles and m targets, find a path for each vehicle satisfying yaw rate contraints such that each target is visited exactly once by a vehicle and the total distance traveled by all vehicles is minimized. We assume that the targets are at least 2r apart, where r is the minimum turning radius of the vehicle. This is a reasonable assumption because the sensors on these vehicles can map or see an area whose width is at least 2r. We give an algorithm to solve this problem by combining ideas from the traveling salesman problem and the path planning literature. We also show how these algorithms perform in the worst-case scenario

Inspecting and monitoring oil-gas pipelines, roads, rivers, and canals are very important in ensuring the reliability and life expectancy of these civil systems. An autonomous unmanned aerial vehicle (UAV) can decrease the operational costs, expedite the monitoring process, and be used in situations where a manned inspection is not possible. This paper addresses the problem of monitoring these systems using an autonomous UAV based on visual feedback. A single structure detection algorithm that can identify and localize various structures including highways, roads, and canals is presented in the paper. A fast learning algorithm that requires minimal supervision is applied to obtain detection parameters. The real time detection algorithm runs at 5 Hz or more with the onboard video collected by the UAV. Both hardware simulations and flight results of the vision-based control algorithm are presented in this paper. A fixed wing UAV equipped with a camera onboard was able to track a 700 m canal based on vision ...

Surveillance operations include inspecting and monitoring river boundaries, bridges and coastlines. An autonomous unmanned aerial vehicle (UAV) can decrease the operational costs, expedite the monitoring process and be used in situations where a manned inspection is not possible. This paper addresses the problem of searching and mapping such littoral boundaries using an autonomous UAV based on visual feedback. Specifically, this paper describes an exploration system that equips a fixed wing UAV to autonomously search a given area for a specified structure (could be a river, a coastal line etc.), identify the structure if present and map the coordinates of the structure based on the images from the onboard sensor(could be vision or near infra-red). Experimental results with a fixed wing UAV searching and mapping the coordinates of a 2 mile stretch of a river with a cross track error of around 9 meters are presented.

Heterogeneous unmanned aerial vehicles (UAVs) are being developed for several civil and military applications. These vehicles can differ either in their motion constraints or sensing/attack capabilities. This article uses methods from operations research to address a fundamental routing problem involving heterogeneous UAVs. The approach is to transform the routing problem into a relatively better understood single, asymmetric, traveling salesman problem (ATSP) and use the algorithms available for the ATSP to address the routing problem. To test the effectiveness of the transformation, the well-known Lin-Kernighan-Helsgaun heuristic was applied to the transformed ATSP. Computational results on the transformed ATSP show that solutions whose costs are within 16% of the optimum can be obtained relatively fast [within 40 s of central processing unit (CPU)] for the routing problem involving ten heterogeneous UAVs and 40 targets.

Low cost unmanned aerial vehicles (UAVs) need multiple refuels to accomplish large area coverage. We propose the use of a mobile Ground Vehicle (GV), constrained to travel on a given road network, as a refueling station for the UAV. Determining optimal routes for a UAV and GV, and selecting rendezvous locations for refueling to minimize coverage time is NP-hard. We develop a two-stage strategy for coupled route planning for UAV and GV to perform a coverage mission. The first stage computes refueling sites that ensure reachability of all points of interest by the UAV and feasible routes for both the UAV and GV. In the second stage, Mixed-Integer Linear Programming (MILP)-based exact methods are developed to plan optimal routes for the UAV and GV. As the problem is NP-Hard, we also develop computationally efficient heuristics that can find good feasible solutions within a given time limit. Extensive simulations are conducted to corroborate the effectiveness of the developed approaches. Field experiments are also performed to verify the performance of the UAV-GV solution.