This article was downloaded by: [Nanjing University of Aeronautics & Astronautics]
On: 24 March 2013, At: 21:42
Publisher: Taylor & Francis
Informa Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House,
37-41 Mortimer Street, London W1T 3JH, UK
International Journal of Systems Science
Publication details, including instructions for authors and subscription information:
http://www.tandfonline.com/loi/tsys20
Optimal consensus algorithm integrated with obstacle
avoidance
Jianan Wang
a
& Ming Xin
a
a
Department of Aerospace Engineering, Mississippi State University, Starkville, MS 39762,
USA
Version of record first published: 14 Jul 2011.
To cite this article: Jianan Wang & Ming Xin (2013): Optimal consensus algorithm integrated with obstacle avoidance,
International Journal of Systems Science, 44:1, 166-177
To link to this article: http://dx.doi.org/10.1080/00207721.2011.598960
PLEASE SCROLL DOWN FOR ARTICLE
Full terms and conditions of use: http://www.tandfonline.com/page/terms-and-conditions
This article may be used for research, teaching, and private study purposes. Any substantial or systematic
reproduction, redistribution, reselling, loan, sub-licensing, systematic supply, or distribution in any form to
anyone is expressly forbidden.
The publisher does not give any warranty express or implied or make any representation that the contents
will be complete or accurate or up to date. The accuracy of any instructions, formulae, and drug doses should
be independently verified with primary sources. The publisher shall not be liable for any loss, actions, claims,
proceedings, demand, or costs or damages whatsoever or howsoever caused arising directly or indirectly in
connection with or arising out of the use of this material.
International Journal of Systems Science
Vol. 44, No. 1, January 2013, 166–177
Optimal consensus algorithm integrated with obstacle avoidance
Jianan Wang and Ming Xin
*
Department of Aerospace Engineering, Mississippi State University, Starkville, MS 39762, USA
(Received 23 December 2010; final version received 7 June 2011)
This article proposes a new consensus algorithm for the networked single-integrator systems in an obstacle-laden
environment. A novel optimal control approach is utilised to achieve not only multi-agent consensus but also
obstacle avoidance capability with minimised control efforts. Three cost functional components are defined to
fulfil the respective tasks. In particular, an innovative nonquadratic obstacle avoidance cost function is
constructed from an inverse optimal control perspective. The other two components are designed to ensure
consensus and constrain the control effort. The asymptotic stability and optimality are proven. In addition,
the distributed and analytical optimal control law only requires local information based on the communication
topology to guarantee the proposed behaviours, rather than all agents’ information. The consensus and obstacle
avoidance are validated through simulations.
Keywords: cooperative control; consensus algorithm; obstacle avoidance; optimal control
1. Introduction
Recent years have witnessed a rapidly growing atten-
tion to multi-agent cooperative missions for both
civilian and military applications. Cooperative control
has been recognised as the key enabling technology to
accomplish these cooperative missions. As a core of the
multi-agent cooperative control, consensus problem
has been extensively studied in recent years with a
variety of approaches. Vicsek, Czirok, Ben-Jacob,
Cohen, and Shochet (1995) showed that a nearest
neighbour rule can be used to achieve coordination of
n autonomous agents’ headings. Afterwards, the graph
theory, especially Laplacian matrix, has been widely
used to model the multi-agent information exchange
topology. Jadbabaie, Lin, and Morse (2003) provided
a theoretical explanation of the Vicsek model and
convergence results for several other similarly inspired
models using the graphic Laplacian. In Ren, Beard,
and McLain (2005), the consensus algorithm based
on the Laplacian matrix was derived for networked
single-integrator systems. Consensus problems with
switching topologies and time-delay in net-
worked single-integrator systems were addressed in
Olfati-Saber and Murray (2004). It has been shown
that the consensus can be achieved if the directed
communication topology is strongly connected and
balanced or the undirected topology is connected.
A less stringent condition was derived in Ren and
Beard (2005) to show that the consensus can be
achieved for networked single-integrator systems
under dynamically changing interaction topologies if
the union of the directed interaction graphs has a
spanning tree frequently enough as the system evolves.
In Moreau (2005), the notion of convexity and
set-valued Lyapunov theory were used to analyse the
convergence of the consensus algorithm under
time-dependent communication topologies. The con-
cept of semistability was used in Hui, Haddad, and
Bhat (2008) to develop the nonlinear information
consensus algorithm for single-integrator dynamical
networks. Necessary and sufficient conditions for
finite-time convergence were given.
The consensus algorithms for double-integrator
systems, or more complex nonlinear dynamics, were
also studied in the literature. Ren (2008) designed
different consensus algorithms for the double-
integrator dynamics under certain constraints, such
as, bounded control input, without relative velocity
measurement or tracking a reference. Hou, Cheng, and
Tan (2009) and Cheng, Hou, Tan, Lin, and Zhang
(2010) utilised a neural-network-based robust adaptive
control strategy to solve the consensus problem for
multi-agent systems with nonlinear dynamics and in
the presence of uncertainties.
The consensus algorithms have been investigated
from the optimisation perspective as well. Lin and
Stephen (2004) designed the consensus algorithm to
achieve the fastest convergence time by finding an
optimal weighting matrix. Kim and Mesbahi (2006)
constructed a proper configuration that maximises the
ISSN 0020–7721 print/ISSN 1464–5319 online
2013 Taylor & Francis
http://dx.doi.org/10.1080/00207721.2011.598960
http://www.tandfonline.com
Downloaded by [Nanjing University of Aeronautics & Astronautics] at 21:42 24 March 2013
second smallest eigenvalue of the Laplacian. An
optimal interaction graph (a de Bruijn’s graph) for
the average consensus problem was studied by
Delvenne, Giarre, and Zampieri (2007). Kazerooni
and Khorasani (2009) formulated the consensus prob-
lem as an optimisation problem using the linear matrix
inequality approach. A linear quadratic regulator
(LQR)-based optimal linear consensus algorithm was
proposed by Cao and Ren (2010) for single-integrator
multi-agent systems.
In order to accomplish cooperative missions in
realistic environments, obstacle/collision avoidance is
of practical importance. Olfati-Saber (2006) proposed
three flocking algorithms considering obstacle avoid-
ance. Zou, Pagilla, and Misawa (2007) introduced a
constraint force, directly converted from the structural
distance constraints for a desired formation, to fulfil
formation requirement as well as the collision avoid-
ance between multiple agents. A class of cooperative
control laws for individual agent to realise collision
avoidance in multi-agent systems was proposed in
Stipanovic, Hokayem, Spong, and Siljak (2007) and
their later works (Chopra, Stipanovic, and Spong 2008;
Mastellone, Stipanovic, Graunke, Intlekofer, and
Spong 2008; Hokayem, Stipanovic, and Spong 2010).
The collision avoidance is achieved by designing a
penalty function as part of the Lyapunov function and
proving that the avoidance behaviour is guaranteed
if this Lyapunov function decreases. However, the
cooperative control law does not guarantee optimality
when the agents are inside the obstacle detection
region.
Most of the obstacle avoidance strategies are
designed for multiple agents without considering opti-
mality and their interaction topologies (consensus),
which is critically important for coordination of
multiple agents. In this article, both consensus problem
and obstacle avoidance are addressed in a unified
optimal control framework. An inverse optimal con-
trol strategy (Bernstein 1993; Haddad and Chellaboina
2008) is proposed such that an analytical optimal
consensus law can be obtained and requires only local
information to implement.
The remainder of this article is organised as
follows. In Section 2, some preliminary notions and
definitions from the graph theory used in this article
are given. The problem is described in Section 3.
Section 4 presents the main result of this article.
Simulation results and analysis are shown in Section 5.
Some conclusion remarks are given in Section 6.
2. Preliminaries
This section briefly describes some preliminary nota-
tions, definitions, and notions from the graph theory.
In general, the information exchange among agents
can be modelled by the directed or undirected graph.
Let G ¼ðN, E Þ denote a directed graph, in which N is a
finite nonempty set of nodes and E is an edge set of
ordered pairs of nodes. A directed path is a sequence of
ordered edges of the form ði
1
, i
2
Þ, ði
2
, i
3
Þ, ..., where
i
j
2 N. For example, ði
1
, i
2
Þ2E indicates that agent i
2
obtains the information from agent i
1
. ði
1
, i
2
Þ2E in an
undirected graph is unordered.
A nonnegative adjacency matrix adj ¼½adj
ij
spe-
cifies the interconnection topology of a network of
agents, which is defined as adj
ii
¼ 0, adj
ij
¼ 1if
ð j, iÞ2E, and adj
ij
¼ 0ifð j, iÞ =2 E where i 6¼ j. For
the undirected graph, the adjacency matrix is symmet-
ric, i.e. adj
ij
¼ adj
ji
, 8i 6¼ j.
The Laplacian matrix L of graph G is defined as
(Ren and Beard 2008):
L ¼ D adj, ð1Þ
where D ¼ diagðadj 1Þ is the degree matrix of G with
diagonal elements d
i
¼
P
j
adj
ij
. Let 1 and 0 denote the
column vector of all ones and all zeros, respectively. In
the case of directed information exchange graph, L has
a simple zero eigenvalue with an associated eigenvector
1 and all of the other eigenvalues have positive real
parts if and only if the digraph has a directed spanning
tree. In the case of an undirected information exchange
graph, L has a simple zero eigenvalue with an
associated eigenvector 1 and all the other eigenvalues
are positive if and only if the graph is connected (Ren
and Beard 2008). Thus, L is positive semi-definite and
has the property of
L 1 ¼ 0: ð2Þ
This property will be used to derive the main results
of this article.
3. Problem statement
Consider n agents with identical single-integrator
dynamics given by
_
x
i
¼ u
i
, i ¼ 1, ..., n ð3aÞ
or in a matrix form
_
X ¼ U ð3bÞ
with
X ¼½x
T
1
, ..., x
T
n
T
, U ¼½u
T
1
, ..., u
T
n
T
,
where x
i
ðtÞ2R
m
and u
i
ðtÞ2R
m
are, respectively, the
state and control inputs of the ith agent. X 2 R
nm
and
U 2 R
nm
are, respectively, the aggregate state and
control inputs of all agents.
International Journal of Systems Science 167
Downloaded by [Nanjing University of Aeronautics & Astronautics] at 21:42 24 March 2013
The consensus problem in this article is to design a
distributed control law u
i
ðtÞ based on the information
exchange topology such that all the agents’ states
converge to the same value, i.e. kx
i
ðtÞx
j
ðtÞk ! 0. In
the meanwhile, it is guaranteed that each agent can
avoid the obstacle along its trajectory.
Figure 1 shows an example scenario of four agents’
consensus problem with one obstacle. For the conve-
nience of the problem formulation, the following
regions are defined:
Collision region for the jth obstacle:
j
¼
D
fxjx 2 R
m
, kx O
bj
kr
j
:g
Detection region for the jth obstacle:
j
¼
D
fxjx 2 R
m
, kx O
bj
kR
j
:g
Reaction region for the jth obstacle:
j
¼
D
fxjx 2 R
m
,r
j
5 kx O
bj
kR
j
:g.
Accordingly, the entire safety region can be
denoted as ¼ð
[
j
j
Þ
c
, and the entire outside detec-
tion region can be denoted as ¼ð
[
j
j
Þ
c
. The symbol
‘[’ denotes the union of sets and the superscript ‘c’
stands for the complement of a set.
In the scope of this article, we make the following
three assumptions:
A1. All the obstacles can be modelled as circle-
shaped objects.
A2.
j
\
k
¼ 1, j 6¼ k.
A3. The information exchange topology among
agents is assumed to be undirected and
connected.
Assumption A2 means that the detection regions of
multiple obstacles have no intersection. This assump-
tion is to exclude the scenario in which an agent steps
into the intersection region and cannot autonomously
determine which obstacle to avoid. It implies that each
agent will face only one obstacle at any instant. Future
research will be conducted to handle the special
scenario with a dense pack of obstacles appearing on
the trajectory at the same time.
4. Optimal obstacle avoidance consensus algorithm
In this section, the consensus problem is formulated as
an optimal control problem. We utilise an inverse
optimal control approach to derive a closed-form
obstacle avoidance consensus law that is a linear
function of ðL I
m
ÞX, which is based on the local
communication topology. denotes the Kronecker
product, which is used to extend the dimension. I
m
denotes the identity matrix with the dimension of m.
For the convenience of formulation, we define the
error state
^
X ¼½
^
x
T
1
^
x
T
2
^
x
T
n
T
¼
D
X X
cs
, ð4Þ
where X
cs
¼½1
1n
x
T
cs
T
is the final consensus state.
For instance, in a planar motion, x
cs
¼½
x
y
T
,
where
x
,
y
are the final consensus position along
x-axis and y-axis, respectively. According to the
property of the Laplacian L in (2), when the agents
reach consensus,
ðL I
m
ÞX
cs
¼ 0
nm1
: ð5Þ
Note that the final consensus state X
cs
will be a
constant and the consensus law U becomes zero when
the agents reach consensus.
Then, the error dynamics becomes
_
^
X ¼ U: ð6Þ
The consensus is achieved when the system (6) is
asymptotically stable.
The optimal obstacle avoidance consensus formu-
lation consists of three cost function components:
min: J ¼ J
1
þ J
2
þ J
3
s:t:
_
^
X ¼ U,
ð7Þ
where J
1
, J
2
, J
3
represent consensus cost, obstacle
avoidance cost and control effort cost, respectively.
The consensus cost has the form of:
J
1
¼
Z
1
0
^
X
T
R
1
^
X dt ¼
Z
1
0
^
X
T
w
2
p
L
2
I
m
^
X
hi
dt, ð8Þ
where L is the symmetric Laplacian matrix established
by the undirected and connected graph. w
p
represents
the weight on the consensus error. In order to show
that J
1
is a meaningful consensus cost, the following
proposition is of necessity.
Proposition 4.1: L
2
is positive semi-definite and
L
2
1
n1
¼ 0
n1
if the graph is undirected and connected.
Proof: Refer to Bernstein (2005). œ
Remark 4.1: Proposition 4.1 shows that R
1
is positive
semi-definite and J
1
is a meaningful consensus cost.
The formulation of R
1
in (8) is to guarantee that the
4 3
1
2
R
j
Consensus point
r
j
jth obstacle
Detection region
Figure 1. Multi-agent consensus scenario with an obstacle.
168 J. Wang and M. Xin
Downloaded by [Nanjing University of Aeronautics & Astronautics] at 21:42 24 March 2013
