1

Bearing Rigidity Theory and its Applications for
Control and Estimation of Network Systems
Life Beyond Distance Rigidity

arXiv:1803.05505v1 [] 14 Mar 2018

Shiyu Zhao

Distributed control and estimation of multi-agent systems
has received tremendous research attention in recent years due
to their potential across many application domains [1], [2].
Here, the term “agent” can represent a sensor, an autonomous
vehicle, or any general dynamical system. These multi-agent
systems are becoming increasingly attractive because of their
robustness against system failure, their ability to adapt to
dynamic and uncertain environments, and their economic
advantages compared to the implementation of more expensive
monolithic systems.
Formation control and network localization are two fundamental tasks for multi-agent systems that enable them to
perform complex missions. The goal of formation control is
to control each agent using local information from neighboring
agents so that the entire team forms a desired spatial geometric
pattern (see [2] for a recent survey on formation control).
While the notion of a formation as a geometric pattern has
a natural meaning for robotic systems, it may also correspond
to more abstract configurations for the system state of a team
of agents. The goal of network localization is to estimate the
location of each agent in a network using locally sensed or
communicated information from neighboring agents [3]–[6].
Network localization is usually the first step that must be
completed before a sensor network provides other services like
positioning mobile robots or monitoring areas of interest.
For a formation control or network localization task, the
type of information available to each agent is an important
factor that determines the design of the corresponding control
or estimation algorithms. Most of the existing approaches
for formation control assume that each agent can obtain the
relative positions of their nearest neighbors. In order to obtain
relative positions in practice, each agent can measure their absolute positions using, for example, GPS, and then share their
positions with their neighbors via wireless communications.
This method is, however, not applicable when operating in
GPS-denied environments such as indoors, underwater, or in
deep space. Furthermore, the absolute accuracy of the GPS
may not meet the requirements of high-accuracy formation
control tasks. Rather than relying on external positioning
systems such as GPS, each agent can use onboard sensors
to sense their neighbors.
Optical cameras are widely used onboard sensors for ground
and aerial vehicles to achieve various sensing tasks due to their
characteristics of being low-cost, light-weight, and low-power.
It is notable that optical cameras are inherently bearing-only
sensors. Specifically, once a target has been recognized in an

Daniel Zelazo

image, its bearing relative to the camera can be calculated
immediately from its pixel coordinate based on the pin-hole
camera model [7, Section 3.3]. As a comparison, the range
from the target to the camera is more complicated to obtain
because it requires additional geometric information of the
target and extra estimation algorithms, which may significantly
increase the complexity of the vision sensing system. Although
stereo cameras can be used to estimate the range of a target
by triangulating the bearings of the target [8], the estimation
accuracy degenerates rapidly as the range of the target increases due to the short baseline between the two cameras.
In summary, since it is easy for vision to measure bearings,
but relatively difficult to obtain accurate range information,
vision can be effectively modeled as a bearing-only sensing
approach in multi-agent formation control [9], [10]. In addition
to cameras, other types of sensors such as passive radars,
passive sonars, and sensor arrays are also able to measure
relative bearings [5], [11], [12].
When each agent is only able to access the relative bearings
to their neighbors, two types of strategies can be adopted to
utilize these bearings to achieve formation control or network
localization. The first strategy is to use bearings to estimate
relative positions. This strategy leads to coupled control and
estimation problems whose global stability is difficult to prove
(see, for example, [13]). Moreover, the estimation of relative
positions depends on an observability condition requiring that
the relative motion of each pair of neighboring agents satisfy
certain conditions [14]. Although this observability condition
can be achieved in certain applications, such as bearing-only
circumnavigation [15]–[18], it is difficult to satisfy in general
formation control tasks where all the agents are supposed to
form a target formation with no relative motions among the
agents. This observability condition is not satisfied either in
network localization because all the sensors are stationary. The
second strategy, which is the focus of this article, is to directly
apply bearings in formation control or network localization
without estimating relative positions. This strategy does not
require relative position estimation, but it requires designing
new control and estimation algorithms that only utilize bearing
measurements.
The purpose of this article is to provide a tutorial overview
of recent advances in the area of bearing-based formation
control and network localization. The first problem addressed
in this article is to understand when the formation control
or network localization problems can be solved using only
inter-neighbor bearing measurements. In fact, any distributed

2

control or estimation task requires certain fundamental architectural conditions of the multi-agent system. For example,
in consensus problems, a network must possess a spanning
tree in order to ensure the states of different agents converge
to the same value [19]–[22]. For bearing-based formation
control and network localization, there is also an architectural
requirement to solve these problems - this property is known
as bearing rigidity. The bearing rigidity theory, also called parallel rigidity theory in the literature, was originally introduced
for computer-aided design [23] and has received increasing
attention in recent years due to its important applications in
bearing-based control and estimation problems [24]–[28]. The
bearing rigidity theory studies the fundamental problem of
under what conditions can the geometric pattern of a network
be uniquely determined if the bearing of each edge in the
network is fixed.
The bearing rigidity theory can be interpreted as an analogous theory for the classic rigidity theory based on interneighbor distances, which is referred to as distance rigidity
theory in this article. The classic distance rigidity theory
studies the problem of under what conditions can the geometric pattern of a network be uniquely determined if the
length (distance) of each edge in the network is fixed. It
is a combinatorial theory for characterizing the stiffness or
flexibility of structures formed by rigid bodies connected by
flexible linkages or hinges. The study of distance rigidity has
a long history as a formal mathematical discipline [29]–[36].
In recent years, it has played a fundamental role in distancebased formation control [37]–[45] and distance-based network
localization [4], [5], [46]. One goal of this article is to compare
the distance and bearing rigidity theories by highlighting their
similarities and differences.
This article addresses three important applications of the
bearing rigidity theory in the area of the distributed control and
estimation of multi-agent systems, briefly described below.
(a) Bearing-Based Network Localization: Consider a network
of stationary nodes where only a subset of the nodes
know their own absolute positions - these special nodes
are referred to as the anchors while the other nodes are
called followers. Suppose each follower node is able to
measure the relative bearings of their neighbors and share
the estimates of their own positions with their neighbors
by wireless communication. The aim of bearing-based
network localization is to localize the follower nodes
using the bearing measurements and the anchors’ absolute
positions [6], [47]–[52]. Here the network localization
problem may also be called network self-localization,
which is usually the first step for a sensor network to
provide other services such as positioning or monitoring.
Network localization is essential for sensor networks in
environments where GPS signals are not available, reliable, or sufficiently accurate.
(b) Bearing-Based Formation Control: Consider a group of
mobile agents where each agent is able to obtain the
relative positions of their neighbors. The aim of bearingbased formation control is to steer the agents from some
initial spatial configuration to a target formation with
a desired geometric pattern predefined by inter-neighbor

bearings [24], [53]–[56]. Since the target formation is
invariant to scaling variations, bearing-based formation
control provides a simple solution for formation scale
control, which is a practically useful technique to adjust
the scale of a formation so that the agents can dynamically
respond to the environment to achieve, for example, obstacle avoidance such as passing through narrow passages
[57], [58]. Note that the bearing-based formation control
problem is dual to the bearing-based network localization
problem. When the agent dynamics are modeled as single
integrators and the leaders are stationary, the two problems
are indeed identical. However, this article also considers
a broader range of cases in the formation control problem - namely formation maneuvering using leaders, and
different models for the agent dynamics, including double
integrators and unicycles.
(c) Bearing-Only Formation Control: The aim of bearingonly formation control is to steer a group of mobile
agents to form a desired geometric pattern predefined by
inter-neighbor bearings. Unlike bearing-based formation
control, bearing-only formation control only requires each
agent to measure the relative bearings of their neighbors,
whereas relative positions are not required to be measured
or estimated [10], [25], [59]–[65]. Bearing-only formation
control provides a novel framework for implementing
vision-based formation control tasks where vision may
be modeled as a bearing-only sensing approach. It also
suggests that distance information may be redundant to
achieve certain formation control tasks.
The notations for networks and formations used throughout
this article are given in “Notations for Networks and Formations”.
B EARING R IGIDITY T HEORY
The bearing rigidity theory studies the problem of under
what conditions the geometric pattern of a network can be
uniquely determined if the bearing of each edge in the network
is fixed. Equivalently stated, bearing rigidity studies as under
what conditions do two networks have the same geometric
pattern if they have the same bearings. To illustrate this idea,
the two networks in Figure 1(a) have the same bearings but
different geometric patterns. As a result, they are not bearing
rigid. The two networks in Figure 1(b) have the same bearings
and the same geometric pattern (modulo a scaling and a
translational factor). The two networks can be shown to be
bearing rigid and the rigorous proof of this result relies on the
theory presented in this section.
There are three different notions of bearing rigidity: bearing rigidity, global bearing rigidity, and infinitesimal bearing
rigidity. The first two are not of practical interest because
they cannot ensure unique geometric patterns of networks.
The third, infinitesimal bearing rigidity, is the most important
one whose properties are discussed in detail in this section.
The precise definitions of the three types of bearing rigidity
are given in “Key Definitions in Bearing Rigidity Theory.”
These definitions are analogous to those in the distance rigidity
theory, which are listed in “Key Definitions in Distance

3

(a)

(b)

Fig. 1: Illustration of bearing rigidity. The networks in (a) are not bearing
rigid because the same inter-neighbor bearings may lead to different geometric
patterns of the networks, for example, a square on the left and a rectangle
on the right. The networks in (b) are bearing rigid because the same interneighbor bearings imply the same geometric pattern though the networks may
differ in terms of translation and scale.

Rigidity Theory” for the purpose of comparison. It is worth
noting that an orthogonal projection matrix plays a key role
in the bearing rigidity theory. The properties of the projection
matrix are summarized in “An Orthogonal Projection Matrix.”
Moreover, note that a bearing, which is represented by a unit
vector, must be expressed in a specific reference frame. In
this article, the bearings in a network are all expressed in a
common reference frame.
Properties of Infinitesimal Bearing Rigidity
Infinitesimal bearing rigidity has two key properties. The
first is a geometric property [28, Theorem 6] that the positions
of the nodes in a network can be uniquely determined up
to a translational and scaling factor by the bearings if and
only if the network is infinitesimally bearing rigid. The second
is an algebraic property [28, Theorem 4] that a network is
infinitesimally bearing rigid in d-dimensional space if and only
if the bearing rigidity matrix RB satisfies
Null(RB ) = span{1n ⊗ Id , p},

(1)

or equivalently,
rank(RB ) = dn − d − 1.

(2)

The definition of the bearing rigidity matrix RB is given in
“Key Definitions in Bearing Rigidity Theory.” Due to the
above two properties, infinitesimal bearing rigidity not only
ensures the unique geometric pattern of a network, but also
can be conveniently examined by a mathematical condition.
Examples of infinitesimally bearing rigid networks are given
in Figure 2.
The notion of infinitesimal bearing rigidity is defined based
on the bearing rigidity matrix. The term “infinitesimal” is
due to the fact that the bearing rigidity matrix is the firstorder derivative (the Jacobian) of the bearing vectors with
respect to the positions of the nodes. It must be noted that
infinitesimal bearing rigidity is a global property in the sense
that the bearings can uniquely determine the geometric pattern
of a network. The term “infinitesimal” may be dropped in this
article when the context is clear.
An infinitesimal bearing motion of a network is a motion of
some nodes that preserves all the bearings. All the infinitesimal
bearing motions of a network form the null space of the bearing rigidity matrix. There are two types of trivial infinitesimal
bearing motions: translational and scaling motions of the entire
network. These two types of trivial motions corresponds to the

(a)

(b)

(c)

(d)

Fig. 2: Examples of infinitesimally bearing rigid networks. The networks in
(a) and (b) are two-dimensional and the networks in (c) and (d) are threedimensional. It can be verified that each of these networks satisfies rank(B) =
dn − d − 1. The networks in (a), (b), and (c) also satisfy the Laman condition
and can therefore be generated using a Henneberg construction. Note that the
two networks in (c) and (d) are infinitesimal bearing rigid but not infinitesimal
distance rigid.

(a)

(b)

(c)

(d)

Fig. 3: Examples of non-infinitesimally bearing rigid networks. The red and
solid arrows represent nontrivial infinitesimal bearing motions that preserves
all the inter-neighbor bearings. These networks are not infinitesimally distance
rigid either because they have nontrivial infinitesimal distance motions (see
the blue/dotted arrows). Note that the infinitesimal distance motions are
perpendicular to the infinitesimal bearing motions.

vectors in span{1n ⊗ Id , p}. As a result, the rank condition
in (1) means that a network is infinitesimally bearing rigid
if and only if all infinitesimal bearing motions are trivial.
This provides an intuitive way to examine bearing rigidity.
For example, the networks in Figure 3 are not bearing rigid
because they have non-trivial infinitesimal bearing motions.
An alternative necessary and sufficient condition for infinitesimal bearing rigidity is based on a special matrix termed
the bearing Laplacian [66]. The bearing Laplacian of a
network can be viewed as a weighted graph Laplacian matrix
with weights that are matrices [67]; thus the bearing Laplacian
not only describes the topological structure of the network,
but also the values of the edge bearings. The definition and
properties of bearing Laplacian are summarized in “Bearing
Laplacian of Networks.” For a network with an undirected
graph, the bearing Laplacian has the same rank and null space
as the bearing rigidity matrix [66, Lemma 2]. It then follows
from (1) and (2) that a network is infinitesimally bearing rigid
if and only if
Null(B) = span{1n ⊗ Id , p},
or equivalently,
rank(B) = dn − d − 1.
Compared to the bearing rigidity matrix, the bearing Laplacian
is more convenient to use because it is symmetric and positive
semi-definite for undirected graphs. When the underlying
graph is directed, the bearing Laplacian and the bearing
rigidity matrix may have different ranks and null spaces [68,
Theorem 4].

4

3

3

1

4

1

1

2

Step 1: vertex addition

3

z

5

2

Step 2: edge splitting

z

4

4
2

4

Step 3: edge splitting

3

1

y

2

x
3
1

4
5

3
1

4
5

2
6

Step 4: edge splitting

3
1

2
7

6

Step 5: edge splitting

4
5

8
7

2
6

Step 6: edge splitting

Fig. 4: Illustration of the Henneberg construction procedure. The Henneberg
construction consists of two basic operations: vertex addition and edge
splitting. In this example, the procedure is used to generate an infinitesimally
bearing rigid network in a three-dimensional ambient space. At each step, the
underlying graph of the network is Laman.

Construction of Infinitesimally Bearing Rigid Networks
The previous discussion provided an overview of the properties defining a bearing rigid network. It is also of interest
to explore how to construct a bearing rigid network by
adding well-placed edges and nodes in a network. Although
a network is jointly characterized by its underlying graph and
the configuration of the nodes, the infinitesimal bearing rigidity
of a network is primarily determined by the underlying graph
rather than its configuration [69, Lemma 2]. Given a graph, if
there exists at least one configuration such that the network is
infinitesimally bearing rigid, then for almost all configurations
the corresponding networks are infinitesimally bearing rigid.
Such graphs are called generically bearing rigid [69]. If a
graph is not generically bearing rigid, then the corresponding
network is not infinitesimal bearing rigid for any configurations. As a result, the key to construct infinitesimally bearing
rigid networks is to construct generically bearing rigid graphs.
One of the most well-known methods for rigid graph construction is the Henneberg construction, originally proposed
for the distance rigidity theory [34]. A Henneberg construction
starting from an edge connecting two vertices results in a
Laman graph [70]. For a tutorial on Laman graphs and
Henneberg construction, see “Laman Graphs and Henneberg
Construction.”
In the bearing rigidity theory, the main result about Laman
graphs is that all Laman graphs are generically bearing rigid
in arbitrary dimensions [69, Theorem 1]. That means if the
underlying graph of a network is Laman, then the network
is infinitesimally bearing rigid for almost all configurations
in an arbitrary dimension. Figure 4 illustrates the Henneberg
construction procedure for a three-dimensional infinitesimally
bearing rigid network whose underlying graph is Laman. Note
that the Laman condition is merely sufficient but not necessary
for generic bearing rigidity. A counterexample is given in
Figure 5, where the graph is generically bearing rigid but
not Laman. However, for networks in the plane, a graph
is generically bearing rigid if and only if it is Laman [69,
Theorem 2].
Since a Laman graph has 2n − 3 edges where n is the

3
1

y

2

x

(a)

(b)

Fig. 5: Example of generically bearing rigid graphs that are not Laman. The
configuration (a) is in the x–y plane and the network is not bearing rigid.
The configuration (b) is three-dimensional and the network is bearing rigid.
It can be verified that rank(B) = dn − d − 1 for the configuration in (b).

number of nodes, 2n − 3 edges are sufficient to guarantee
the bearing rigidity of a network in an arbitrary dimension.
For example, every network in Figure 4 is bearing rigid in
the three dimensional space and has 2n − 3 edges. It must
be noted that 2n − 3 is not the minimum number of edges
required to ensure bearing rigidity. The counterexample given
in Figure 5 shows that a graph with less than 2n−3 edges may
be generically bearing rigid in three dimensions. It is still an
open problem to construct all generically bearing rigid graphs
up to now. A comparison between the bearing and distance
rigidity theories is given in “Comparison of Bearing Rigidity
and Distance Rigidity.”
B EARING -BASED N ETWORK L OCALIZATION
This section introduces the theory of bearing-based network
localization that addresses two fundamental problems. The first
problem is localizability, which describes whether or not a
network can possibly be localized. The second problem is how
to localize a network in a distributed manner if it is localizable.
Consider a network of nodes where the first na nodes are
anchors and the remaining nf (nf = n − na ) nodes are
followers. Let Va = {1, . . . , na } and Vf = V \ Va be the sets
of anchors and followers, respectively. The true positions of
the leaders and followers are denoted as pa = [pT1 , . . . , pTna ]T
and pf = [pTn−na , . . . , pTn ]T , respectively. The aim of network
localization is to determine the positions of the followers
{pi }i∈Vf using the edge bearings {gij }(i,j)∈E and the positions of the anchors {pi }i∈Va . All the inter-neighbor bearings
are expressed in a common reference frame.
Bearing-Based Localizability
Localizing the follower nodes is to solve for p̂i , the estimate
of pi , for all i ∈ Vf , obtained from the set of nonlinear
equations,

 p̂j − p̂i = g , (i, j) ∈ E,
ij
(3)
kp̂j − p̂i k

p̂i = pi ,
i ∈ Va .
The true location p of the network is a feasible solution to
(3). However, there may exist an infinite number of other
feasible solutions. This leads to the definition of localizability.
A network (G, p) is called bearing localizable if the true
position p is the unique feasible solution to (3). It can be
further shown that p is the unique solution to (3) if and only if

5

anchor
follower

anchor
follower
(a)

(d)

(b)

(e)

(a) (G, p)

(c)

(f)

(g)

Fig. 6: Examples of bearing localizable networks. The networks are localizable
because Bf f of each network is nonsingular. The intuitive interpretation is
that every infinitesimal bearing motion involves at least one anchor. Note
that the networks in (b)-(f) are not infinitesimally bearing rigid but they are
localizable.

anchor
follower

(a)

Fig. 8: Illustration of an augmented network for the localization problem. The
augmented network (Ḡ, p) in (b) is obtained from (G, p) by connecting each
pair of anchors in (G, p). Since deleting or adding the edge between any pair
of anchors only changes Baa but not Bf f , (G, p) and (Ḡ, p) have exactly
the same Bf f , and hence they have the same localizability properties.

to examine network localizability (see, for example, Figure 7).
The following condition indicates how many anchors are
required to guarantee bearing localizability. The number of
anchors in a bearing localizable network in Rd must satisfy
[66, Corollary 1]
na ≥

(b)

(c)

(d)

Fig. 7: Examples of networks that not bearing localizable. The black solid
dots represent the anchors and the white dots for followers. The networks
are not localizable because Bf f of each network is singular. The intuitive
interpretation is that the networks have infinitesimal bearing motions that only
correspond to the followers (see the red arrows).

p is the unique global minimizer of the least-squares problem
[66, Lemma 1]
1X X
min J(p̂) =
kPgij (p̂i − p̂j )k2 = p̂T B p̂, (4)
2
p̂∈Rdn
i∈V j∈Ni

subject to p̂i = pi for i ∈ Va . It has been proven that
p is the unique minimizer of (4) if and only if the matrix
Bf f is nonsingular [66, Theorem 1]. The definition of Bf f
is given in “Bearing Laplacian of Networks.” When Bf f is
nonsingular, the positions of the followers can be solved as
p̂∗f = −Bf−1
f Bf a pa . Examples of bearing localizable and nonlocalizable networks are given in Figures 6 and 7, respectively.
While the nonsingularity of Bf f is an algebraic condition
for bearing localizability, it does not give any intuition on
what a bearing localizable network looks like. The following
conditions can provide more intuition for bearing localizable
networks. First of all, a necessary and sufficient rigidity
condition for bearing localizability is that every infinitesimal
bearing motion of a network must involve at least one anchor
[66, Theorem 2]. More specifically, if there exists a nonzero
infinitesimal bearing motion for a network, there would exist
different networks having exactly the same bearings as the true
network. As a result, infinitesimal bearing motions introduce
ambiguities to the localization of the true network. When
the infinitesimal motion involves at least one anchor, the
ambiguities can be resolved by the anchors whose positions
are known, and hence the network location can be uniquely
determined. This rigidity condition provides an intuitive way

(b) (Ḡ, p)

d+1
dim (Null(B))
≥
.
d
d

(5)

Inequality (5) has two important implications. The first is
that every bearing localizable network must have at least two
anchors because (d + 1)/d > 1. The second is that more
anchors are required when the “degree of bearing rigidity” of
the network is weak. Here, the “degree of bearing rigidity”,
characterized by dim(Null(B)), is strongest if dim(Null(B))
reaches the smallest value d+1 (when the network is infinitesimally bearing rigid) and weak if its value is greater than d+1.
The following two conditions explicitly address the relation
between bearing localizability and bearing rigidity. (i) A
sufficient condition for a network to be bearing localizable
is that it is infinitesimally bearing rigid and has at least two
anchors [66, Corollary 3]. The intuition behind this condition
is as follows. If a network is infinitesimally bearing rigid, then
it can be uniquely determined up to a translation and a scaling
factor. If there are at least two anchors, the translational and
scaling ambiguity can be eliminated by the anchors and thus
the entire network can be fully determined. It must be noted
that infinitesimal bearing rigidity is merely sufficient but not
necessary for bearing localizability. For example, the networks
in Figure 6(b)-(f) are bearing localizable but not infinitesimally
bearing rigid. (ii) Let (Ḡ, p) be the augmented network of
(G, p) which is obtained from (G, p) by connecting each
pair of anchors (see Figure 8 for illustration). Then, another
sufficient condition for bearing localizability is that network
(G, p) is bearing localizable if the augmented network (Ḡ, p) is
infinitesimally bearing rigid and there are at least two anchors
[66, Corollary 2]. This condition is more relaxed in the sense
that it does not require (G, p) to be infinitesimally bearing
rigid. When there are more than two anchors, the infinitesimal
bearing rigidity of (Ḡ, p) is merely sufficient but not necessary
for the bearing localizability of (G, p) (see Figure 6(f) for a
counterexample where the network is bearing localizable but
the augmented network is not infinitesimally bearing rigid).
When there are exactly two anchors, the infinitesimal bearing
rigidity of (Ḡ, p) is both necessary and sufficient for the
bearing localizability of (G, p) [66, Theorem 3].

6

Anchor
Follower: initial estimate
Follower: final estiamte

p̂j (t)

−Pgij (p̂i (t) − p̂j (t))

120
100

gij

z (m)

80

p̂i (t)

Fig. 9: The geometric interpretation of the bearing-based control law in (6).
The term Pgij (p̂j − p̂i ) is perpendicular to gij and it aims to steer agent i
such that ĝij (t) aligns with gij .

60
40
20

120100
80

Distributed Localization Protocols

j∈Ni
T
where Pgij = Id −gij gij
. Protocol (6) is actually the gradientdescent protocol for the objective function in the least-squares
problem (4). The geometric interpretation of this protocol
is illustrated in Figure 9. The expression of protocol (6) is
similar to the well-known linear consensus protocols [19],
[21]. The difference is that the weight for each edge in (6)
is an orthogonal projection matrix, while in the consensus
protocols, the weight for each edge is a scalar. This important
distinction leads to very different properties of the dynamical
system. The unique structure of the projection matrix is the
key feature that enables (6) to solve the bearing-based network
localization problem.
The compact matrix form of (6) is

p̂˙f (t) = −Bf f p̂f (t) − Bf a pa ,
where B is the bearing Laplacian of the true network. This
protocol can globally localize the network if and only if the
network is bearing localizable (that is Bf f is nonsingular)
[66, Theorem 4]. Figure 10 shows a simulation example to
demonstrate protocol (6). The impact of measurement noise
on bearing-based network localization has been discussed in
[66].
B EARING -BASED F ORMATION C ONTROL
This section introduces the theory of bearing-based formation control, which studies how to steer a group of agents to
achieve a bearing-constrained target formation using relative
position measurements. In particular, consider a group of
mobile agents where the first n` agents are leaders and
the remaining nf (nf = n − n` ) agents are followers.
Let V` = {1, . . . , n` } and Vf = V \ V` be the sets of
leaders and followers, respectively. The positions of the leaders and followers are denoted as p` = [pT1 , . . . , pTn` ]T and
pf = [pTn−n` , . . . , pTn ]T , respectively. The target formation is
∗
specified by the constant bearing constraints {gij
}(i,j)∈E and
the leader positions {pi (t)}i∈V` . The control objective is to

120 100 80

20

60

40

20

y (m)

x (m)

(a) Initial and final estimates.
200
Localization error (m)

If a network is bearing localizable, a question that follows is
how to localize it in a distributed manner. Suppose each node
has an initial guess of its own position as p̂i (0). The objective
is to design a distributed protocol to drive p̂i (t) → pi for all
i ∈ Vf as t → ∞. This objective can be achieved by the
protocol [66]
X
p̂˙i (t) = −
Pgij (p̂i (t) − p̂j (t)), i ∈ Vf ,
(6)

60 40

150

100

50

0
0

10

20

30

40

50

Time (sec)

(b) Localization error kp̂i (t) − pi k.

Fig. 10: Simulation example to demonstrate the localization protocol in (6).
The real network is located on a three-dimensional surface. It consists of 210
edges and 64 nodes, four of which are anchors. The network is infinitesimally
bearing rigid because rank(B) = 188 = dn − d − 1. Therefore, the network
is localizable since there are more than two anchors. As can be seen, given a
random initial guess, the localization error of each node converges to zero.

control the positions of the followers {pi (t)}i∈Vf such that
∗
gij (t) → gij
as t → ∞ for all (i, j) ∈ E. All the bearings are
expressed in a common reference frame.
Bearing-Based Formation Control of Single Integrators
First, consider the case where the dynamics of each mobile
agent can be modeled as the single integrator
ṗi (t) = ui (t),
where ui (t) is the velocity input to be designed. If the leaders
are stationary, the bearing-based formation control problem
can be solved by [54]
X
∗ (pi (t) − pj (t)),
ṗi (t) = −
Pgij
i ∈ Vf ,
(7)
j∈Ni
∗
∗ T
∗ = Id − g (g ) . The matrix form of the control
where Pgij
ij ij
law is
ṗf (t) = −Bf f pf (t) − Bf ` p` ,

where B is the bearing Laplacian of the target formation.
Control law (7) can globally stabilize a target formation if and
only if the target formation is bearing localizable (that is Bf f
is nonsingular) [54]. Note that control law (7) has a similar
expression to the network localization protocol in (6). In fact,
the bearing-based formation control problem is mathematically

7

j∈Ni

Z
− kI

t

i
(pi (τ ) − pj (τ ))dτ ,

i ∈ Vf , (8)

Leader
Follower

10
z (m)

equivalent to the bearing-based network localization problem
when the target formation is stationary and each agent is a
single integrator.
If the leaders move at a constant nonzero speed, control law
(7) would yield a constant nonzero tracking error. The tracking
error may be eliminated by using the following proportionalintegral control law proposed in [71],
h
X
∗
kp (pi (t) − pj (t))
Pgij
ṗi (t) = −

0
-10
-10
0
10

x (m)

20

0

80

60

40
y (m)

(a) Generated formation maneuver trajectory (the dark area represents an
obstacle).

0

kp=1, kv=3

where kp and kI are constant positive control gains. The target
formation is globally stable under the action of control law (8)
if and only if it is bearing localizable [71].
If the leader velocities are time-varying, control law (8)
would fail to ensure zero tracking errors. The time-varying
case can be handled by the following control law that requires
velocity feedback:
X
∗ [kp (pi (t) − pj (t)) − ṗj (t)] , i ∈ Vf ,
ṗi (t) = −Ki−1
Pgij
j∈Ni

(9)

P
∗ . The stability of control law (9) can
where Ki = j∈Ni Pgij
be proven as below. First, the nonsingularity of Ki can be
guaranteed by the bearing localizability of the target formation
[55, Lemma 3]. Second, multiplying
P Ki on both sides of (9)
∗ (pi (t) − pj (t))
yields ε̇i = −kp εi where εi = kp j∈Ni Pgij
for i ∈ Vf . It follows that εi → 0 as t → ∞ for all i ∈
∗
Vf , and consequently gij → gij
when the network is bearing
localizable.
Under the action of the control laws (8) and (9), the formation is able to perform translational and scaling formation
maneuvers. A translational maneuver means that all the agents
move at a common velocity such that the formation translates
as a rigid body. A scaling maneuver means that the scale
of the formation, which can be described by the distance
from each agent to the formation centroid, varies while the
geometric pattern of the formation is preserved. In order to
achieve the scaling maneuver, the leaders only needs to adjust
the distances among them. One merit of the bearing-based
control laws is that the desired maneuver is only known to the
leaders and the followers are not required to access or estimate
it.

Bearing-Based Formation Control of Double Integrators
Consider the case where the dynamics of each mobile agent
can be modeled as a double integrator
ṗi (t) = vi (t),
v̇i (t) = ui (t),
where ui (t) is the acceleration input to be designed. If
the velocities of the leaders are constant, the bearing-based

Bearing error

8
6
4
2
0
0

10

20

30

40
50
Time (sec)

(b) Total bearing error of the trajectory,

P

60

(i,j)∈E

70

80

∗ k.
kgij (t) − gij

Fig. 11: Simulation example to demonstrate the bearing formation maneuvering control law in (11). The target formation in the example is a threedimensional cube with two leaders and six followers. The translation and
scale of the formation can continuously vary while the formation pattern is
maintained as desired. This example demonstrates that formation scale control
can be used for obstacle avoidance such as passing through narrow passages.

formation control problem can be solved by [55]
ṗi (t) = vi (t),
h
i
X
∗
v̇i (t) = −
Pgij
kp (pi (t) − pj (t)) + kv (vi (t) − vj (t)) ,
j∈Ni

(10)

where i ∈ Vf and kp , kv are positive constant control gains.
Under control law (10), the target formation is globally stable
if it is bearing localizable.
If the velocities of the leaders are time-varying, the following control law requiring acceleration feedback can be used to
track time-varying target formations [55],
ṗi (t) = vi (t),
v̇i (t) = Ki−1

X

h
∗
Pgij
− kp (pi (t) − pj (t))

j∈Ni

i
− kv (vi (t) − vj (t)) + v̇j (t) ,

(11)

P
∗ . The nonsingularity of
where i ∈ Vf and Ki = j∈Ni Pgij
Ki for any i ∈ Vf is guaranteed by the bearing localizability
of the target formation [55, Lemma 3]. Under control law
(11), the target formation is globally stable if and only if
it is bearing localizable. A simulation example is given in
Figure 11 to demonstrate control law (11). In practice, absolute
acceleration can be measured by each agent using, for example, inertial measurement units, and then transmitted to their
neighbors by wireless communication. Due to measurement
errors and transmission delays, the acceleration measurement
is corrupted by errors. However, since the system is linear,

8

15

pj (t)

2
2

1

1

gij (t)

10
∗
−Pgij (t) gij

y (m)

5

3

4

-5

∗
Pgij (t) gij

4

-10
-15

∗
gij

pi (t)

3

0

-10

-5

0

x (m)

5

10

15

20

Fig. 12: Simulation example to demonstrate the control law in (12). In this
example, there are four unicycle agents whose initial positions and heading
angles are chosen randomly. As can be seen, the formation converges to the
target formation whose square geometric pattern is defined by five bearing
vectors.

bounded acceleration errors would cause bounded tracking errors. Bearing-based formation control in the presence of some
other problems including input disturbance, input saturation,
and collision avoidance have been addressed in [55].

Fig. 13: The geometric interpretation of the bearing-only control law in (13).
∗ is perpendicular to the bearing g , the
Since the control term −Pgij gij
ij
control law aims to reduce the bearing error of gij (t) while maintaining the
distance between agents i and j.
Intial formation
Final formation

1

2

2

1

Bearing-Based Formation Control of Unicycles
Suppose the dynamics of agent i ∈ V can be described by
the unicycle model
ẋi = vi cos θi ,
ẏi = vi sin θi ,
θ̇i = wi ,
where pi = [xi , yi ] ∈ R2 is the coordinate of agent i, θi ∈ S 1
is the heading angle, and vi ∈ R and wi ∈ R are the linear
and angular velocities to be designed. Here, S 1 is the onedimensional manifold on the unit circle. The bearing-based
formation control law for unicycles is [72]
X
∗ (pj (t) − pi (t)),
vi = [cos θi sin θi ]
Pgij

Fig. 14: Simulation example to demonstrate the bearing-only formation control
law in (13). In this example, the formation has two agents and one edge. In the
∗ =
target formation, the bearings are in the horizontal direction; that is g12
∗ = [1, 0]T . The initial formation (the dotted line in the figure) does
−g21
not fulfil the desired bearings. Under the control law in (13), the formation
converges to the desired one (the solid line in the figure). Note that the velocity
of each agent is always perpendicular to the bearing and hence the two agents
move on a circle centered at their midpoint. As a result, the centroid and scale
of the formation are invariant.

T

j∈Ni

wi = [− sin θi cos θi ]

X

∗ (pj (t) − pi (t)).
Pgij

(12)

j∈Ni

When there are no leaders, control law (12) ensures global
∗
∗
stability in the sense that gij (t) converges to either gij
or −gij
as t → ∞ given any initial values of pi (0) and θi (0) if the
target formation is infinitesimally bearing rigid [72]. The final
value of θi is not specified in the control law. A simulation
example is shown in Figure 12.
B EARING -O NLY F ORMATION C ONTROL
This section introduces the theory of bearing-only formation
control, which studies how to steer a group of agents to
achieve a bearing-constrained target formation using bearingonly measurements. Suppose the target formation is specified
∗
by constant bearing constraints {gij
}(i,j)∈E , and there are no
leaders. The control objective is to control the positions of the
∗
agents {pi (t)}i∈V such that gij (t) → gij
for all (i, j) ∈ E as

t → ∞. All the bearings are expressed in a common reference
frame.
The following nonlinear control law, proposed in [28], can
be used to solve the bearing-only formation control problem,
X
∗
ṗi (t) = −
Pgij (t) gij
, i ∈ V,
(13)
j∈Ni
T
where Pgij (t) = Id − gij (t)gij
(t). The geometric interpretation of the control law is illustrated in Figure 13. Some
properties of the control law are highlighted below. First,
the control of each agent only requires bearing measurements
and does not require distance or position estimation. Second,
the control input of (13) is always bounded as kṗi (t)k ≤
P
∗
∗
j∈Ni kPgij (t) kkgij k = |Ni |, since kPgij (t) k = kgij k = 1.
Third, the centroid and scale of the formation are invariant
under the control law [28, Theorem 9]. Here, the centroid is
defined as the average position of the agents and the scale
is defined as the standard deviation of the distances from
the agents to the centroid. Simulation examples are given in
Figures 14 and 15 to demonstrate control law (13).
System (13) is nonlinear and almost globally stable if the
target formation is infinitesimally bearing rigid [28, Theorem 11]. The term “almost” is due to the fact that there are
two isolated equilibriums of the error dynamics, one is desired

9

An optimization-based approach for bearing-only formation
control can be found in [10], [65], where a bearing-only
control law is proposed as
X
∗
(gij (t) − gij
ṗi (t) =
), i ∈ V.
(15)

Initial position
Final position
10
8

j∈Ni

6

This is a gradient-descent control law with the corresponding
objective function as
1 X
1 X
∗ 2
T ∗
keij kkgij − gij
k =
keij k(1 − gij
gij ).
φ2 =
4
2

4
2
0
10
5

0

5

0

10

(a) Initial configuration (grey circle) and final desired
formation (blue circles).
2

(i,j)∈E

(i,j)∈E

∗
Since φ2 contains keij k, φ2 is zero when gij = gij
or eij =
0. As a result, the scale of the formation always decreases
under the action of control law (15). Simulation shows that
this control law may steer all the agents to the same position
given certain initial conditions. To avoid this problem, leaders
must be introduced [65].

Bearing error

1.5

C ONCLUSIONS AND F UTURE D IRECTIONS

1

0.5

0
0

10

20

30

40

50

Time (sec)

(b) Plot of the bearing error,

P

(i,j)∈E

∗ k.
kgij (t) − gij

Fig. 15: Simulation example for the bearing control law in (13) in threedimensional space. In this example, the formation has 27 nodes and 62 edges.
For the target formation, the rank of the bearing rigidity matrix, which equals
the rank of the bearing Laplacian matrix, is 3n − 4 = 77. As a result, the
target formation is infinitesimally bearing rigid and hence the control law (13)
is almost globally stable. As can be seen, given a random initial configuration,
the target formation is achieved and the bearing errors converge to zero.

and the other is undesired. At the desired equilibrium, the
∗
bearings are equal to the desired values; that is gij = gij
for (i, j) ∈ E. At the undesired equilibrium, the bearings
∗
are opposite to the desired values; that is gij = −gij
for
(i, j) ∈ E. The formations at the two equilibriums have the
same centroid and scale but opposite bearings. The almost
global stability means that the formation would converge to
the desired equilibrium unless the initial formation lies exactly
on the undesired equilibrium, which can be shown to be an
unstable equilibrium.
Control law (13) is a modified gradient-descent control law.
In particular, consider the following objective function,
X
1 X
∗ 2
T ∗
kgij − gij
k =
(1 − gij
gij ).
φ1 =
2
(i,j)∈E

(i,j)∈E

∗
The objective function is equal to zero if and only if gij = gij
for all (i, j) ∈ E. The corresponding gradient-descent control
law is
X
1
∗
Pg (t) gij
, i ∈ V.
(14)
ṗi (t) = −
keij (t)k ij
j∈Ni

The two-dimensional version of control law (14) was first
proposed in [24]. This control law requires both bearing and
distance measurements. Removing the distance term keij (t)k
in (14) yields the bearing-only formation control law in (13).

This article presented a review of the bearing rigidity
theory and its applications in distributed formation control
and network localization for multi-agent systems. Motivated
by the fact that many existing approaches rely on measurement
assumptions that may be difficult to realize under certain
circumstances, this article demonstrated how to utilize bearingonly sensors, such as cameras or sensor arrays, to solve the
problems of formation control and network localization. The
article discussed three specific problems including bearingbased network localization, bearing-based formation control,
and bearing-only formation control.
As a newly emerged research area, bearing-based control and estimation is far from being fully explored. Many
important problems in this area remain unsolved. One key
assumption for the results presented in this article is that
the underlying graph is undirected, which means any pair of
neighbors must be able to access each other’s information.
Since this assumption may not be valid in some practical tasks,
it is important to study the case of directed graphs. When the
graph is directed, the control and estimation problem would
become more complicated because undesired equilibriums
may emerge, as observed in [68]. Similar problems also exist
in distance-based formation control [73]–[75]. Despite the
resent progress on bearing-only formation control for some
special directed graphs [76], [77], the problem for general
directed graphs remains an important challenge in this area.
Another key assumption for the results addressed in this
article is that all bearings must be measured in a global
reference frame. Global reference frames, however, may not be
accessible to each agent in some environments such as indoors.
It is important to study how to achieve control or estimation
when bearings are measured in each agent’s local reference
frames. One potential approach is to estimate or synchronize
the orientations of the local reference frames [10], [28]. This
approach has been applied to adapt the bearing-only formation
control law in (13) to use locally measured bearings [28,
Section IV], and a simulation example is given in Figure 16.
This is also a general approach for many types of formation

10

2

2

1.5

1.5

1

1

0.5

0.5

0

0

-0.5

-0.5

-1

-1
2

2

1
-2

-1.5

-1

-0.5

0

0
0.5

1

1.5

2

2.5

(a) Initial formation.

-1

1
-2

-1.5

-1

-0.5

0

0
0.5

1

1.5

2

2.5

-1

(b) Final formation.

Fig. 16: Simulation example for bearing-only formation control without a
global reference frame. The control law is given in [28, Equation (19)]. In
this example, the formation has 8 nodes and 13 edges. The target formation
is a three-dimensional cube that is infinitesimally bearing rigid. The control
is based on inter-neighbor bearings expressed in each agent’s local reference
frames. The orientations of the agents are synchronized in the final formation.

control and network localization tasks in the absence of global
reference frames [78], [79]. However, distributed orientation
estimation or synchronization requires each agent to obtain
their neighbors’ relative orientations, which are usually difficult to measure in practice. Other potential approaches that do
not require an orientation estimation may be based on bearing
rigidity in the special Euclidean group SE(n) [26], [80]–
[83] or complex Laplacian [52], [57]. A brief introduction to
bearing rigidity in SE(2) is given in “Bearing Rigidity Theory
for SE(2).” Nevertheless, the formation control strategies
provided for SE(2) frameworks still require additional sensing
[80], and a complete theory for bearing-only formation control
is still unsolved.
In addition to network localization and formation control,
many other tasks may also be achieved with bearing-only
measurements such as bearing-only rendezvous [84]–[88], and
bearing-only target tracking [16]–[18], [89]–[91] though the
analysis of these tasks may not rely on the bearing rigidity
theory.
The bearing rigidity theory and its application for formation control and network localization is strongly motivated
by the sensing mediums available to distributed and multiagent systems. This work contributed to a broader theory of
cooperative control and estimation for networked systems and
hopes to serve as a starting point for both practitioners and
theoreticians in this community.

11

R EFERENCES
[1] Y. Cao, W. Yu, W. Ren, and G. Chen, “An overview of recent progress
in the study of distributed multi-agent coordination,” IEEE Transactions
on Industrial Informatics, vol. 9, no. 1, pp. 427–438, 2013.
[2] K.-K. Oh, M.-C. Park, and H.-S. Ahn, “A survey of multi-agent
formation control,” Automatica, vol. 53, pp. 424–440, March 2015.
[3] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey
on sensor networks,” IEEE Communications Magazine, vol. 40, pp. 102–
114, Aug 2002.
[4] J. Aspnes, T. Eren, D. K. Goldenberg, A. S. Morse, W. Whiteley, Y. R.
Yang, B. D. O. Anderson, and P. N. Belhumeur, “A theory of network
localization,” IEEE Transactions on Mobile Computing, vol. 12, no. 5,
pp. 1663–1678, 2006.
[5] G. Mao, B. Fidan, and B. D. O. Anderson, “Wireless sensor network
localization techniques,” Comupter Networks, vol. 51, pp. 2529–2553,
2007.
[6] P. Barooah and J. P. Hespanha, “Estimation on graphs from relative
measurements,” IEEE Control Systems Magzine, no. 1, pp. 57–74, 2007.
[7] Y. Ma, S. Soatto, J. Kosecka, and S. Sastry, An Invitation to 3D Vision.
New York: Springer, 2004.
[8] R. I. Hartley and P. Sturm, “Triangulation,” Computer vision and image
understanding, vol. 68, no. 2, pp. 146–157, 1997.
[9] N. Moshtagh, N. Michael, A. Jadbabaie, and K. Daniilidis, “Visionbased, distributed control laws for motion coordination of nonholonomic
robots,” IEEE Transactions on Robotics, vol. 25, pp. 851–860, August
2009.
[10] R. Tron, J. Thomas, G. Loianno, K. Daniilidis, and V. Kumar, “A
distributed optimization framework for localization and formation control: applications to vision-based measurements,” IEEE Control Systems
Magazine, vol. 36, no. 4, pp. 22–44, 2016.
[11] A. Farina, “Target tracking with bearings-only measurements,” Signal
Processing, vol. 78, pp. 61–68, 1999.
[12] Y.-Y. Dong, C.-X. Dong, W. Liu, H. Chen, and G.-Q. Zhao, “2-D
DOA estimation for L-shaped array with array aperture and snapshots
extension techniques,” IEEE Signal Processing letters, vol. 24, no. 4,
pp. 495–499, 2017.
[13] G. Stacey and R. Mahony, “A passivity-based approach to formation
control using partial measurements of relative position,” IEEE Transactions on Automatic Control, vol. 61, no. 2, pp. 538–543, 2016.
[14] K. Becker, “Simple linear theory approach to TMA observability,” IEEE
Transactions on Aerospace and Electronic Systems, vol. 29, no. 2,
pp. 575–578, 1993.
[15] M. Deghat, I. Shames, B. D. O. Anderson, and C. Yu, “Localization
and circumnavigation of a slowly moving target using bearing measurements,” IEEE Transactions on Automatic Control, vol. 59, no. 8,
pp. 2182–2188, 2014.
[16] J. O. Swartling, I. Shames, K. H. Johansson, and D. V. Dimarogonas, “Collective circumnavigation,” Unmanned Systems, vol. 2, no. 3,
pp. 219–229, 2014.
[17] R. Zheng, Y. Liu, and D. Sun, “Enclosing a target by nonholonomic
mobile robots with bearing-only measurements,” Automatica, vol. 53,
pp. 400–407, 2015.
[18] M. Ye, B. D. O. Anderson, and C. Yu, “Bearing-only measurement selflocalization, velocity consensus and formation control,” IEEE Transactions on Aerospace and Electronic Systems, vol. 52, no. 2, pp. 575–586,
2017.
[19] R. Olfati-Saber and R. M. Murray, “Consensus problems in networks
of agents with switching topology and time-delays,” IEEE Transactions
on Automatic Control, vol. 49, no. 9, pp. 1520–1533, 2004.
[20] Z. Lin, B. Francis, and M. Maggiore, “Necessary and sufficient graphical
conditions for formation control,” IEEE Transactions on Automatic
Control, vol. 50, pp. 121–127, January 2005.
[21] W. Ren, R. W. Beard, and E. M. Atkins, “Information consensus
in multivehicle cooperative control,” IEEE Control Systems Magazine,
vol. 27, pp. 71–82, April 2007.
[22] Z. Li, Z. Duan, G. Chen, and L. Huang, “Consensus of multiagent
systems and synchronization of complex networks: A unified viewpoint,”
IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 57,
no. 1, pp. 213–224, 2010.
[23] B. Servatius and W. Whiteley, “Constraining plane configurations in
computer-aided design: Combinatorics of directions and lengths,” SIAM
Journal on Discrete Mathematics, vol. 12, no. 1, pp. 136–153, 1999.
[24] A. N. Bishop, “Stabilization of rigid formations with direction-only
constraints,” in Proceedings of the 50th IEEE Conference on Decision
and Control and European Control Conference, (Orlando, FL, USA),
pp. 746–752, December 2011.

[25] T. Eren, “Formation shape control based on bearing rigidity,” International Journal of Control, vol. 85, no. 9, pp. 1361–1379, 2012.
[26] D. Zelazo, A. Franchi, and P. R. Giordano, “Rigidity theory in SE(2) for
unscaled relative position estimation using only bearing measurements,”
in Proceedings of the 2014 European Control Conference, (Strasbourgh,
France), pp. 2703–2708, June 2014.
[27] R. Tron, L. Carlone, F. Dellaert, and K. Daniilidis, “Rigid components
identification and rigidity control in bearing-only localization using
the graph cycle basis,” in Proceedings of the 2015 American Control
Conference, (Chicago, IL, USA), pp. 3911–3918, 2015.
[28] S. Zhao and D. Zelazo, “Bearing rigidity and almost global bearingonly formation stabilization,” IEEE Transactions on Automatic Control,
vol. 61, no. 5, pp. 1255–1268, 2016.
[29] L. Asimow and B. Roth, “The rigidity of graphs,” Transactions of the
American Mathematical Society, vol. 245, pp. 279–289, November 1978.
[30] R. Connelly and S. D. Guest, Frameworks, Tensegrities and Symmetry: Understanding Stable Structures. 2015. Available online
at http://www.math.cornell.edu/∼web7510/framework.pdf (last accessed
November 2017).
[31] B. Hendrickson, “Conditions for unique graph realizations,” SIAM
Journal on Computing, vol. 21, no. 1, pp. 65–84, 1992.
[32] R. Connelly, “Generic global rigidity,” Discrete & Computational Geometry, vol. 33, pp. 549–563, 2005.
[33] D. Jacobs, “An algorithm for two-dimensional rigidity percolation: The
pebble game,” Journal of Computational Physics, vol. 137, pp. 346–365,
Nov. 1997.
[34] T.-S. Tay and W. Whiteley, “Generating isostatic frameworks,” Structural
Topology, vol. 11, pp. 21–69, 1985.
[35] R. Haas, D. Orde, G. Rote, F. Santos, B. Servatius, H. Servatius,
D. Souvaine, I. Streinu, and W. Whiteley, “Planar minimally rigid graphs
and pseudo-triangulations,” Computational Geometry, vol. 31, no. 1–2,
pp. 31–61, 2005.
[36] B. Jackson, “Notes on the rigidity of graphs,” tech. rep., Queen Mary
University of London, 2007.
[37] B. D. O. Anderson, C. Yu, B. Fidan, and J. Hendrickx, “Rigid graph
control architectures for autonomous formations,” IEEE Control Systems
Magazine, vol. 28, pp. 48–63, December 2008.
[38] L. Krick, M. E. Broucke, and B. A. Francis, “Stabilization of infinitesimally rigid formations of multi-robot networks,” International Journal
of Control, vol. 82, no. 3, pp. 423–439, 2009.
[39] K.-K. Oh and H.-S. Ahn, “Distance-based undirected formations of
single-integrator and double-integrator modeled agents in n-dimensional
space,” International Journal of Robust and Nonlinear Control, vol. 24,
pp. 1809–1820, August 2014.
[40] Y.-P. Tian and Q. Wang, “Global stabilization of rigid formations in the
plane,” Automatica, vol. 49, pp. 1436–1441, May 2013.
[41] D. Zelazo, A. Franchi, and P. R. Giordano, “Distributed rigidity maintenance control with range-only measurements for multi-robot systems,”
The International Journal of Robotics Research, vol. 34, no. 1, pp. 105–
128, 2015.
[42] S. Mou, M.-A. Belabbas, A. S. Morse, Z. Sun, and B. D. O. Anderson,
“Undirected rigid formations are problematic,” IEEE Transactions on
Automatic Control, vol. 61, no. 10, pp. 2821–2836, 2016.
[43] X. Chen, M.-A. Belabbas, and T. Başar, “Global stabilization of triangulated formations,” SIAM Journal on Optimization and Control, vol. 55,
no. 1, pp. 172–199, 2017.
[44] Z. Sun, M.-C. Park, B. D. O. Anderson, and H.-S. Ahn, “Distributed
stabilization control of rigid formations with prescribed orientation,”
Automatica, vol. 78, pp. 250–257, 2017.
[45] H. G. de Marina, B. Jayawardhana, and M. Cao, “Distributed rotational
and translational maneuvering of rigid formations and their applications,” IEEE Transactions on Robotics, vol. 32, no. 3, pp. 684–697,
2016.
[46] T. Eren, O. K. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse,
B. D. O. Anderson, and P. Belhumeur, “Rigidity, computation, and randomization in network localization,” in INFOCOM 2004. Twenty-third
Annual Joint Conference of the IEEE Computer and Communications
Societies, (Pasadena, USA), pp. 2673–2684, 2004.
[47] T. Eren, W. Whiteley, A. S. Morse, P. N. Belhumeur, and B. D. O.
Anderson, “Sensor and network topologies of formations with direction,
bearing and angle information between agents,” in Proceedings of
the 42nd IEEE Conference on Decision and Control, (Hawaii, USA),
pp. 3064–3069, December 2003.
[48] A. N. Bishop, B. D. O. Anderson, B. Fidan, P. N. Pathirana, and
G. Mao, “Bearing-only localization using geometrically constrained
optimization,” IEEE Transactions on Aerospace and Electronic Systems,
vol. 45, no. 1, pp. 308–320, 2009.

12

[49] G. Piovan, I. Shames, B. Fidan, F. Bullo, and B. D. O. Anderson,
“On frame and orientation localization for relative sensing networks,”
Automatica, vol. 49, pp. 206–213, January 2013.
[50] I. Shames, A. N. Bishop, and B. D. O. Anderson, “Analysis of noisy
bearing-only network localization,” IEEE Transactions on Automatic
Control, vol. 58, pp. 247–252, January 2013.
[51] G. Zhu and J. Hu, “A distributed continuous-time algorithm for network
localization using angle-of-arrival information,” Automatica, vol. 50,
pp. 53–63, January 2014.
[52] Z. Lin, T. Han, R. Zheng, and M. Fu, “Distributed localization for 2D sensor networks with bearing-only measurements under switching
topologies,” IEEE Transactions on Signal Processing, vol. 64, no. 23,
pp. 6345–6359, 2016.
[53] A. N. Bishop, M. Deghat, B. D. O. Anderson, and Y. Hong, “Distributed
formation control with relaxed motion requirements,” International
Journal of Robust and Nonlinear Control, vol. 25, pp. 3210–3230, 2015.
[54] S. Zhao and D. Zelazo, “Bearing-based distributed control and estimation in multi-agent systems,” in Proceedings of the 2015 European
Control Conference, (Linz, Austria), pp. 2207–2212, July 2015.
[55] S. Zhao and D. Zelazo, “Translational and scaling formation maneuver
control via a bearing-based approach,” IEEE Transactions on Control of
Network Systems, vol. 4, no. 3, pp. 429–438, 2017.
[56] K. Fathian, D. I. Rachinskii, M. W. Spong, and N. R. Gans, “Globally
asymptotically stable distributed control for distance and bearing based
multi-agent formations,” in Proceedings of the 2016 American Control
Conference, (Boston, MA, USA), pp. 4642–4648, 2016.
[57] Z. Han, L. Wang, Z. Lin, and R. Zheng, “Formation control with size
scaling via a complex Laplacian-based approach,” IEEE Transactions
on Cybernetics, vol. 46, no. 10, pp. 2348–2359, 2016.
[58] S. Coogan and M. Arcak, “Scaling the size of a formation using relative
position feedback,” Automatica, vol. 48, pp. 2677–2685, October 2012.
[59] M. Basiri, A. N. Bishop, and P. Jensfelt, “Distributed control of
triangular formations with angle-only constraints,” Systems & Control
Letters, vol. 59, pp. 147–154, 2010.
[60] A. Franchi, C. Masone, V. Grabe, M. Ryll, H. H. Bulthoff, and P. R.
Giordano, “Modeling and control of UAV bearing formations with
bilateral high-level steering,” The International Journal of Robotics
Research, vol. 31, no. 12, pp. 1504–1525, 2012.
[61] A. Cornejo, A. J. Lynch, E. Fudge, S. Bilstein, M. Khabbazian, and
J. McLurkin, “Scale-free coordinates for multi-robot systems with
bearing-only sensors,” The International Journal of Robotics Research,
vol. 32, no. 12, pp. 1459–1474, 2013.
[62] S. Zhao, F. Lin, K. Peng, B. M. Chen, and T. H. Lee, “Distributed
control of angle-constrained cyclic formations using bearing-only measurements,” Systems & Control Letters, vol. 63, no. 1, pp. 12–24, 2014.
[63] S. Zhao, F. Lin, K. Peng, B. M. Chen, and T. H. Lee, “Finite-time
stabilization of cyclic formations using bearing-only measurements,”
International Journal of Control, vol. 87, no. 4, pp. 715–727, 2014.
[64] E. Schoof, A. Chapman, and M. Mesbahi, “Bearing-compass formation
control: a human-swarm interaction perspective,” in Proceedings of the
2014 American Control Conference, (Portland, USA), pp. 3881–3886,
June 2014.
[65] R. Tron, J. Thomas, G. Loianno, K. Daniilidis, and V. Kumar, “Bearingonly formation control with auxiliary distance measurements, leaders,
and collision avoidance,” in Proceedings of the 55th Conference on
Decision and Control, (Las Vegas, USA), pp. 1806–1813, 2016.
[66] S. Zhao and D. Zelazo, “Localizability and distributed protocols for
bearing-based network localization in arbitrary dimensions,” Automatica,
vol. 69, pp. 334–341, 2016.
[67] C. Godsil and G. Royle, Algebraic Graph Theory. New York: Springer,
2001.
[68] S. Zhao and D. Zelazo, “Bearing-based formation stabilization with
directed interaction topologies,” in Proceedings of the 54th IEEE
Conference on Decision and Control, (Osaka, Japan), pp. 6115–6120,
December 2015.
[69] S. Zhao, Z. Sun, D. Zelazo, M. H. Trinh, and H.-S. Ahn, “Laman graphs
are generically bearing rigid in arbitrary dimensions,” in Proceedings
of the 56th IEEE Conference on Decision and Control, (Melbourne,
Australia), December 2017. in press (available online at https://arxiv.
org/abs/1703.04035).
[70] G. Laman, “On graphs and rigidity of plane skeletal structures,” Journal
of Engineering Mathematics, vol. 4, no. 4, pp. 331–340, 1970.
[71] S. Zhao and D. Zelazo, “Bearing-based formation maneuvering,” in Proceedings of the 2015 IEEE Multi-Conference on Systems and Control,
(Sydney, Australia), pp. 658–663, September 2015.

[72] S. Zhao, D. V. Dimarogonas, Z. Sun, and D. Bauso, “A general
approach to coordination control of mobile agents with motion constraints,” IEEE Transactions on Automatic Control. in press (DOI:
10.1109/TAC.2017.2750924).
[73] J. Hendrickx, B. D. O. Anderson, J. Delvenne, and V. Blondel, “Directed
graphs for the analysis of rigidity and persistence in autonomous
agent systems,” International Journal of Robust and Nonlinear Control,
vol. 17, no. 10-11, pp. 960–981, 2007.
[74] C. Yu, B. D. O. Anderson, A. S. Dasgupta, and B. Fidan, “Control of
minimally persistent formations in the plane,” SIAM Journal on Control
and Optimization, vol. 48, pp. 206–233, Februray 2009.
[75] T. H. Summers, C. Yu, S. Dasgupta, and B. D. O. Anderson, “Control
of minimally persistent leader-remote-follower and coleader formations
in the plane,” IEEE Transactions on Automatic Control, vol. 56, no. 12,
pp. 2778–2792, 2011.
[76] D. Mukherjee, M.-H. Trinh, D. Zelazo, and H.-S. Ahn, “Bearing-only
cyclic pursuit in 2-D for capture of moving target,” in 57th Israel Annual
Conference on Aerospace Sciences, (Haifa, Israel), 2017.
[77] M.-H. Trinh, D. Mukherjee, D. Zelazo, and H.-S. Ahn, “Formations on
directed cycles with bearing-only measurements,” International Journal
of Robust and Nonlinear Control, pp. 1–23, 2017. in press (DOI:
10.1002/rnc.3921).
[78] K.-K. Oh and H.-S. Ahn, “Formation control and network localization
via orientation alignment,” IEEE Transactions on Automatic Control,
vol. 59, pp. 540–545, February 2014.
[79] B.-H. Lee and H.-S. Ahn, “Distributed formation control via global
orientation estimation,” Automatica, vol. 73, pp. 125–129, 2016.
[80] D. Zelazo, A. Franchi, and P. R. Giordano, “Formation control using a
SE(2) rigidity theory,” in Proceedings of the 54th IEEE Conference on
Decision and Control, (Osaka, Japan), pp. 6121–6126, 2015.
[81] F. Schiano, A. Franchi, D. Zelazo, and P. R. Giordano, “A RigidityBased Decentralized Bearing Formation Controller for Groups of
Quadrotor UAVs,” in Proceedings of IEEE/RSJ International Conference
on Intelligent Robots and Systems, (Daejeon, Korea), pp. 5099–5106,
2016.
[82] G. Michieletto, A. Cenedese, and A. Franchi, “Bearing rigidity theory
in SE(3),” in Proceedings of the 55th IEEE Conference on Decision and
Control, (5950–5955), pp. 83–92, 2016.
[83] F. Schiano and P. G. Robuffo, “Bearing rigidity maintenance for formations of quadrotor UAVs,” in Proceedings of IEEE International
Conference on Robotics and Automation, (Singapore), 2017.
[84] J. Yu, S. M. LaValle, and D. Liberzon, “Rendezvous without coordinates,” IEEE Transactions on Automatic Control, vol. 57, no. 2, pp. 421–
434, 2012.
[85] R. Zheng and D. Sun, “Rendezvous of unicycles: A bearings-only and
perimeter shortening approach,” Systems & Control Letters, vol. 62,
pp. 401–407, May 2013.
[86] J. Grzymisch and W. Fichter, “Optimal rendezvous guidance with
enhanced bearings-only observability,” Journal of Guidance, Control,
and Dynamics, vol. 38, no. 6, pp. 1131–1139, 2015.
[87] M. Kriegleder, S. T. Digumarti, R. Oung, and R. D’Andrea, “Rendezvous with bearing-only information and limited sensing range,” in
Proceedings of the 2015 IEEE International Conference on Robotics
and Automation, (Seattle, Washington), pp. 5941–5947, 2015.
[88] S. Zhao and R. Zheng, “Flexible bearing-only rendezvous control of
mobile robots,” in Proceedings of the 36th Chinese Control Conference,
(Dalian, China), pp. 8051–8056, July 2017.
[89] S. G. Loizou and V. Kumar, “Biologically inspired bearing-only navigation and tracking,” in Proceedings of the 46th IEEE Conference on
Decision and Control, (New Orleans, LA, USA), pp. 1386–1391, 2007.
[90] M. Deghat, I. Shames, A. N. Bishop, B. D. O. Anderson, and C. Yu,
“Localization and circumnavigation of a slowly moving target using bearing measurements,” IEEE Transactions on Automatic Control,
vol. 59, pp. 2182–2188, August 2014.
[91] M.-H. Trinh, G.-H. Ko, V.-H. Pham, K.-K. Oh, and H.-S. Ahn, “Guidance using bearing-only measurements with three beacons in the plane,”
Control Engineering Practice, vol. 51, pp. 81–91, 2016.

13

N OTATIONS FOR N ETWORKS AND F ORMATIONS
Given a network of n nodes in Rd where n ≥ 2, d ≥ 2, let
the position of node i be pi ∈ Rd and the configuration of the
points be p = [pT1 , . . . , pTn ]T ∈ Rdn . The interaction among
the nodes is described by a graph G = (V, E) which consists
of a vertex set V = {1, . . . , n} and an edge set E ⊆ V × V. If
(i, j) ∈ E, node i receives information from node j, and node
j is called adjacent to i. The set of neighbors of vertex i is
denoted as Ni = {j ∈ V : (i, j) ∈ E}. This article focuses on
undirected graphs where (i, j) ∈ E ⇔ (j, i) ∈ E. Let m be
the number of undirected edges in the graph. An orientation
of an undirected graph is the assignment of a direction to each
edge. An oriented graph is an undirected graph together with
an orientation. The incidence matrix H ∈ Rm×n of an oriented
graph is the {0, ±1}-matrix with rows indexed by edges and
columns by vertices.
A network, denoted as (G, p), is G with its vertex i ∈ V
mapped to pi . Network may be called as formation in the
context of formation control. For a network (G, p), define the
edge and bearing vectors for (i, j) ∈ E as eij = pj − pi and
gij = eij /keij k, respectively. Here gij is the unit vector pointing from pi to pj . It represents the relative bearing of pi with
respect to pj . Note that eij = −eji and gij = −gji . Consider
an orientation of the graph G and suppose (i, j) corresponds to
the kth edge in the oriented graph. Then the edge and bearing
vectors may be reexpressed as ek = pj −pi and gk = ek /kek k
where k ∈ {1, . . . , m}. Denote e = [eT1 , . . . , eTm ]T and
T T
] . Note that e = (H ⊗ Id )p where ⊗ denotes
g = [g1T , . . . , gm
the Kronecker product. In this article, Null(·) and Range(·)
denote the null and range spaces of a matrix, respectively.
Denote 1n , [1, . . . , 1]T ∈ Rn . Let k·k be the Euclidian norm
of a vector or the spectral norm of a matrix, and Id ∈ Rd×d
be the identity matrix.

14

K EY D EFINITIONS IN B EARING R IGIDITY T HEORY

K EY D EFINITIONS IN D ISTANCE R IGIDITY T HEORY

Definition S1 (Bearing Equivalency). Two networks (G, p)
and (G, p0 ) are bearing equivalent if P(pi −pj ) (p0i − p0j ) = 0
for all (i, j) ∈ E.

Definition S1 (Distance Equivalency). Two networks (G, p)
and (G, p0 ) are distance equivalent if kpi − pj k = kp0i − p0j k
for all (i, j) ∈ E.

Definition S2 (Bearing Congruency). Two networks (G, p) and
(G, p0 ) are bearing congruent if P(pi −pj ) (p0i − p0j ) = 0 for all
i, j ∈ V.

Definition S2 (Distance Congruency). Two networks (G, p)
and (G, p0 ) are distance congruent if kpi − pj k = kp0i − p0j k
for all i, j ∈ V.

Definition S3 (Bearing Rigidity). A network (G, p) is bearing
rigid if there exists a constant  > 0 such that any network
(G, p0 ) that is bearing equivalent to (G, p) and satisfies kp0 −
pk <  is also bearing congruent to (G, p).

Definition S3 (Distance Rigidity). A network (G, p) is distance
rigid if there exists a constant  > 0 such that any network
(G, p0 ) that is distance equivalent to (G, p) and satisfies kp0 −
pk <  is also distance congruent to (G, p).

Definition S4 (Global Bearing Rigidity). A network (G, p) is
globally bearing rigid if an arbitrary network that is bearing
equivalent to (G, p) is also bearing congruent to (G, p).

Definition S4 (Global Distance Rigidity). A network (G, p) is
globally distance rigid if an arbitrary network that is distance
equivalent to (G, p) is also distance congruent to it.

Consider an oriented graph where the inter-neighbor bearings can be expressed by {gk }m
k=1 . Define the bearing function
FB : Rdn → Rdm as

Consider an oriented graph where the inter-neighbor distances can be expressed by {kek k}m
k=1 . Define the distance
function FD : Rdn → Rdm as

T T
FB (p) = [g1T , . . . , gm
] ∈ Rdm .

FD (p) = [ke1 k2 , . . . , kem k2 ]T /2 ∈ Rm .

The bearing rigidity matrix is defined as the Jacobian of the
bearing function

The distance rigidity matrix is defined as the Jacobian of the
distance function
∂FD (p)
∈ Rm×dn .
(S2)
RD (p) =
∂p

RB (p) =

∂FB (p)
∈ Rdm×dn .
∂p

(S1)

A matrix-vector form RD (p) is

A matrix-vector form RB (p) is
RB (p) = diag(Pg1 /ke1 k, . . . , Pgm /kem k)(H ⊗ Id ).

RD (p) = diag(eT1 , . . . , eTm )(H ⊗ Id ).

Let δp ∈ Rdn be a variation of the configuration p. If
RB (p)δp = 0, then δp is called an infinitesimal bearing motion
of (G, p). An infinitesimal bearing motion is called trivial if
it only corresponds to a translation and a scaling of the entire
network.

Let δp ∈ Rdn be a variation of the configuration p. If
RD (p)δp = 0, then δp is called an infinitesimal distance
motion of (G, p). An infinitesimal distance motion is called
trivial if it only corresponds to a translation and a rotation of
the entire network.

Definition S5 (Infinitesimal Bearing Rigidity). A network is
infinitesimally bearing rigid if all the infinitesimal bearing
motions are trivial.

Definition S5 (Infinitesimal Distance Rigidity). A network is
infinitesimally distance rigid if all the infinitesimal distance
motions are trivial.

The relation between bearing rigidity, global bearing rigidity, and infinitesimal bearing rigidity is illustrated in Figure S1.
Details of these notions can be found in [28].

The relation between distance rigidity, global distance rigidity, and infinitesimal distance rigidity is illustrated in Figure S2. Details of the notions can be found in [29]–[32], [36].
infinitesimal
distance rigidity

infinitesimal
bearing rigidity

bearing rigidity

global
bearing rigidity

Fig. S1: The relation between bearing rigidity, global bearing rigidity, and
infinitesimal bearing rigidity. Infinitesimal bearing rigidity implies both bearing rigidity and global bearing rigidity. Global bearing rigidity and bearing
rigidity imply each other.

distance rigidity

global
distance rigidity

Fig. S2: The relation between distance rigidity, global distance rigidity, and
infinitesimal distance rigidity. Both infinitesimal and global distance rigidity
imply distance rigidity. Infinitesimal and global distance rigidity do not imply
each other.

15

B EARING L APLACIAN OF N ETWORKS

A N O RTHOGONAL P ROJECTION M ATRIX
For any nonzero vector x ∈ R
orthogonal projection matrix as
P (x) = Id −

d

(d ≥ 2), define an

x xT
∈ Rd×d .
kxk kxk

For notational simplicity, denote Px = P (x). The matrix Px is
an orthogonal projection matrix that geometrically projects any
vector onto the orthogonal compliment of x (see Figure S3).
Matrix Px satisfies PxT = Px , Px2 = Px , and Null(Px ) =
span{x}. This matrix is positive semi-definite with one eigenvalue equal to zero and d − 1 eigenvalues equal to one. Other
properties of Px are summarized as below.
(a) Any two nonzero vectors x, y ∈ Rd are parallel if and
only if Px y = 0 [28, Lemma 1].
(b) Any two unit vectors x, y ∈ Rd satisfy xT Py x = y T Px y
[28, Lemma 8].
(c) For any nonzero vectors
∈ Rd where m ≥
Pm x1 , . . . , xmd×d
2, d ≥ 2, the matrix i=1 Pxi ∈ R
is nonsingular if
and only if at least two of x1 , . . . , xm are not collinear
[69, Lemma 3].
(d) For any nonzero vector x ∈ R2 , denote x⊥ ∈ R2 as
a nonzero normal vector that satisfies xT x⊥ = 0. Then
Px = x⊥ (x⊥ )T /kx⊥ k2 . The proof follows from the fact
that the matrix A = [x/kxk, x⊥ /kx⊥ k] ∈ R2×2 satisfies
AT A = AAT = I2 .
(e) For any two nonzero vectors x, y ∈ Rd , if θ ∈ [0, π] is
the angle between them so that xT y = kxkkyk cos θ, then
kPx − Py k = sin θ [66, Lemma 5]. This property has
been used to analyze the perturbation of the orthogonal
projection matrix.
2
(f) If x ∈ R3 is a unit vector, then Px = − [x]× , where


0
−x3 x2
0
−x1  ∈ R3×3
[x]× =  x3
−x2 x1
0
is the skew-symmetric matrix associated with x [7, Theorem 2.11]. This property has been used in [72, Equation (6)]
The orthogonal projection matrix plays an important role in
the bearing rigidity theory and its applications.
x
y

0

Px y

Fig. S3: Illustration of the orthogonal projection matrix. Given any nonzero
x, y ∈ Rd , the vector Px y is the orthogonal projection of y onto the
orthogonal compliment of x.

Given network (G, p) with no collocated nodes, define the
bearing Laplacian B ∈ Rdn×dn as [66]

i 6= j, (i, j) ∈
/ E,
 0d×d ,
−P
,
i
=
6
j,
(i,
j)
∈
E,
[B]ij =
g
ij
 P
P
,
i
=
j,
i
∈
V,
g
ik
k∈Ni
where [B]ij ∈ Rd×d is the ijth block of submatrix of
B. The bearing Laplacian can be viewed a matrix-weighted
Laplacian which describes both the underlying graph and the
inter-neighbor bearings of the network. See Figure S4 for
illustration.
For undirected graphs, the bearing Laplacian has the following properties [66, Lemma 2]:
(a) B is symmetric and positive semi-definite because for any
x = [xT1 , . . . , xTn ]T ∈ Rdn
1X X
(xi − xj )T Pgij (xi − xj ) ≥ 0.
xT Bx =
2
i∈V j∈Ni

(b) rank(B) ≤ dn − d − 1 and span{1 ⊗ Id , p} ⊆ Null(B)
for any network.
(c) rank(B) = dn − d − 1 and Null(B) = span{1 ⊗ Id , p} if
and only if the network is infinitesimally bearing rigid.
In a network with na anchors and nf = n − na followers, the
bearing Laplacian may be partitioned into


Baa Baf
B=
,
Bf a Bf f
where Bf f ∈ Rdnf ×dnf . For any network, Bf f is positive
semi-definite and satisfies Bf f pf = −Bf a pa [66, Lemma 3].
In the context of formation control, the anchors are called
leaders and the subscript a is replaced by `.
g31
g13
1

g12

3



g32
g23
g21

2

B=


Pg12 + Pg13
−Pg12
−Pg13

−Pg21
Pg21 + Pg23
−Pg23
−Pg31
−Pg32
Pg31 + Pg32

Fig. S4: Example to demonstrate bearing Laplacian. The network is the
complete graph on three nodes. The bearing Laplacian has the same structure
as a weighted graph Laplacian matrix [67] with the weights on each edge
corresponding to the projection matrices Pgij .

16

L AMAN G RAPHS AND H ENNEBERG C ONSTRUCTION
An undirected graph G = (V, E) is called Laman if m =
2n − 3 and every subset of k ≥ 2 vertices spans at most
2k − 3 edges [70]. Laman graphs can be characterized by the
Henneberg construction as described below. Given a graph
G = (V, E), a new graph G 0 = (V 0 , E 0 ) is formed by adding
a new vertex v to G and performing one of the following two
operations:
(a) Vertex addition: connect vertex v to any two existing
vertices i, j ∈ V. In this case, V 0 = V ∪ {v} and
E 0 = E ∪ {(v, i), (v, j)}. See Figure S5(a) for illustration.
(b) Edge splitting: consider three vertices i, j, k ∈ V with
(i, j) ∈ E and connect vertex v to i, j, k and delete
(i, j). In this case, V 0 = V ∪ {v} and E 0 = E ∪
{(v, i), (v, j), (v, k)} \ {(i, j)}. See Figure S5(b) for illustration.
A Henneberg construction starting from an edge connecting
two vertices leads to a Laman graph [34]–[36]. The converse is
also true. That is if a graph is Laman, then it can be generated
by a Henneberg construction [35, Lemma 2]. The underlying
graphs of the networks in Figure 2(a)–(c) are Laman. Laman
graphs play critical roles in the construction of distance rigid
and bearing rigid networks.
v

v

i

i

k

j
G
(a) Vertex addition

j
G
(b) Edge splitting

Fig. S5: The two operations of the Henneberg construction. The Henneberg
construction can be used to generate all minimally infinitesimally distance
rigid graphs in the plane. The main idea is to ensure that the vertex addition
and edge splitting operations satisfy the Laman condition at each step.

C OMPARISON OF B EARING R IGIDITY AND D ISTANCE
R IGIDITY
Both of the bearing and distance rigidity theories address
the same problem of when the geometric pattern of a network
can be uniquely determined. The difference is that the bearing
rigidity theory considers inter-neighbor bearings whereas the
distance rigidity theory considers inter-neighbor distances. The
term “unique pattern” in the bearing rigidity theory means the
location of a network can be determined up to a translational
and scaling factor, while in the distance rigidity theory it
means the network can be determined up to a translational
and rotational factor.
One connection between the two rigidity theories is that
infinitesimal bearing rigidity is equivalent to infinitesimal
distance rigidity in two dimensions [28, Theorem 8]. In other
words, a network in the plane is infinitesimally bearing rigid
if and only if it is infinitesimally distance rigid. This equivalence property explains why the distance rigidity theory could
be used to analyze the problems of bearing-based network
localization or formation control in the literature [49], [51],
[64]. It also suggests that the infinitesimal distance rigidity of
a network by be examined by its infinitesimal bearing rigidity.
For example, it may not be straightforward to see that the networks in Figure 3(c)-(d) are not infinitesimally distance rigid.
However, it is intuitive to see these networks are not infinitesimally bearing rigid because there exist nontrivial infinitesimal
bearing motions. It must be noted that the equivalence cannot
be generalized to three or higher dimensions. For example,
the three-dimensional networks shown in Figure 2(c)-(e) are
infinitesimally bearing rigid but not infinitesimally distance
rigid.
Compared to infinitesimal distance rigidity, infinitesimal
bearing rigidity possess some interesting properties. First, infinitesimal bearing rigidity not only ensures the unique pattern
of a network, but also can be examined by a rank condition
easily. As a comparison, infinitesimal distance rigidity may not
be able to ensure a unique pattern though it can be examined
by a rank condition. Second, an infinitesimally bearing rigid
network remains infinitesimally bearing rigid when the dimension is lifted up to a higher dimension [28, Theorem 7]. As a
comparison, a network that is infinitesimally distance rigid in
the plane may be flexible in a higher dimension. Third, in the
bearing rigidity theory, a Laman graph is generically bearing
rigid in arbitrary dimensions and at most 2n−3 edges would be
sufficient to guarantee the bearing rigidity of a network in an
arbitrary dimension. As a comparison, although a Laman graph
embedded in a generic configuration is infinitesimally distance
rigid [30], [34]–[37], this result, known as Laman’s Theorem
[70], is valid merely in two dimensional spaces. In three
or higher dimensions, extra conditions and more edges are
required to guarantee distance rigidity. The above comparison
is summarized in Table S1.
Why bearing rigidity has appealing properties in high dimensions can be explained intuitively from the perspective
of degree of freedom. For example, consider a network of n
nodes in d-dimensional space. The network has dn degrees
of freedoms. In order to ensure the rigidity of the network,

17

there must exist sufficient distance or bearing constraints to
reduce the degrees of freedom of the network to certain desired
values. Given a distance rigid network, when lifted up to
a higher dimension, the degrees of freedom of the network
increases while the number of constraints posed by an interneighbor distance remain the same. As a result, in order to
preserve distance rigidity in higher dimensions, more distance
constraints are required. As a comparison, when lifted to
a higher dimension, the number of independent constraints
posed by an inter-neighbor bearing also increases. For example, a bearing in the plane is equivalent to an azimuth angle
whereas a bearing in the three dimensional space is equivalent
to two bearing angles: azimuth and altitude. As a result, the
same number of bearings are still able to preserve the bearing
rigidity of the network.

B EARING R IGIDITY T HEORY FOR SE(2)
Consider a collection of n nodes in R2 × S 1 . Each point is
described by its position pi ∈ R2 and its orientation ψi ∈ S 1 .
An SE(2) network, denoted as (G, p, ψ), is the directed graph
G = (V, E), and the configuration (p, ψ), where each vertex
i ∈ V in the graph is mapped to the point (pi , ψi ) ∈ SE(2).
Note that SE(2) networks, directed graphs are considered.
Suppose (i, j) ∈ E is the kth directed edge where k =
{1, . . . , m} and m denotes the number of directed edges in E.
Let gk be the relative bearing of pj with respect to pi expressed
in the global frame. Then,


cos ψi
sin ψi
rk =
gk
− sin ψi cos ψi
is the bearing gk expressed in node i’s local reference frame.
Define the directed bearing function associated with the
m
SE(2) network, FSE : SE(2)n → S 2 , as
m

T T
FSE (p, ψ) = [r1T · · · rm
] ∈ S2 .

(S3)

The corresponding directed bearing rigidity matrix is defined
as the Jacobian of the directed bearing function,
RSE (p, ψ) ,

∂FSE (p, ψ)
∈ R2m×3n .
∂(p, ψ)

(S4)

Let δχ ∈ R3n be a variation of the configuration (p, ψ). If
RSE (p, ψ)δχ = 0, then δχ is called an infinitesimal SE(2)
bearing motion of G(p, ψ). There are three types of trivial
infinitesimal SE(2) motions corresponding to translations,
scalings, and coordinated rotations of the entire network. The
coordinated rotation involves an angular rotation of each agent
about its own body axis with a rigid-body rotation of the
network (see Figure S6). An SE(2) network is infinitesimally
bearing rigid if all the infinitesimal bearing motions are trivial.
A necessary and sufficient condition for an SE(2) network to
be infinitesimally bearing rigid is [80], [81]
rank[RSE (p, ψ)] = 3n − 4,
or equivalently

Null[RSE (p, ψ)] = span

1n ⊗ I2
0

 
  ⊥ 
p
p
,
,
,
0
1n

T
⊥ T T
and p⊥
where p⊥ = [(p⊥
1 ) , . . . , (pn ) ]
i = Rπ/2 pi . The
null-space is characterized in this way after a permutation of
the matrix that groups the positions and attitudes of all agents
together. Here Rπ/2 is a rotation matrix that rotates any vector
by π/2.
Detailed definitions in the SE(2) bearing rigidity theory
can be found in [26], [80], [81]. The SE(2) rigidity theory
has been employed for distributed relative position estimation
[26] and formation control [80], [81], [83]. A similar approach
has been extended for SE(3) [82].

18

TABLE S1: Comparison of infinitesimal bearing rigidity and infinitesimal distance rigidity.
Infinitesimal Bearing Rigidity (IBR)

Infinitesimal Distance Rigidity (IDR)

Unique geometric pattern

Yes, IBR ensures the unique pattern of a network.

No, IDR does not ensure the unique pattern of a
network (global distance rigidity does).

Rank condition

Yes, IBR corresponds to a rank condition of the
bearing rigidity matrix.

Yes, IDR corresponds to a rank condition of the
distance rigidity matrix.

Invariance to dimension

Yes, a network that is IBR in a lower dimension
remains IBR in a higher dimension.

No, a network that is IDR in a lower dimension may
be flexible in a higher dimension. (Universal distance
rigidity is invariant to dimensions)

Minimum edge number

In an arbitrary dimension, 2n − 3 edges are sufficient to ensure IBR. Less than 2n − 3 edges may
also be sufficient to ensure IBR in three or higher
dimensions.

In the plane, 2n−3 is the minimum number of edges
to ensure IDR. More than 2n − 3 edges are required
to ensure IDR in three or higher dimensions.

Laman graphs

In an arbitrary dimension, Laman graphs mapped to
almost all configurations result in IBR networks.

In the plane, Laman graphs mapped to almost all
configurations result in IDR networks. A similar
result does not exist in higher dimensions.

3
3

1

1

2

2

Fig. S6: Example of two congruent SE(2) networks. The above two networks
differ in terms of a translation, a scaling, and a coordinated rotation.

19

AUTHOR I NFORMATION
Shiyu Zhao is a Lecturer in the Department of Automatic Control and Systems Engineering at the University of
Sheffield, UK. He received the B.E. and M.E. degrees from
Beijing University of Aeronautics and Astronautics, China, in
2006 and 2009, respectively. He obtained the Ph.D. degree in
Electrical Engineering from the National University of Singapore in 2014. From 2014 to 2016, he served as post-doctoral
researchers at the Technion - Israel Institute of Technology and
University of California at Riverside. He is a corecipient of the
Best Paper Award (Guan Zhao-Zhi Award) in the 33rd Chinese
Control Conference, Nanjing, China, in 2014. His research
interests lie in networked dynamical systems and unmanned
aerial vehicles.
Daniel Zelazo is an Assistant Professor of Aerospace Engineering at the Technion - Israel Institute of Technology, Israel.
He received the B.S. (99) and M.Eng. (01) degrees in Electrical
Engineering from the Massachusetts Institute of Technology.
In 2009, he completed his Ph.D. from the University of
Washington in Aeronautics and Astronautics. From 2010 to
2012, he served as a post-doctoral research associate and
lecturer at the Institute for Systems Theory & Automatic
Control in the University of Stuttgart. His research interests
include topics related to multi-agent systems, optimization,
and graph theory.

