ANU Open Research Repository has been upgraded. We are still working on a few minor issues, which may result in short outages throughout the day. Please get in touch with if you experience any issues.

Directed graphs for the analysis of rigidity and persistence in autonomous agent systems




Hendrickx, Julien M
Anderson, Brian
Delvenne, Jean-Charles
Blondel, Vincent D

Journal Title

Journal ISSN

Volume Title


John Wiley & Sons Inc


We consider in this paper formations of autonomous agents moving in a two-dimensional space. Each agent tries to maintain its distances toward a pre-specified group of other agents constant and the problem is to determine if one can guarantee that the distance between every pair of agents (even those not explicitly maintained) remains constant, resulting in the persistence of the formation shape. We provide here a theoretical framework for studying this problem. We describe the constraints on the distance between agents by a directed graph and define persistent graphs. A graph is persistent if the shapes of almost all corresponding agent formations persist. Although persistence is related to the classical notion of rigidity, these are two distinct notions. We derive various properties of persistent graphs, and give a combinatorial criterion to decide persistence. We also define minimal persistence (persistence with the least possible number of edges), and we apply our results to the interesting special case of cycle-free graphs.



Keywords: Constraint theory; Graph theory; Problem solving; Rigidity; Corresponding agent formations; Cycle-free graphs; Minimal persistence; Persistent graphs; Autonomous agents Autonomous agents; Graph theory; Rigidity



International Journal of Robust and Nonlinear Control


Journal article

Book Title

Entity type

Access Statement

License Rights



Restricted until