Closing ranks in rigid multi-agent formations using edge contraction

This paper proposes a systematic approach to solve the closing rank problem for a rigid multi-agent formation, viz. restoring rigidity after loss of an agent. The approach is based on a particular graph operation, the edge contraction operation. It is proven that when an agent is lost in an arbitrary two-dimensional rigid formation, rigidity can always be restored by transferring all links to which this agent was incident on to one of its neighbors, though not in general any arbitrary one of them. From a graph theoretical point of view, this corresponds to contraction of a certain edge incident to the vertex representing the agent being lost. It is established, for any two-dimensional rigid formation (graph), that there exists at least two such edges that can be contracted to solve the closing ranks problem. Later, it is demonstrated that any potential decentralized algorithm to check if an arbitrary edge is contractible would need to use information on vertices and edges that can be at arbitrarily large distance from the edge considered; and a set of rigid graph theoretical results are established for several general settings, which can be used in selection of the edge to contract in these settings in order to solve the corresponding closing ranks problems. Partial results are also obtained for three-dimensional formations, and it is shown that the two-dimensional results do not generalize as such to higher dimension. Copyright (C) 2010 John Wiley & Sons, Ltd.