Automatica 43 (2007) 387 – 402

www.elsevier.com/locate/automatica

Three and higher dimensional autonomous formations: Rigidity, persistence

and structural persistence(cid:2)

Changbin Yu a,b,∗, Julien M. Hendrickx c, Barı¸s Fidan a,b,

Brian D.O. Anderson a,b, Vincent D. Blondel c

aNational ICT Australia Ltd., Locked Bag 8001, Canberra ACT 2601, Australia

bResearch School of Information Sciences and Engineering, The Australian National University, Canberra ACT 2601, Australia

cDepartment of Mathematical Engineering, Université Catholique de Louvain, Avenue Georges Lemaitre 4, B-1348 Louvain-la-Neuve, Belgium

Received 26 August 2005; received in revised form 17 January 2006; accepted 17 August 2006

Available online 10 January 2007

Abstract

In this paper, we generalize the notion of persistence, which has been originally introduced for two-dimensional formations, to Rd

for d (cid:2) 3,

seeking to provide a theoretical framework for real world applications, which often are in three-dimensional space as opposed to the plane.

Persistence captures the desirable property that a formation moves as a cohesive whole when certain agents maintain their distances from

certain other agents. We verify that many of the properties of rigid and/or persistent formations established in R2 are also valid for higher

dimensions. Analysing the closed subgraphs and directed paths in persistent graphs, we derive some further properties of persistent formations.

We also provide an easily checkable necessary condition for persistence. We then turn our attention to consider some practical issues raised

in multi-agent formation control in three-dimensional space. We display a new phenomenon, not present in R2, whereby subsets of agents

can behave in a problematic way. When this behaviour is precluded, we say that the graph depicting the multi-agent formation has structural

persistence. In real deployment of controlled multi-agent systems, formations with underlying structurally persistent graphs are of interest. We

analyse the characteristics of structurally persistent graphs and provide a streamlined test for structural persistence. We study the connections

between the allocation of degrees of freedom (DOFs) across agents and the characteristics of persistence and/or structural persistence of a

directed graph. We also show how to transfer DOFs among agents, when the formation changes with new agent(s) added, to preserve persistence

and/or structural persistence.

(cid:3) 2006 Elsevier Ltd. All rights reserved.

Keywords: Autonomous agents; Formations control; Structural persistence; Graph theory

1. Introduction

Multi-agent systems have attracted considerable attention

recently as witnessed by the explosion of papers in the area (see

e.g. Baillieul & Suri, 2003; Das, Fierro, Kumar, & Ostrowski,

2002; Eren, Anderson, Morse, Whiteley, & Belhumeur, 2004;

(cid:2) Parts of this paper were presented at The First International Workshop

on Multi-Agent Robotic Systems sponsored by the IFAC. This paper was

recommended for publication in revised form by Associate Editor Ioannis

Paschalidis under the direction of Editor Ian Petersen.

∗

Corresponding author. Tel.: +61 2 61256242; fax: +61 2 61258660.

E-mail addresses: Brad.Yu@nicta.com.au (C. Yu),

Hendrickx@inma.ucl.ac.be (J.M. Hendrickx), Baris.Fidan@nicta.com.au (B.

Fidan), Brian.Anderson@nicta.com.au (B.D.O. Anderson),

Blondel@inma.ucl.ac.be (V.D. Blondel).

0005-1098/$ – see front matter (cid:3) 2006 Elsevier Ltd. All rights reserved.

doi:10.1016/j.automatica.2006.08.025

Gazi & Passino, 2003; Jadbabaie, Lin, & Morse, 2003; Lin,

Francis, & Maggiore, 2005; Marshall, Broucke, & Francis,

1963; Olfati-Saber & Murray, 2002, 2004; Ren & Beard, 2004;

Tanner, Pappas, & Kumar, 2004). As illustrated in these refer-

ences, many control tasks for multi-agent systems require coor-

dinated motion of the agents in well-structured formations and

hence acquisition and maintenance of the formation structure

as well as the distance between nominated pairs of agents. The

phenomena of formation acquisition and maintenance can be

observed in nature in many forms, e.g., ﬂocking birds, school-

ing ﬁsh, and swarming bees (see e.g. Hubbard, Babak, Sigurd-

sson, & Magnusson, 2004; Janson, Middendorf, & Beekman,

2005). Motivated by these observations, a signiﬁcant number of

recent studies have been performed in engineering applications

including UAVs, roving robots, collection of ships, submarines,

388

C. Yu et al. / Automatica 43 (2007) 387 – 402

etc (see e.g. Ceccarelli, Di Marco, Garulli, & Giannitrapani,

2005; Ihle, Jouffroy, & Fossen, 2005).

because this notion is not equivalent to the simple application

of the deﬁnition of rigidity to directed graphs.

Note here that we distinguish between two formation con-

trol tasks: (i) moving the whole formation from position A to

B; (ii) maintaining the shape of the formation while the whole

formation is moving. These are clearly different problems, and

this paper focuses on (ii). Note that in large biological forma-

tions in nature, it appears very unlikely that all members of

the formation share a common view about where to go. Some

members will just play the role of maintaining the shape, i.e.,

focus on (ii). This is consistent with a common idea in the liter-

ature concerning man-made formations, that some agents have

leadership responsibility (and thus are concerned with moving

the formation from A to B), and the rest (forming the majority)

are followers.

Consequently, one needs to consider the following two ques-

tions in designing control structures and for such multi-agent

systems: what can be measured, and what should be controlled?

Possible measurements include distance to neighbours,

angular information between neighbours, angular information

relative to ﬁxed coordinates, e.g. vertical or north. For the

control schemes, which are the subject of the paper, civil en-

gineering structures give the ﬁrst clue: if we maintain enough

lengths/distances, we will retain rigidity, even with pinjoints.

This indicates that one can imagine controlling lengths only,

without worrying about active angle control in a formation.

Note also that we do not need to control every single length; ac-

tively controlling some, the rest are consequentially maintained.

By all means, the control effort (as measured by the number of

actively controlled lengths) could be more than the minimum

possible value for safety’s sake, but in general the control effort

should grow linearly with the number of formation elements. It

is yet to be determined what is the best scheme, i.e., one based

on lengths, or lengths and angles, etc. (and the issue of what is

best will naturally depend on the sensor and possibly actuator

settings). We know that if one can control based on lengths,

one can then push the theory out to cope also with angular in-

formation of certain sorts (Eren, Whiteley, Morse, Belhumeur,

& Anderson, 2003).

The problem of maintaining the shape of a moving formation

has been previously studied with graphs depicting the control

architecture as follows (Eren et al., 2004; Olfati-Saber & Mur-

ray, 2002): to each agent corresponds a vertex, and for each

agent (vertex) pair i, j there is an edge (i, j ) if the distance

between i and j must be actively maintained. Note there is an

implicit assumption that this is a joint task for both agents,

which is often not the case for autonomous agents. The purpose

of this paper is to focus on lengths/distances with the novel

thrust being to hand the control task to just one agent rather

than both, at the end of a particular length. In the recent control

literature, the characterization of a system of the above type

had started to be attempted under the name of rigidity of a

directed graph (Baillieul & Suri, 2003; Eren, Whiteley, Ander-

son, Morse, & Belhumeur, 2005; Lin et al., 2005; Olfati-Saber

& Murray, 2002), and appears to have been ﬁrst formalized

using the notion of persistence of a directed graph (Hendrickx,

Anderson, Delvenne, & Blondel, 2005). This term is preferred

In Section 2, the formal deﬁnition of persistence given in

Hendrickx, Anderson et al. (2005) is generalized to Rd

for

d (cid:2)3, seeking to provide a theoretical framework for real world

applications, which often are in three-dimensional space as

opposed to the plane. Persistence has the following intuitive

meaning: a formation (and its underlying graph) is persistent

if, provided that all the agents are trying to satisfy their dis-

tance constraints, they can in fact do that, and at the same time,

a consequence of this fact is that the global structure of the

formation is preserved, i.e., when the formation moves, it nec-

essarily moves as a cohesive whole. We will see that rigidity

of the underlying undirected graph is a necessary but not suf-

ﬁcient condition. This will lead us to the notion of constraint

consistence of graph, which is the additional condition for a

rigid graph (formation) to be persistent. Intuitively, a formation

is constraint consistent if every agent is actually able to sat-

isfy all its distance constraints provided that all the others are

trying to do so. We will then argue that a graph is persistent if

and only if it is rigid and constraint consistent. In Section 3, we

generalize some of the main properties of persistent graphs to

three- and higher dimensional graphs, drawing on established

results in R2 (Hendrickx, Anderson et al., 2005).We also deﬁne

minimal persistence in Rd

for d (cid:2)3 analogously to minimal

rigidity. We discuss some differences and similarities between

the two notions, and give a characterization of minimally per-

sistent graphs. In Section 4, we reason about the persistence of

closed subgraphs of persistent graphs and use this reasoning

to analyze the directed paths in persistent graphs (Hendrickx,

Fidan, Yu, Anderson, & Blondel, 2005). As results of this anal-

ysis, we present some further properties of persistent graphs

and an easily checkable necessary condition for persistence.

We then use this material to focus on a practical issue

related to persistence. We demonstrate that a persistent for-

mation may suffer from a practical problem where any single

agent can move to a position which satisﬁes the constraints on

it once all the other agents are ﬁxed but it is not possible to

satisfy all the constraints on all the agents at the same time.

In Section 5, we formally characterize this problem, which

is closely associated with unsafe control of a formation in

practical three-dimensional applications. We then introduce

the notion of a structurally persistent graph, a class of per-

sistent graphs free of the above problem. In real deployment

of control of multi-agent systems, formations with underlying

structurally persistent graphs are of interest. It is established

in Section 5 importantly that in two dimensions, structural

persistence and persistence are equivalent. We also provide a

streamlined test of structural persistence.

In Section 6, we focus on the connections between allocation

of degrees of freedom (DOFs) across agents and the character-

istics of persistence and/or structural persistence of a directed

graph. We also show how to transfer DOFs among agents, when

the formation changes with new agent(s) added, to preserve

persistence and/or structural persistence. We study cycle-free

graphs in R3 and show some more powerful results for this

special case, including the existence of a linear time criterion to

C. Yu et al. / Automatica 43 (2007) 387 – 402

389

verify the cycle-free property and to decide persistence, which

automatically assures structural persistence. The paper is ended

with some concluding remarks given in Section 7.

2. Rigidity and persistence

In Hendrickx, Anderson et al. (2005), rigidity, persistence,

and some other related notions have been deﬁned for directed

graphs in R2. In this section, we generalize these deﬁnitions

to be applicable for any space Rd

, d ∈ {2, 3, . . .}. Some of the

terms we use such as “rigidity” are undirected notions, i.e., no-

tions that are deﬁned for undirected graphs. Notions for undi-

rected graphs can of course also be applied to directed graphs,

e.g., we call a directed graph rigid if and only if its underlying

undirected graph is rigid. Note that, in directed graphs, rigidity

and the other undirected notions are not affected by modiﬁca-

tion of the edge directions.

In Rd (d ∈ {2, 3, . . .}), a representation of an undirected

graph G = (V , E) with vector set V and edge set E is a function

p : V → Rd

is the position of the

vertex i, and deﬁne the distance between two representations

p1 and p2 of the same graph by

. We say that p(i) ∈ Rd

d(p1, p2) = max

i∈V

||p1(i) − p2(i)||.

A distance set ¯d for G is a set of distances dij > 0, deﬁned for

all edges (i, j ) ∈ E. A distance set is realizable if there exists a

representation p of the graph for which ||p(i) − p(j )|| = dij for

all (i, j ) ∈ E. Such a representation is then called a realization.

Note that each representation p of a graph induces a realizable

distance set (deﬁned by dij = ||p(i) − p(j )|| for all (i, j ) ∈ E),

of which it is a realization.

A representation p is rigid if there exists (cid:2) > 0 such that

for all realizations p(cid:5) of the distance set induced by p and

satisfying d(p, p(cid:5)) < (cid:2), there holds ||p(cid:5)(i) − p(cid:5)(j )|| = ||p(i) −
p(j )|| for all i, j ∈ V . (We say in this case that p and p(cid:5)
are congruent).1 A graph is said to be generically rigid if
almost all its representations are rigid, in fact if there exists an
open dense set in which all representations are rigid (Whiteley,
1997). Note that the reasons for which we only require almost
all representations to be rigid instead of all of them will be
detailed in Remark 4.
A widely used approach in the analysis of rigidity is the
use of linear algebraic tools such as the rigidity matrix (Tay &
Whiteley, 1985; Whiteley, 1996a, 1997). For a graph G=(V , E)
in Rd
, the rigidity matrix R(G) of G is deﬁned as the |E|×d|V |
matrix
⎡
.
. . .
.
.
· · · 0 pT(i) − pT(j )
0
.
. . .
..
· · ·
· · · 0 pT(j ) − pT(i)
.
. . .
.
.
· · · 0
.
. . .
..
.
.
.
0
.
..
.
.
.
0
.
..
⎢
⎢
⎣
⎥
⎥
⎦
· · ·
⎤
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
..
.
..
.
..
1 The deﬁnition of rigidity, involving a quantiﬁer (cid:2), is standard (Tay &
Whiteley, 1985; Whiteley, 1996b). Any continuous large perturbation neces-
sarily starts with a small perturbation. If small perturbations not preserving
congruency exist, the same is true for large perturbations. Additionally, focus-
ing on small perturbations allows study of the rigidity problem using linear
algebraic methods, which is not the case for large perturbations.
where each row
[0 · · · 0 pT(i) − pT(j ) 0 · · · 0 pT(j ) − pT(i) 0 · · · 0]
corresponds to an edge (i, j ) ∈ E, pT(i) − pT(j ) is a row d-
vector in the d columns corresponding to vertex i. A standard
result is that a graph G with at least d vertices is rigid if and
only if for almost all representations, R(G) has rank d|V | −
d(d + 1)/2, which is the maximum rank an R(G) can have
(Tay & Whiteley, 1985; Whiteley, 1996a, 1997).
Another notion that is widely used in rigidity analysis is min-
imal rigidity. A graph is called minimally rigid if it is rigid and
if there exists no rigid graph with the same number of vertices
and a smaller number of edges. Equivalently, a graph is mini-
mally rigid if it is rigid and if no single edge can be removed
without losing rigidity. These two equivalent deﬁnitions of min-
imal rigidity lead to the following theorem, a version of which
is presented as the “Necessary Counts Theorem” in Whiteley
(1996a, 1997).
Theorem 1. If a graph G = (V , E) in Rd (d ∈ {2, 3, . . .})
with at least d vertices is rigid, then there exists a subset E(cid:5)
of edges such that G(cid:5) = (V , E(cid:5)) is minimally rigid. This also
implies the following:
• |E(cid:5)| = d|V | − d(d + 1)/2.
• Any subgraph G(cid:5)(cid:5) = (V (cid:5)(cid:5), E(cid:5)(cid:5)) of G(cid:5) with at least d vertices
satisﬁes |E(cid:5)(cid:5)|(cid:3)d|V (cid:5)(cid:5)| − d(d + 1)/2.
Proof. G is rigid if and only if the rigidity matrix R(G) has
rank d|V | − d(d + 1)/2. Therefore, there exists a set of d|V | −
d(d + 1)/2 linearly independent rows in the matrix R(G), cor-
responding to a set E(cid:5) ⊂ E of d|V | − d(d + 1)/2 independent
edges. Since the submatrix R(cid:5) composed of these rows has rank
d|V | − d(d + 1)/2, G(cid:5) = (V , E(cid:5)) is rigid. Moreover, since R(cid:5) is
full rank, G(cid:5) is minimally rigid and |E(cid:5)| = d|V | − d(d + 1)/2.
Now, assume that there exists a subgraph G(cid:5)(cid:5) = (V (cid:5)(cid:5), E(cid:5)(cid:5)) of G(cid:5)
for which |E(cid:5)(cid:5)| > d|V (E(cid:5)(cid:5))| − d(d + 1)/2. Then the rows of R(cid:5)

corresponding to the edges in E(cid:5)(cid:5) have to be linearly dependent,

noting that the entries of these rows corresponding to the ver-

tices outside V (cid:5)(cid:5) are all zero. For otherwise, the matrix R(G(cid:5)(cid:5))

would have a rank greater than d|V (cid:5)(cid:5)| − d(d + 1)/2, which as

mentioned above is impossible for a rigidity matrix. However,

this contradicts the fact that R(cid:5) is full-rank. Therefore, each

subgraph G(cid:5)(cid:5) = (V (cid:5)(cid:5), E(cid:5)(cid:5)) of G(cid:5) with at least d vertices satisﬁes

|E(cid:5)(cid:5)|(cid:3)d|V (cid:5)(cid:5)| − d(d + 1)/2. (cid:4)

Lemma 2. Let G = (V , E) be a minimally rigid graph in Rd

(d ∈ {2, 3, . . .}) and G(cid:5) = (V (cid:5), E(cid:5)) a subgraph of G such that

|E(cid:5)| = d|V (cid:5)| − d(d + 1)/2. Then, G(cid:5) is minimally rigid.

Proof. Since G is minimally rigid, the edge set E is linearly

independent. Therefore, E(cid:5) ⊆ E is linearly independent as well.

Since |E(cid:5)| = d|V (cid:5)| − d(d + 1)/2, this implies that the rigidity

matrix of G(cid:5) = (V (cid:5), E(cid:5)) is full rank, i.e., G(cid:5) is minimally rigid.

(cid:4)

As mentioned above, rigidity is an undirected notion, and

as noted in Hendrickx, Anderson et al. (2005), rigidity of a

390

C. Yu et al. / Automatica 43 (2007) 387 – 402

representation implies that if an external observer (or some

physical properties) ensures that the distance between the posi-

tions of any pair of vertices connected by an edge remains con-

stant, then all the sufﬁciently close realizations of the induced

distance set are congruent to each other. But, in a typical sys-

tem of autonomous agents, there is no such external observer.

Each agent is only aware of its own distance constraints, and

can “move freely” as long as these particular constraints are

satisﬁed. The system therefore more naturally corresponds to

a directed graph G = (V , E), where each agent corresponds to

a vertex in V, and for each agent (vertex) pair i, j there is a

−−→

(i, j ) ∈ E from i to j if i has a constraint on the

directed edge

distance it must actively maintain from j.

For example, agents that have only one constraint can move

along a hyper-sphere centred on the position of the only other

agent of which they are aware. So, it could happen that be-

cause one agent i can lie anywhere on such a hyper-sphere, it

becomes impossible for another agent j to satisfy all its con-

straints, especially if j has d + 1 or more constraints. So, in

order to have a more formal deﬁnition of persistence that guar-

antees the control of a system modelled using directed graph,

we ﬁrst need to characterize the fact that each agent is trying to

keep the distances from its neighbours constant. Let us also ﬁx

−−→

desired distances dij > 0, ∀

(i, j ) ∈ E and a representation p.

−−→

(i, j ) ∈ E is active if ||p(i)−p(j )||=dij ,

We say that the edge

i.e., the actual distance equals what is desired. We also say that

the position of the vertex i ∈ V is ﬁtting for the distance set ¯d

if it is not possible to increase the set of active edges leaving

i by modifying the position of i while keeping the positions of

the other vertices unchanged. More formally, given a represen-

tation p, the position of vertex i is ﬁtting if there is no p∗ ∈ Rd

for which the following strict inclusion holds:

−−→

(i, j ) ∈ E : ||p(i) − p(j )|| = dij }

{

⊂ {

−−→

(i, j ) ∈ E : ||p∗ − p(j )|| = dij }.

(1)

This condition intuitively means that the agent i cannot satisfy

additional distance constraints without breaking some that it

already satisﬁes, as shown in the two-dimensional example in

Fig. 1, which is drawn from Hendrickx, Anderson et al. (2005).

A representation of a graph is a ﬁtting representation for a

certain distance set ¯d if all the vertices are at ﬁtting positions

for ¯d. Note that any realization is a ﬁtting representation for its

distance set. We can now give a formal deﬁnition of persistence:

A representation p is persistent if there exists (cid:2) > 0 such

that every representation p(cid:5) ﬁtting for the distance set induced

by p and satisfying d(p, p(cid:5)) < (cid:2) is congruent to p. A graph is
then generically persistent if almost all its representations are
persistent.
Next, we argue that a generically persistent graph in Rd
(d ∈
{2, 3, . . .}) is always generically rigid, and give a necessary and
sufﬁcient condition for a generically rigid graph to be generi-
cally persistent. This condition is called the generic constraint
consistence of a graph. A representation p is constraint consis-
tent if there exists (cid:2) > 0 such that any representation p(cid:5) ﬁtting

for the distance set ¯d induced by p and satisfying d(p, p(cid:5)) < (cid:2)
is a realization of ¯d. Intuitively, the constraint consistence of a
a
c
1
4
2
b
2
1
3
3
c
c
ee
4
Fig. 1. Suppose that d41 = qd
ﬁtting because it only makes
(4, 1) and
= d43 = c. The position of 4 in (a) is not
42
→
(4, 1) active while there exists a position that
→
(4, 3) active. On the other hand, its position in
would make both
(b) is ﬁtting because no point can be at the same time at a distance c from
1, 2 and 3.
→
representation means that if each agent tries to satisfy its dis-
tance constraints (i.e., is at a ﬁtting position), then all the dis-
tance constraints will be satisﬁed, or equivalently, no agent will
be in a situation where it cannot satisfy some constraint. The il-
lustration of such a situation in R2 can be found in Hendrickx,
Anderson et al. (2005). Again, we say that a graph is generi-
cally constraint consistent if almost all its representations are
constraint consistent.
We have the following useful equivalences for directed
graphs in any d-dimensional space Rd
(d ∈ {2, 3, . . .}), which
have already been established for R2 in Hendrickx, Anderson
et al. (2005).
Theorem 3. A representation in Rd
(d ∈ {2, 3, . . .}) is persis-
tent if and only if it is rigid and constraint consistent. A graph
in Rd
(d ∈ {2, 3, . . .}) is generically persistent if and only if it
is generically rigid and generically constraint consistent.
The proof of Theorem 3 is identical to the two-dimensional
case presented in Hendrickx, Anderson et al. (2005) and is
omitted.
Remark 4. In our deﬁnitions of generic rigidity, persistence
and constraint consistence, a graph has a generic property if
almost all its representations have the property. Some perti-
nent discussion on our use of “generic” and “almost all” can
be found in Hendrickx, Anderson et al. (2005) and Tay and
Whiteley (1985). One reason for using these terms in Rd
(d ∈
{2, 3, . . .}) is to exclude the problems arising from having d +1
or more vertices lying on a d1-dimensional hyper-surface where
d1 (cid:3)d − 1. In the sequel however, we shall frequently assume
the “generic” qualiﬁer applies without explicit use of the word,
when no misunderstanding is likely to occur.
3. Characterization of persistent graphs
In this section, we examine the properties of persistent graphs
in three and higher dimensions. We present the fundamental
results related to persistence and minimal persistence. These
results are comparable to the properties of two-dimensional
C. Yu et al. / Automatica 43 (2007) 387 – 402
391
persistent graphs presented in Hendrickx, Anderson et al.
(2005), and hence the corresponding propositions and lemmas
are given as generic ones that are applicable to R2 as well.
3.1. Persistence
G (i) and d+
We begin characterization of persistent graphs by giving a
lower bound on the number of active edges, and an associated
sufﬁcient condition for a graph to be constraint consistent. In
the sequel, d−
G (i) designate respectively the in- and
out-degree of the vertex i in the graph G. When no confusion
is possible about the graph, we will use d−(i) and d+(i). Note
also that the results given in this section and their proofs are very
similar to the two-dimensional case presented in Hendrickx,
Anderson et al. (2005).
Lemma 5. Let p be a representation of a graph G = (V , E) in
Rd
(d ∈ {2, 3, . . .}), and i a vertex of this graph. If the posi-
tion p(i) does not lie on any (d − 1)-dimensional hyper-plane
containing d or more of its neighbours, then there exists (cid:2) > 0

such that in every representation p(cid:5) ∈ B(p, ε)(cid:5){ ¯p : V →

Rd |d(p, ¯p)(cid:3)ε} ﬁtting for the distance set induced by p, the

number of active edges leaving i is at least min(d, d+(i)). Con-

sequently, a graph in which all the vertices have an out-degree

smaller than or equal to d is always generically constraint con-

sistent.

Proof. We follow the same steps as in the proof of Lemma 1

in Hendrickx, Anderson et al. (2005). Let us consider a repre-

sentation p(cid:5) ﬁtting for the distance set ¯d induced by p. First, if

the out-degree of the vertex i is less than d then the set of pos-

sible positions that could make all the edges leaving i active is

always non-empty, e.g., this set is equal to Rd

for d+(i) = 0,

a circle for d+(i) = d − 1, etc. The position p(cid:5)(i) will then be

ﬁtting if and only if all the d+(i) = min(d, d+(i)) edges are

active.

Second, if the out-degree of i is greater than or equal to d,

we need the following result, which can be shown using simple

geometric and continuity arguments:

Suppose there are given d + 1 points a1, a2, . . . , ad+1 ∈ Rd

that do not all lie on any (d − 1)-dimensional hyper-plane.

Let dkl denote the distance between each pair ak, al where

k (cid:9)= l. There exists an (cid:2)(a1, a2, . . . , ad+1) > 0 such that for any

d ∈ Rd

satisfying ||ak −a(cid:5)

a(cid:5)

k|| < (cid:2)(a1, a2, . . . , ad+1)
1
∈ Rd
for k = 1, 2, . . . , d, there exists a(cid:5)
k −
d+1
a(cid:5)
|| = dk(d+1) for k = 1, 2, . . . , d.
d+1
We can now show that
such that ||a(cid:5)
, . . . , a(cid:5)
, a(cid:5)
2
(cid:2)i =
min
(i,j1),...,(i,jd )∈E
(cid:2)(p(i), p(j1), . . . , p(jd ))
(2)
satisﬁes the required condition in the statement of Lemma
5. Let us indeed suppose that there is a representation p(cid:5) ∈
B(p, (cid:2)) such that less than d active edges are leaving i, and
−−−→
(i, jd ), containing the active
take a set of d edges
edges leaving i if there are any. Observe that by hypothesis,
p(i), p(j1), . . . , p(jd ) do not all lie on any (d −1)-dimensional
hyper-plane. By (2), there exists thus a point p∗ such that
−−−→
(i, j1), . . . ,
||p∗ − p(cid:5)(jk)|| = dik for k = 1, . . . , d, or equivalently a pointp∗
such that the strict inclusion (1) holds. The position p(cid:5)(i) and
the representation p(cid:5) are thus not ﬁtting for ¯d, which contra-
dicts our hypothesis.
Next, we show the second part of the result. Observe ﬁrst
that in almost all representations of the graph G, no vertex
has a position lying on any (d − 1)-dimensional hyper-plane
containing d or more of its neighbours. Let us consider such
a representation p of G for which every vertex i has an out-
degree d+(i)(cid:3)d, and the induced distance set ¯d. If we take
(cid:2)(cid:5) < (cid:2)i, ∀i ∈ V where the (cid:2)i comes from (2) for each vertex, then
for any representation p(cid:5) ∈ B(p, (cid:2)(cid:5)) ﬁtting for ¯d, each vertex
will be left by min(d, d+(i))=d+(i) active edges, so that all the
edges will be active. Every such p(cid:5)is thus a realization of ¯d, and
the representation p is thus constraint consistent. As we already
mentioned, this can be done for almost all representations of G,
which is therefore also generically constraint consistent. (cid:4)
The next proposition which is the generalization of Propo-
sitions 1 and 2 in Hendrickx, Anderson et al. (2005) for any
arbitrary dimension d ∈ {2, 3, . . .}, allows us to delete edges
in a persistent (constraint consistent) graph and maintain per-
sistence (constraint consistence).
Proposition 6. A persistent graph in Rd
(d ∈ {2, 3, . . .}) re-
−−→
(i, j ) for which
mains persistent after deletion of any edge
d+(i)(cid:2)d + 1. Similarly, a constraint consistent graph in Rd
(d ∈ {2, 3, . . .}) remains constraint consistent after deletion of
any edge
−−→
(i, j ) for which d+(i)(cid:2)d + 1.
Proof (Sketch). We follow the same steps as in the proof of
the like Proposition 1 in Hendrickx, Anderson et al. (2005).
Let G = (V , E) be a persistent graph having a vertex i with
d+(i)(cid:2)d + 1, and G∗ = (V , E∗) be the graph obtained by
−−→
(i, j ) from G. Let us consider a realization p
removing an edge
of G∗ and the induced distance set ¯d∗. Observe that p can also be
viewed as a representation of G, and the induced distance set is
then ¯d = ¯d∗ ∪{dij }.We assume here that no vertex has a position
that lies on a (d − 1)-dimensional hyper-plane containing d or
more of its neighbours (and thus that Lemma 5 can be applied),
which is the case for almost all realizations. We can ﬁrst prove
(A) that any ﬁtting representation of G∗ for ¯d∗ sufﬁciently close
to p is also a ﬁtting representation of G for ¯d. This then allows
us to prove in (B) the persistence of G∗ in a relatively direct
way. (cid:4)
An interesting corollary of Proposition 6 concerns the total
number of DOFs, which we also call the total DOF count, in
the graph. The number of degrees of freedom (DOF count) of
a vertex is the maximal dimension, over all generic represen-
tations of the graph, of the set of possible ﬁtting positions for
this vertex. Effectively, the DOF count of the vertex v is equal
to max{d − d+(v), 0}. For example, in R3, the DOF counts
of the vertices with zero, one, and two out-degrees are respec-
tively 3, 2, and 1; all the other vertices have zero DOF. Note
that a vertex with zero DOF can have more than one possible
ﬁtting position. Observe indeed that, in almost all situations in
392
C. Yu et al. / Automatica 43 (2007) 387 – 402
Proof (Sketch). We follow the similar steps as in the proof
of Theorem 3 in Hendrickx, Anderson et al., 2005. Let us
consider a d-dimensional graph G = (V , E) and (cid:3)the set of
all the subgraphs S of G satisfying for each vertex i ∈ V ,
d+
S (i) = min(d+
G (i), d). We can prove separately the following
two implications:
• If G is persistent, any S ∈ (cid:3) is rigid.
Since it is possible to obtain S from G only by removing
edges leaving vertices with an out-degree larger or equal to
d + 1, Proposition 6 guarantees the persistence of S and thus
its rigidity.
• If every S ∈ (cid:3) is rigid, G is persistent.
Using Theorem 1, having every S ∈ (cid:3) rigid and hence at
least one rigid subgraph of G implies that G is rigid. Hence,
we just need to, and indeed we can, prove the constraint
consistence of G. (cid:4)
Theorem 9 provides a non-polynomial time algorithm to
check the persistence of any d-dimensional graph for d ∈
{2, 3, . . .}: it is sufﬁcient to check the rigidity of all subgraphs
obtained by deleting the edges leaving vertices with out-degree
larger than or equal to d + 1 until all the vertices have an out-
degree less or equal to d. An algorithm with a smaller com-
plexity would be useful in the case of large graphs, especially
if there is a high number of vertices with high out-degrees, but
no such algorithm is currently available. More discussions on
determining the persistence of two-dimensional directed graphs
in polynomial time can be found in Hendrickx, Anderson et al.
(2005). We also note the existence of a quadratic time algo-
rithm for the cycle-free graphs in R3 (Yu, Hendrickx, Fidan, &
Anderson, 2005), which can be generalized easily to any d ∈
{2, 3, . . .}.
We also deﬁne the notion of minimal persistence, analo-
gously to minimal rigidity deﬁned in Section 2. A persistent
graph in Rd
(d ∈ {2, 3, . . .}) is said to be minimally persistent if
no single edge can be removed without losing persistence. Ob-
viously then, any persistent graph contains a minimally persis-
tent subgraph with the same vertex set. However, an important
difference between the concepts of minimal rigidity and mini-
mal persistence is that a g