Closing ranks in rigid multi-agent formations using edge contraction
Date
2010
Authors
Fidan, Baris
Hendrickx, Julien M
Anderson, Brian
Journal Title
Journal ISSN
Volume Title
Publisher
John Wiley & Sons Inc
Abstract
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.
Description
Keywords
Keywords: autonomous formations; closing ranks; Decentralized algorithms; edge contraction; Edge contractions; Graph operations; Higher dimensions; Multi-Agent; Rigid formations; Theoretical points; Theoretical result; three-dimensional rigidity; Graph theory; Rigi autonomous formations; closing ranks; edge contraction; multi-agent systems; rigidity; three-dimensional rigidity
Citation
Collections
Source
International Journal of Robust and Nonlinear Control
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
DOI
Restricted until
2037-12-31
Downloads
File
Description