Decentralized closing ranks in 2-dimensional rigid multi-agent formations

In this paper, we consider the closing ranks problem which deals with the addition of links to a rigid multi-agent formation that is “damaged” by losing one of its agents, in order to recover rigidity. We model the information architecture of formation as a graph, where each vertex represents an agent in formation, and each edge represents a communication link between a pair of agents. We prove that if an agent is lost, we only need to add a set of new edges on its neighbor vertices such that the subgraph which is induced by neighbor vertices of the lost vertex is minimally rigid, and then the resulting graph is rigid. Utilizing the result, we propose two systematic `self-repair´ operations to recover the rigidity in case of agent removals, named Triangle Patch and Vertex Addition Patch. Considering the requirement of practical implementation, we give two algorithms corresponding the above two operations.