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.
4, N
o
. 1
,
Mar
c
h
20
15
,
pp
. 31
~40
I
S
SN
: 208
9-4
8
5
6
31
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
A PSO-
Optimized Recip
r
ocal Velocit
y
Obstacl
e
s
Algorith
m for
Navigation of Multiple Mobile Robots
Z
i
y
a
d
T. Allawi*
,
Turki Y. Abda
lla*
*
*College of
Edu
cation for
Humanitarian
Stud
ies,
University
of
Baghdad, I
r
aq
**Departm
ent
of
Com
puter Eng
i
neering
,
Co
lleg
e
of Eng
i
ne
ering
,
Univers
i
t
y
of
Ba
s
r
ah, Ir
aq
Article Info
ABSTRACT
Article histo
r
y:
Received
May 31, 2014
Rev
i
sed
Sep
21
, 20
14
Accepted Oct 15, 2014
In this paper, a new optimization
method for the Reciprocal
Velocity
Obstacles (RVO) is
proposed. It us
es
the well-known Particle
Swarm
Optim
ization
(PSO) for navigation cont
rol of m
u
ltiple m
obile robots with
kinem
a
tic
constraints. The RVO is us
ed
for collision avoidance between the
robots, while PSO
is used to
choose th
e best
path for the
robot maneuver
to
avoid colliding with other robots
and to get to
its goal faster. This
m
e
thod
was applied on 24 m
obile robots facing
each other. Sim
u
lation results have
shown
that this method
outperforms the ordinary
RVO
when the path is
heuristically
chosen.
Keyword:
Mu
ltip
le Mo
b
i
l
e
Rob
o
t
s
Navi
gat
i
o
n
Particle Swarm Op
ti
m
i
zatio
n
Reciprocal
Vel
o
city Obstacles
Copyright ©
201
5 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
:
Ziyad T.
Allawi,
Co
lleg
e
o
f
Educatio
n
for Hu
m
a
n
itarian
Stud
ies
Uni
v
ersi
t
y
o
f
B
a
gh
da
d, Ira
q
Em
a
il: zi
yad
.
allawi@g
m
a
il.co
m
1
.
IN
TR
ODUC
TION
The robot
i
c
t
echnol
ogi
es have
been wi
del
y
em
pl
oy
ed i
n
m
a
ny
appl
i
cat
i
ons. Nowaday
s
,
robot
system
s have been applied in fact
ory autom
a
tion, entertainm
ent, sp
ace, etc... Recently, m
o
re and m
o
re
researchers
t
a
kes i
n
t
e
rest
i
n
t
h
e
robot
whi
c
h
can hel
p
peopl
e
i
n
our
dai
l
y
l
i
f
e,
such as
servi
ce robot
, offi
ce
robot
, securi
t
y
robot
, hom
e robot
, and so on.
Other
than control and coordinati
on of
m
u
ltiple m
obile robots, one
of
the central problem
s in this
area is m
o
tion
planning am
ong m
u
ltiple
m
oving m
obile robots.
In this paper,
we address the
problem
of
real-
t
i
m
e navi
gat
i
on for
m
u
l
t
i
-robot
m
o
t
i
on
pl
anni
ng i
n
dy
nam
i
c
envi
ronm
ent
s
. Each
robot
navi
gat
e
s
i
ndependent
l
y
wi
t
hout
expl
i
c
i
t
com
m
uni
cat
i
on wi
t
h
t
h
e
ot
her m
obi
l
e
robot
s. Therefore, we
can form
ul
at
e t
h
e
basic
problem
as navigating a single agent to its
goal
location without colliding with the obstacles and the
ot
her m
obi
l
e
robot
s i
n
t
h
e envi
ronm
ent
[1]
.
Th
e prob
lem
of co
m
p
u
tin
g a
co
llisio
n
-
free
path
fo
r a
robo
t
m
o
v
i
n
g
am
o
ng d
y
n
a
m
i
c o
b
s
tacles is
n
o
t
onl
y
of
i
n
t
e
res
t
t
o
r
o
bot
i
c
s
b
u
t
al
so
ha
s
be
en
wi
del
y
st
u
d
i
e
d
f
o
r
cr
ow
d si
m
u
l
a
t
i
on i
n
c
o
m
put
er
gr
aphi
c
s
,
virtual e
n
vironments, vi
deo
gam
i
ng,
traffic
enginee
r
ing a
n
d arc
h
itecture
design, whe
r
e
each a
g
e
n
t ca
n
be
con
s
i
d
ere
d
as
a vi
rt
ual
h
u
m
a
n, a
m
ovi
n
g
ca
r,
or
an
i
n
di
vi
d
u
al
pe
dest
ri
an
[1]
.
It
i
s
i
m
por
t
a
nt
i
n
m
a
ny
r
o
b
o
t
i
c
s
ap
p
lication
s
, i
n
clud
ing
au
tomated
tran
sportatio
n
system
s, au
to
m
a
ted
facto
r
ies, and
ap
p
lication
s
invo
lv
ing
robo
t hu
m
a
n
interactio
n
s
, su
ch
as ro
bo
tic wheelch
airs.
The problem
of collision avoidance
between the robot
s is harder
than the m
oving obstacles
because
the
robots are not sim
p
ly m
oving wit
hout considering their environm
ent;
they are also in
telligent decision-
m
a
k
i
n
g
en
tities th
at try to
av
o
i
d
co
llisio
n
s
as well.
Sim
p
ly co
n
s
id
erin
g
th
em
as m
o
v
i
n
g
o
b
s
tacles m
a
y lead
to
o
s
cilla
tio
n
s
if the other entity considers all other robots as
m
oving obstacles as well. Therefore, the reactive
nature of the other entities m
u
st be specifically taken
into account in order to guarantee that collisions
are
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
089
-48
56
IJR
A
V
o
l
.
4,
No
. 1,
M
a
rc
h 20
1
5
:
3
1
– 40
32
avoi
ded
[14]
. An al
t
e
rnat
i
v
e
t
o
com
p
l
e
t
e
pl
anni
ng i
s
t
o
pl
an for t
h
e
robot
as i
t
act
s,
t
a
ki
ng new sensor i
nput
s
as
th
ey arriv
e
an
d
p
l
an
n
i
n
g
lo
cally.
So
m
e
o
f
th
e p
r
o
m
in
en
t wo
rk
in
th
is
area is b
a
sed
o
n
th
e Velo
city
Obstacles (VO) [1].
Thi
s
work i
n
t
r
oduces an opt
i
m
i
zed navi
gat
i
on m
e
t
hod t
h
at
com
b
i
n
es t
h
e
reci
procal
vel
oci
t
y
obstacles
(RVO) [1] collision
avoidan
ce navigation m
e
thod
with the
p
a
r
ticle
swa
r
m o
p
timiza
tio
n
al
gori
t
h
m
(PSO) [2]
.
R
VO const
r
uct
s
t
h
e vel
o
ci
t
y
obst
acl
e
re
gi
ons for a
gi
ven robot
i
nduced
by
ot
her robot
s
and
chooses feasi
b
l
e
vel
o
ci
t
y
and
ori
e
nt
at
i
on i
n
t
e
rval
s c
onsi
d
eri
ng
t
h
e ki
nem
a
t
i
c
const
r
ai
nt
s
of t
h
e robot
.
PSO
inspects
these intervals
and chooses th
e
best velocity and
orientation that
ensures a collision-free
path for the
robot
which m
a
kes
it closer to
the desired
goal. Th
is m
e
thod
is sim
u
lated
on 24 m
obile
robots facing each
other; each robot tries to reach a goal that is behind
its opposite partner. This m
e
thod is com
p
ared with
the
sam
e
R
VO m
e
t
hod wi
t
h
arbi
t
r
ary
chosen confi
gurat
i
ons
and t
h
e resul
t
s
were obt
ai
ned for di
fferent
si
m
u
l
a
t
i
on
param
e
ters.
Th
e p
a
p
e
r is stru
ctu
r
ed
as fo
llo
ws: Sectio
n
2
p
r
esen
ts th
e related
wo
rk
s o
f
th
e n
a
v
i
g
a
tio
n
o
f
m
u
ltip
le
m
obile
robots; Section 3
illustrates
the principles of
the RVO and
for
the PSO. Section
4 shows the design
procedure of t
h
e m
e
t
hod
wi
t
h
t
h
e si
m
u
l
a
t
i
on
resul
t
s
;
a
nd fi
nal
l
y
, Sect
i
on
5 hol
ds t
h
e
concl
u
si
on of t
h
e
overal
l
work.
2.
REL
A
TED
WO
RKS
Num
e
rous m
o
t
i
on pl
anni
ng al
gori
t
h
m
s
have been devel
oped for m
obi
l
e
robot
s i
n
st
at
i
c
envi
ronm
ent
s
. In [3]
,
t
h
e not
i
on of a car-l
i
k
e robot
was form
al
i
zed, and t
h
e fact
t
h
at
a pat
h
for a hol
onom
i
c
robot lying fully in open regi
ons of the configuration space can
always
be
transform
e
d into a feasible path for
a nonhol
onom
i
c
robot
was proven.
Laum
ond
et al.
[3]
al
so provi
ded an al
gori
t
h
m
t
o
generat
e
a feasi
b
l
e
pat
h
for
a nonhol
onom
i
c
robot
from
a
pat
h
found for
a hol
onom
i
c
robot
. Approaches appl
i
cabl
e
t
o
m
obi
l
e
robot
s
have been devel
oped for com
p
l
e
t
e
t
r
aject
ory
pl
anni
ng am
ong m
ovi
ng obst
acl
es, such as [4]
,
[5]
.
Several
variations of the veloc
ity
obstacle form
ulation have been
proposed for m
u
lti-robot system
s,
g
e
n
e
rally b
y
attem
p
tin
g
to
in
co
rp
o
r
ate
th
e reactiv
e
b
e
h
a
v
i
o
r
o
f
th
e
o
t
h
e
r en
tities
in
th
e
en
v
i
ro
n
m
en
t.
Variatio
n
s
su
ch
as RVO [1
], [2
1
]
, recu
rsiv
e p
r
o
b
a
b
ilistic
v
e
lo
city o
b
s
tacles [2
2
]
, [2
3
]
, an
d
co
m
m
o
n
v
e
lo
city
obstacles
[24] use various m
eans
to
handle reciprocity, but each
have th
eir own shortcom
i
ngs. Specifically,
t
h
e approach of [23]
m
a
y
fai
l
t
o
converge, whi
l
e
ot
her concept
s
[1]
,
[24]
are l
i
m
i
t
e
d t
o
deal
i
ng wi
t
h
onl
y
t
w
o
robot
s.
Ot
her
work has
focused m
a
i
n
l
y
on fol
l
o
w-t
h
e-l
eader behavi
or
when navi
gat
i
ng
robot
s i
n
real
-worl
d
settings [25], [26]. Also, there is
a large body of work on
centrally c
oordinating the m
o
tions of
m
u
ltiple
robots [27].
However, there
is little
work on
navigation of
m
u
ltiple indepe
ndent robots
to arbitrary
goals in
real world settings while taking into account
the reactive behavior of other robots.
In t
h
e fi
el
d of
m
obi
l
e
robot
i
c
s, m
a
ny
papers di
scussed t
h
e
i
n
t
e
grat
i
on of PSO
for cont
rol
of
m
obi
l
e
robot
navi
gat
i
on. For i
n
st
ance, Vahdat
et al.
[6] proposed two recent sam
p
le-b
ased evolutionary algorithm
s
for gl
obal
l
o
cal
i
zat
i
on
of a
m
obi
l
e
robot
.
The fi
rst
i
s
t
h
e
DE al
gori
t
h
m
and t
h
e
second i
s
t
h
e PSO
al
gori
t
h
m
.
They
used PSO t
o
adjust
t
h
e l
o
cat
i
on and vel
o
ci
t
y
of t
h
e robot
'
s
pose. Juang and C
h
ang [7]
proposed
an
evol
ut
i
onary
-group-based part
i
c
l
e
-swarm
-opt
i
m
i
zat
i
on (EGPSO) al
gori
t
h
m
for fuzzy
cont
rol
l
e
r desi
gn.
The
objective of EGPSO was to im
prove fuzzy-control accu
racy and design efficien
cy. EGPSO-designed fuzzy
cont
rol
l
e
r
was appl
i
e
d t
o
m
obi
l
e
-robot
navi
gat
i
on i
n
unknown envi
ronm
ent
s
. Kwok
et al.
[8]
proposed a
generi
c cont
rol
st
ruct
ure based on
t
h
e l
eader-fol
l
o
wer
st
rat
e
gy
and
vi
rt
ual
robot
t
r
acki
ng fram
e
work
t
o
param
e
t
e
ri
ze
t
h
e form
at
i
on confi
gurat
i
on for cooperat
i
v
el
y
depl
oy
i
ng
t
h
e m
obi
l
e
robot
s i
n
t
o
desi
red pat
t
e
rns.
Th
e PSO alg
o
r
ith
m
was u
s
ed
fo
r its co
m
p
u
t
atio
n
a
lly-efficien
t cap
ab
ility o
f
h
a
n
d
lin
g
m
u
lti-o
b
j
ectiv
e
criteria.
Tang
and Eberhard [9]
present
e
d an al
gori
t
h
m
cal
l
e
d
augm
ent
e
d Lagrangi
an part
i
c
l
e
swarm
opt
i
m
i
zat
i
on
with
v
e
lo
city lim
its (VL-ALPSO). It
u
s
ed
a PSO b
a
sed
al
gori
t
h
m
t
o
opt
i
m
i
ze t
h
e
m
o
t
i
on pl
anni
ng for swarm
m
obile
robots. The algorithm
com
b
ined the m
e
thod
of
augm
ented Lagrangian
m
u
ltip
liers and strategies of
v
e
lo
city lim
its an
d
v
i
rtu
a
l d
e
tecto
r
s so
as
to
en
su
re
enforcem
ent of constraint
s, obst
acl
e avoi
dance
and
m
u
tual collision
avoidance. Yang
a
nd Li
[10] proposed
a new
algorith
m
based
on im
proved
PSO of
cubic
splines for m
u
ltiple m
obile
robot path planning. The
center path was described
by
string of cubic
splines,
t
hus
t
h
e pat
h
pl
anni
ng was
equi
val
e
nt
t
o
param
e
t
e
r
opt
i
m
i
zat
i
on of
part
i
c
ul
ar cubi
c spl
i
n
es. Im
proved PSO
was
i
n
t
r
oduced t
o
get
t
h
e
opt
i
m
al
pat
h
for t
h
e
m
obi
l
e
robot
s. M
oham
e
d et
al
. [11]
descri
bes a m
a
t
h
em
at
i
cal
m
odel
for devel
opi
ng a
schem
e
for an aut
onom
ous
l
o
w cost
m
obi
l
e
robot
sy
st
em
usi
ng vi
sual
si
m
u
l
t
a
neous
lo
calizatio
n
an
d
m
a
p
p
i
n
g
an
d
p
a
rticle swarm
in
tellig
en
t p
a
th
p
l
an
n
e
r.
Th
e resu
lts in
d
i
cated
th
at th
is system
coul
d provi
de a sol
u
t
i
on for t
h
e probl
em
of i
ndoor m
obi
l
e
robot
navi
gat
i
on.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA
I
S
SN
:
208
8-8
7
0
8
A PSO-Op
timi
z
ed
Reci
p
r
o
c
a
l
Velo
city Ob
st
a
c
les Algo
rithm fo
r Na
vi
g
a
t
i
o
n o
f
Mu
ltip
le
… (Ziya
d
T.
Alla
wi
)
33
3. RESE
AR
C
H
METH
OD
3.1. Reci
procal
Vel
o
ci
ty Obstacl
e
s
It
i
s
a navi
gat
i
on m
e
t
hod used for robot
m
o
t
i
on pl
anni
ng i
n
dy
nam
i
c envi
ronm
ent
s
. It
consi
s
t
s
of
selecting
avoidance m
a
neuvers to
a
void static and
m
oving obstacles in
the velocity space,
based on the
current positions and
velocities of
the
robot
and obstacles.
It is a
first-or
der m
e
thod
since it
does not
integrate
v
e
lo
cities to
yield
p
o
s
itio
n
s
as fu
n
c
tio
n
s
o
f
tim
e [1
2
]
.
The avoidance
m
a
neuvers are
gene
rated by
selecting robot
veloc
ities outside of
the VO, which
represent the set of robot velocities th
at
would
result in a collision with a
given obstacle that m
oves at a given
v
e
lo
city
at
so
m
e
fu
tu
re
tim
e. To
en
su
re th
at
th
e
av
o
i
d
a
n
ce m
a
n
e
u
v
e
r
is d
y
n
a
m
i
cally
feasib
le, th
e
set o
f
avoidance velocities are
intersected w
ith
the set
of adm
i
ssible velocities,
defined
by the
robot'
s
kinem
a
tics
const
r
ai
nt
s.
Fiorini and Shiller [12] were the fi
rst who introduced this approach to
be used in the path planning
and navi
gat
i
on of m
obi
l
e
robot
s i
n
dy
nam
i
c envi
ronm
en
t
s
whi
c
h com
p
ri
se t
h
e presence of st
at
i
c
and m
ovi
ng
obstacles (or other m
oving
robots). They applied the approach
upon the intelligent vehicles
negotiating
hi
ghway
t
r
affi
c.
The key
feat
ures of t
h
e VO as m
e
nt
i
oned i
n
[12]
were:
1.
VO provi
des a si
m
p
l
e
geom
et
ri
c represent
a
t
i
on of pot
ent
i
a
l
avoi
dance m
a
neuvers;
2.
Any
num
bers of m
ovi
ng obst
acl
es can be avoi
ded by
consi
d
eri
ng of t
h
e uni
on of t
h
ei
r VO'
s;
3.
It
uni
fi
es t
h
e avoi
dance of m
ovi
ng as wel
l
as st
at
i
onary
obst
acl
es;
and
4.
It
al
l
o
ws for t
h
e si
m
p
l
e
consi
d
erat
i
on of robot
dy
nam
i
cs.
Si
nce t
h
e VO had been i
n
t
r
oduced, som
e
devel
opm
ent
s
were
carri
ed
out
upon
t
h
e
ori
g
i
n
al
al
gori
t
h
m
.
Jur B
e
rg cont
ri
but
ed m
o
st
of t
h
ese devel
opm
ent
s
. R
eci
procal
VO was i
n
t
r
oduced by
B
e
rg
et al.
[1]
,
general
i
zed
VO was
proposed by
W
i
l
k
i
e
et al.
[13]
and hy
bri
d
reci
procal
VO
was proposed by
Snape
et al.
[14 and 15]. All these approaches were applied on
the
navigation of m
u
ltiple m
obile robots and it was
m
a
inly
used for inter-robot collision avoidance. For instan
ce,
a hybrid reciprocal VO for collision-free
and
oscillation-free navigation of m
u
ltiple m
obile
robots
was presented in
[15]. Each robot senses
its
surroundi
ngs and act
s i
ndependent
l
y
wi
t
hout
cent
r
al
c
oordi
nat
i
on or com
m
uni
cat
i
on wi
t
h
ot
her robot
s.
The
approach used bot
h t
h
e
current
posi
t
i
on and
t
h
e vel
o
ci
t
y
of ot
her
robot
s t
o
com
put
e
t
h
ei
r fut
u
re t
r
aject
ori
e
s
i
n
o
r
d
e
r to
av
o
i
d
co
llisio
n
s
. Th
e
ap
p
r
o
ach
was
recip
r
o
cal an
d
av
o
i
d
s
o
s
cillatio
n
s
b
y
ex
p
licitly tak
i
n
g
in
to
account that the other robots sense
their surroundings as well and change
their trajectories accordingly.
The m
e
thod presented in this
paper sim
u
ltaneously
determ
ines actions
for m
a
ny robots that
each
m
a
y have different
objectives. The
actions are
com
puted for
each robot
independently without
com
m
unication
am
ong the robots. The m
e
thod uses PSO
algorithm
to obtain the optim
um
collision-free
velocity which guarantees the collision-free m
o
tion for each robot in the environm
ent.
The fundam
e
nt
al
confi
gurat
i
on of t
h
e ori
g
i
n
al
VO i
s
shown i
n
t
h
e fi
gure bel
o
w [13]
:
Fi
gu
re
1.
The
Vel
o
ci
t
y
O
b
st
a
c
l
e
of
R
o
bot
A
i
n
d
u
ce
d
by
R
o
bot
B
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
089
-48
56
IJR
A
V
o
l
.
4,
No
. 1,
M
a
rc
h 20
1
5
:
3
1
– 40
34
In t
h
e Fi
gure 1, for a di
sc-shaped robot
A
(l
i
ght
gray
) of radi
us
r
A
, located at
p
A
, has a vel
o
ci
t
y
of
v
A
and a di
sc-shaped robot
B
(dark gray
) of radi
us
r
B
, located at
p
B
, has a vel
o
ci
t
y
of
v
B
,
th
e v
e
lo
city o
b
s
tacle fo
r
A
i
nduced
by
B
, denot
ed
VO
A|B
(th
e
p
i
n
k
-
co
lo
red
co
n
e
),
is th
e
set o
f
all v
e
lo
cities
fo
r
A
t
h
at
woul
d, at
som
e
p
o
i
n
t
in
th
e fu
tu
re, resu
lt a co
llisio
n
with
B
. Thi
s
set
i
s
defi
ned geom
et
ri
cal
l
y
.
Let
t
h
e robot
A
be a si
ngl
e
poi
nt
i
n
t
h
e
ori
g
i
n
and
B
be a di
sc
(l
i
ght
gray
ri
ng
enci
rcl
i
ng dark gray
di
sc) cent
e
red at
p
AB
wi
t
h
a
radi
us
eq
u
a
l
to
th
e su
m
o
f
A
’s and
B
’s (
r
A
+
r
B
). If
B
is static (i.e. n
o
t
m
o
v
i
n
g
)
, we
co
u
l
d
d
e
fin
e
a co
n
e
o
f
v
e
lo
cities
for
A
th
at wo
u
l
d
lead
to
a co
llisio
n
with
B
as
t
h
e
set
of ray
s
shot
from
t
h
e ori
g
i
n
t
h
at
i
n
t
e
rsect
t
h
e boundary
of
B
.
To
d
e
riv
e
a v
e
lo
city
o
b
s
tacle fro
m
th
is,
we sim
p
ly
tran
slate th
e
co
n
e
b
y
th
e
v
e
lo
city
v
B
of
B
,
as shown i
n
fi
gure. B
r
i
e
fl
y
,
t
h
e general
represent
a
t
i
on of t
h
e St
andard Vel
o
ci
t
y
Obst
acl
es appears i
n
t
h
e Eq. 1 [13]
:
B
v
v
p
v
)
(
::
0
|
|
B
A
B
A
t
t
VO
(1)
The
R
eci
procal
Vel
o
ci
t
y
Obst
acl
es
(R
VO) ori
g
i
n
at
es from
t
h
e
m
u
t
u
al
behavi
or of
t
h
e t
w
o robot
s t
o
avoid oscillation which m
a
y happen due to
the change
of direction. In this
m
e
thod, instead of choosing a
new
velocity for each robot that
is outside
the other robot’s
VO, we choose a ne
w
velocity that is the average
of
i
t
s
current
vel
o
ci
t
y
and a vel
o
ci
t
y
t
h
at
l
i
e
s out
si
de t
h
e ot
her robot
’s VO.
The general
represent
a
t
i
on of t
h
e R
eci
procal
Vel
o
ci
t
y
Obst
acl
es (R
VO) i
s
shown bel
o
w [1]
:
B
v
v
v
p
v
)
)
1
(
(
::
0
|
|
B
A
A
B
A
t
t
RVO
(2)
whe
r
e
α
is a
co
nstant
w
h
ich
re
fer t
o
the
ef
fo
rt
sh
are
b
e
tween th
e
robo
ts.
In th
e stan
d
a
rd R
V
O,
α
=0
.5
.
Thi
s
m
e
t
hod perform
s si
m
p
l
e
r cal
cul
a
t
i
ons
t
h
an t
h
e ori
g
i
n
al
RVO
i
n
[1]
usi
ng t
h
e
shape of R
VO cone
(base
angle and axis) to check if
v
A
is in
sid
e
th
e co
n
e
o
r
o
u
t
sid
e
it;
an
d
p
e
rm
its th
e u
s
e o
f
o
p
tim
izatio
n
alg
o
-
rith
m
s
.
The al
gori
t
h
m
begi
ns by
cal
cul
a
t
i
ng t
h
e di
st
ance bet
w
een t
h
e t
w
o robot
s
d
AB
and i
t
s
argum
ent
α
AB
with
resp
ect to
th
e Cartesian
co
o
r
d
i
n
a
tes as in
Eq
. 3
:
)
,
atan2(
]
,
[
2
2
x
y
y
x
d
y
x
AB
AB
AB
A
B
AB
p
p
p
p
(3)
The line
d
AB
and i
t
s
argum
ent
α
AB
represent the cone axis of
sym
m
e
try. Then, the cone base
sem
i
-
angl
e
φ
AB
can be calculated as shown in the Eq. 4:
)
(
sin
1
AB
B
A
AB
d
r
r
(4)
The param
e
ters
v
B
,
d
AB
,
α
AB
, and
φ
AB
can be used t
o
check
t
h
e robot
A
's p
o
ssib
ility o
f
co
llisio
n
with
robot
B
as fo
llo
ws. W
e
assu
m
e
v'
A
t
o
be a
heuri
s
t
i
cal
l
y
chosen vel
o
ci
t
y
of t
h
e
robot
A
, subjected to the
nonhol
onom
i
c
const
r
ai
nt
s
of t
h
at
robot
. Fi
rst
,
t
h
e m
a
gni
t
ude
of vel
o
ci
t
y
di
fference bet
w
een
t
h
e t
w
o
robot
s
an
d
its arg
u
m
en
t with
resp
ect to
th
e
Cartesian
co
o
r
d
i
n
a
tes,
v
AB
and
β
AB
, respectively
are calculated as shown
in Eq. 5:
)
,
atan2(
]
,
[
)
'
(
2
2
2
x
y
y
x
v
y
x
AB
AB
AB
A
AB
B
A
v
v
v
v
v
(5)
The suffi
ci
ent
condi
t
i
on of bei
ng
v'
A
in
sid
e
th
e
RVO
A|B
is
wh
en
ψ
AB
, the absolute difference
between
α
AB
and
β
AB
, is sm
aller th
an
φ
AB
as in Eq. 6:
AB
AB
B
A
A
AB
AB
B
A
A
AB
AB
AB
RVO
RVO
if
'
if
'
|
|
v
v
(6)
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA
I
S
SN
:
208
8-8
7
0
8
A PSO-Op
timi
z
ed
Reci
p
r
o
c
a
l
Velo
city Ob
st
a
c
les Algo
rithm fo
r Na
vi
g
a
t
i
o
n o
f
Mu
ltip
le
… (Ziya
d
T.
Alla
wi
)
35
If
v'
A
lies in
th
e
RVO
A|B
,
t
h
en changi
ng t
h
e m
a
gni
t
ude and/
or t
h
e
di
rect
i
on of
v'
A
is m
a
ndatory
for
escaping collision.
Choosing
v
A
*
(opt
i
m
um
vel
o
ci
t
y
)
for escapi
ng
from
al
l
t
h
e
robot
s i
n
t
h
e envi
ronm
ent
m
a
y
be carri
ed out
by
usi
ng heuri
s
t
i
c
m
e
t
hods
or op
t
i
m
i
zat
i
on t
echni
ques
consi
d
eri
ng subject
i
on t
o
t
h
e
nonhol
onom
i
c
const
r
ai
nt
s of t
h
e robot
A
in linear and angular velocities.
On
e can
calcu
late
th
e m
i
n
i
m
u
m
p
o
ssib
l
e tim
e
o
f
co
llisio
n
(if
th
ere is
o
n
e
). Th
is
tim
e is
calcu
lated
onl
y
i
f
v'
A
lies in
th
e
RVO
A|B
, because otherwise the tim
e will
be infinite. Eq. 7 explains:
AB
AB
AB
B
A
AB
AB
c
v
d
r
r
d
t
2
2
2
sin
)
(
cos
(7)
The term
under the square root will be positive only if
ψ
AB
≤
φ
AB
.
Th
e tim
e o
f
co
llisio
n
t
c
shoul
d
be com
p
ared wi
t
h
t
h
e sam
p
l
i
ng t
i
m
e
of t
h
e si
m
u
l
a
t
i
on
τ
. Al
t
hough
v
A
lies in
th
e
VO
A|B
, b
u
t
th
e co
llisio
n
will
b
e
certain
o
n
l
y
wh
en
τ
is greater than
t
c
. If t
h
e opposi
t
e
happen (i
.e.
τ
is
sm
aller th
an
t
c
), the collision will not happen in the
next tim
e sam
p
le although the collision is still possible,
then a penalty form
ula can be used to choose the be
st velocity am
ong a set of candidate velocities. The
penal
t
y
form
ul
a used i
n
t
h
i
s
work i
s
shown i
n
Eq. 8 [1]
:
A
G
A
c
A
t
k
p
'
)
'
(
v
v
v
(8)
where
v
G
A
i
s
t
h
e goal
-
di
rect
ed vel
o
ci
t
y
of t
h
e
robot
A
and
k
is
a constant. The
penalty is
increased when the
robot
velocity diverges from
the
goal velocity and the collision tim
e
is short. The optim
um
velocity
v
A
*
will
b
e
th
e v
e
lo
city wh
ich
h
a
s th
e least p
e
n
a
lty (i.e. clo
s
e to
th
e g
o
a
l v
e
lo
city an
d
o
u
t
fro
m
th
e
RVO
).
Thi
s
al
gori
t
h
m
m
a
y
be used
for opt
i
m
i
zat
i
on
concerns where
t
h
e opt
i
m
i
zat
i
on
al
gori
t
h
m
shoul
d use
th
ese p
r
ev
io
u
s
assu
m
p
tio
n
s
to
select an
o
t
h
e
r v
e
lo
city
h
e
u
r
istically u
n
til an
o
p
tim
u
m
v
e
lo
city
v
A
*
i
s
found
which guarantees a collision-free path for the robot
A
i
n
t
h
e overal
l
envi
ronm
ent
.
The R
eci
procal
Vel
o
ci
t
y
Obst
acl
es pseudo al
gori
t
h
m
i
s
shown bel
o
w:
F
unc
tion
V
=
VelocityObstacles
(
n
)
//
n
=number of robots in the environment
for
i
=1
to
n
do
p
i
=position of robot
i
[
x
i
,
y
i
,
θ
i
]
;
//
θ
i
m
a
y
be directed toward a target
v
i
=
v
i
ma
x
*[cos
θ
i
, s
i
n
θ
i
];
r
i
=radius of the robot;
e
nd for
for
i
=1
to
n
do
for
j
=1
to
n
,
j
≠
i
do
d
ij
&
α
ij
=the
RVO
cone axis and its ar
gument as in Eq. 3;
φ
ij
=the
RVO
cone semi-angle as in Eq. 4;
e
nd for
loop
f
=0;
for
j
=1
to
n
,
j
≠
i
do
v
ij
&
β
ij
=the magnitude and argument of ve
locity
difference as in Eq. 5;
Us
e Eq. 6 to check if
v
i
lies in the
RVO
A|B
; if so,
flag
=1; els
e
flag
=0;
t
c
=collision tim
e (if
v
i
lies in the
RVO
A|B
) as
in Eq. 7;
Check if
t
c
>
τ
; if so,
flag
=0;
f
=
f
+
flag
;
e
nd for
Use heuristics or an optimization method to find
v
i
*
that
m
i
nim
i
zes
f
considering the nonholonomic constraints of
the
robot
i
or by
using Eq. 8;
until
v
i
*
is found;
V
i
=
v
i
*
;
e
nd for
retu
r
n
V
;
en
d
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
089
-48
56
IJR
A
V
o
l
.
4,
No
. 1,
M
a
rc
h 20
1
5
:
3
1
– 40
36
3.
2.
Par
t
i
c
l
e
S
w
arm O
p
ti
mi
z
a
ti
on
Particle Swarm
Op
tim
izatio
n
Alg
o
r
ith
m
is o
n
e
o
f
th
e wid
e
ly u
s
ed
b
i
o
-
in
sp
ired
o
p
tim
izatio
n
alg
o
r
ith
m
s
wh
ich
in
clu
d
e
An
t Co
lo
n
y
Op
tim
izatio
n
(ACO
),
Differen
tial Ev
o
l
u
tio
n
(DE) an
d
Artificial Bee
C
o
l
ony
(AB
C
)
. PSO uses t
h
e i
d
ea of t
h
e soci
al
behavi
or for m
ovem
e
nt
of fl
ock of bi
rds or school
of fi
sh.
PSO
i
s
a
m
e
t
a
-heuri
st
i
c
al
gori
t
h
m
,
i
.
e.
i
t
m
a
kes few
or no
assum
p
t
i
ons about
t
h
e probl
em
bei
ng
opt
i
m
i
zed and does not
guarant
ee an opt
i
m
al
sol
u
t
i
on i
s
ever found.
PSO was ori
g
i
n
al
l
y
i
n
t
r
oduced by
Kennedy
and Eberhart
[16]
i
n
1995. PSO was
pri
m
ari
l
y
devel
oped for
opt
i
m
i
z
i
ng cont
i
nuous
nonl
i
n
ear funct
i
ons
and sy
st
em
s.
Som
e
paradi
gm
s
t
h
at
i
m
pl
em
ent
t
h
e
concept
of part
i
c
l
e
swarm
were
dem
onst
r
at
ed, and t
h
en
one of
t
h
ese paradi
gm
s was i
m
pl
em
ent
e
d i
n
det
a
i
l
s
,
t
h
en t
h
e new al
gori
t
h
m
was t
e
st
ed for neural
net
w
ork we
i
ght
t
r
ai
ni
ng. In t
h
e very
sam
e
y
ear, Kennedy
and
Eberhart
[17]
devel
oped
anot
her t
w
o
paradi
gm
s
for PSO
and i
n
t
e
grat
ed t
h
em
i
n
t
h
e sam
e
al
gori
t
h
m
t
o
m
a
ke
i
t
m
o
re powerful
.
They
used l
o
cal
and gl
obal
ori
e
nt
ed search m
e
t
hod for
fi
ndi
ng t
h
e opt
i
m
um
val
u
e for a
si
ngl
e
part
i
c
l
e
and for
t
h
e part
i
c
l
e
s as
a whol
e. These t
w
o
paradi
gm
s i
m
proved t
h
e
al
gori
t
h
m
great
er t
h
an t
h
e
fi
rst
proposed one.
Anot
her t
ouch on t
h
e ori
g
i
n
al
PSO
was from
Shi
and Eberhart
[2]
when t
h
ey
proposed a
m
odi
fi
ed
o
p
tim
izer fo
r th
e alg
o
r
ith
m
.
A n
e
w p
a
ram
e
ter called
(In
ertia W
e
ig
h
t
) was in
tro
d
u
ced
in
th
e
o
r
ig
in
al
alg
o
r
ith
m
to
m
a
k
e
b
a
lan
ce b
e
tween
g
l
o
b
a
l an
d
lo
cal search
. Th
is p
a
ram
e
ter co
u
l
d
b
e
p
o
s
itiv
e co
n
s
tan
t
o
r
p
o
s
itiv
e lin
ear
or nonl
i
n
ear funct
i
on of t
i
m
e.
PSO has been used-si
n
ce i
t
was
proposed – i
n
a wi
de area
of appl
i
cat
i
ons. Pol
i
[18]
l
i
s
t
e
d 26
m
a
jor
ap
p
licatio
n
s
wh
ich
PSO
was u
s
ed
with
in
.
So
m
e
o
f
t
h
ese
appl
i
cat
i
ons were ant
e
nnas,
com
m
uni
cat
i
ons,
cont
rol
,
fuzzy
sy
st
em
s,
graphi
cs,
neural
net
w
orks, r
obot
i
c
s, wi
rel
e
ss sensor net
w
orks, si
gnal
processi
ng et
c…
The
problem
s which face
the PSO
algorithm
are lim
ited to
the slow
convergence
and trapping into
l
o
cal
opt
i
m
um
val
u
es.
Several
m
odi
fi
cat
i
ons have
b
een carri
ed out
upon PSO t
o
overcom
e t
h
ese probl
em
s.
One of t
h
ese m
odi
fi
cat
i
ons
was proposed by
W
a
ng
a
nd Fan [19]
. They
proposed an i
m
proved PSO
al
gori
t
h
m
by
nonl
i
n
earl
y
decreasi
ng
t
h
e val
u
e of
i
n
ert
i
a
wei
ght
. The
si
m
u
l
a
t
i
on resul
t
s
reveal
ed
t
h
at
t
h
e proposed
PSO
had the best convergence speed and reaching to
optim
um
com
p
ared to th
e original algorithm
.
As
th
e m
o
st o
f
th
e b
i
o
-
in
sp
ired
alg
o
r
ith
m
s
, PSO was o
r
ig
in
ally u
s
ed
fo
r g
l
o
b
a
l m
u
lti-d
i
m
e
n
s
io
n
a
l
o
p
tim
izatio
n
.
It sh
ares m
a
n
y
sim
ilarities with
ev
o
l
u
tio
n
a
ry
alg
o
r
ith
m
s
su
ch
as
Gen
e
tic Alg
o
r
ith
m
s
(GA).
Th
e
system
is initialized
with a
population of
random
solu
tions and
searches for
op
tim
a by
updating generations.
However, unl
i
k
e GA, PSO has no
evol
ut
i
on operat
o
rs such
as crossover
and m
u
t
a
t
i
on. In t
h
e PSO
al
gori
t
h
m
,
the
birds in a flock are sym
bolically represented as “p
articles”. These particles can be considered as sim
p
le
agents
“flying” through
a problem
space.
A particle
’s
location in the
m
u
lti-dim
e
nsional problem
space
represent
s
one sol
u
t
i
on for t
h
e probl
em
.
W
h
en a part
i
c
l
e
m
oves t
o
a new l
o
cat
i
on, a di
fferent
probl
em
so
lu
tio
n
is g
e
n
e
rated
.
Th
is so
lu
tio
n
is ev
alu
a
ted
b
y
a fitn
ess fu
n
c
tio
n
th
at p
r
o
v
i
d
e
s a q
u
a
n
titativ
e v
a
lu
e o
f
th
e
so
lu
tio
n
’
s u
tility. Each
in
d
i
v
i
d
u
a
l o
r
p
a
rticle
in
a swarm
b
e
h
a
v
e
s in
a d
i
strib
u
t
ed
way u
s
in
g
its
o
w
n
intelligence and the
collective or group
intelligence of the
swarm
.
As such,
if one particle
discovers a
good
path to food, the rest of
the swarm
will also be
able to follow the good path
instantly even if
their location
is
far away in the swarm
.
The
advantage of using
an optim
i
zation m
e
thod
such as PSO
is that
it
does not rely
explicitly on the
gradi
e
nt
of t
h
e probl
em
t
o
be opt
i
m
i
zed, so
t
h
e m
e
t
hod can
be readi
l
y
em
pl
oy
ed for
a host
of opt
i
m
i
zat
i
on
probl
em
s. Thi
s
i
s
especi
al
l
y
useful
when t
h
e gradi
e
nt
i
s
t
oo l
a
bori
ous or even i
m
possi
bl
e t
o
deri
ve.
In
th
e co
n
t
ex
t o
f
m
u
ltiv
ariab
l
e o
p
tim
izatio
n
,
th
e swarm
is assu
m
e
d
to
b
e
o
f
sp
ecified
o
r
fix
e
d
size
with each particle located
initially at random
locations
in the m
u
ltidim
ensional design
space. Each particle
is
assum
e
d t
o
have t
w
o charact
eri
s
t
i
c
s:
a
posi
t
i
on and a
vel
o
ci
t
y
. Each
part
i
c
l
e
wanders around i
n
t
h
e
desi
gn
space
and rem
e
m
b
ers the best
position (in term
s of
the food source or
objective function value) it has
discovered. The particles com
m
unicate
inform
ation
or good
positions to each
ot
her and adjust
their
individual positions and veloc
ities based on the inform
ation received on the good positions.
Although each bird has a lim
ited intelligence by itsel
f, it follows the following sim
p
le rules [20]:
1.
It
t
r
i
e
s not
t
o
com
e
t
oo cl
ose t
o
ot
her bi
rds.
2.
It steers toward the average
di
rect
i
on of ot
her bi
rds.
3.
It
t
r
i
e
s t
o
fi
t
t
h
e “average posi
t
i
on” bet
w
een ot
her bi
rds wi
t
h
no wi
de gaps i
n
t
h
e fl
ock.
Thus t
h
e behavi
or of t
h
e fl
ock or swarm
i
s
based on a com
b
i
n
at
i
on of t
h
ree si
m
p
l
e
fact
ors:
1.
C
ohesi
on-st
i
c
k t
oget
h
er.
2.
Separat
i
on-don'
t
com
e
t
oo cl
ose.
3.
Al
i
gnm
ent
-fol
l
o
w t
h
e general
headi
ng of t
h
e fl
ock.
In
the past several years, PSO ha
s b
een
su
ccessfu
lly ap
p
lied
in
m
a
n
y
research and application areas.
It
i
s
dem
onst
r
at
ed t
h
at
PSO get
s
bet
t
e
r resul
t
s
i
n
a fast
er, cheaper way
com
p
ared wi
t
h
ot
her m
e
t
hods. Anot
her
reaso
n
th
at
PSO is
attractiv
e is
th
at
t
h
ere
are few
param
e
t
e
rs t
o
adjust
.
One versi
on,
wi
t
h
sl
i
ght
vari
at
i
ons,
wo
rk
s well in
a
wid
e
v
a
riety o
f
ap
p
licatio
n
s
. Particle
swarm
opt
i
m
i
zat
i
on has been
used for approaches
that
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA
I
S
SN
:
208
8-8
7
0
8
A PSO-Op
timi
z
ed
Reci
p
r
o
c
a
l
Velo
city Ob
st
a
c
les Algo
rithm fo
r Na
vi
g
a
t
i
o
n o
f
Mu
ltip
le
… (Ziya
d
T.
Alla
wi
)
37
can
be used across a wi
de range of appl
i
cat
i
ons, as
well as for specific applica
tions focused on a specific
requi
rem
e
nt
.
PSO solves a problem
as follows:
first,
the particles are
initialized
random
ly. Then,
it finds the
best
solution by iteration. Each particle
flies through the solution space of problem
and adjust its flying velocity to
search
for the global optim
um
according to its own and
social historical experi
ences. Through the iteration,
each
particle updates itself by following the
two best va
lues, one of which
is the best solution found by the
p
a
rticle itself, we call it p
e
rso
n
a
l b
e
st v
a
lu
e, n
a
m
e
ly
P
best
, and t
h
e ot
her i
s
t
h
e best
sol
u
t
i
on found by
t
h
e
whol
e swarm
,
we
cal
l
i
t
gl
obal
best
val
u
e,
nam
e
l
y
G
best
. W
h
en
the two
best values are
found, each
particle
updates its velocity and position according
to the form
ula as follows [2, 20]:
)
1
(
)
(
)
1
(
))
(
)
(
(
))
(
)
(
(
)
(
)
1
(
2
2
1
1
i
i
i
i
i
r
c
i
i
r
c
i
w
i
j
j
j
j
best
j
jbest
j
j
v
x
x
x
G
x
P
v
v
(9)
where
v
j
(
i
) and
x
j
(
i
)
are the
n
-di
m
ensi
onal
vel
o
ci
t
y
and
posi
t
i
on vect
ors
of t
h
e
j
th
p
a
rticle in
th
e
i
th
iteratio
n
;
r
1
and
r
2
are t
w
o random
funct
i
ons i
n
t
h
e range [0, 1]
,
c
1
and
c
2
refer to the two acceleration factors,
usually
bel
ong
t
o
t
h
e i
n
t
e
rval
[0,
4]
, and
w
is
th
e in
ertial weig
h
t
. Fo
r th
e
stan
d
a
rd
PSO, th
e
w
is a co
n
s
tan
t
. In
th
e
m
odi
fi
ed
PSO by
Shi
and
Eberha
rt [2]
where they presented
w
, t
h
ey
proposed a
l
i
n
earl
y
decreasi
ng equat
i
on
to
calcu
late it,
b
u
t
th
ey in
fer
th
at it is
p
o
ssib
l
e to
u
s
e an
y n
o
n
lin
ear
d
ecreasin
g
eq
u
a
tio
n
to
rep
r
esen
t
w
. The
in
ertial weig
h
t
is d
e
fin
e
d
as fo
llo
ws:
2
max
max
min
max
min
)
(
)
(
)
(
i
i
i
w
w
w
i
w
(10)
where
w
ma
x
and
w
mi
n
are
t
h
e m
a
xi
m
u
m
and m
i
ni
m
u
m
val
u
es
of t
h
e i
n
ert
i
a
l
wei
ght
,
and
i
ma
x
i
s
t
h
e
ma
x
i
mu
m
possi
bl
e num
ber of i
t
e
rat
i
ons.
The const
a
nt
s
c
1
and
c
2
deci
de t
h
e rel
a
t
i
v
e i
n
fl
uence of t
h
e soci
al
and cogni
t
i
on com
ponent
s.
Ty
pi
cal
l
y
t
h
ese const
a
nt
s have
t
h
e sam
e
val
u
e
(
c
1
=
c
2
=2) to give
equal weight
to
each social and cognition
com
ponent
s. Al
so, t
h
e i
n
ert
i
a
l
wei
ght
w
has t
w
o ext
r
em
es, t
y
pi
cal
l
y
m
i
n. 0 and m
a
x. 1.
The PSO pseudo al
gori
t
h
m
i
s
shown bel
o
w:
F
unc
tion
G
best
=
ParticleSwarm
(
N
,
i
ma
x
)
//
N
=number of particles,
i
ma
x
=maximum no.
of iterations.
Initialize
x
j
(0), (
j
=1, 2, …,
N
) randomly
,
x
j
∊
n
,
x
min
≤
x
j
≤
x
ma
x
;
i
=0;
loop
Evaluate Fitness
f
j
(
i
) for each particle
x
j
(
i
);
Determ
ine
G
best
, the particle which has the global best fitness;
If a stopping condition is satisfied,
b
reak
;
Update the particles using Eq. 9;
i
=
i
+ 1;
until
i
=
i
ma
x
;
retu
r
n
G
best
;
en
d
.
4.
RES
U
LTS AN
D DIS
C
US
SION
S
The desi
gn procedure i
s
done under M
A
TLAB
®
envi
ronm
ent
by
usi
ng 24 i
d
ent
i
cal
m
obi
l
e
robot
s.
It
will
be assum
e
d that a sim
p
lified robot
m
odel will be
used, where each
robot is assum
e
d to have a sim
p
le
shape (circle)
m
oving in
a two-dim
e
nsional
workspace. Al
so, each
robot has
perfect sensing,
and is
able to
infer
the exact
shape, position and
velo
city of
other robots in
the envir
onm
ent.
The robots are
positioned in a
circle perim
e
ter and facing its
center as in Figure 2.
The goals are located in
the sam
e
place of
their
opponents. So, the robot will try
to m
a
neuver all ot
her 23 robots
to escape and reach its goal.
For
com
p
arison, we used the RVO m
e
thod
with arbitrary c
hosen velocities.
In
t
h
e si
m
u
l
a
t
i
on
phase, t
h
e si
ngl
e
part
i
c
l
e
i
s
a
2-di
m
e
nsi
on vect
or hol
di
ng
t
h
e m
a
gni
t
ude and
di
rect
i
on
of robot
’s vel
o
ci
t
y
. The
fi
t
n
ess equat
i
on
used i
n
si
m
u
l
a
t
i
on
i
s
Eq. 8, and t
h
e
val
u
es of
c
1
and
c
2
=2.
W
e
vary
t
h
e penal
t
y
const
a
nt
k
and t
h
e popul
at
i
on si
ze
N
. The m
a
xi
m
u
m
num
ber of i
t
e
rat
i
ons i
s
fi
xed. It
s
v
a
lu
es is
i
ma
x
=200. The m
i
ni
m
u
m
and m
a
xi
m
u
m
val
u
es of t
h
e i
n
ert
i
a
wei
ght
are 0 and 1, respect
i
v
el
y
.
The robot
speci
fi
cat
i
ons are shown i
n
Tabl
e 1.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
089
-48
56
IJR
A
V
o
l
.
4,
No
. 1,
M
a
rc
h 20
1
5
:
3
1
– 40
38
Tabl
e 1. Speci
f
i
cat
i
ons of
t
h
e M
obi
l
e
R
o
b
o
t
Specification
Value
Whe
e
l Rota
tiona
l Ve
loc
ity
20 r
a
d/s
Ang
u
lar
Ste
e
r
i
n
g
V
e
loc
ity
5 r
a
d/s
Radius of the Robot
10 cm
Radius of the W
h
eel
5 cm
Max
imum Heading
Velo
cit
y
100 cm/s
Tables
2
and 3 illustrate the m
ean robot travelling
distances (in cm
) for the two m
e
thods respectively
for various
k
and
N
(Direct Displacem
ent=1000).
Table 2.
Mea
n
Distances for robots
i
n
RVO
m
e
t
hod
RV
O
Dist
ance
k
=5 1133
k
=10 1158
k
=20 1207
k
=50 1262
Table 3.
Mea
n
Distances for robots
i
n
PSO-RVO
m
e
t
hod
PSO-RVO
N
=10
N
=20
N
=50
N
=100
k
=5 1140
1112
1103
1096
k
=10 1155
1197
1180
1174
k
=20 1200
1233
1221
1194
k
=50 1300
1244
1266
1283
Fig
u
re 2
.
Rob
o
t
Po
sition
s
for PSO-RVO
al
go
rith
m
,
N
=100,
k
=5.
Fi
gu
re
3.
R
o
bo
t
s
are m
a
neuv
e
r
i
n
g eac
h
ot
he
r
Fig
u
re
4
.
All ro
bo
ts are in th
e go
als
Fig
u
re
5
.
Rob
o
t Path
s i
n
th
e ab
ov
e
scen
ario
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA
I
S
SN
:
208
8-8
7
0
8
A PSO-Op
timi
z
ed
Reci
p
r
o
c
a
l
Velo
city Ob
st
a
c
les Algo
rithm fo
r Na
vi
g
a
t
i
o
n o
f
Mu
ltip
le
… (Ziya
d
T.
Alla
wi
)
39
Fi
gu
re
6.
R
o
bo
t
Pat
h
s
fo
r R
V
O m
e
t
hod,
k
=50
Fi
gu
re 7.
R
o
bo
t
Pat
h
s fo
r PS
O-R
V
O
m
e
t
hod fo
r
N
=20,
k
=5
0
In
the above Figures (2 to 5), we see the behavior
of the robots in a scenario of facing each others
with
th
e p
a
ram
e
ters
k
=5 and
N
=100. In Fi
gure 2, t
h
e robot
s are headi
ng di
rect
l
y
t
o
wards t
h
ei
r goal
s
despi
t
e
of the possible collisions. The robots
then begin
to m
a
neuver when the
distances between them
are
being
sm
al
l
e
r and sm
al
l
e
r. PSO t
r
i
e
s t
o
sel
ect
t
h
e best
next
m
ove for t
h
e robot
s dependi
ng on t
h
ei
r
current
configuration and the other robot
s configuration. The m
a
neuver takes place in a sm
all area of the
environm
ent, that’s because
k
i
s
sm
al
l
.
W
e
see i
n
Fi
gure 3 (zoom
ed i
n
) t
h
at
som
e
of t
h
e robot
s are cl
ose
t
o
each other
but they
will not
collide b
ecause that
PSO chooses
the best
co
llision free
path for
every one. The
robots then succeeded to
es
cape the m
a
neuvering
space and m
oved direc
tly
towards their destinations.
In
Fi
gure 4, al
l
t
h
e robot
s have arri
ved safel
y
t
o
t
h
ei
r goal
s
.
Figure
5 illustrates the
paths which all
robots ta
ke. W
e
see
that the m
a
neuvering
took place in a
sm
all area, and the robots m
oved in a pure line
from
their origins to the m
a
neuvering space and from
that
space to the goals after escaping.
W
e
see that
the robot paths
have reasonable
oscillati
ons in som
e
regions of
the environm
ent, that’s
because
k
i
s
sm
al
l
.
C
hoosi
ng
k
i
s
very
i
m
port
a
nt
i
n
t
h
at
si
t
u
at
i
on;
i
t
shoul
d be
sm
al
l
enough t
o
cancel
al
l
oscillations
that m
a
y happen
in the cour
se of
m
a
neuvering. But if
one chooses
k
v
e
ry
sm
all, th
e p
r
o
cess m
a
y
fail d
u
e
to
co
llisio
n
s
b
e
fo
re th
e m
a
n
e
u
v
e
rin
g
.
Fi
gures 6 and 7 show t
h
e envi
ronm
ent
when choosi
ng
hi
gh
k
. It
’s cl
ear t
h
at
t
h
e robot
pat
h
s
are
oscillatory from
the beginning and do
not
be a direct path unless
the robot
escapes m
a
neuvering. W
e
see
in
the Figure 8
the oscillations are
m
o
re than the
oscillations
in Figure
7, that’s becau
se
of the arbitrary
choice
of velocities in ordinary RVO m
e
thod.
If we l
ook t
o
t
h
e t
a
bl
es 2 & 3, we see t
h
at
PSO-R
VO out
perform
s i
t
s
el
f and t
h
e ordi
nary
R
VO i
n
t
h
e
m
ean robot
di
st
ances when
k
=5
, an
d
b
eco
m
e
s m
o
re
an
d
m
o
re o
s
cillato
ry with
th
e in
crease in
trav
ellin
g
distance when
k
i
s
i
n
creasi
ng;
t
h
erefore, one shoul
d choose
k
wisely to ensure collision-free and oscillation-
free navigation of m
u
ltiple robots.
Increasing
N
ai
ds i
n
fi
ndi
ng t
h
e opt
i
m
al
next
m
ove of t
h
e robot
. W
e
see i
n
Tabl
e
3
t
h
at
t
h
e
m
i
ni
m
u
m
m
ean di
st
ance
t
r
avel
l
e
d by
t
h
e robot
s
occur when
N
=100, whi
c
h
i
s
1096
cm
. As
i
n
al
l
opt
i
m
i
zat
i
on
alg
o
r
ith
m
s
,
in
creasin
g
ag
en
t size is
im
p
o
r
tan
t
to
fin
d
th
e
o
p
tim
al so
lu
tio
n
b
u
t
it
co
n
s
u
m
es tim
e; th
erefo
r
e o
n
e
shoul
d choose a m
oderat
e
val
u
e for
N
if h
e
wan
t
s to
ap
p
l
y th
is alg
o
r
ith
m
in
real-tim
e en
v
i
ro
n
m
en
ts.
5
.
CONC
LUSION
It
can be concluded from
this work
that using the optim
ization m
e
t
hods in the navigation of m
u
ltiple
m
obi
l
e
robot
s hel
p
ed i
n
som
e
way
t
o
i
n
crease t
h
e effi
ci
ency
of robot
m
a
neuveri
ng. Thi
s
i
s
cl
ear from
t
h
e
results shown in Tables 2 and 3. PSO-RVO m
e
thod has
succeeded in creating a collis
ion-free, oscillation-free
opt
i
m
um
pat
h
for al
l
t
h
e robot
s provi
ded t
h
at
choosi
ng t
h
e appropri
a
t
e
val
u
es of
k
and
N
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
089
-48
56
IJR
A
V
o
l
.
4,
No
. 1,
M
a
rc
h 20
1
5
:
3
1
– 40
40
REFERE
NC
ES
[1]
.
J. van den Berg,
et al.
, “
R
eciprocal Velocity
Obstacles for Real-T
im
e Multi-Agent Navigation”, IEEE
International
Conference on Robotics and Automation, 2008, pp. 1928-1935.
[2]
.
Y.
S
h
i and R. Eberhart, “
A
m
odified particle
s
w
arm
op
tim
izer”,
P
r
oceedings
of IEEE International Conference on
Evolutionary
Computation, 1998, pp. 69-73.
[3]
.
J.P. Laumond,
et al.
, “A motion
planner for nonholonomic mobile robots”,
IEEE Transactions on Robotics and
Automation
, Vol. 10, No. 5, 1994, pp. 577-593.
[4]
.
E. F
r
azzoli,
et al.
“Real-time motion
planning for
agile autonomous vehicles”,
Journal of
Guidance Control and
Dynamics
, Vol. 25, No. 1, 2002, pp. 116-129.
[5]
.
D.
Hsu,
et al.
,
“Randomized kinody
namic motion pl
anning
with moving obstacles”,
The International Journal of
Robotics Research
, Vol. 21, No. 3, p. 233, 2002.
[6]
.
A.
R.
Vahdat,
et al.
, “Mobile Robot Global
Localization using Di
fferential Evolution and Particle Swarm
Optim
ization”, IEEE International Conference of
Evolutionary
Com
putation, 2007, pp. 1527-1534.
[7]
.
C. Juang, and Y. Chang,
“Evolutionary
-Group-Based Par
ticle-Swarm-Optimized Fuzzy
Controller with Application
to Mobile-Robot Navigation in Unknown Environments”,
IEEE T
r
ansactions on Fuzzy Systems
, Vol. 19, No. 2,
2011, pp. 379-392.
[8]
.
N.
M.
Kwok,
et al.
, “PSO-Based Cooperative Control
of Multiple M
obile Robots in Param
e
ter-Tuned Form
ations”,
P
r
oceedings
of the 3
rd
Annual IEEE Conference on Autom
a
tion Scie
nce and Engineering, 2007, pp. 332-337.
[9]
.
Q. Tang and
P. Eberhard, “A
PSO-based algor
ithm designed
for a swarm
of mobile robots”,
Springer Journal
of
Structural and Multidisci
plinary Optimization
, Vol. 44, No. 4, 2011, pp. 483-498.
[10]
.
M.
Yang and C. Li, “Path Planning
and Tracking for Multi-robot Sy
stem
Based on Improved PSO Algorithm”,
IEEE International Conference on Mechatronic Science, 2011, pp. 1667-1670.
[11]
.
A. Z.
Mohamed,
et al.
,
“
A
fas
t
er path
planner us
ing
accelerated particle
s
w
arm
optim
ization”,
Springer
International Journal of Artificial Life and Robotics
, Vol. 17, 2012, pp. 233-240.
[12]
.
P. Fiorini and Z.
Shiller, “
M
otion planning
in dy
nam
i
c environm
ents
using velocity
obstacles”,
The International
Journal of Robotics Research
, Vol. 17, No. 7, 1998, pp. 760-772.
[13]
.
D. W
ilkie
et al.
, “
G
eneralized Velocity
Obstacles”, The IEEE/
RSJ International Conference on Intelligent Robots
and Sy
stems, 2009, pp. 5573-5578.
[14]
.
J
.
S
n
ape,
et al.
, “Independent navigation of m
u
ltiple m
obile robots
with hy
brid reciprocal velocity
obstacles”,
IEEE/RSJ International Conference on Intellig
ent Robots and Sy
stem
s, 2009, pp. 5917-5922.
[15]
.
J
.
S
n
ape,
et al.
, “
T
he
Hy
brid Reciprocal
Velocity
Obs
t
acle”,
IEEE Transactions
on Robotics
,
Vol. 27,
No. 4, 2011,
pp. 696-706.
[16]
.
J
.
Kennedy
and R. Eberhart,
“
P
article S
w
arm
Optim
ization”, P
r
oceedings
of
IEEE 4
th
International Conference
on
Neural Networks, 1995, pp. 1942-1948.
[17]
.
R. Eberhart and J. Kennedy
,
“
A
New Optim
i
zer Using P
a
rticle
S
w
arm
Theory
”, IEEE 6
th
International
Sy
m
posium
on Micro Machine and Human Science, 1995, pp. 39-43.
[18]
.
R. Poli, “
A
naly
sis of the Publications on the
Applicati
ons of Particle Swarm
Optim
i
zation”, Hindawi Journal
of
Artificial Evolution and Applications, 2008, pp. 1-10.
[19]
.
D. W
a
ng and
F
.
F
a
n, “
S
tudy
on Modified P
S
O
Algorithm
”
, IEEE 6
th
International Conference on
Natural
Computation, 2010, pp. 640-645.
[20]
.
S. S. Rao, "Engineering Optimization", John Wile
y
& Sons Inc., Hoboken, New Jersey
, USA, 2009.
[21]
.
S.
J.
Guy
,
et al.
,
“
C
lear P
a
th: Highly
parallel
collision avoidance fo
r m
u
lti-agent
sim
u
lation,” in P
r
oceedings of
the
ACM SIGGRAPH
Eurographics Sy
mposium of
Computer and Animation, 2009, pp. 177-187.
[22]
.
C. F
u
lgenzi,
et al.
, “
D
y
n
am
ic
obs
tacle avoidance in uncertain envi
ronment
combining PVOs and occupancy
grid,”
in Proceedings of the IEEE International Confer
ence of Robotics and Autom
a
tion, 2007, pp. 1610-1616.
[23]
.
B. Kluge and E. Prassler, “Re
fl
ective navigation: Individual
behaviors and
group behaviors,” in Proceedings of
the
IEEE International Conference of Robotics and Autom
a
tion, 2004, pp. 4172–4177.
[24]
.
Y. Abe and M. Yoshiki, “Collision avoidance
m
e
thod
for m
u
ltiple autonom
ous m
obile agents by
im
plicit
cooperation,”
in Proceedings of the
IEEE RSJ Internationa
l. Conference of
Intelligent Robotic Sy
stem
s, 2001, pp.
1207-1212.
[25]
.
K. C. Ng
and M. M.
Trivedi, “A
neuro-fuzzy
contro
ller for
m
obile robot navigation
and m
u
ltirobot
convoy
ing,”
IEEE Transactions of System
s, Man and Cybernetics B
, Vol. 28, No. 6, 1998, pp. 829-840.
[26]
.
S. Carpin and L. E. Parker, “
C
ooperative m
o
tion coordina
tion am
idst dy
nam
i
c obstacles,” in Proceedings of the
International Sy
mposium of Distributive Au
tonomous Robotic Sy
stems, 2002, pp. 145-154.
[27]
.
S. M. LaValle, “Planning Algorith
ms”, Cambridge, U.K. Cambri
dge University
Press, 2006.
Evaluation Warning : The document was created with Spire.PDF for Python.