Intern
ati
o
n
a
l Jo
urn
a
l
o
f
R
o
botics
a
nd Au
tom
a
tion
(I
JR
A)
V
o
l.
3, N
o
. 2
,
Ju
n
e
201
4, p
p
. 8
4
~
10
6
I
S
SN
: 208
9-4
8
5
6
84
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJRA
Distributed Receding Horizon Co
verage Control
by Multiple
Mobile Robots
Fate
meh Mohseni*,
Ali Do
ustmohammadi**, Mohamm
ad
B
a
gher Me
nhaj***
Departem
ent
of
Ele
c
tri
cal
Eng
i
n
eering
,
Am
irkab
i
r Univers
i
t
y
of
Techno
log
y
,
Te
hran,
Iran
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Aug 2, 2013
R
e
vi
sed M
a
r
3,
2
0
1
4
Accepted
Mar 24, 2014
This
paper
pres
e
n
ts
a dis
t
r
i
buted
reced
ing hori
z
on
cover
a
ge
contro
l algor
ithm
to control
a group of mobile robots having linear d
y
n
a
mics with th
e
assum
p
tion that
the
robot d
y
n
a
m
i
cs are
decou
p
led from
each
other
.
Th
e
objective of th
e coverag
e
algor
ithm c
onsidered
here is to m
a
xim
i
ze th
e
detection
of
the occurr
ence of
the ev
ents. First the authors
introduce
a
centr
alized
receding horizon co
verage
control
and th
en th
ey
introduce
a
distributed
version of it.
To avoi
d the common disadvantages that
ar
e
as
s
o
ciat
ed with the cen
tral
iz
ed appro
ach
, the pr
oblem
is
then decom
pos
ed
into s
e
ver
a
l RH
CC problem
s
,
ea
ch as
s
o
cia
t
ed wi
th a par
ticu
l
ar ro
bot, th
at ar
e
s
o
lved us
ing dis
t
ributed
techn
i
qu
es
. In order
to s
o
lve e
ach RHCC,
each robo
t
needs to know the trajector
ies o
f
its
neighbors during the optimization time
interv
al.
Sinc
e t
h
is inform
ation
i
s
not
av
ail
a
bl
e,
an
a
l
gorithm
is
pres
ented
to
estimate the trajector
y
of
the n
e
ighboring robots. To
minimize
th
e estimation
error,
a com
p
at
ibili
t
y
constr
ain
t
, which
is a
l
so a ke
y r
e
quir
e
m
e
nt in th
e
closed-loop st
ab
ilit
y
anal
y
s
is, i
s
considered
.
Moreover,
the
proof of th
e
close-loop stab
ility
o
f
this distrib
u
ted
version is p
r
ovided and shows that the
location of the robots will indeed conve
rge to
the cen
troids of a Voronoi
partition. Simulation resu
lts validate the algor
ithm and the convergence of
the robo
ts to
the
centro
i
dal Voron
o
i conf
iguration.
Keyword:
C
ove
rage
co
nt
r
o
l
Di
st
ri
b
u
t
e
d c
o
nt
r
o
l
Mu
lti ag
en
t sy
ste
m
s
Op
tim
al co
n
t
rol
Receding horiz
o
n
control
Stab
ility
Copyright ©
201
4 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
Fat
e
m
e
h M
o
hs
eni
,
Depa
rtem
ent of Elect
ri
cal
E
n
gi
nee
r
i
n
g,
Am
irk
a
b
i
r
Un
iv
ersity o
f
Tech
no
log
y
(Tehran Po
lytech
n
i
c)
Teh
r
an
, Ir
an.
Em
a
il: fate
m
e
m
o
h
s
en
i@au
t.ac.ir
1.
INTRODUCTION
App
licatio
n of m
u
lt
i-ag
en
t
syste
m
s fo
r con
t
ro
llin
g
a gro
u
p
of rob
o
t
s h
a
s g
a
i
n
ed a sign
ifican
t
at
t
e
nt
i
on i
n
rec
e
nt
y
ears d
u
e t
o
co
nsi
d
e
r
a
b
l
e
adva
n
cem
ent in com
puter te
chnolo
gy
.
R
e
s
earche
r
s have sho
w
n
that
m
u
ltiple robots could
potentially
acco
m
p
l
i
sh a task m
o
re efficiently
than a single
robot.
In a m
u
lti-agent
sy
st
em
, severa
l
aut
o
nom
ous
agent
s
are
si
m
u
l
t
a
neo
u
sl
y
c
o
or
di
nat
e
d a
n
d
cont
rol
l
e
d
i
n
or
der
t
o
ac
hi
e
v
e a
co
mm
o
n
syste
m
o
b
j
ectiv
e.
Th
e
u
n
d
e
rlying
assu
m
p
tio
n
is th
at in
mu
lti-ag
en
t syste
m
s, th
e ag
ents are
distributed in a predete
r
m
i
ned
fa
shi
on a
nd eac
h age
n
t
will act autonom
ously while excha
ngi
ng local
i
n
f
o
rm
at
i
on wi
t
h
nei
g
h
b
o
ri
ng
age
n
t
s
[
1
]
,
[2]
.
F
u
rt
h
e
rm
ore,
i
t
has
been
est
a
bl
i
s
he
d t
h
at
t
h
e
di
st
ri
b
u
t
e
d
cont
ro
l
approach am
ong a
u
tonom
ous agents
provi
des a better
sc
alability and im
prove
d tract
ability than centralize
d
approaches
.
W
i
t
h
th
e
prog
resses m
a
d
e
in
real-tim
e o
p
t
i
m
izatio
n
-
base
d control, som
e
researc
h
ers ha
ve s
u
ggest
e
d
n
e
w
d
i
stribu
ted
con
t
ro
l algo
rith
m
s
in
an
atte
m
p
t to
m
a
n
i
p
u
l
ate con
s
traints in
real-tim
e
[3
],
[4
].
On
e
maj
o
r
fact
or
fo
r co
nsi
d
erat
i
o
n i
n
de
v
e
l
opi
n
g
rel
i
a
bl
e di
st
ri
but
e
d
c
ont
rol
al
g
o
ri
t
h
m
s
i
s
l
o
cat
i
on
of
no
des f
o
r t
h
e ro
bot
network i
n
the
mission s
p
ace.
This is
refe
rre
d to as
the
c
o
verage c
ont
rol
or
active sensi
n
g
problem
[5], [6].
Th
e
d
e
p
l
o
y
m
e
n
t
lo
cation
o
f
th
e m
o
b
ile ro
bo
t m
u
st p
r
ov
id
e
fo
r m
a
x
i
m
u
m
in
form
at
io
n
retrieval,
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
089
-48
56
IJR
A
V
o
l
.
3,
No
. 2,
J
u
ne 2
0
14:
8
4
– 1
0
6
85
satisfacto
r
y commu
n
i
catio
n
lev
e
l, and
effectiv
e en
erg
y
co
n
s
u
m
p
tio
n
[7]. Si
m
i
lar to
ch
allen
g
e
s in
facility
lo
catio
n
o
p
timizatio
n
su
ch
as static p
r
ob
lems, an
o
f
flin
e sch
e
m
e
can
b
e
im
p
l
e
m
en
ted
to d
e
term
in
e co
verag
e
co
n
t
ro
l
b
y
d
e
plo
y
in
g
th
e
ro
bo
ts in
an
op
timal lo
catio
n
th
at will n
o
t
req
u
i
re m
o
b
ility.
As an
altern
at
iv
e, in
a
coo
r
di
nat
e
d
-
m
ovem
e
nt
dy
na
m
i
c schem
e
,
t
h
e
m
obi
l
e
rob
o
t
s
can be de
pl
o
y
e
d i
n
t
o
a geo
g
ra
p
h
i
cal
area wi
t
h
t
h
e
h
i
gh
est in
fo
rm
atio
n
d
e
n
s
ity. Howev
e
r, du
e to
si
m
ilari
t
i
es
b
e
tween
facility lo
catio
n
and
cov
e
rag
e
con
t
ro
l
o
p
tim
izat
io
n
,
i
ssu
es
reg
a
rd
ing
robo
t d
e
p
l
o
y
men
t
h
a
v
e
been
st
u
d
i
ed
u
s
ing facility lo
catio
n
o
p
tim
izat
io
n
[5
].
It h
a
s
b
een
d
e
t
e
rm
in
ed
th
at th
e lev
e
l of sensitiv
ity an
d
th
e d
o
m
ain
o
f
cov
e
rag
e
o
f
m
o
bile ro
bo
ts in
th
eir d
e
p
l
o
y
men
t
lo
catio
n
i
s
essen
tial to
th
e o
v
e
rall efficien
cy of th
e system n
e
twork. It inv
o
l
v
e
s a
com
p
rehe
nsi
v
e
cove
rage m
e
t
r
i
c
encom
p
assi
ng a
n
o
p
t
i
m
i
z
ed sensi
ng
per
f
o
rm
ance and
p
l
acem
e
nt
s of m
obi
l
e
robo
ts [5
], [8
]. Research
ers
hav
e
u
s
ed
Vo
ron
o
i
p
a
rtitio
n
i
ng
o
f
th
e reg
i
on
m
o
d
e
l to
red
u
ce ch
allen
g
e
s
o
f
th
e
locational optimization [9].
The focus
of the original
algorithm
,
for an optim
a
l
m
obile
robot placem
e
n
t, wa
s
on
co
o
r
di
nat
i
o
n a
n
d
c
ont
r
o
l
o
f
m
obi
l
e
r
o
b
o
t
s
, l
eadi
n
g
t
o
t
h
e
de
vel
o
pm
ent
of
m
o
re en
ha
n
ced
fo
rm
ul
at
i
ons a
n
d
coo
r
di
nat
i
o
n al
go
ri
t
h
m
s
by
ot
her
sch
o
l
a
rs
[
5
]
,
[8]
.
As
s
u
ch
, d
u
r
i
n
g re
cent
y
ears,
f
o
rm
ul
at
i
ng a
co
o
p
er
at
i
v
e
cont
rol
desi
g
n
am
ong
di
st
ri
b
u
t
ed age
n
t
s
assi
gne
d t
o
a spec
i
f
i
c
t
a
sk t
h
at
can na
vi
gat
e
au
t
o
n
o
m
ousl
y
wi
t
h
o
u
t
collision has received
si
gnificant
atte
ntions [1],
[10].C
onse
que
ntly, the c
once
p
t
of c
o
ordination a
n
d c
ont
rol
al
go
ri
t
h
m
s
for
net
w
or
ke
d dy
n
a
m
i
c
sy
st
em
s
has bec
o
m
e
a
central
foc
u
s
for re
searc
h
ers i
n
system
s and
cont
rol
arena
,
dra
w
ing overwhelm
i
ng
at
t
e
nt
i
ons
[
5
]
,
[1
1]
. F
o
r
exam
pl
e,
Du
n
b
ara a
n
d
hi
s c
o
l
l
eag
u
e
s ha
ve s
u
gges
t
ed a
design for formation pattern in a
m
u
lti-agent syste
m
based on
recedi
ng
horizon c
ontrol [1
2]. Meguerdchi
a
n
and
hi
s col
l
eag
ues ha
ve p
u
r
p
o
r
t
e
d cent
r
oi
dal
Vo
ro
n
o
i
con
f
i
g
uration
as a so
lu
tion
to
proble
m
s asso
ciate
d
with
area
of covera
ge in a
way tha
t
clarif
i
e
s t
h
e
i
ssue
o
f
c
ove
ra
ge c
ont
rol
.
T
h
e
y
have
p
r
ese
n
t
e
d t
h
ei
r al
g
o
r
i
t
h
m
s
i
n
a cen
tralized
man
n
e
r as a
practical ap
p
r
o
a
ch
an
d as
h
a
v
i
ng
a
po
ssib
ility for ap
p
lication [1
6
]
. C
o
rtes an
d h
i
s
associates [5] have s
u
ggeste
d a decen
tralized covera
ge control algorithm
for m
u
lti-robot
s in an area in a way
that the m
i
ssion space is
part
itioned i
n
Voronoi cells. Fr
om
this perspe
ctive, which is conside
r
ed i
n
this
pape
r, t
h
ey
ha
ve di
sc
usse
d s
e
ns
ory
co
nt
r
o
l
i
ssue w
h
i
c
h i
n
fact
i
s
t
h
e p
r
obl
em
of l
o
cat
i
onal
o
p
t
i
m
i
zati
on f
o
r
sens
ors
.
Wh
ile sign
ifican
t resu
lts h
a
v
e
b
e
en
ach
i
ev
ed,
th
ere is still ro
o
m
fo
r n
e
w ideas an
d
furth
e
r
im
pro
v
em
ent
s
.
Thi
s
pa
per p
r
esent
s
a di
st
ri
b
u
t
e
d rece
di
n
g
ho
ri
zo
n
c
o
vera
ge
c
ont
rol
(D
R
H
C
C
)
al
g
o
ri
t
h
m
for
co
n
t
ro
lling
a
group
of m
o
b
ile robo
ts hav
i
n
g
lin
ear
d
y
n
a
m
i
c
s
with
t
h
e assum
p
t
i
o
n
th
at t
h
e robo
t d
y
n
a
m
i
c
s
are
decoupled from each other.
The algo
rithm
will provide for
m
a
xi
m
u
m
even
t detection t
h
rough confl
u
e
n
ce of
robo
ts po
sitio
n to
a cen
t
r
o
i
d
a
l Vorono
i Configu
r
ation
.
Th
e p
r
op
o
s
ed
al
g
o
rith
m
en
su
res
en
h
a
n
c
ed
co
v
e
rage
an
d stab
ility.
Co
n
c
ep
ts exp
l
o
ited
fo
r t
h
eo
retical fram
e
w
o
rk
in
cl
u
d
e
Lo
catio
n
a
l op
timizatio
n
,
reced
i
ng
horizon
co
n
t
ro
l, d
i
stri
bu
ted
cov
e
rag
e
con
t
ro
l, cen
t
ro
id
al
Vo
ro
no
i
p
a
rtitio
n
s
and are
briefly d
i
scu
ssed
i
n
th
e n
e
x
t
sect
i
on. C
e
nt
r
a
l
i
zed rece
di
n
g
h
o
r
i
z
o
n
c
o
v
e
rage c
o
nt
r
o
l
(C
R
H
C
C
)
a
p
p
r
oac
h
fo
r a
gr
ou
p
of l
i
near
m
obi
l
e
ro
b
o
t
s
i
s
prese
n
t
e
d i
n
sect
i
o
n
3. Usi
ng t
h
e r
e
sul
t
s
of t
h
i
s
sect
i
on, t
h
e
di
st
ri
b
u
t
e
d rece
di
n
g
h
o
ri
z
on c
o
ve
rag
e
co
n
t
ro
l (DRHCC) alg
o
rith
m is g
i
v
e
n
i
n
sectio
n
4. In
se
ctio
n
5, stab
ility an
alysis o
f
clo
s
ed-loo
p
syste
m
is
stu
d
i
ed
an
d it is prov
ed
t
h
at by u
s
ing
sugg
ested
DR
HCC
al
g
o
rith
m
,
th
e cl
o
s
ed
-loop
syst
e
m
is stab
le and
will
co
nv
erg
e
to
cen
t
ro
id
al
Voro
no
i co
nfigu
r
atio
n
.
Sec
tion 6
p
r
esen
ts
si
m
u
latio
n
results th
at v
a
lid
ate th
e
al
go
ri
t
h
m
and t
h
e co
nve
rge
n
ce of t
h
e a
g
ent
s
t
o
t
h
e desi
re
d co
nfi
g
u
r
at
i
o
n, a
nd fi
nal
l
y
, sect
i
on 7 s
u
m
m
a
ri
zes
th
e m
a
in
resu
lt
s of th
is p
a
p
e
r.
2.
BA
C
KGR
OUN
D
S
2.
1.
Loca
tion
al O
p
timiz
a
tion
Thi
s
sect
i
on
pr
esent
s
som
e
fact
s regar
d
i
n
g t
h
e m
e
t
hod use
d
t
o
de
scri
be
c
o
ver
age c
ont
r
o
l
for m
obile
sen
s
ing n
e
t
w
or
k in [5
] and in
t
h
e
f
r
a
m
e
w
o
r
k
of
l
o
catio
nal op
ti
m
i
zat
io
n
p
r
esen
ted in [9
] wh
ich
u
n
d
e
r
p
i
n
s
cove
ra
ge al
g
o
r
i
t
h
m
s
depi
ct
ed
i
n
V
o
ro
n
o
i
di
a
g
ram
.
Ass
u
m
e
that
S
be a convex s
p
a
ce in
2
and
1
,
...,
n
Pp
p
b
e
th
e lo
cation
of
n
m
obi
l
e
robot
s
,
i
.
e.
i
pS
den
o
t
e
s
i
th
robot position. Furt
herm
ore, assum
e
that
m
ove
m
e
nt of each
robot is confi
n
ed i
n
S
and
1
,
.
..,
n
WW
W
is a tessellatio
n
o
f
S
such that
()
(
)
ij
IW
I
W
.
(.
)
I
denotes interi
or space
of ea
ch
i
W
and
1
n
i
i
WS
. So, it is
suppose
d that
each a
g
e
n
t
i
is on
ly respo
n
s
i
b
le to cov
e
r its do
m
a
in
i
W
.
To
ob
tain
th
e pro
b
a
b
ility
of an
ev
en
t
occu
rring
at a po
in
t in
S
, t
h
e
m
a
ppi
n
g
:
S
is defin
e
d
.
No
te th
at in
t
h
i
s
sense,
is th
e d
i
strib
u
tion
d
e
nsity fu
n
c
tion
.
As robo
t
i
m
ove
s fu
rt
he
r away
fr
om
any
gi
ven
poi
nt
s
in
sid
e
t
h
e
m
i
ssion space
S
,
i
t
s
sensi
n
g pe
r
f
o
r
m
a
nce at
po
i
n
t
s
tak
e
n fr
om
i
th
sensor l
o
cated at
ii
pW
red
u
c
es with
the
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA I
S
SN
:
208
9-4
8
5
6
Distrib
u
t
ed
Reced
ing
Horizon
C
o
verag
e C
o
n
t
ro
l
b
y
Mu
ltiple Mob
ile Robo
ts (Fa
t
emeh
Moh
s
en
i)
86
distance
(,
)
ii
dsp
s
p
b
ecause of no
ise and
lo
ss of
reso
lu
tio
n
.
T
h
i
s
re
duct
i
o
n i
s
de
fi
ned
by
fu
nct
i
o
n
:
g
. As
a m
easure
m
ent
fo
r sy
st
e
m
's per
f
o
r
m
a
nce, co
ve
rage
c
o
st
f
u
nct
i
o
n
i
s
descri
bed
as
11
(,
)
(
,
)
(
(
,
)
)
(
)
,
i
nn
ii
i
ii
W
J
PW
J
p
W
g
d
s
p
s
d
s
(1
)
whe
r
e
J
is a d
i
fferen
tiab
l
e fun
c
tio
n
.
No
te th
at
th
e co
st fun
c
tio
n
J
m
u
st b
e
m
i
n
i
mized
in
regard
s to
location
of robots a
n
d
partition
of t
h
e space.
2.
2.
C
e
n
t
ro
ida
l
V
o
ro
no
i
Co
nf
igura
t
io
n
A col
l
ect
i
o
n
of
poi
nt
s
1
,
...,
n
Pp
p
gene
rat
e
V
o
r
o
noi
Di
a
g
ra
m
whi
c
h i
s
defi
ne
d a
s
1
{
,
...,
}
n
VV
V
and
i
V
th
at co
m
m
o
n
l
y is r
e
f
e
rred
to
as Vo
rono
i do
m
a
in or
Voronoi cell associated with
poi
nt
i
p
are define
d by
:(
,
)
(
,
)
,
ii
j
Vs
S
d
s
p
d
s
p
j
i
The above definition is commonly used
to describe Voronoi
partition [5]
,
[9]. Voronoi
partitioni
ng
is one of
the im
portant t
ools in l
o
cali
zation optim
izat
i
o
n
theory.
Definiti
on 1
[
1
3
]
. F
o
r r
o
bot
i
all neighboring Voronoi
robots (m
eaning
i
) are desc
ribe
d
as collection
of
robots with a shar
ed Voronoi cell
bord
er.
B
a
sed on definit
i
on of
Voronoi partitioni
ng we
have
1
,
...,
mi
n
(
(
,
)
)
(
(
,
)
)
in
i
i
g
dsp
g
d
s
p
For eac
h
j
s
V
accordi
ngly,
1
,
.
..,
(,
(
)
)
m
i
n
(
(
,
)
)
(
)
in
i
S
J
PV
P
g
d
s
p
s
d
s
(2
)
To continue, the two results
pr
esented in
[5] a
r
e re
viewe
d
.
Prop
osi
t
i
o
n 1 [5
].
On
e of
th
e n
ecessar
y
cond
iti
ons t
o
m
i
nim
i
ze (1) is tha
t
W
partitioni
ng
m
u
st be equal
to
Voronoi configuration
()
VP
.
A
ccord
ing
to (2
)
()
(
,
)
((
,
)
)
(
)
i
Vi
i
i
V
ii
i
JP
J
p
V
g
ds
p
s
d
s
pp
p
So,
partial derivative of
V
J
with respect to
i
th
robot is only associated with
position of the robot itself and it
s
neig
hb
o
r
s. Ne
xt, we
discuss
som
e
of the co
ncepts ass
o
ciated with
Voronoi diagram
.
In [5], the (ge
n
eralized)
m
a
ss and first
m
o
m
e
nt (not
norm
alized) and center of
Voronoi cell a
r
e
defined a
s
()
()
,
()
,
()
ii
ii
i
ii
i
i
VV
VV
V
VV
V
V
s
sd
s
L
Ms
d
s
L
s
s
d
s
C
M
s
ds
(3
)
Using t
h
e above definition
and
proposition and letting
1
2
i
g
sp
,
we
have
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN:
2
089
-48
56
IJR
A
V
o
l. 3,
No
. 2,
J
u
ne 2
0
14:
8
4
– 1
0
6
87
()
((
,
)
)
(
)
(
)
ii
i
V
iV
i
V
V
ii
JP
g
ds
p
s
d
s
M
p
C
pp
(4
)
Th
us, the local
m
i
nim
u
m
points fo
r the
locational opti
m
i
z
a
tion cost function
V
J
are centroids
of Voronoi
cells. In
othe
r
wo
rd
s, to m
i
nim
i
ze
V
J
, each
robot m
u
st not only be a ge
nera
t
o
r
point of its own
Voronoi c
e
ll
but also m
u
st
be at the center of the cell [5].
Accordingly, the critical
partitions and points for
J
are called
centroidal Voronoi partitions.
W
e
will refer
to a robots’ confi
g
urati
on as
a centroi
dal Voronoi confi
g
uration
if it gives rise to a centro
idal Voronoi
partition [5].
2.
3.
Receding Hor
i
z
o
n Contr
o
l (RHC)
RHC is an opt
i
m
i
zation a
p
proach that ca
n
be
used
for syste
m
s, even if
som
e
constrai
nts on states
and inputs exist.
I
n
R
H
C
,
t
h
e
cu
rre
nt c
ont
ro
l law
is obtained by
solvi
n
g a
fin
ite horizon opti
m
a
l
proble
m
at
each sam
p
ling instant. Eac
h
optim
ization
gene
rates a
n
open-loop optim
al control
trajectory, and t
h
e first
portion
of t
h
is
optim
al control
traj
ect
ory is app
lied to
system
until next sam
p
l
i
ng tim
e [4], [15].
The c
o
ntribution of t
h
is pa
per is
using R
H
C (t
he
state
space-base
d m
odel
predictive
control) i
n
or
der t
o
co
ve
r
a
ge an e
n
vir
o
n
m
ent. There
f
or
e, first we
su
g
g
est centralize
d
rece
din
g
ho
r
i
zon c
ove
ra
ge
cont
rol
and then this centralized
approach will be extended to
a
distributed approach.
In t
h
e sections that foll
ow,
the RHC a
ppro
ach
is
u
s
ed
to
dr
iv
e a
gr
ou
p
of
n
m
obile robots at
centroidal Voronoi
configurat
ion.
3.
CENT
RALIZ
ED RE
CED
I
NG
HO
RIZ
O
N
CO
VER
A
G
E
CO
NTR
O
L
(C
RH
C
C
)
The c
o
ope
rative
recedi
n
g horiz
o
n coverage control
approach for m
u
ltiple linear m
obile robots i
s
pr
o
pose
d
in t
h
is section. T
h
e
ob
jective
is t
o
asym
ptotically force a
group
of
n
linear
m
obile robots toward
centroidal Voronoi configur
a
tion in a coo
p
e
rative m
a
nner usin
g rece
ding
ho
rizo
n co
ntr
o
l. To d
o
so, let
1
(
)
(
,
..
.,
)
n
P
tpp
be a
n
-vector whose elem
ents ar
e robots’
pos
ition, i.e.
()
(
(
)
,
()
)
ii
i
pt
x
t
y
t
, and
1
(
,
.
..,
)
n
VV
V
CC
C
be a
vector
of
Voronoi cells c
e
ntroids. T
h
e
overall system
dynam
i
c can
be
descri
bed as
()
()
,
0
,
Pt
ut
t
(5
)
whe
r
e
(0
)
P
is kn
ow
n an
d
2
()
n
Pt
and
2
()
n
ut
ar
e state an
d
input v
ecto
r
s
r
e
sp
ectiv
ely.
I
t
is assu
m
e
d
that there
exist
som
e
constrai
nts
on state and input, i.e
.
()
n
Pt
and
()
n
ut
u
whe
r
e
n
and
n
u
are t
h
e
state and input
constraints sets respectively.
Assum
p
ti
on 1.
u
is a com
p
act and a c
o
nnecte
d
set that
contai
ns
ori
g
in i
n
its
interior
Each
robot ca
n m
easure all of its states.
The com
putational tim
e is negligible
The c
o
vera
ge
algo
rithm
pro
p
o
se
d in
this
p
a
per
is
base
d
on
V
o
ro
n
o
i di
agram
.
A
u
re
n
h
am
m
e
r ha
s
sho
w
n that the
dual o
f
V
o
r
o
noi dia
g
ram
is Delaunay
tria
ng
ulation
w
h
ich lies un
der
g
r
ap
h the
o
ry
co
ncept
[1
3]
. T
o
pr
oce
e
d, t
h
e c
ove
ra
g
e
p
r
o
b
lem
is investigated
usi
n
g
gra
p
h the
o
ry
.
Lemma
1 ([13] Lemm
a 2.4).
Tw
o poi
nts
o
f
P
in Voronoi di
agram
are connected
with a
Delaunay edge, iff
th
eir
co
rr
espond
ing
Voro
no
i cells ar
e adj
acen
t
.
These t
w
o poi
n
ts (or robot
s) are
called neighbors.
By drawi
ng
robots’ Voronoi diagram
and its corresponding Delaunay
graph,
the
set of robots’ positions
can
be shown wit
h
a graph
where its ve
rtexes are robots position and its
edges are connecti
n
g segm
ent between
any
two
neig
h
b
o
r
in
g r
o
bots
.
We de
n
o
te the
cove
ra
ge g
r
ap
h to
pol
ogy
by
(
,
),
1
,
...
,
,
GV
E
V
n
E
V
V
.
Each edge i
n
graph is illust
rated with
an ordered pair
(,
)
ij
E
, w
h
ere
,
ij
ar
e an
y two n
e
ig
hbo
r
i
ng
r
obo
ts.
Ou
r co
vera
ge
gra
p
h is assum
e
d to be u
n
d
ire
c
ted. He
nce,
(,
)
(
,
)
ij
j
i
. R
o
b
o
ts
,
ij
are called neighbors if in
the cove
ra
ge g
r
ap
h
(,
)
ij
E
. The set of
neig
hb
or
s o
f
i
th
rob
o
t is denote
d
by
i
V
. Each ele
m
ent of
E
is
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA I
S
SN:
208
9-4
8
5
6
Distributed Receding
Hori
zon C
o
verage C
o
ntrol
by M
u
ltiple Mo
bile Robots (Fatemeh
Mohseni)
88
d
e
no
ted b
y
i
e
.
Accordingly,
1
,.
.
.
,
M
Ee
e
, w
h
ere
M
is the num
b
er of
Delaunay edge
s.
To
pr
ocee
d,
w
e
nee
d
to
de
fin
e
the
pr
op
ose
d
n
o
tion
o
f
"
c
o
verage vector" and
"
c
overage matrix".
Befo
r
e
th
at
we
defin
e
the
desire
d c
o
nn
ecting
vecto
r
betwee
n a
n
y two n
e
ig
hbo
r
s
in
a co
ver
a
ge g
r
aph
,
d
e
n
o
ted
by
2
ij
d
as
j
i
ij
V
V
dC
C
(6
)
This vector has
the
following property
ij
j
i
dd
(7
)
Definiti
on 2. "
coverage
vect
or"
and "
c
overage
matrix"
: t
h
e
"
c
overage v
ector
" d
e
no
ted b
y
COV
is
defi
ned
as
2(
)
11
(
,
...,
,
...,
,
,
...,
)
,
M
n
lM
M
M
n
C
O
V
c
o
v
co
v
c
o
v
co
v
c
o
v
w
h
er
e
,1
,
.
.
.
,
,
(
,
)
li
j
i
j
cov
p
p
d
l
M
i
j
E
(8
)
and
1
,
...,
k
Mk
k
V
cov
p
C
k
n
(9
)
The
robots will be in centroi
da
l Voronoi configuration,
nam
e
ly
V
P
C
, w
h
en
0
CO
V
. Hence,
we ca
n
write
the linear m
a
pping
from
P
to
COV
as:
,
COV
T
P
d
(1
0)
whe
r
e
(.
..
,
,
..
.,
,
.
..)
k
ij
V
dd
C
,.
1
,
...,
,
fo
r all
(
,
)
kn
i
j
E
.
We call
T
as
"
coverage
matrix"
.
From
defi
nition
of the covera
ge vector, we know
t
h
at
if
t
h
en
0
V
COV
T
P
d
P
C
COV
T
h
e
r
efo
r
e
0
VV
TC
d
d
TC
(1
1)
Substitution of (11) int
o
(10)
yields:
()
VV
COV
T
P
T
C
T
P
C
(1
2)
Lemma 2.
The
co
vera
ge m
a
trix
T
used
in (10) has full
rank and it is equal t
o
dim
(
)
2
Pn
.
Proof.
Using the definition
of m
a
trix
T
, one can veri
fy that it can be written as
T
T
T
, whe
r
e
T
is an
identity m
a
trix of size
2
n
. T
h
ere
f
ore the
cove
ra
ge m
a
trix
T
in (10) has full rank equal to
dim
(
)
2
Pn
.
□
Matrix
T
give
n i
n
the a
b
o
v
e f
o
r
m
ulation is a g
e
neralized i
n
cidence m
a
trix o
f
the co
ve
rage
gra
p
h an
d ca
n be
obtained
from
the incidence
m
a
trix of the covera
ge graph by
m
u
ltiply
ing every elem
ent
of
that m
a
trix by
2
I
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN:
2
089
-48
56
IJR
A
V
o
l. 3,
No
. 2,
J
u
ne 2
0
14:
8
4
– 1
0
6
89
whe
r
e
2
I
is an i
d
entity m
a
trix of size
2.
Furtherm
ore, si
nce our coverage
graph is a Del
a
unay
graph, it is
connected [13], and its
ge
nera
lized in
cide
nce
m
a
trix has
a
r
a
nk
eq
ual to
2(
1
)
n
.
Definiti
on 3.
T
h
e ce
ntralized
recedi
n
g horiz
o
n cove
rage
control cost
func
t
i
on is de
fine
d a
s
:
2
2
(,
)
(
(
),
(.),
)
[
(
)
(
)
(
)
p
th
pi
j
i
j
V
ij
E
t
HP
t
u
h
p
p
d
P
C
2
2
()
]
(
,
(
)
)
,
pV
ud
P
t
h
P
t
C
(1
3)
whe
r
e
,,
are positive
weighting cons
tants.
The first and second term
s in
(13) are tracking term
s, the third
term
is a ter
m
for
m
i
nim
i
zing cont
rol e
f
f
o
rt,
and
the last term
is called term
inal control cost.
Prop
osi
t
i
o
n 2.
Using the above
definitions
and
Lem
m
a
, we can descri
be th
e CR
HCC cost function (13)
d
e
sign
ed
to dr
iv
e a
gr
oup
o
f
n
r
o
b
o
ts t
o
a ce
ntr
o
idal
Vo
r
o
n
o
i
con
f
ig
uratio
n
b
y
a cost
fu
nctio
n
give
n
by
:
2
2
2
(
(
),
(.),
)
(
;
(
))
(
)
(
;
(
)
)
p
th
pV
p
V
R
Q
G
t
H
P
t
u
h
P
Pt
C
u
d
P
t
h
Pt
C
(
14)
Proof.
As it has been p
r
ove
d
in [13], a Delaunay graph is connected.
Furthe
rm
ore, as stated before, the
cove
ra
ge gr
ap
h co
nside
r
ed i
n
this pa
per is Delau
n
ay
and
thus it is a con
n
ected g
r
a
p
h
.
I
f
the co
vera
ge
gra
p
h
was
not c
o
n
n
e
c
ted, it co
uld
be se
parate
d to at least
two sub
-
gra
p
hs.
M
o
re
ove
r,
t
h
e cost
f
u
nction wo
uld
b
e
separate
d in to
m
o
re than
on
e cou
p
led c
o
st
fu
nction
.
Sinc
e by
Lem
m
a 2 the cove
ra
ge
m
a
trix has f
u
ll ran
k
,
T
TT
is a positive
definite m
a
trix an
d hence
usi
n
g (12)
one can get
2
2
((
)
(
)
)
T
TT
VV
V
TT
CO
V
P
C
T
T
P
C
P
C
(1
5)
We de
note
,
T
QT
T
G
I
and
RI
(w
he
re
I
is an identity
m
a
tri
x
). Si
nce
,,
are
positive, the
m
a
trices
Q
,
G
,
and
R
are positive definite m
a
trices, and consideri
ng
1
,.
.
.
,
n
VV
V
CC
C
, (13) can
be rewritten
as:
2
2
2
(
(
)
,
(.
),
)
(
;
(
))
(
)
(
;
(
)
)
p
th
pV
p
V
R
Q
G
t
HP
t
u
h
P
P
t
C
u
d
P
t
h
P
t
C
whic
h is i
ndee
d
e
qual t
o
(1
4)
.
No
w
by
usin
g t
h
e a
b
o
v
e c
o
nc
epts, t
h
e C
R
H
CC problem
ca
n
be stated as
follows:
Probl
em 1.
C
R
HCC p
r
ob
lem:
Find
*
(.
)
(
(
),
)
m
in
(
(
),
(.
)
,
),
p
p
u
H
Pt
h
H
P
t
u
h
with
2
2
2
(
(
)
,
(.
),
)
(
;
(
))
(
)
(
;
(
)
)
p
th
pV
p
V
R
Q
G
t
HP
t
u
h
P
P
t
C
u
d
P
t
h
P
t
C
subject t
o
:
()
()
()
,
,
(;
(
)
)
p
Pu
ut
t
h
PP
t
S
u
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA I
S
SN
:
208
9-4
8
5
6
Distrib
u
t
ed
Reced
ing
Horizon
C
o
verag
e C
o
n
t
ro
l
b
y
Mu
ltiple Mob
ile Robo
ts (Fa
t
emeh
Moh
s
en
i)
90
2
2
(;
(
)
)
(
)
:
:
,
0
n
pV
G
Pt
h
P
t
P
P
C
(1
6)
No
te th
at (16
)
represen
ts th
e ter
m
in
al co
n
s
train
t
[10
]
, [12
]
. Assu
m
e
th
at th
e first segmen
t o
f
th
e op
ti
m
a
l
cont
rol
pr
obl
e
m
i
s
sol
v
ed at
t
i
m
e
i
n
st
ant
0
t
,
c
h
i
s
t
h
e rece
di
n
g
h
o
ri
z
on
u
pdat
e
peri
od
, an
d t
h
e
cl
osed l
o
o
p
syste
m
that we wish to stabilize at
C
V
is
*
0
()
()
,
,
P
ut
(1
7)
wh
er
e
*
(;
(
)
)
uP
t
,
,
p
tt
h
, is th
e op
en-loop
o
p
ti
m
a
l so
lu
tion of Prob
lem
1
.
Th
is
o
p
tim
al
con
t
ro
l
so
lu
tion
is app
lied
to th
e syste
m
u
n
til
c
th
, i.e. th
e app
lied con
t
ro
l t
o
the syste
m
in
th
e tim
e in
terv
al
,
c
tt
h
,
0
cp
hh
is
**
()
(
;
(
)
)
,
,
c
uu
P
t
t
t
h
. The ope
n
-l
oop optimal state
trajectory is
d
e
no
ted as
*
(;
(
)
)
PP
t
.
B
a
sed
on
t
h
e
r
e
sul
t
s
o
f
C
R
H
C
C
obt
ai
ne
d i
n
t
h
i
s
sect
i
o
n,
a
DR
HC
C
al
go
ri
t
h
m
i
s
pro
p
o
s
e
d
i
n
t
h
e
ne
xt
se
ct
i
on.
4.
DIST
RIBUT
E
D
RE
CED
I
NH HO
RIZ
O
N CO
VER
A
G
E
CO
NTR
O
L
In DR
HCC approach the
objec
tiv
e is to
force a g
r
o
u
p
of
n
ro
bo
ts to
cen
tro
i
d
a
l Vo
ron
o
i
con
f
i
g
urat
i
o
n
i
n
a
di
st
ri
b
u
t
e
d
m
a
nner
usi
n
g
R
H
C
.
I
n
C
R
H
C
C
app
r
oach
,
t
h
e co
nt
r
o
l
l
a
w
re
qui
re
s ce
nt
r
a
l
i
zed
i
n
f
o
rm
at
i
on an
d com
put
at
i
o
n
s
. The DR
HC
C
appr
oac
h
p
r
op
ose
d
i
n
t
h
i
s
sect
i
on, av
oi
ds t
h
e di
sa
d
v
a
n
t
a
ges
associated with
CRHCC appro
ach.
Let
2
i
p
and
2
i
u
be st
at
e and c
ont
rol
i
n
p
u
t
o
f
t
h
e
th
i
r
obo
t, wh
er
e
1
,
...,
in
. It is assu
m
e
d
th
at ro
bo
ts’
dynam
i
cs are decoupled from
each
othe
r a
n
d
hence
their dy
nam
i
cs can be
written as:
()
()
,
0
,
(
0
)
g
i
v
e
n
ii
i
pt
ut
t
p
(1
8)
To
ach
i
ev
e th
e d
e
sired co
st
fu
n
c
tion
,
th
e cou
p
ling th
at is
i
n
h
e
ren
t
with the cen
tralized
ap
pro
ach is elimin
ated
by
de
fi
ni
ng
n
di
ffe
re
nt
co
st
s,
o
n
e fo
r
eac
h r
o
b
o
t
,
a
n
d o
n
l
y
t
h
e
c
o
nnect
i
o
ns bet
w
ee
n
a
n
y
gi
ve
n ro
b
o
t
and
i
t
s
n
e
igh
bors are
p
r
esen
t.
To facilitate th
e resu
l
t
s, th
e term
in
al con
s
train
t
and th
e term
in
al co
st are assu
m
e
d
to b
e
d
ecoup
led
,
i.e.
1
(
,
..
.,
)
n
Gd
i
a
g
G
G
. Furth
e
rm
o
r
e, in
ad
d
ition
to
prev
i
o
u
s
co
n
s
train
t
s,
a co
m
p
atib
ili
t
y
constraint is a
dde
d t
o
e
n
sure
that each robot does
not m
o
ve away too
far from
the tr
aje
c
tory expecte
d
by its
n
e
igh
bors
[12]. It will
b
e
ex
p
l
ain
e
d later.
It is also
assu
m
e
d
th
at
,
p
c
hh
are id
en
tical fo
r all ro
bo
ts.
C
onsi
d
eri
ng (
5
)
a
nd defi
ni
ng
1
(
)
(
,
..
.,
)
n
P
tpp
and
1
(
,
..
.,
)
n
uu
u
, the overall system dynam
i
c can be
decom
pose
d
i
n
t
o
n
su
b-sy
st
e
m
s havi
n
g
t
h
e dy
nam
i
cs gi
ven by
(
1
8
)
. Acc
o
r
d
i
n
gl
y
,
t
h
e o
b
ject
i
v
e i
s
t
o
desi
gn
a
DRHCC for
each robot t
h
at drive
s
the robot
to
the centroid of
it
s own cell in centroidal
Voronoi
co
nfigu
r
ation, wh
ile
co
op
eratin
g
with
its n
e
i
g
hbo
rs.
Definiti
on 4
.
The DR
HCC cost function for each
robot with the obj
ective of
reachi
n
g its ce
ll’s centroid i
n
cent
r
oi
dal
Vo
r
o
n
o
i
c
o
n
f
i
g
urat
i
on i
n
a c
o
op
er
at
i
v
e way
wi
t
h
i
t
s
nei
g
hb
or
s, i
s
de
fi
ne
d as:
2
2
(
(
)
,
(
)
,
(
.
)
,
)
()
()
(
)
2
p
i
i
th
i
i
jip
i
j
i
j
i
V
j
t
Hp
t
p
t
u
h
p
p
d
p
C
2
2
()
(
,
(
)
)
i
i
ii
p
i
V
G
ud
P
t
h
p
t
C
(1
9)
In the ne
wly considere
d
sys
t
e
m
, the state
and the co
nt
rol constrai
nts are separate
d for eac
h robot, i.e.
2
()
i
pt
and
2
()
i
ut
u
.
Give
n
1
(
,
..
.,
)
n
R
di
ag
R
R
, con
t
ro
l co
st can
b
e
rewritten
as
2
2
1
i
n
i
R
R
i
uu
, whe
r
e
eac
h
i
R
I
is a
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
089
-48
56
IJR
A
V
o
l
.
3,
No
. 2,
J
u
ne 2
0
14:
8
4
– 1
0
6
91
p
o
s
itiv
e
d
e
fi
n
ite
m
a
trix
. To
p
r
o
ceed
fu
rth
e
r, th
e no
tion
s
o
f
“
distribute
d
coverage vect
or
” and “
di
st
ri
but
e
d
cover
age
matrix
” are
nee
d
ed
.
B
e
fo
re t
h
at
,
so
m
e
not
at
i
o
ns
m
u
st
be defi
ne
d.
As stated i
n
se
ction
3,
i
N
is th
e
set th
at con
t
ain
s
th
e n
e
i
g
hbor
s of
t
h
e
th
i
ro
bot
nei
g
h
b
o
r
s.
Th
eref
ore
,
t
h
e
r
e
ex
ists a D
e
laun
ay ed
g
e
b
e
tw
een
th
e
r
obot an
d
its n
e
igh
bor
s. Let
(..
.
,
,
..
.)
ij
pp
and
(
...
,
,
.
..)
ij
VV
CC
whe
r
e
i
j
N
, d
e
no
te th
e state an
d
cen
tro
i
d
v
ect
o
r
s o
f
th
e n
e
ighbo
r
s
o
f
rob
o
t
i
respectively.
Now for eac
h
r
obo
t,
i
, defi
ne t
h
e
f
o
l
l
o
wi
n
g
v
ect
or:
1
(
.
..,
,
...
,
)
i
ii
i
l
N
cov
c
o
v
cov
,
w
h
er
e
1
,
...,
,
i
li
j
i
j
i
i
co
v
p
p
d
l
N
j
N
(2
0)
1
i
i
i
iV
N
co
v
p
C
(2
1)
and
i
N
is the
number of elem
ents in
N
i
. Let t
h
e lin
ear m
a
p
p
i
ng
fro
m
,
i
ii
P
pp
to
i
co
v
b
e
written
as
,
ii
i
i
co
v
T
P
d
(2
2)
w
h
er
e
...,
,
...,
,
i
i
ij
V
i
dd
C
j
N
(2
3)
We can
n
o
w
state th
e fo
llowin
g
d
e
fin
ition
s
:
Definiti
on 5.
"Distribute
d
c
o
verage vector
"
and
"distributed c
o
ver
age
matrix"
:
For eac
h
i
th
robo
t, th
e "
distributed c
o
ver
age
vector
"
i
s
defi
n
e
d as:
1
(...
,
,
...
,
)
i
ii
i
l
N
co
v
c
ov
co
v
,
w
h
er
e
1
,
1
,
...
,
2
ii
ll
i
cov
c
o
v
l
N
(2
4)
and
11
ii
ii
NN
co
v
c
o
v
(2
5)
The "
di
st
ri
b
u
t
e
d c
o
ver
age
m
a
t
r
i
x
"
is
d
e
fi
n
e
d as m
a
trix
i
T
in
the fo
llo
wi
n
g
equ
a
tio
n
,
ii
i
i
co
v
T
P
d
(2
6)
whe
r
e
1
.
..,
,
.
..
,
2
i
i
ij
V
i
dd
C
j
N
and
,
i
ii
Pp
p
..
Since
1
(
,
..
.,
)
n
Qd
i
a
g
Q
Q
, th
e term
½ is ad
d
e
d in
(24
)
in
ord
e
r
to
satisfy th
e fo
llo
wi
n
g
equ
a
t
i
o
n
:
2
2
2
11
,,
i
ii
i
i
i
nn
iV
ii
i
VV
V
V
V
Q
Q
iV
ii
Q
pC
PC
P
C
C
C
C
pC
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA I
S
SN
:
208
9-4
8
5
6
Distrib
u
t
ed
Reced
ing
Horizon
C
o
verag
e C
o
n
t
ro
l
b
y
Mu
ltiple Mob
ile Robo
ts (Fa
t
emeh
Moh
s
en
i)
92
No
te t
h
at if
ro
bo
t
i
and its
nei
g
hbors
be
locat
ed at thei
r ce
ntro
i
d
s in cen
t
r
o
i
d
a
l Vorono
i con
f
i
g
uratio
n, i.e.
ii
V
P
C
, th
en
(20
)
,
(21) an
d th
erefo
r
e
(24
)
,
(25
)
will
b
e
eq
u
a
l t
o
zero
.
Hen
c
e
0
ii
i
i
ii
i
i
i
i
i
VV
V
TC
d
d
TC
c
o
v
T
P
T
C
()
ii
i
i
V
co
v
T
P
C
(2
7)
Sim
ilar to cent
r
alized case, it can
be
prove
d
t
h
at
The
di
st
ri
but
e
d
c
ove
ra
ge
m
a
t
r
i
x
i
T
in
(27
)
h
a
s
fu
ll
rank
an
d
it is eq
u
a
l t
o
di
m(
)
2
p
.
Prop
osi
t
i
o
n 3.
The
cost
f
unct
i
on
gi
ve
n
by
(1
9)
can
be
re
wri
t
t
e
n as
2
2
(
(
),
(.
)
,
)
(
(
)
(
)
)
p
i
i
th
ii
i
ip
V
i
R
Q
t
HP
t
u
h
p
C
u
d
2
(;
(
)
)
i
i
ip
V
G
pt
h
p
t
C
(2
8)
and
1
(
(
)
,
(.),
)
(
(
)
,
(
.).
)
,
n
ii
ip
p
i
H
Pt
u
h
H
P
t
u
h
whe
r
e
H
is th
e C
R
HCC co
st
fun
c
tio
n.
Proof.
Using (27), it can
be s
een that
22
ii
T
ii
i
V
TT
cov
P
C
.
Since
1
(
,
..
.,
)
n
R
di
ag
R
R
and
1
(
,
..
.,
)
n
Gd
i
a
g
G
G
, t
h
en
by
defi
ni
n
g
ii
T
i
QT
T
one can
re
write (19) as:
2
2
(
(
),
(.
)
,
)
(
(
)
(
)
)
p
i
i
th
ii
i
ip
V
i
R
Q
t
HP
t
u
h
p
C
u
d
2
(;
(
)
)
i
i
ip
V
G
pt
h
p
t
C
Th
is is i
n
d
e
ed
(28
)
wh
ich is
usefu
l
i
n
stab
ilit
y an
alys
is. Now, accord
i
n
g
to
d
e
fi
n
itio
n
s
2
-5, it is con
c
l
u
d
e
d
th
at
1
(
(
),
(.),
)
(
(
)
,
(
.
)
.
)
n
ii
ip
p
i
H
Pt
u
h
H
P
t
u
h
,
i.e. th
e
su
m
o
f
n
di
st
ri
b
u
t
e
d
c
o
s
t
fu
nct
i
o
ns i
s
e
qui
val
e
nt
t
o
ce
nt
ral
i
zed c
o
st
f
unct
i
o
n.
No
w s
u
pp
ose t
h
at
n
DR
HC
C
opt
i
m
al
pro
b
l
e
m
s
, one co
rre
s
p
o
n
d
i
n
g
to eac
h robot, are all
solve
d
at a c
o
mmon
tim
e
instant called “update time”, denote
d
by
0
kc
tt
h
k
,
{
0
,
1
,
...}
k
. As stated in (19)
, (28), for each cost
fu
nct
i
o
n, t
h
ere
i
s
a t
e
rm
t
h
at
cont
ai
n
s
c
o
n
n
e
c
t
i
on
bet
w
ee
n
t
h
e c
o
r
r
esp
o
n
d
i
ng
r
o
b
o
t
a
n
d
i
t
s nei
g
h
b
o
r
s.
S
o
, i
n
every update tim
e
, when th
e
local optim
al problem
s
are solve
d
, each
robot requires
to know the
state
traj
ectories of all i
t
s n
e
ig
hb
ors ov
er tim
e
in
terv
al
[,
]
kk
p
tt
h
. Bu
t, such
in
fo
rm
atio
n d
o
e
sn
’t ex
ist
at in
stan
t
k
t
.Th
e
r
e
fo
r
e
each
r
obo
t m
u
st esti
m
a
te so
m
e
state tr
aj
ector
ies fo
r
its
n
e
ighbo
r
s
at
[,
]
kk
p
tt
h
and t
h
en sol
v
es
its optim
a
l
control problem
.
The
tra
j
ectories that each
robot estim
a
tes for its neighbors
are called
estima
t
ed
t
r
aj
ect
ori
e
s
.
Si
nce eac
h
r
o
b
o
t
i
s
ass
u
m
e
d t
o
ha
ve t
h
e i
n
f
o
rm
ati
on a
b
o
u
t
t
h
e
dy
nam
i
cs of
i
t
s
nei
g
h
b
o
r
s
, a
n
est
i
m
a
t
e
d cont
rol
(
d
efi
n
ed s
h
o
r
t
l
y
) i
s
obt
a
i
ned f
r
o
m
wh
ich the state trajectories are
deri
ved. To e
n
sure
co
m
p
atib
ilit
y b
e
tween
t
h
e act
u
a
l and th
e estimated
traj
ect
o
r
ies, an add
ition
a
l con
s
train
t
called
“co
m
p
atib
ility
con
s
t
r
ai
nt
” i
s
a
dde
d t
o
DR
HC
C
pr
o
b
l
e
m
of e
ach
ro
b
o
t
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
089
-48
56
IJR
A
V
o
l
.
3,
No
. 2,
J
u
ne 2
0
14:
8
4
– 1
0
6
93
Definiti
on 6.
E
s
timated contr
o
l
At eve
r
y tim
e interval
,
kk
p
tt
h
, the
estimated cont
rol
for each robot i
s
de
fine
d as
*
1
ˆ
(;
(
)
)
0
;
()
ˆ
(;
(
)
)
(
;
(
)
)
;
ii
k
kV
ii
k
i
i
k
up
t
if
P
t
C
Othe
rwise
up
t
u
p
t
The actual and the estim
a
te
d st
ate trajectories are de
noted by
(.;
(
))
ii
k
pp
t
and
ˆ
(.;
(
))
ii
k
pp
t
respectively.
No
te
th
at
ˆ
(
;
()
)
(
;
(
)
)
()
ik
ik
ik
ik
i
k
pt
p
t
pt
p
t
pt
,
1
,
..
.,
in
.
Th
e D
R
H
CC pr
ob
lem
can
now
be stated as
follows.
Problem 2
.
W
i
t
h
a gi
ve
n fi
x
e
d u
p
d
at
e peri
od t
i
m
e
0,
cp
hh
and a
opt
i
m
i
zati
on p
e
ri
o
d
t
i
m
e
p
h
,
fo
r ev
er
y
1
,
..
.,
in
an
d at an
y sa
m
p
lin
g
tim
e
k
t
an
d wi
t
h
gi
ven
ˆˆ
(
,
(
)),
(
)
,
(
),
(
;
(
)
)
ii
k
i
k
i
k
i
i
k
up
t
p
t
p
t
u
p
t
at
[,
]
kk
p
tt
h
f
i
nd
*
(.
)
(
(
)
,
()
,
)
m
i
n
(
()
,
(
.
;
()
,
)
,
i
i
i
k
i
kp
i
k
i
i
kp
u
H
pt
p
t
h
H
p
t
u
p
t
h
whe
r
e
2
2
2
2
(
(
),
(.),
)
(
(
)
(
)
(
)
(
)
)
2
(,
(
)
)
,
p
i
i
i
i
th
i
ii
p
i
j
i
j
i
V
i
j
t
ip
i
V
G
H
pt
u
h
p
p
d
p
C
u
d
t
Pt
h
p
t
C
subj
ect to
t
h
e
f
o
llow
i
ng
(;
(
)
)
(
)
ii
k
i
pp
t
u
,
ˆˆ
(;
(
)
)
(
)
,
j
jk
j
i
pp
t
u
j
N
,
(;
(
)
)
ii
k
up
t
u
,
(;
(
)
)
ii
k
pp
t
,
2
ˆ
(;
(
)
)
(
;
(
)
)
,
ii
k
i
i
k
c
pp
t
p
p
t
h
(0
,
)
(2
9)
(;
(
)
)
(
)
ik
p
i
k
i
i
pt
h
p
t
,
whe
r
e
,
kk
p
tt
h
,
and
2
2
()
:
:
,
0
i
i
ii
i
i
V
i
i
G
pR
p
C
(3
0)
whe
r
e
2
0
c
h
.
(29
)
is called
co
m
p
atib
ilit
y
co
nstrain
t
and (30
)
is
ta
rg
et
o
r
termina
l
set
. The optimal so
lution for each
DR
HC
C
p
r
o
b
l
e
m
i
s
denot
ed
by
*
(;
(
)
)
,
,
ii
k
k
k
p
up
t
t
t
h
and the closed-l
oop syste
m
where
we wish to
stab
ilize it, is
*
()
()
)
,
0
,
Pu
(3
1)
where
**
*
11
(
;
()
)
(
(
;
()
)
,
.
.
.
,
(
;
(
)
)
)
kk
n
n
k
uP
t
u
p
t
u
p
t
. The optim
a
l sta
t
e tra
j
ectory for
th
i
ro
bo
t is d
e
no
ted
by
Evaluation Warning : The document was created with Spire.PDF for Python.