Abstract | ||
---|---|---|
In this paper, we study the construction and trans- formation of two-dimensional 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 multi-agent formations. In the context of mobile autonomous agent for- mations, 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 on-line 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. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1109/TAC.2008.920239 | IEEE Trans. Automat. Contr. |
Keywords | Field | DocType |
Autonomous agents,Australia,Shape,Intelligent vehicles,Remotely operated vehicles,Underwater vehicles,Robot kinematics,Land vehicles,Road vehicles,Mobile robots | Graph operations,Autonomous agent,Mathematical optimization,Directed graph,Theoretical computer science,Multi-agent system,Null graph,Artificial intelligence,Critical graph,Mathematics,Feedback arc set,Complement graph | Journal |
Volume | Issue | ISSN |
53 | 4 | 0018-9286 |
Citations | PageRank | References |
3 | 0.60 | 6 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Julien M. Hendrickx | 1 | 772 | 77.11 |
Changbin Yu | 2 | 845 | 75.14 |
Brian D. O. Anderson | 3 | 3727 | 471.00 |
Vincent D. Blondel | 4 | 1880 | 184.86 |
Vincent D. Blondel | 5 | 173 | 6.84 |