Threeandhigherdimensionalautonomousformations:Rigidity …

Loading...

Taking too long?

Reload document

| Open in new tab

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., flocking birds, school-
ing fish, and swarming bees (see e.g. Hubbard, Babak, Sigurd-
sson, & Magnusson, 2004; Janson, Middendorf, & Beekman,
2005). Motivated by these observations, a significant 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 definition 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 fixed coordinates, e.g. vertical or north. For the
control schemes, which are the subject of the paper, civil en-
gineering structures give the first 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 first formalized
using the notion of persistence of a directed graph (Hendrickx,
Anderson, Delvenne, & Blondel, 2005). This term is preferred

In Section 2, the formal definition 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-
ficient 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 define
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 satisfies the constraints on
it once all the other agents are fixed 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 defined for directed
graphs in R2. In this section, we generalize these definitions
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 defined 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 modifica-
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 define 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, defined 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 (defined 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 defined as the |E|×d|V | matrix ⎡ . . . . . . · · · 0 pT(i) − pT(j ) 0 . . . . .. · · · · · · 0 pT(j ) − pT(i) . . . . . . · · · 0 . . . . .. . . . 0 . .. . . . 0 . .. ⎢ ⎢ ⎣ ⎥ ⎥ ⎦ · · · ⎤ . . . . . . . . . . . . . .. . .. . .. . .. 1 The definition of rigidity, involving a quantifier (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 definitions 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 satisfies |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 satisfies
|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 sufficiently 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
satisfied. 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 definition of persistence that guar-
antees the control of a system modelled using directed graph,
we first need to characterize the fact that each agent is trying to
keep the distances from its neighbours constant. Let us also fix
−−→
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 fitting 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 fitting 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 satisfies, 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 fitting representation for a
certain distance set ¯d if all the vertices are at fitting positions
for ¯d. Note that any realization is a fitting representation for its
distance set. We can now give a formal definition of persistence:
A representation p is persistent if there exists (cid:2) > 0 such
that every representation p(cid:5) fitting 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 sufficient 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) fitting
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 fitting 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 fitting 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 fitting position), then all the dis- tance constraints will be satisfied, 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 definitions 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” qualifier 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 sufficient 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)ε} fitting 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) fitting 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
fitting 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) satisfies 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 fitting for ¯d, which contra- dicts our hypothesis. Next, we show the second part of the result. Observe first 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)) fitting 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 first prove (A) that any fitting representation of G∗ for ¯d∗ sufficiently close to p is also a fitting 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 fitting 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 fitting 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 sufficient 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 define the notion of minimal persistence, analo- gously to minimal rigidity defined 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