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 repository.admin@anu.edu.au if you experience any issues.
 

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

Date

2007

Authors

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

Journal Title

Journal ISSN

Volume Title

Publisher

John Wiley & Sons Inc

Abstract

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.

Description

Keywords

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

Citation

Source

International Journal of Robust and Nonlinear Control

Type

Journal article

Book Title

Entity type

Access Statement

License Rights

DOI

10.1002/rnc.1145

Restricted until

2037-12-31