| Unmanned Aerial Vehicle (UAV) technology holds great promise for various civilian and military applications. Cooperative control of a network of autonomous UAVs poses novel challenges because of the inherent constraints like non-holonomic motion, limited range communication, etc. In this dissertation, we present some recently-developed tools and strategies for motion coordination of UAVs. In particular, the focus is on algorithms for various coordination tasks such as vehicle routing to meet service demands, deployment over a region for surveillance and flying in flock-like formations.;We study minimum-time motion planning and routing problems for the Dubins vehicle, i.e., a nonholonomic vehicle that is constrained to move along planar paths of bounded curvature, without reversing direction. We consider the Traveling Salesperson Problem for the Dubins vehicle (DTSP): given n points on a plane, what is the shortest Dubins tour through these points and what is its length? We start by showing that the worst-case length of such a tour grows linearly with n and we propose a novel algorithm with worst-case performance within a constant factor approximation of the optimum. In doing this, we also obtain an upper bound on the optimal length in the classical point-to-point problem. We then study a stochastic version of the DTSP where the n targets are randomly sampled from a uniform distribution. We show that the expected length of such a tour is of order at least n2/3 and we propose a novel algorithm yielding a solution with length of order n 2/3 with high probability. We apply these results in a dynamic version of the DTSP: given a stochastic process that generates target points, is there a policy which guarantees that the number of unvisited points does not diverge over time? If such stable policies exist, what is the minimum expected time that a newly generated target waits before being visited by the vehicle? We propose a novel stabilizing algorithms such that the expected wait time is provably within a constant factor from the optimum. We obtain analogous results for the three dimensional space and extend various results to a double integrator vehicle model.;We also study a facility location problem for groups of Dubins vehicles, i.e., nonholonomic vehicles that are constrained to move along planar paths of bounded curvature, without reversing direction. Given a compact region and a group of Dubins vehicles, the coverage problem is to minimize the worst-case traveling time from any vehicle to any point in the region. Since the vehicles cannot hover, we assume that they fly along static closed curves called loitering curves. We present circular loitering patterns for a Dubins vehicle and for a group of Dubins vehicles that minimize the worst-case traveling time in sufficiently large regions. We do this by establishing an analogy to the disk covering problem.;Finally, we consider ad-hoc networks of robotic agents with double integrator dynamics. For such networks, the connectivity maintenance problems are: (i) do there exist control inputs for each agent to maintain network connectivity, and (ii) given desired controls for each agent, can one compute the closest connectivity-maintaining controls in a distributed fashion? The proposed solution is based on three contributions. First, we define and characterize admissible sets for double integrators to remain inside disks. Second, we establish an existence theorem for the connectivity maintenance problem by introducing a novel state-dependent graph, called the double-integrator disk graph . Finally, we design a distributed "flow-control'' algorithm to compute optimal connectivity-maintaining controls. |
