17th International Symposium on
Mathematical Theory of Networks and Systems
Kyoto International Conference Hall, Kyoto, Japan, July 24-28, 2006

MTNS 2006 Paper Abstract


Paper TuA13.2

Hendrickx, Julien M. (Univ. catholique de Louvain), Fidan, Baris (The Australian National Univ. and National ICT Australia Ltd), Yu, Changbin (The Australian National Univ. and National ICT Australia Ltd.), Anderson, Brian D O (Australian National Univ.), Blondel, Vincent (Univ. Catholique de Louvain)

Elementary Operations for the Reorganization of Minimally Persistent Formations

Scheduled for presentation during the Mini-Symposium "Control of Mobile Multiagent Systems" (TuA13), Tuesday, July 25, 2006, 10:50−11:15, Room 101

17th International Symposium on Mathematical Theory of Networks and Systems, July 24-28, 2006, Kyoto, Japan

This information is tentative and subject to change. Compiled on June 23, 2024

Keywords Group formation, Systems on graphs, Coordinated control


In this paper we study the construction and transformation of two-dimensional minimally persistent graphs. Persistence is a generalization to directed graphs of the undirected notion of rigidity. In the context of moving autonomous agent formations, persistence characterizes the efficacy of a directed structure of unilateral distances constraints seeking to preserve a formation shape. 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 an autonomous agent formation. We show 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.