Rigidity and Persistence of Directed Graphs

Date

2005

Authors

Hendrickx, Julien M
Anderson, Brian
Blondel, Vincent D

Journal Title

Journal ISSN

Volume Title

Publisher

Institute of Electrical and Electronics Engineers (IEEE Inc)

Abstract

Motivated by [1], [2] and [3], we consider here formations of autonomous agents in a 2-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 structure of the formation will persist, i.e., if the distance between any pair of agents will remain constant. A natural way to represent such a formation is to use a directed graph. We provide a theoretical framework for this problem, and give a formal definition of persistent graphs (a graph is persistent if almost all corresponding agents formations persist). Note that although persistence is related to rigidity (concerning which much is known [4]), these are two distinct notions. We then derive various properties of persistent graphs, and give a combinatorial criterion to decide persistence. We also define the notion of minimal persistence (persistence with least number of edges), and eventually, we apply these notion to the interesting special case of cycle-free graphs.

Description

Keywords

Keywords: Directed graphs; Persistence; Persistent graphs; Combinatorial mathematics; Intelligent agents; Optimization; Problem solving; Graph theory

Citation

Source

Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference 2005

Type

Conference paper

Book Title

Entity type

Access Statement

License Rights

DOI

10.1109/CDC.2005.1582484

Restricted until