Planning and control of unmanned aerial vehicles in a dynamic stochastic system

In this thesis, we consider the problem of automatic routing and scheduling of Unmanned Aerial Vehicles (UAVs) in a dynamic stochastic environment motivated by surveillance applications. Unlike standard routing and scheduling problems, the problems associated with UAVs in surveillance operations involve uncertain effects such as the risk of UAV loss, arrival of new tasks, and the need for real-time adaptations. Such problems can be formulated as dynamic scheduling problems under uncertainty, and can be solved in principle by stochastic dynamic programming techniques. However, due to the size and complexity of the state space in these problems, dynamic programming becomes intractable. In this thesis, we develop several approximate dynamic programming approaches using forms of model predictive control. In model predictive control, current control actions are determined at each time by solving a finite horizon control formulation based on the current state. As new information is acquired, the problems are reformulated and solved to obtain revised controls.; The goal of this thesis is to develop computationally feasible and near-optimal scheduling solutions for UAVs operating in surveillance operations where adaptations can be made in real time to new information. In order to accomplish this, we investigate three different approaches for model predictive control, accounting for various levels of risk and uncertainty, and develop and evaluate computational algorithms for model predictive control based on each of these models.; The first approach is based on deterministic models similar to the classical vehicle routing problem that is known to be NP-hard, and thus requires approximate algorithms for real-time computation. We develop two new solution techniques for this class of problem: a primal-dual algorithm based on a separable Lagrangian relaxation and a multiple vehicle combinatorial rollout algorithm. The second approach includes models with risk of vehicle loss; we extend a formulation based on weapon-target assignment to the UAV routing and scheduling problem to account for risk of loss of UAVs. This formulation hedges against risk by maximizing the expected value received by a schedule a priori. We extend our previous combinatorial rollout algorithms to solve the resulting risky schedule problems. The third approach includes models with uncertain task arrivals; we develop a new formulation based on models for package pickup and delivery problems. We develop a class of simulation-based algorithms that iteratively learn piece-wise linear cost-to-go approximations that can be used in approximate dynamic programming to generate fast optimal strategies. In order to evaluate our algorithms, we develop a simulation of an abstracted military UAV scheduling problem with unknown task arrivals and flight risks. The model predictive control algorithms are evaluated in the simulation to illustrate their potential for real-time UAV control.; The contributions of this thesis are the development of planning and control methodologies for a surveillance problem that focuses on real-time planning and control of UAVs and computational experiments for the developed algorithms.