Decentralized closing ranks in vehicle formations and sensor networks

Abstract

In this paper, we present recent results on the closing ranks problem in vehicle formations and sensor networks. The closing ranks problem is to determine new sensing/communication links in the event of agent failure in order to recover certain properties of the underlying information architecture. We model the information architecture as a graph G(V.E), where V is a set of vertices representing the agents and E is a set of edges representing information flow amongst the agents. We focus on two properties of the graph called rigidity and global rigidity, which are required for formation shape maintenance and sensor network self-localization, respectively. We show that while previous results permit local repair involving only neighbours of the lost agent, the repair cannot always be implemented using only local information. Utilizing a graph theoretic substitution principle, we present new results that can be applied to make the local repair using only local information. We also describe implementation of the solution and illustrate the ideas through examples.