Intern
ati
o
n
a
l Jo
urn
a
l
o
f
R
o
botics
a
nd Au
tom
a
tion
(I
JR
A)
Vol
.
3
,
No
. 2,
J
une
2
0
1
4
,
pp
. 10
7~
11
1
I
S
SN
: 208
9-4
8
5
6
1
07
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
An Opti
mized Algorithm Bas
e
d
on Random Tree and Particle
Swarm
Zh
o
u
F
e
ng
Shandong Institu
te of
Com
m
e
rce
and T
echnolo
g
y
, Shang Dong Ji
Nan, 250103
, C
h
ina
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Aug 11, 2013
Rev
i
sed
Feb
20
, 20
14
Accepted
Mar 10, 2014
A based on R
a
pidly
-
explo
r
ing
Random
Tree (
RRT) and
Particle Swarm
Optimizer (PSO) for path plann
i
ng of
the robot is proposed. First the grid
method is built
to describ
e
the
working
space o
f
the mobile rob
o
t, th
en
the
Rapidly
-
exploring Random Tree algorith
m is
used to obtain the glob
al
navigation path, and the Parti
c
l
e
Sw
arm
Optimizer
algor
ithm
is adopted
t
o
get th
e better p
a
th.Computer ex
periment
results demonstrate th
at this nov
el
algorithm can plan an optimal p
a
th rap
i
dly
in a cluttered enviro
nment.
The
successful obstacle
avoidan
ce is achie
v
e
d, and
the model is
robust and
performs reliably
.
Keyword:
Particle swarm op
ti
m
i
zer
Pat
h
pl
an
ni
n
g
R
a
pi
dl
y
-
ex
pl
or
i
ng ra
nd
om
t
r
ee
Ro
bo
t
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
:
Zh
ou
Fe
ng
,
Sh
an
don
g In
stitu
te of Co
mm
e
r
ce an
d Tech
no
log
y
, Sh
an
gDo
n
g
Ji
Nan
,
25
01
03
, Ch
i
n
a
Em
a
il: zh
o
u
feng
k
e
y
@
163
.com
1.
INTRODUCTION
Robot path
pl
anni
ng m
eans in the
working space, a pat
h
is found
with the robot starting from
a
poi
nt
, r
o
un
di
n
g
b
a
r
r
i
e
rs a
n
d
arri
vi
n
g
t
o
t
h
e
dest
i
n
at
i
o
n.
C
o
m
m
onl
y
,
there a
r
e m
a
ny
pat
h
s
fo
r
ro
bot
t
o
accom
p
lish the task, but in fa
ct the best
path is selected according to some
guide line.
These guide li
nes are:
sho
r
t
e
st
pat
h
,
l
east
ene
r
gy
co
ns
um
i
ng o
r
s
h
o
r
t
e
st
t
i
m
e.So
, t
h
e r
o
b
o
t
pat
h
pl
an
n
i
ng i
s
a c
o
ns
t
r
ai
ned
opt
i
m
i
zati
on
p
r
o
b
l
e
m
.
R
obot
pat
h
pl
an
ni
ng
has
bee
n
a
n
ac
t
i
v
e resea
r
ch
a
r
ea, a
n
d m
a
ny
m
e
t
hod
s
have
bee
n
devel
ope
d t
o
tackle this problem
,
such as
rolling pla
n
[1], RRT
m
e
thods [2],
neural
networks a
p
proache
s
[3]
,
GA
m
e
t
hod
s[4]
a
n
d
AC
O
al
go
ri
t
h
m
[5]
so
on
. T
h
ese
w
o
rks
ha
ve m
a
de
som
e
i
nno
vat
i
v
e ac
hi
evem
ent
s
.b
ut
th
e co
mm
o
n
sh
ortag
e
is th
at
so
l
v
ing
tim
e i
s
too
long
, effi
cien
cy is no
t
hig
h
.
Althou
gh
In [6
] th
e al
g
o
rith
m
can achi
e
ve ra
pi
d
opt
i
m
i
z
at
i
on, b
u
t
beca
use
a ro
bot
go
do
gl
eg pat
h
i
n
f
r
ee zone
, t
h
e pat
h
m
a
y
not
be o
p
t
i
m
a
l
.
Gri
d
m
e
t
hod
i
s
o
n
e
of
t
h
e
co
m
m
onl
y
used
m
odel
i
ng m
o
d
e
l
i
ng m
e
t
hod
,
but
i
t
has
a
def
ect
:
a r
o
b
o
t
go
do
gl
e
g
p
a
th
i
n
free
zon
e
.
Th
e dog
leg is subo
p
tim
al
p
a
th
s and
robot arriv
a
l tim
e w
ill in
crease.
In
t
h
i
s
pape
r,
A
base
d
on
R
a
pi
dl
y
-
e
xpl
ori
n
g
R
a
n
d
o
m
Tree (R
R
T
)
an
d
Part
i
c
l
e
Swa
r
m
Opt
i
m
i
zer
(PS
O
)
for pat
h
planning of
the robot is
propose
d
. First the
gri
d
m
e
t
hod is built to des
c
ribe the working
spac
e
o
f
th
e m
o
b
ile ro
bo
t, th
en
th
e Rap
i
d
l
y-exp
l
oring
Ra
nd
o
m
Tree al
gori
t
hm
i
s
used
to
ob
tain
th
e g
l
ob
al
navi
gat
i
on
pat
h
, an
d t
h
e Pa
rt
i
c
l
e
Swarm
Opt
i
m
i
zer al
g
o
ri
t
h
m
i
s
adopt
ed t
o
get
t
h
e bet
t
e
r pat
h
. The
effective
n
ess a
n
d
efficiency of
t
h
e
p
r
o
p
o
se
d
al
go
ri
t
h
m
i
s
dem
onst
r
at
ed by
sim
u
l
a
t
i
on st
u
d
i
es.
2.
DESC
RIPTI
O
N OF
E
N
V
I
RO
NME
N
T
To ens
u
re t
h
at
t
h
e pat
h
i
s
not
t
oo cl
ose t
o
any
of t
h
e
obst
acl
es, t
h
e
di
m
e
nsi
on of
t
h
e ro
bot
i
s
rep
r
ese
n
t
e
d by
a poi
nt
, an
d
t
h
e bo
u
nda
ri
es
of t
h
e o
b
st
ac
l
e
s are expa
n
d
ed acc
or
di
n
g
t
o
t
h
e pl
us o
f
t
h
e
m
a
xim
u
m
di
stance occ
u
pi
ed
by
ro
b
o
t
’
s cr
o
ss.Let
AS
b
e
th
e fin
ite wal
k
in
g
area of
Rob
in
a two-d
i
men
s
ion
pl
ane a
nd
AS
i
s
a p
r
o
t
ru
d
i
n
g
p
o
l
ygon
, in
wh
ich
th
er
e ar
e
f
i
n
ite nu
m
b
er
s o
f
static ob
stacles
b
1
, b
2
,
……
, b
n
.
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:
1
0
7
– 11
1
10
8
Th
e task
is to
p
l
an
a m
u
ch
sh
orter
p
a
th
fo
r th
e rob
o
t
to walk
fro
m
begin
g
to
end
g
co
llisio
n-freely. And
0
is
th
e ri
g
h
t
-ang
led
co
ord
i
n
a
te syste
m
in
AS
who
s
e orig
in
i
s
th
e left and
u
p
p
e
r co
rn
er of
AS and
its lan
d
s
cap
e
ori
e
nt
at
i
on i
s
X-a
x
es, i
t
s
po
r
t
rai
t
i
s
Y-axes.
The m
a
xim
a
l
val
u
es
of x a
n
d y
are
ma
x
x
and
ma
x
y
, re
spectively.
The
n
x an
d y
can be di
vi
de
d
usi
n
g
δ
as an
unit, as a result, all grids can
be f
o
rm
ed one
by
one (
f
i
g
.
1
)
.
The
num
bers
of e
ach
row a
nd col
u
m
n
are
a
x
R
x
N
/
ma
x
and
a
y
R
y
N
/
ma
x
, res
p
ectively
,
(i
f
AS
is
co
nsid
ered
as t
h
e arb
itrary shap
e, so
m
e
g
r
id
-ob
s
tacles
can
b
e
filled
on
the b
oun
d
a
ry o
f
AS to
m
a
k
e
it
sq
uare
or rect
a
ngl
e
)
,
whe
r
e
1,
2
,
,
i
bi
n
hol
ds one
or m
o
re grat
i
n
gs,
whe
n
i
t
i
s
not
a ful
l
one, t
h
ey
are
considere
d
a
s
t
h
e
full
one
.
The m
obi
l
e
ro
bot
e
nvi
ro
nm
ent
i
s
rep
r
ese
n
t
e
d by
or
derl
y
n
u
m
b
ered
gri
d
s
C
={1,
2,
3,…
，
,
M
}, eac
h of
wh
ich
rep
r
esents a lo
catio
n
in th
e env
i
ro
n
m
en
t.
g
(
x
,
y
) also represe
n
ts a location i
n
the
envi
ronm
ent,
x
is th
e
ro
w num
ber,
y
is th
e co
lu
m
n
s
n
u
m
b
e
r.
In t
h
e
gri
d
ba
sed r
o
b
o
t
en
vi
ro
nm
ent
,
t
h
e num
ber
i
and
g
(
x
,
y
) de
n
o
t
e
gri
d
a
nd e
nvi
ro
nm
ent
coor
d
i
nat
e
,
respectively,t
h
us
x
i
=((
i
-1
) m
o
d
N
x)+
1
,
y
i
=(int)((
i
-1)
/
N
x)+
1
(1
)
Fi
gu
re
1.
R
e
l
a
t
i
ons
hi
p
bet
w
ee
n
gri
d
c
o
o
r
di
na
t
e
s an
d se
que
n
ce n
u
m
b
er
3.
RRT
-PS
O
Gri
d
m
e
thod is
sim
p
le co
m
m
on m
odeling m
e
thods. But
its dra
w
back is that partition size is difficult
to
con
t
ro
l, th
e
g
r
i
d
size is smaller, ob
stacles are said
t
o
b
e
m
o
re p
r
ecise,
b
u
t
at th
e sam
e
ti
m
e
i
t
will ta
k
e
up
a
lot of storage s
p
ace; the gri
d
size is
too large, the planne
d path is no
t accurate. T
h
ere
f
ore whe
n
planni
ng the
preci
se
pat
h
, t
h
e
gri
d
m
e
t
hod ca
nn
ot
be
u
s
ed.T
o
res
o
l
v
e
t
h
e s
h
o
r
t
a
ge
i
n
t
h
i
s
pa
per
t
h
e R
a
pi
dl
y
-
ex
pl
o
r
i
n
g
Ran
d
o
m
Tree alg
o
rith
m
is u
s
ed
to
ob
tain th
e
g
l
ob
al
na
vi
gat
i
o
n
pat
h
,
a
nd
t
h
e
Part
i
c
l
e
Swarm
Opt
i
m
i
zer
alg
o
rith
m
is a
d
op
ted
t
o
adjust
m
e
n
t
th
e in
tersectio
n
po
in
t
o
f
each
in
itial p
a
th
an
d
the bo
und
ary of th
e g
r
id.
Each di
m
e
nsi
on
of eac
h
di
m
e
nsi
on
rep
r
e
s
ent
s
a p
o
i
n
t
of i
n
t
e
rsect
i
o
n
.
The c
o
n
n
ect
i
on
whi
c
h f
r
o
m
l
o
w
d
i
m
e
n
s
io
n
to
h
i
gh
d
i
m
e
n
s
io
n
will con
s
titute a n
e
w p
a
t
h
, After sev
e
ral
iteratio
n
s
t
h
e
ap
pro
x
i
m
a
te o
p
t
i
m
al
g
l
ob
al p
a
t
h
will b
e
find
ed. The op
ti
m
i
zatio
n
task
is to ad
ju
st th
e po
sition
o
f
x
d
to
sho
r
ten
th
e leng
th of p
a
t
h
and
get the optim
i
zed (or acc
eptable)
path
in the pla
nni
ng
space.T
h
e a
d
just proce
ss of
x
d
i
s
show
n i
n
Fi
gu
re
2. A
n
y
x
d
can
slid
e freely alo
n
g
th
e free link
t
h
at it lies on
. Path
Cod
i
ng
Meth
od
n
e
w path
form
ed
b
y
th
e
slid
e
of
x
d
on
lin
e
x
d
mi
n
、
x
d
ma
x
will
no
t in
tersect
with
th
e ob
stac
les. After
proc
essing eve
r
y
x
d
,
t
h
e ne
w pat
h
no
de
s
sequ
en
ce fo
rm
s a
n
e
w co
llisio
n free
p
a
th
for th
e ro
bo
t.
Fi
gu
re 2.
Pat
h
C
odi
ng
M
e
t
h
o
d
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA I
S
SN
:
208
9-4
8
5
6
A n
o
vel
pat
h
pl
an
ni
n
g
f
o
r r
o
b
o
t
s
base
d
o
n
r
a
pi
dl
y-ex
pl
ori
n
g r
a
n
d
o
m
t
r
ee
an
d
p
a
rt
i
c
l
e
sw
arm…
(
Z
h
o
u
Fen
g
)
10
9
Fo
r co
nv
en
ien
t
ly d
e
scrib
e
,
we m
a
k
e
th
e fo
llowing
d
e
fi
n
itio
n:
Defi
n
itio
n
1
.
Th
e d
i
stan
ce between
an
y two
grid
cells g
i
and g
h
(
o
r c
o
r
r
esp
o
ndi
ng
p
o
i
n
t
s
P
i
and P
h
) is
th
e
len
g
t
h of t
h
e lin
e
b
e
tween
the cen
ter po
in
ts of th
e
two
g
r
ids an
d
is d
e
no
ted b
y
d(g
i
, gh
)
or
d(
P
i
, P
h
).
i,h
∈
C.
22
dg
g
x
x
y
y
ih
i
h
ih
（，
）
（
）
（
）
(2
)
Defi
ni
t
i
on
2.
T
h
e n
u
m
b
er o
f
i
wh
ich
is free
g
r
i
d
m
a
k
e
u
p
a set wh
ich
was called
th
e feasib
le reg
i
o
n
, M
a
rk
ed
as F
.
F
∪
S=A
., i
F
。
Defi
ni
t
i
on
3.
F
o
r al
l
no
des i
n
t
h
e R
R
T
c
o
r
r
e
sp
on
di
n
g
gri
d
seri
al
n
u
m
b
er
i
co
nsistin
g
of a co
llectio
n
called
R
R
T
n
ode
set
,
M
a
rke
d
as
P
(
RR
T
).
Defi
n
itio
n
4
.
If g
is a
grid
cell
,
th
e set
NEIB
i
is called
th
e
n
e
ighbo
rho
o
d
o
f
g
i
.
T
h
e broad
lines marked
t
h
e
n
e
igh
bor
hoo
d
o
f
g(
4,4)
i
n
f
i
g1
.
Defi
n
itio
n
5
.
Co
llectio
n
wh
ich
is co
m
p
o
s
ed
b
y
th
e
serial
n
u
m
b
er th
at th
e
ro
bo
t is
no
t search
ed called
Q(RRT)
3.2 The
Basic
Idea
and Steps of the
Algori
thm
Fi
gu
re 3.
The
R
R
T
C
o
n
s
t
r
uct
i
on
Th
e r
a
p
i
d
l
y-
exp
l
or
ing
r
a
ndom
tr
ee p
l
ann
e
r is an
i
n
cr
em
en
tal sear
ch algo
r
ith
m
th
at
p
r
o
v
i
d
e
s b
e
n
e
f
i
t
s
ov
er
co
nv
en
tio
n
a
l
ro
ad
m
a
p
p
l
ann
e
rs
du
e t
o
t
h
e i
n
h
e
ren
t
feasib
ility o
f
th
e so
lu
tio
n
s
g
e
n
e
rated.In
itially, th
e
G
b
e
gin
is
t
h
e onl
y
no
de
of G
end
.
For ea
ch iteration, a random state
G
rand
i
s
chosen
, and G
nearst
is selected as the nearest
state to G
rand
acco
rd
ing
t
o
a
metric fun
c
tion
p.
For G
nearst
a
best
i
n
p
u
t
G
best
is ch
osen to
g
e
n
e
rate a new state
G
extend
wh
ich
is clo
s
est to
G
ran
d
of
al
l
st
at
es g
e
nerat
e
d
by
ap
pl
y
i
ng
o
n
e st
e
p
c
ont
r
o
l
fr
om
G
rand
.
If
G
rand
satisfies
t
h
e
gl
obal
co
ns
t
r
ai
nt
s, G
rand
wi
l
l
be ad
de
d t
o
G
end.
St
ep1:
G
begin
a
s
the start point,
G
end
as t
h
e goal
poi
nt
,
The gri
d
serial num
b
er
of
G
begin
as
RRT
r
oot
n
o
d
e
, in
itializes relev
a
n
t
p
a
rameters.
St
ep2:
Let
G
nea
r
st
=
G
root
,
G
neast
is th
e clo
s
est no
d
e
in
t
h
e
P(R
R
T)
to
th
e
G
end
.
St
ep3:
i
f
G
nearst
=
G
end
, t
h
en goto Step6;else
goto
Step4.
St
ep4:
p
whi
c
h
o
b
ey
s u
n
i
f
orm
di
st
ri
b
u
t
i
o
n i
s
a ra
nd
om
nu
m
b
er
(
p
∈
[0
,1]
). If
p
is less th
an
p
g
,
th
en
let
G
targe
equal
s
G
end
. I
f
p
is
greater tha
n
p
g
, let
G
target
i
s
bl
ank
gri
d
w
h
i
c
h i
s
ra
n
dom
l
y
sel
ect
ed i
ndi
vi
dual
s
fr
om
Q(RRT)
.
p
g
is
known as
the consta
nts.
St
ep5:
Fi
n
d
a n
ode
G
n
(
Gn
P(RRT
)
),and
G
n
is t
h
e clo
s
est to
th
e
G
target.
An
d t
h
e
n
fi
nd a
n
o
d
e
G
extend
(
Gextend
NEIB
Gn
,
P(RRT)
Gextend
)wh
i
ch
is th
e clo
s
est to
th
e
G
n
.
If
G
extend
can
b
e
find
,it will b
e
ad
d
e
d
to
P(RRT)
.
If d
(
G
extend,
G
end
) is less th
an d(
G
nearst,
G
end
),
th
en let
G
nears
equa
l
s
G
extend
. Oth
e
rwise, th
e ex
ten
s
ion
failed
,
go
to
Step
3
;
St
ep6:
R
e
t
u
r
n
t
o
t
h
e
f
o
rm
at
i
on
of
t
h
e R
R
T
,
a pat
h
f
r
om
G
en
d
to
G
begin
ca
n
be m
a
de
by
t
r
aversi
ng
u
p
the tree
until the root
node
is reached.
St
ep7:
Sel
ect
t
h
e best
navi
gat
i
on pat
h
P=
{
P
0
P
1
……P
u+1
} ,P
0
is th
e start
poin
t
,
P
u+1
is th
e
g
o
a
l
po
in
t.
St
ep8:
C
a
l
c
ul
a
t
ed t
h
e
num
ber(M
ar
ke
d as
Pn
um
)
o
f
i
n
t
e
r
s
ect
i
on
poi
nt
s t
h
e na
vi
gat
i
on
pat
h
a
n
d t
h
e
vertical boundary of the
grid
,that is each
pa
rticle has
Pnum
di
m
e
nsi
on, C
a
l
c
ul
at
e t
h
e sl
i
d
i
ng
ran
g
e
o
f
t
h
e fi
rst
d-
di
m
e
nsi
onal
fr
om
x
d
mi
n
to
x
d
ma
x
.
Step
9
:
In
itialize
p
a
rticle
c
(ra
ndom
ly init
iali
ze each
dim
e
nsion
of the
pa
rticle’s position
(0)
x
c
and
v
e
lo
city in
t
h
e
so
lu
tion
sp
ace
(0
)
v
c
), each pa
rticle’s historic
opti
m
al position
p
c
is itself.
In
itializes relev
a
n
t
p
a
ram
e
te
rs:
max
、
mi
n
、
1
c
、
2
c
max
P
(the larg
est
num
b
e
r o
f
iteratio
n
s
) n
(iteratio
n coun
ter).
G
begi
n
G
ne
ar
s
t
G
ta
r
g
e
t
G
ex
t
e
n
d
G
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
.
3,
No
. 2,
J
u
ne 2
0
14:
1
0
7
– 11
1
11
0
Step10: Calculate each article’s
fitness val
u
e according to
Eq.
(3
)
and
lab
e
l th
e p
a
rticle with
th
e
minim
u
m
fitness val
u
e as
P
g
;
1
,1
,
1
,
,
1
((
)
)
(
,
)
(
(
)
,
(
)
)
(
,
(
)
)
(
3
)
P
num
c
b
e
g
in
c
c
d
c
d
e
nd
c
P
num
d
Fx
t
d
G
x
d
x
t
x
t
d
G
x
t
Step11: Updat
e
particle’s
velocity according to Eq. (4)
.
if
d
d
c
v
v
max
,
,
set
d
d
c
v
v
max
,
,
if
d
d
c
v
v
max
,
, set
d
d
c
v
v
max
,
;r
1
and r
2
a
r
e ra
n
dom
num
ber
bet
w
een
0
and
1
.
,,
1
1
,
,
22
,
,
(
1
)
(
)
[
()
()
]
[(
)
(
)
]
(
4
)
c
d
cd
cd
cd
gd
c
d
vt
V
t
c
r
pt
xt
cr
p
t
x
t
Update pa
rticle’s position
according to
Eq.
(5),
if
d
d
c
x
x
min
,
,
set
d
d
c
x
x
min
,
. if
d
d
c
x
x
max
,
, set
d
d
c
x
x
max
,
;
,,
,
(1
)
(
)
(
1
)
(
5
)
cd
c
d
cd
x
t
xt
vt
Step12: Calcul
ate each article’s fitnes
s val
u
e (
F
c
(
x
(
t
+
1
))) according to
Eq.
(3
)
.
U
pdat
e
p
c
、
Up
dat
e
p
g
、
n=n+
1,
()
/
ma
x
m
ax
m
i
n
m
ax
np
.
Step
13
: if n
<
p
ma
x
,t
urn
t
o
st
ep 11
and
iterate
;
if n
=
p
ma
x
tu
rn to
step
1
4
.
Step
14
:
find
the op
ti
m
a
l p
a
th
.
4.
SIMULATION RESULT
To i
nve
st
i
g
at
e
t
h
e ef
fect
of
t
h
e al
g
o
ri
t
h
m
pr
op
ose
d
i
n
t
h
i
s
pape
r,
m
a
ny
si
m
u
l
a
t
i
on e
xpe
r
i
m
e
nt
s were
co
ndu
cted
.
As will b
e
shown in
th
e
n
e
x
t
sectio
n
s
, th
e
results were
qu
ite
satisfacto
r
y and
co
m
p
are favo
rab
l
y
t
o
res
u
l
t
s
usi
n
g
ot
her
al
g
o
ri
t
h
m
s
. A Pe
nt
i
u
m
deskt
op c
o
m
put
er wi
t
h
I
n
t
e
l
D
u
al
C
o
r
e
C
P
U,
2
.
3
3
G
Hz, a
n
d
2
G
B
m
e
m
o
ry
was used. Th
e so
ft
ware is written
in M
S
Visu
al St
udio
6
.
0
C. In
o
r
d
e
r to resu
lts were
com
p
arabl
e
, s
e
t
t
i
ng t
h
e
sam
e
expe
ri
m
e
nt
al
envi
ro
nm
ent
Un
de
r t
h
e sam
e
con
d
i
t
i
ons a
nd
wi
t
h
t
h
e en
vi
r
onm
ent
of F
i
gu
re 4.
We co
m
p
are our res
u
l
t
s
wi
t
h
t
h
e
resu
lts in
[7
]. Th
e fi
n
e
lin
e
wh
ich
leng
th
i
s
32
.1
4
stan
ds
for th
e
p
a
th
o
f
ACO. Th
e bo
l
d
lin
e
wh
ich
len
g
t
h
is
30
.1
2 st
an
ds f
o
r t
h
e pat
h
of t
h
e al
gori
t
h
m
i
n
[7]
.
T
h
e re
d l
i
n
e whi
c
h l
e
ngt
h
i
s
29.
57 st
a
n
d
s
fo
r t
h
e pat
h
o
f
o
u
r
alg
o
rith
m
.
Th
e grid
is
u
s
ed
as len
g
t
h
u
n
it i
n
t
h
is
d
r
awing
.
In c
o
m
p
l
e
x en
vi
r
onm
ent
s
t
h
e
ro
b
o
t
na
vi
gat
i
on i
s
ve
ry
suc
cessf
ul
usi
ng
o
u
r al
go
ri
t
h
m
.
We c
o
m
p
are
o
u
r resu
lts
with
th
e
resu
lts in [6
]. Th
e
b
l
ack lin
e wh
ich
le
ng
th
is
3
2
.13
stan
d
s
fo
r t
h
e
p
a
th
of th
e algo
rit
h
m
in
[6
].
Th
e red
line wh
ich
len
g
t
h
is 31
.2
5 stand
s
fo
r t
h
e
p
a
th
of ou
r algo
rith
m
.
Fi
gu
re
4.
The
pat
h
i
n
a
si
m
p
le en
vi
r
onm
ent
Fi
gu
re
5.
The
pat
h
i
n
a c
o
m
p
l
e
x en
vi
r
o
nm
en
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA I
S
SN
:
208
9-4
8
5
6
A n
o
vel
pat
h
pl
an
ni
n
g
f
o
r r
o
b
o
t
s
base
d
o
n
r
a
pi
dl
y-ex
pl
ori
n
g r
a
n
d
o
m
t
r
ee
an
d
p
a
rt
i
c
l
e
sw
arm…
(
Z
h
o
u
Fen
g
)
11
1
In orde
r t
o
further validate t
h
e algorithm
,
We com
p
ared
our algo
rith
m
with
o
t
h
e
rs in th
e
3
0
* 30
env
i
ron
m
en
t
of
re
fere
nce
[8
]
.
In
t
h
e t
a
bl
e
1
are l
i
s
t
e
d t
h
e a
v
era
g
e l
e
ngt
h
of
pat
h
whi
c
h
obt
ai
ne
d i
n
fi
v
e
t
e
st
s.
Tabl
e 1. Per
f
o
r
m
a
nce
C
o
nt
ras
t
envir
o
n
m
ent
A* GA
ACO
－
grid
RRT-grid
[7]
ref
e
ren
c
e
[9
]
our
algor
ith
m
30*3
0
[8
]
N/A 85.
491
65.
0
61.
2
45.
0
44.
5
5.
CO
NCL
USI
O
N
In t
h
i
s
pa
per, t
h
e aut
h
o
r
s
pr
o
pos
e a n
ovel
m
e
t
hod t
o
s
o
l
v
e t
h
e gl
o
b
al
pa
t
h
-
p
l
a
n
n
i
n
g p
r
obl
em
for t
h
e
m
obile robot.
First the
grid
method is
buil
t
to
desc
ri
be t
h
e
working s
p
ace of t
h
e m
o
bile robot, the
n
the
R
a
pi
dl
y
-
ex
pl
or
i
ng R
a
n
dom
Tree al
go
ri
t
h
m
i
s
used t
o
obt
ai
n t
h
e
gl
o
b
al
navi
gat
i
o
n
pat
h
, an
d t
h
e
Part
i
c
l
e
Swarm
Op
tim
i
zer algo
rith
m
is ad
op
ted
t
o
g
e
t th
e b
e
tter
p
a
th
.
Exp
e
rimen
t
resu
lts show th
e
v
a
lid
ity and
practicability of the m
e
thod.
By this
m
e
thod, it is eas
y to build a m
odel and m
eet
the
real-tim
e dem
a
nd
for
m
o
b
ile ro
bo
t’s
n
a
v
i
g
a
tio
n wit
h
th
e sim
p
le al
g
o
rith
m
,
wh
ich resu
lts in
a certain
practical valu
e.
REFERE
NC
ES
[1]
Yanrong Hu and Simon
X. Yang.
A Knowledge
Based Genetic A1gorith
m for Path of a Mobile Robot
. P
r
oceed
ings
of the 2004 I
E
EE in
ternation
a
l
Conferenceon R
obotics
& Auto
mation New Orleans. 200
: 4350-
4355.
[2]
GUO Tongy
ing
,
QU
Daokui, DONG Zaili.
Res
e
arch of Path Planning for Polishing Robot Based on Improved
Genetic Algorith
m
. Proceedings
of the 2004 I
E
EE International
C
onference on
R
obotics
and Bio
m
imetics: 334-3
38
[3]
Qin Yuan Qing, Sun De Bao.
Path Plann
ing
For Mobile Ro
bot Using
The Particl
e
Swarm Optimization
With
Mutation Op
erator
. Proceedings
of th
e
Third I
n
ternational Co
nfer
ence on
Machine Learning
and C
y
bern
etics,
Shanghai, 26-29
August 2004: 24
73-2478.
[4]
Sun Bo, Chen Weidong, Xi Yugeng. Pa
rticle Swarm Optimization Based Globa
l Path Planning
for Mobile Rob
o
ts.
Control and Decision
. 2005
; 20(9
)
: 1052-1060
(in
Chinese)
[5]
Zhu Qing Bao. Ant Algorithm
for Navigation
of
Multi-Robot Movem
e
nt in Unknown Environm
ent.
Journal of
Software
. 2006;
17(9): 1890-189
8 (in Ch
inese)
.
[6]
Guo Haitao, Zh
u Qingbao, Xu
Shoujiang.
Rapid-exploring rand
om tree algorith
m for
path plan
ning of robot based
on grid method.
Journal of Nanjing Normal Univers
ity: Engin
eering and Technology Edition
. 2007
; 7(2): 58-61. (in
Chines
e)
[7]
GUO Haitao,
ZHU Qingbao, SI
Yingtao. Novel Path Planni
ng
f
o
r Robots S
y
ncr
e
tizing Ant Alg
o
rithm and Gen
e
tic
Algorithm.
Jour
nal of Chinese C
o
mputer Systems
. 2008; 29(10): 1
838-1841. (in
C
h
inese)
[8]
Zhang Meiy
u
,
Huang Han, Hao Zhifeng
.
Motion Planni
ng Of
Autonomous Mobile Robo
t Bas
e
d On Ant Colo
n
y
Algorithm.
Com
puter Eng
i
neerin
g and App
lica
tio
ns
. 2005; 41
(9):
34-37 (in Ch
ines
e)
[9]
Cai Wenbin
,
Z
hu Qingbao. Ro
lling Path Plan
ning of R
obot
Based on Rap
i
d
l
y
Explor
ing R
a
ndom
Tree
in
an
Unknown Environment.
Journal of Nanjing Normal
University:
Engineering and
Technolog
y Ed
ition
. 2009
; 6(2)
:
79-83. (in
Chin
ese)
Evaluation Warning : The document was created with Spire.PDF for Python.