UAV swarm coordination and control for establishing wireless connectivity

Abstract

This thesis addresses the vital problem of enabling communications in a disaster struck area. Emphasis is placed on the need for data communication between various points on the ground, which cannot be effectively established in a short time frame using existing methods. We propose the use of completely autonomous Unmanned Aerial Vehicles (UAVs) mounted with wireless equipment to accomplish this goal by coordinating themselves to build a wireless backbone for communication. The problem then becomes one of coverage, search and tethering, where a swarm of UAVs (agents) are required to cooperatively cover a given area and search for ground nodes while also relaying packets between already found ground nodes. We explore the above problem from two main perspectives - 1) a theoretical perspective that identifies what can be done with complete a priori information, and 2) a practical perspective that demands a decentralized solution under realistic networking and environmental conditions.

For the theoretical perspective, we take a geometric approach to design paths for agents with the aim of minimizing maximum latency in the network. We propose Bounded Edge-Count Diametric Latency Minimizing Steiner Tree (BECDLMST) as a solution structure capable of achieving very low maximum latency. BECDLMST, which is based on the concept of minimal Steiner trees, generates agent paths such that agent travel distances are lowered, which in turn lowers maximum network latency. We show that finding the optimal BECDLMST is an NP-hard problem. So we first provide an exact exponential algorithm to find the best BECDLMST, and then devise an efficient approximation through an anytime heuristic. Although exponential in nature, the exact algorithm ensures that the solution space is pruned as much as possible at every step. The approximation on the other hand utilizes ideas from particle swarm optimization to generate a near optimal BECDLMST in quadratic time by iteratively evolving from a Minimum Diameter Steiner Tree (MDST). Experimental results on computation time and resulting network latency are presented for both algorithms.

Considering a practical perspective, we identify a number of challenges to be addressed, namely: 1) Lack of global information in online agent planning, 2) Intermittent and mobile ground nodes, 3) Opposing trade-offs in a dynamic environment, 4) Limited communication bandwidth, and 5) Adverse wind effects. To this end, we propose a suitable hierarchical, decentralized control and coordination architecture. A robust control algorithm is developed to ensure precise waypoint navigation of UAVs. This in turn is shown to lay the foundation for a multiagent coordination algorithm that can afford to not consider adverse wind effects within operational limits. A communication-realistic, dynamically adaptive, completely decentralized, agent-count-and-node-count-independent coordination algorithm is presented that has been empirically shown to non-monotonically reduce network latency and increase search quality. The approach taken is "near-decision-theoretic", where each agent tries to maximize a scoring function, without a fixed horizon and without assuming stochastic models to describe the environment. The decision algorithm for relaying packets is designed so that agent paths mimic certain characteristics of BECDLMST. Simulations show that the decentralized control and coordination algorithm achieves very promising latency results that are inferior to the centralized version by only 10-50%. Experimental results illustrating the adaptive behavior of the agents and the resulting performance in terms of network latency and search quality are presented. Real flight tests and hardware-in-the-loop simulations are performed to prove the performance of our autonomous control system as well as the viability of air-to-ground and air-to-air communication.