Graph Matching-Based Topology Reconfiguration Algorithm for Systems of Networked Autonomous Vehicles

As missions change or evolve, the formation of a system of networked autonomous vehicles may need to be reconfigured. When the vehicles communicate over a wireless ad hoc network, network connectivity may need to be preserved during the reconfiguration process. In addition, achieving the network topology associated with the desired final physical formation can then enable the physical formation to be achieved through a variety of formation control algorithms. In this paper, we focus on the problem of anonymous reconfiguration in which any vehicle in the initial formation of the system can be assigned to any of the positions in the final formation. We consider a key unsolved subproblem, which is how the nodes in the initial formation should be mapped onto the nodes in the final formation before the formation 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.