Topology reconfiguration for systems of networked autonomous vehicles with network connectivity constraints

Future systems of networked autonomous vehicles, such as unmanned aerial or ground vehicles, may rely on peer-to-peer, wireless communication to coordinate their actions. The physical formation of the network may need to be reconfigured at times based on the specified missions. However, reconfiguring the physical formation also impacts the link connectivity and, hence, the connectivity of the network. If the network is partitioned, then the autonomous vehicles can no longer coordinate their movements, and the mission may fail. In this dissertation, we develop techniques to transform the formation of a system of autonomous vehicles while preserving network connectivity. Several different approaches to address this problem are presented, with a focus on a method that utilizes ideas from routing packets in networks. We also discuss the problem of formation selection and give an example of formation optimization in which communication costs are minimized under constraints on preserving network connectivity and on the amount of movement required. In this dissertation, we first consider the problem of how to transform the network topology of a system of autonomous vehicles from an initial topology to a desired topology while maintaining network connectivity throughout the topology transformation process. We propose algorithms based on the concepts of prefix labeling and routing from the computer networking community to solve this problem when the final network topology is a tree. We present simulation results to evaluate the performance of our algorithms in terms of the amount of movement and time required to achieve the desired network topology. The algorithms we develop can be used to generate navigation functions that can be used by control systems to achieve a desired physical topology. Next, we consider a key unsolved subproblem, which is how the nodes in the initial network topology should be mapped onto the nodes in the final network topology before the network topology is reconfigured, while taking into account the needs to preserve network connectivity. We develop algorithms to solve this problem based on optimal and suboptimal graph-matching algorithms. We then apply these techniques with previously developed techniques to plan node movement to reconfigure the network topology while preserving network connectivity at all times. The performance of these techniques is evaluated via simulation. Afterward, we consider the problem of optimizing the network topology of a system of networked autonomous vehicles to minimize the aggregate network traffic required to support a given set of data flows under constraints on the total amount of movement by the autonomous vehicles. We propose a solution to this problem consisting of two steps. First, we develop algorithms to select a network tree topology from an arbitrary initial connected network topology. Second, we develop optimization algorithms to reconfigure the network tree topology found in the first step while preserving the connectivity to minimize the aggregate traffic under constraints on the total number of hops that the autonomous vehicles may move. Simulation results are presented to evaluate the performance of the algorithms. Finally, we apply networking concepts and optimization strategies to determine a feasible physical formation that reduces aggregate data traffic under constraints on the total amount of movement by the autonomous vehicles. We develop techniques that provide waypoints for use by physical control algorithms, under which the network connectivity will be ensured at all times if movement is on linear paths between the waypoints. Simulation results are presented to demonstrate that our proposed techniques can significantly reduce aggregate network traffic.