Formation Reorganization by Primitive Operations on Directed Graphs
Authors:
- Julien M. HendrickxJHJulien M. Hendrickx
- Baris FidanBFBaris Fidan
- Changbin YuCYChangbin Yu
- Brian D. O. AndersonBABrian D. O. Anderson
- Vincent D. BlondelVBVincent D. Blondel
- 16 May 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 53 (4) , 968-979
Abstract
In this paper, we study the construction and transformation of 2-D persistent graphs. Persistence is a generalization to directed graphs of the undirected notion of rigidity. Both notions are currently being used in various studies on coordination and control of autonomous multiagent formations. In the context of mobile autonomous agent formations, persistence characterizes the efficacy of a directed formation structure with unilateral distance constraints seeking to preserve the shape of the formation. Analogously to the powerful results about Henneberg sequences in minimal rigidity theory, we propose different types of directed graph operations allowing one to sequentially build any minimally persistent graph (i.e., persistent graph with a minimal number of edges for a given number of vertices), each intermediate graph being also minimally persistent. We also consider the more generic problem of obtaining one minimally persistent graph from another, which corresponds to the online reorganization of the sensing and control architecture of an autonomous agent formation. We prove that we can obtain any minimally persistent formation from any other one by a sequence of elementary local operations such that minimal persistence is preserved throughout the reorganization process. Finally, we briefly explore how such transformations can be performed in a decentralized way.Keywords
This publication has 14 references indexed in Scilit:
- Switching control for robust autonomous robot and vehicle platoon formation maintenance2007
- Three and higher dimensional autonomous formations: Rigidity, persistence and structural persistenceAutomatica, 2007
- Directed graphs for the analysis of rigidity and persistence in autonomous agent systemsInternational Journal of Robust and Nonlinear Control, 2006
- Optimal sensor placement and motion coordination for target trackingAutomatica, 2006
- Information structures to secure control of rigid formations with leader-follower architecture2005
- Leader-to-Formation StabilityIEEE Transactions on Robotics and Automation, 2004
- Graph rigidity and distributed formation stabilization of multi-vehicle systems2003
- Ad hoc networks for localization and control2003
- Payload technologies and applications for uninhabited air vehicles (UAVs)1997
- On graphs and rigidity of plane skeletal structuresJournal of Engineering Mathematics, 1970