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
. 11
2~
11
7
I
S
SN
: 208
9-4
8
5
6
1
12
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
Rolling Path Plan of Mobile Robo
t Based on automatic diffluent
ant algorithm
Zh
o
u
f
e
ng
Shandong Institu
te of
Com
m
e
rce
and T
echnolo
g
y
, Shang Dong Ji
Nan, 250103
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Aug 11, 2013
R
e
vi
sed M
a
r
4,
2
0
1
4
Accepted
Mar 26, 2014
This paper
prop
oses a new rolling algor
ithm for path p
l
an of
mobile robo
t
based on automatically
shunt th
e ant
algor
ithm. The goal node is mapped to
the nod
e n
earb
y
the boundar
y
in
the ey
eshot of
the robot,
and make ou
t th
e
best parti
a
l path
, which the robo
t goes ahead for
a step. The alg
o
rithm
will
iter
a
te on
e t
i
m
e
when the robo
t arrive
s at
the go
al
node.
The robo
t
will reach
the d
e
stination
along th
e optim
al path
. Simulatio
n
expe
r
i
ments illustrate th
at
the algor
ithm can be used to plan the op
timal path for mobile robot even in
the complex and
unknown
st
atic environment.
Keyword:
An
t al
g
o
rith
m
Aut
o
m
a
tic diffluent
Pat
h
pl
an
ni
n
g
R
o
l
l
i
ng pl
an
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
Shandong Institu
te of
Com
m
e
rce
and T
echnolo
g
y
, Shang Dong Ji
Nan, 250103
Em
a
il: zh
o
u
feng
k
e
y
@
163
.com
1.
INTRODUCTION
Path planning is an basic issue in
researchi
n
g robotics. It is also an
im
port
a
nt
bra
n
ch
of t
h
i
s
fi
el
d. It
mean
s th
at In
an
en
v
i
ron
m
en
t with
o
b
s
tacles, how to fi
n
d
a su
itab
l
e co
llisio
n-free
p
a
th
for a m
o
b
ile rob
o
t
t
o
m
o
v
e
fro
m
a s
t
art lo
catio
n
to a targ
et lo
catio
n. Rob
o
t
pat
h
pl
anni
ng
has
been a
n
act
i
v
e
researc
h
area,
and
m
a
ny
m
e
t
hod
s
have bee
n
de
v
e
l
ope
d t
o
t
ackl
e
t
h
i
s
pro
b
l
e
m
,
such as rol
l
i
n
g
pl
an [1]
,
R
R
T
m
e
t
hods [
2
]
,
n
e
ural
net
w
or
ks a
p
pr
oache
s
[
3
]
,
G
A
m
e
t
hods
[
4
]
and
s
o
on
.
Ant
sy
st
em
(AS)
al
g
o
ri
t
h
m
i
s
a
no
vel
si
m
u
l
a
t
e
d
evol
ut
i
ona
ry
a
l
go
ri
t
h
m
.
In re
cent
y
ears,
m
a
ny
sch
o
l
a
rs
ha
ve a
ppl
i
e
d
A
S
al
go
ri
t
h
m
t
o
t
h
e
pat
h
pl
an
ni
ng
o
f
m
obi
l
e
robot
s,
but
t
h
e com
m
on
pr
obl
em
i
s
t
h
at
t
h
ei
r al
gor
i
t
h
m
lim
i
t
e
d on t
h
e ori
g
i
n
al
AS al
g
o
ri
t
h
m
.
In t
h
e
ori
g
i
n
al
AS
a
l
go
ri
t
h
m
,
Ant
s
de
p
o
si
t
a c
e
rt
ai
n am
ount
o
f
phe
r
o
m
one
whi
l
e
wal
k
i
n
g,
an
d eac
h a
n
t
p
r
ob
ab
ilisticall
y
p
r
efers to fo
llo
w a d
i
rectio
n rich in
ph
erom
o
n
e
rath
er than
a
po
or
on
e. Du
e to th
is
po
sitive
feedbac
k
, t
h
e
algorithm
can’t broa
der
search,
so the al
gorithm
is easy ear
ly convergence.
Latest re
search
shows
that a
u
tom
a
tic diffl
ue
nce is t
h
e c
h
aracteristic of
re
al
an
ts [7
].
If t
h
e
p
a
th
h
a
v
e
lots o
f
an
ts
wh
ich
m
ean
s
a h
e
av
y traffic, th
e later an
t
will ch
o
o
se an
o
t
h
e
r p
a
t
h
to reach
th
e d
e
stin
atio
n th
ey
wan
t
In t
h
i
s
pa
per,
a new m
e
t
hod
fo
r r
o
b
o
t
pat
h
pl
an
ni
n
g
i
s
p
r
op
ose
d
ba
sed
on a
u
t
o
m
a
t
i
c
di
ffl
uent
a
n
t
alg
o
rith
m
.
First th
e grid m
e
th
o
d
is
b
u
ilt to
describ
e
t
h
e
work
i
n
g sp
ace of
th
e m
o
b
ile robo
t, th
e go
al
nod
e i
s
m
a
pped t
o
t
h
e no
de nea
r
by
t
h
e bo
un
da
ry
i
n
t
h
e ey
es hot
of
t
h
e ro
bot
, a
n
d
t
h
e best
l
o
cal
pat
h
i
s
pl
an
ne
d
wi
t
h
au
to
m
a
tic d
i
fflu
e
n
t
an
t algo
ri
th
m
,
wh
en
t
h
e robo
t go
es ahead
fo
r a step. Th
e algorith
mwill iterate when
th
e
robo
t arriv
e
s at
th
e
g
o
a
l
no
de.
Accord
ing
to th
e ex
p
e
rim
e
n
t
s, th
e m
e
th
od
is
effectiv
e.
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
1
2
– 11
7
11
3
2.
DESC
RIPTI
O
N OF
THE
ENVI
RO
N
M
ENT
Thi
s
pa
pe
r us
es Gri
d
m
e
t
hod m
odel
i
ng.
F
o
r c
o
n
v
e
n
i
e
nc
e, we
nam
e
t
h
e ro
bot
Rob
. Let
δ
be t
h
e
len
g
t
h th
at th
e
Rob
can m
ove
freely at one time.At any time,
Rob
ca
n
probe the
environm
en
tal in
formatio
n
i
n
a circle,
wh
ich rad
i
u
s
is
r
an
d cen
ter is Rob
’
s curren
t
p
o
s
itio
n. Th
is area i
s
n
a
m
e
d
RVie
w
.The vel
o
ci
t
y
of
Ro
b
is
R
V
, and t
h
e t
i
m
e
spent
on
pr
o
b
i
n
g t
h
e e
nvi
r
o
nm
ent
and pl
a
nni
ng t
h
e pat
h
can be i
g
n
o
re
d
.
Let
AS
be a
fi
ni
t
e
2-
D fi
el
d
,
i
n
whi
c
h a fi
ni
t
e
num
ber o
f
st
at
i
c
obst
acl
es
n
Sb
Sb
Sb
，
，
，
2
1
.
0
is th
e righ
t-ang
l
ed
co
ord
i
n
a
t
e
syste
m
in
AS
, its o
r
ig
in
is th
e left an
d
upp
er co
rn
er
o
f
AS
an
d
its lan
d
scape o
r
ien
t
atio
n
is X-ax
es, its portrait
is Y-ax
es. Th
e
m
a
x
i
m
a
l v
a
lu
es o
f
x
and
y
are
ma
x
x
and
ma
x
y
, res
p
ectively. Then
x
and
y
c
a
n b
e
di
vi
de
d
usi
n
g
δ
as
an
unit, a
s
a
res
u
lt, all gri
d
s ca
n be
form
ed
one b
y
o
n
e
(f
igu
r
e 1)
. Th
e
nu
mb
er
s of
each
r
o
w
and
colum
n
are
a
x
R
x
N
/
ma
x
and
a
y
R
y
N
/
ma
x
, respectiv
ely.Th
e
m
o
b
ile ro
bo
t en
v
i
ron
m
en
t is
rep
r
ese
n
t
e
d
by
or
derl
y
n
u
m
b
ered
gri
d
s
（
C
={1,
2,
3,…
，
,
M
}
）
, each
of whic
h re
prese
n
ts a location
in the
envi
ro
nm
ent
.
g
(
x
,
y
) al
s
o
re
prese
n
t
s
a
l
o
c
a
t
i
on i
n
t
h
e
e
n
vi
r
onm
ent
,
x
is
t
h
e ro
w n
u
mb
e
r
,
y
is t
h
e colu
m
n
s
num
ber.
In t
h
e
gri
d
b
a
sed r
o
bot
e
n
vi
r
onm
ent
,
t
h
e num
ber
i
and
g
(
x
,
y
)
de
n
o
t
e
gri
d
an
d
envi
ro
nm
ent
co
ord
i
n
a
te, resp
ectiv
ely,thu
s
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.
R
O
LLING PA
TH PLAN
NIN
G
BA
SED
ON
AU
TOMA
TIC D
I
FFLU
E
N
T
AN
T ALGOR
ITHM
3.
1.
T
h
oug
h
t
of
Al
gori
t
hm and
De
fi
ni
ti
o
n
Latest research
shows th
at au
to
m
a
tic d
i
ffluen
t
is th
e be
ha
vior cha
r
acteri
s
tic of real ant
s
[7].
Ants
h
a
v
e
th
e ab
ility to
au
to
m
a
tic
d
i
stribu
tio
n, just lik
e h
i
g
h
-
speed
ing
cars. M
a
n
y
an
ts in
th
e sa
m
e
p
a
th
will cau
se
traffic jam
.
Therefore
,
if there are
m
a
n
y
an
t
s
in
th
e sa
m
e
p
a
th
, th
ose who
co
m
e
later will
ch
o
s
e ano
t
h
e
r
p
a
th
.
Th
e algo
rith
m
d
e
sign
ed
in
th
i
s
p
a
per is b
a
sed
on
an
ts’ c
h
aracteristic.
W
h
e
n
a node alrea
d
y ha
d bee
n
c
hos
en
b
y
m
a
n
y
an
ts, th
o
s
e an
ts who
cam
e
later
will d
i
v
e
rt to
o
t
h
e
r no
d
e
s auto
m
a
ticall
y
. An
d
it can
en
larg
e th
e
search ra
nge, i
n
crease
the
di
versity of the s
o
lution, in
ord
e
r to
search ev
erywh
e
re to g
e
t t
h
e
b
e
st so
lu
tion
.
Fi
gu
re
2.
The
s
u
b
-
goal
sc
hem
a
t
i
c
di
agram
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA I
S
SN
:
208
9-4
8
5
6
Ro
llin
g Pa
t
h
Pla
n
o
f
Mob
ile Rob
o
t
Ba
sed
on
a
u
t
o
m
a
tic d
i
f
flu
en
t an
t
a
l
gorith
m (Zh
o
u
fen
g
)
11
4
Ro
b’s curren
t
p
o
s
ition
is
()
Pt
R
. The g
o
al
no
de i
s
m
a
pped t
o
t
h
e no
de near
by
t
h
e bo
u
nda
ry
i
n
t
h
e
ey
eshot
of
t
h
e
ro
b
o
t
,
as
a loca
l sub-targets
g
s
ub
,
Rob
d
e
tect th
e
en
v
i
ron
m
en
tal in
fo
rm
atio
n
of
RView
, and t
h
e
best
l
o
cal
pat
h
form
()
Pt
R
to
g
s
ub
i
s
pl
an
ned
by
aut
o
m
a
t
i
c
di
ffl
uent
ant
al
gori
t
h
m
,
t
h
en t
h
e ro
bot
g
o
e
s
ahead for a step along this path.
Rob
goes
forward eve
r
y time and then
carries on
the above loc
a
l path
pl
an
ni
n
g
pr
oce
ss. T
h
ere
f
o
r
e, t
h
e
pat
h
i
s
real
-
t
im
e dy
nam
i
cal
l
y
m
odi
fi
ed.
Whe
n
g
s
ub
and
g
en
d
are (in) the
sam
e
p
o
s
itio
n,
Rob
goes forward
directly for
g
en
d
. In
th
is algo
ri
th
m
,
Rob
al
wa
y
s
goes f
o
rwa
r
d t
o
t
h
e gl
obal
object, furt
herm
ore the local
path is
optim
a
l. The algor
ithm iterates whe
n
Rob
ar
ri
ves a
t
t
h
e goal
n
ode
. Fi
gu
r
e
2 i
s
a
schem
a
t
i
c di
ag
ram
t
h
at
sho
w
s
h
o
w
sub
g
i
s
m
a
pped
t
o
t
h
e
sub
-
goal
.
In
o
r
de
r t
o
des
c
ri
be c
o
nve
ni
e
n
t
l
y
,
W
e
m
a
ke
t
h
e f
o
l
l
o
wi
n
g
d
e
fi
ni
t
i
on:
Defi
ni
t
i
on 1
.
c
o
unt
e
r(g
,g
)
ij
mean
s th
e n
u
m
b
e
r o
f
an
ts wh
ich
visited
th
e lin
e b
e
tween
g
i
and
g
j
。
1
c
ount
e
r(g
,g
)
ij
CMAX
.
W
h
en
th
e
cou
n
t
e
r(
g
,
g
)
ij
is th
e larg
er
，
th
e
p
r
ob
ab
ility o
f
wh
ich
selected is sm
al
ler.
Defi
ni
t
i
on 2.
Move
max
i
s
t
h
e
ma
x
i
mu
m o
f
a
n
y
a
n
t’
s
s
t
ep
.
I
n
o
r
d
e
r
t
o
p
r
ev
en
ts th
e an
t se
archi
n
g lim
i
tle
ssly.
Defi
ni
t
i
on 3. I
f
,
g
Ag
S
S
,
g
is called
feasib
le nod
e.
All feasib
le
nod
es m
a
k
e
up
t
h
e feasib
le regio
n
,
Mar
k
ed
as
FS.
If
,
g
Ag
S
S
,
g
is called th
e
forb
i
d
d
e
n
no
d
e
.
All fo
rb
idd
e
n nod
es m
a
k
e
up
th
e fo
rb
idden
regi
on
,
Mark
ed
as
NFS.
Defi
ni
t
i
on 4
.
T
h
e di
st
ance
bet
w
een a
n
y
t
w
o
gri
d
cel
l
s
g
i
and
g
h
or
cor
r
e
spo
n
d
i
ng
po
in
ts
P
i
and
P
h
is th
e len
g
t
h
of
t
h
e l
i
n
e
bet
w
een
t
h
e ce
nt
e
r
poi
nt
s o
f
t
h
e t
w
o
g
r
i
d
s
an
d
(
w
hi
c
h
)
i
s
de
n
o
t
ed by
d
(
g
i
,
g
h
)o
r
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 5.
I
f
g
is
a
g
r
id cell, th
e set
((
,
)
)
{
|
,
(
,
)
2
}
,
BR
g
x
y
g
g
A
d
g
g
i
C
ii
i
i
i
is called
th
e
n
e
ighbo
rho
o
d
o
f
g
i
. T
h
e
b
r
oa
d l
i
nes m
a
rked
t
h
e
nei
g
h
b
o
r
ho
o
d
of
g
(4
,4
) i
n
fi
g
u
re
1
.
Defi
ni
t
i
on 6.
L
e
t
k
be
an ant
，
tabu
k
i
s
t
h
e
set
of
g
r
i
d
whi
c
h ha
ve b
een passe
d by
k
fr
om
tim
e
t
0
to
t
i
.
tabu
k
is
cal
l
e
d t
h
e
fo
r
b
i
dde
n t
a
bl
e.
tabu
k
={
P
(
t
0
),
P
(
t
1
),
…
，
P
(
t
i
)}
.
The
pat
h
t
a
ke
n
by
k
fr
om
time
0
t
th
ro
ugh
ti
m
e
i
t
is
p
ath
k
=
{,
,
,
}
12
PP
P
i
.Th
e
sequ
en
ce of
co
nn
ectio
n
lines
betwee
n adjace
nt grids in
k
path
is called
the p
a
th
fro
m
0
P
to
P
i
. Th
e leng
th,
L
, o
f
t
h
e
pat
h
i
s
gi
ve
n by
fo
rm
ula (3):
Defi
n
itio
n
7. Th
e h
e
u
r
istic fun
c
tio
n
wh
ich
gu
id
es th
e an
t to
cho
o
se th
e nex
t
n
o
d
e
d
u
ring
its search
is called
(g
)
, that
g
is an arbitrary
gri
d
cell
.
In t
h
i
s
pape
r
(g
)
= 1/
d
(
g
,
g
sub
)
f
o
r a
n
t’s fam
ily
1 and
(g
)
= 1/
d
(
g,
g
R
)
fo
r
a
n
t’s fam
i
ly
2.
Defi
ni
t
i
on 8.
S
u
p
p
o
se
k
1
an
t
1
and
k
2
an
t
2
.
1
k
starts from
g
be
g
i
n
and
2
k
fr
om
g
end
. At tim
e
t
n
t
h
e po
si
t
i
on
of
k
1
is
1
P
k
, th
e po
sitio
n of
k
2
is
2
P
k
If
|(
,
)
|
0
12
dP
P
kk
,we say t
h
at
k
1
and
k
2
have
en
cou
n
t
e
re
d eac
h
ot
he
r.
Defi
ni
t
i
on 9.
((
)
)
{
|
,
(
,
(
)
)
}
R
Vi
e
w
P
t
P
P
A
d
P
P
t
r
Ri
Ri
i
s
cal
l
e
d t
h
e
vi
s
u
al
dom
ai
n o
f
Ro
b
at po
sition
()
Pt
R
i
.
3.
2.
St
eps
of
t
h
e Al
gori
t
hm
m
an
ts fro
m
o
n
e
fam
ily tak
e
Pt
R
（）
a
s
n
e
s
t
a
n
d
g
s
ub
as food s
o
urce, a
nd
chose t
h
e sa
me num
ber
of
an
ts form
an
o
t
h
e
r fam
ily tak
e
s
g
s
ub
as the
nest
and
Pt
R
（）
as the
food s
o
urce.
The
s
e ants
of two fam
i
lies
coo
p
e
r
at
e t
o
se
arch
fo
r a pat
h
i
n
an o
p
posi
t
e
di
rect
i
o
n
.
Eac
h
ant
searc
h
es
fo
r a pat
h
by
s
e
que
nt
i
a
l
l
y
choosi
n
g
th
e n
ear
est nod
e to
th
e tar
g
et p
o
i
n
t
in
its c
u
rr
en
t n
e
i
g
hbor
ing
d
o
m
ain
.
A
r
a
ndo
m
sear
ch
str
a
teg
y
is u
s
ed
to
increase
divers
ity of the
search.
Sin
ce t
h
e a
l
gorithm
s
for t
h
e two a
n
t
fa
mi
lies are ide
n
tical except for thei
r
d
i
fferen
t
startin
g
an
d
end
i
ng
p
o
i
n
t
s, th
e search
i
n
g
algor
ithm o
f
an
t fam
i
l
y
1
will b
e
tak
e
n
as th
e ex
am
p
l
e in
th
e fo
llowing
an
d all th
e sub
s
crip
ts
d
e
no
ting th
is fam
ily wil
l
b
e
o
m
i
tted
to
si
m
p
lify th
e notatio
n
.
The pr
oce
d
u
r
e i
s
desc
ri
be
d
as fol
l
o
ws.
(
,
)
,
,
,
,
(
3
)
1
e
Ld
d
d
g
g
g
g
O
s
i
h
C
ll
i
h
i
h
l
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
1
2
– 11
7
11
5
Step
1
:
Set the startin
g
po
i
n
t
g
be
g
i
n
and t
h
e
t
e
rm
i
n
al
poi
nt
g
end
, th
en
in
itializes relev
a
n
t
param
e
ters.
St
ep2:
Acco
rdi
ng t
o
t
h
e m
e
t
hod s
h
ow
n i
n
F
i
gu
re 2, t
h
e
g
en
d
poi
nt
i
s
m
a
pped
t
o
t
h
e cl
osest
no
de
in
sid
e
Rob
’
s
RV
ie
w
; th
is will b
e
regard
ed as th
e local n
a
vig
a
tio
n
sub
-
goal
g
s
ub
. T
h
e selection of
g
s
ub
is
go
ve
rne
d
by
t
h
e f
o
l
l
o
wi
ng:
If
()
,
dP
t
g
r
Ri
e
n
d
（）
,then
gg
s
ub
e
n
d
;o
th
erwi
se
()
,
dP
t
g
r
Ri
s
u
b
（）
and
min
,
dg
g
s
ub
end
（）
(4
)
whe
r
e
r
is th
e rad
i
u
s
of
Rob
's
RView
; an
d
δ
is
Rob
'
s
st
ep l
e
ngt
h.
St
ep3:
Ro
b
detects in
form
at
io
n
abo
u
t
ob
stacles with
its se
n
s
or (
感器
传
) with
in
its cu
rrent
RView
. If
obstacles a
r
e
detected, their c
o
ordinates
（坐
标
）
（
推算）
will b
e
com
p
u
t
ed
.
St
ep4:
Assi
gn
m
an
ts to
t
h
e startin
g po
in
t
）
（
t
P
R
,
th
en
ad
d
）
（
t
P
R
to
th
e fo
rb
idd
e
n
tab
l
e
tabu
k
(
k
=1,2…
m
).In
i
tializes
count
e
r
(
g
i
,g
j
)
=1,t
he f
o
o
d
-
searc
h
i
n
g i
t
e
rat
i
on
co
u
n
t
e
r
n=
0,
MAX
( t
h
e m
a
xim
u
m
num
ber
o
f
iteratio
n) and
CMAX
(t
he u
ppe
r bo
un
d o
f
co
un
te
r(g
i
,g
j
)
)
.
Step 5:
Denote
（
表示）
t
h
e cu
rren
t
p
o
s
ition
of an
t
k
is
i
g
(
i
g
∈
FS
).T
h
e ant
k
sel
ect the ne
xt node
j
g
(
j
g
∈
)
(
i
i
g
Wk
,
k
j
tabu
g
) by
E
q
. (5
) or Eq
.
(
6
).
whe
r
e
j
(
j
∈
C
)i
s g
r
i
d
se
ri
al
num
bers
of
j
g
.
q
i
s
a ra
n
dom
num
ber
uni
fo
rm
ly
di
st
ri
but
e
d
i
n
[0
,1]
.
q
0
is a
param
e
t
e
r
（参
数
）
(0<
q
0
≤
1)
.
S
is
a rand
o
m
v
a
riab
le selected
acco
r
d
i
ng
t
o
th
e pro
b
a
b
ility d
i
stribu
tio
n giv
e
n
i
n
Eq
. (6
).
whe
r
e
)
(
j
j
g
i
s
co
m
put
ed
by
defi
ni
t
i
on
7.
(
α
≥
0)
expreses relative im
portance
of
1/
counter
(
g
i
,
g
j
).
β
(
β
≥
0)
ex
pr
esses
re
l
a
t
i
v
e im
port
a
nce
of
)
(
j
j
g
.
)
(
n
p
k
ij
is tran
sform
p
r
ob
ab
ility o
f
t
h
e an
t
k fro
m
i
to
j
at the
n
iteratio
n
.
|Z| i
s
th
e set
o
f
grid
th
at
rem
a
i
n
to
b
e
v
i
sited
b
y
an
t
k
positio
n
e
d
on
j
g
.
q
and
q
0
prev
ent
th
e
st
agnat
i
o
n.
I
f
q
>
q
0
,th
e
an
t com
p
u
t
e th
e prob
ab
ility o
f
|Z|
an
d select th
e
n
e
x
t
no
de
j
g
b
y
rou
l
ette selectio
n.
Wh
en
th
e
n
u
m
b
er o
f
ele
m
e
n
ts is
m
o
re than
Move
max
in
tabu
k
, the ant
k
is d
ead. Retu
rn to
Step
4
,
t
h
en
in
itializes a n
e
w an
t.
Or return
to Step 6.
Step 6:
Wh
ile
b
u
ild
i
n
g a so
lutio
n
at
i
g
, ant
s
c
h
ange
t
h
ei
r
p
h
e
r
om
one l
e
vel
b
y
appl
y
i
n
g
t
h
e
l
o
cal
up
dat
i
n
g rul
e
o
f
E
q
. (
7
).
(,
)
1
(,
)
(,
)
(
7
)
c
ounter
g
g
if
counter
g
g
C
M
AX
ij
ij
c
ounter
g
g
ij
CM
AX
e
l
se
Step 7:
After a
n
t
k
has c
h
o
s
e
n
t
h
e
no
de
j
, a
nd t
h
en c
h
ec
ks
whet
her t
w
o a
n
t
s
fr
om
opp
os
i
t
e
fam
i
li
es have m
e
t
according to the conditions in definition
8. If ant has enc
o
unte
r
ed a
not
he
r an
t, then
return to
Step
8.Or let
j
take
the place of
i
,
th
en
retu
rn
to Step 5
and cho
o
s
e th
e
n
e
x
t
nod
e.
Un
til th
ere is an an
t
wh
ich
h
a
s en
co
un
tered
anot
her
ant
,
o
r
al
l
no
des
ha
ve
been
ch
ose
n
.
a
(can
i
t
be st
o
p
p
e
d.
)
Step
8: If (one
)ant has
e
n
countere
d
anothe
r ant, for each
new e
n
c
o
unter
connect all the cells passed
by the
encountering a
n
ts and c
o
m
p
ute the lengt
h
L
of
t
h
e
c
o
n
n
ect
ed pat
h
by
Eq
. (3
).
c
h
a
nge
t
h
e
i
r
p
h
er
om
one on
t
h
e
feasib
le
p
a
th by Eq
.(8).
whe
r
e
1
R
ou
is the pherom
one
decay
pa
ram
e
ter.
a
r
g
m
a
x
{
[
1
/
(
,
)
]
(
)
}
0
(
5
)
count
er
g
g
g
i
f
q
q
ij
j
j
j
Se
l
s
e
[1
/
(
,
)
]
(
)
(
)
(
6
)
[1
/
(
,
)
]
(
)
||
c
ount
e
r
g
g
g
ij
j
j
k
pn
j
t
a
b
u
ij
k
c
oun
t
e
r
g
g
g
ij
j
j
qZ
(,
)
(
,
)
1
(
8
)
1
c
ounter
g
g
Rou
c
ount
e
r
g
g
ij
ij
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
RA I
S
SN
:
208
9-4
8
5
6
Ro
llin
g Pa
t
h
Pla
n
o
f
Mob
ile Rob
o
t
Ba
sed
on
a
u
t
o
m
a
tic d
i
f
flu
en
t an
t
a
l
gorith
m (Zh
o
u
fen
g
)
11
6
Co
m
p
u
t
e
all
th
e feasib
le p
a
t
h
b
y
Eq
. (3).
L
kmin
is saved
as the s
h
ortest
distance
. Com
p
ared
L
kmin
with
th
e
historical optimal distance
L
d
. If
L
kmin
<
d
L
, replace
L
d
with
L
kmin
and rec
o
rd the
new s
e
t of nodes as
the
ten
t
ativ
e op
timal p
a
th
.
Step 9:
After al
l an
ts
h
a
v
e
com
p
le
ted
th
eir t
o
urs, th
e
ph
erom
o
n
e
o
f
th
e
opti
m
a
l
p
a
th
is
up
d
a
ted
b
y
Eq
.
(9
).
Whe
r
e
2
Rou
is the
pherom
one
global decay parameter.
Step10: Let
n
=
n
+1
.
I
f
n<
M
AX,
em
pt
y
tabu
k
a
n
d
r
e
tu
rn
to
St
e
p
4
.
I
f
n
=
MAX
, t
h
e
planning i
s
fi
ni
she
d
.
T
h
e l
a
st
reco
r
d
ed
pa
t
h
i
s
t
h
e
pl
a
nne
d
opt
i
m
al
pat
h
.
Step 11: If
end
g
is detected
or
sub
g
is th
e sam
e
as
end
g
,
Rob
will walk
t
o
end
g
al
on
g
t
h
e pl
an
ned pat
h
.
Othe
rwise,
Rob
will retu
rn
t
o
step
2
after m
o
v
i
n
g
on
e
step
alo
n
g
th
e p
l
ann
e
d lo
cal
o
p
t
i
m
al n
a
v
i
g
a
tion p
a
th.
4.
E
X
PERI
MEN
T
RES
U
LTS
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
con
d
u
ct
ed. T
h
i
s
sect
i
on pres
ent
s
t
h
e sim
u
l
a
t
i
on res
u
l
t
s
of t
h
e pr
o
pose
d
al
gori
t
h
m
.
The pro
p
o
se
d sol
u
t
i
o
n
al
go
ri
t
h
m
i
s
im
pl
em
ent
e
d wi
t
h
M
S
Vi
sual
C
++ 6.0 o
n
a Int
e
l
Pent
i
u
m
4
3.0G
Hz com
put
er wi
t
h
25
6M
B
RA
M.
In
th
e
s
e f
i
gu
r
e
s
,
sh
ad
es
of
b
l
a
c
k
ar
e
obstacles.
We
define t
h
at 10*10
gri
d
as t
h
e
Rv
ie
w
.
Here
, w
e
gene
rat
e
a
back
gr
o
u
n
d
e
n
vi
r
onm
ent
ra
n
dom
(Fi
g
ure
3
Fi
g
u
re
4
)
. T
h
ese e
xpe
ri
m
e
nt
s sh
ow
une
xpectedly excellent pe
rformance w
ith
con
s
u
m
ed
ti
m
e
s
m
aller th
an
0
.
01 second, the
minim
u
m
precision
of
t
h
e com
put
er
c
l
ock
o
n
ou
r sy
s
t
em
.
Fi
gu
re
3.
O
p
t
i
m
al
pat
h
i
s
fr
o
m
our al
g
o
ri
t
h
m
i
n
si
m
p
le en
v
i
ronmen
t
Fi
gu
re
4.
O
p
t
i
m
al
pat
h
i
s
fr
o
m
our al
g
o
ri
t
h
m
in
co
m
p
lex
en
viron
m
en
t
5.
SU
MM
A
R
Y
AN
D CO
N
C
LUSIO
N
S
The di
f
f
i
c
ul
t
y
of
navi
gat
i
on
or
pat
h
pl
a
nni
ng i
n
c
o
m
p
l
e
x envi
r
o
nm
ent
s
wi
t
h
m
obi
l
e
o
b
st
acl
es an
d
un
k
n
o
w
n st
at
i
c
obst
acl
es i
s
ho
w t
o
g
u
ara
n
t
e
e
t
h
e gl
o
b
al
opt
i
m
al
or near-
o
p
t
im
al
pat
h
and
ho
w t
o
a
voi
d t
h
e so
called
d
ead
l
o
ck
and
oscillati
o
n
, etc. In
th
is
p
a
p
e
r, th
e
fin
a
l
targ
et po
in
t is map
p
e
d
t
o
a sub
-
go
al p
o
i
n
t
ou
tsid
e
of t
h
e
ro
b
o
t
’
s
vi
sual
dom
ai
n.
Thi
s
s
u
b-
g
o
al
i
s
use
d
as
t
h
e
l
o
cal
na
vi
gat
i
on
su
b
-
g
o
al
. T
h
i
s
p
r
ocess
wi
l
l
be
repeate
d
after
each of Rob’s
steps.
There
f
ore eve
r
y local
path
only c
ons
titutes a kind
of na
vigation trend. If
ev
ery lo
cal
p
a
th
is op
tim
a
l
, t
h
e g
l
o
b
a
l
p
a
th
walk
ed
b
y
Rob
is alm
o
st the global op
t
i
m
a
l
.
The di
rect
i
on
fr
om
Rob
to
end
g
sho
u
l
d
al
way
s
be t
h
e
gui
de f
o
r
Ro
b
'
s
di
rect
i
o
n o
f
m
o
ti
on. T
h
i
s
p
r
oces
s i
s
dy
na
m
i
cal
ly
ong
oi
n
g
with
th
e m
o
tio
n
o
f
t
h
e
robo
t. Th
eref
o
r
e, th
e robo
t can
walk
along
a
g
l
obal o
p
tim
al o
r
al
m
o
st o
p
tim
al
p
a
th
u
n
d
e
r th
e g
u
i
d
a
n
ce
o
f
th
e lo
cal o
p
tim
al
c
o
llisio
n
-
free
path
with
in
each
v
i
su
al do
m
a
in
o
f
th
e ro
bot an
d
ev
en
t
u
ally reach
th
e targ
et po
i
n
t safely
with
ou
t co
llision
.
REFERE
NC
ES
[1]
Zhang CG, Xi
YG. Path plann
i
ng of robot based
on rolling win
dow in global
l
y
unknown enviro
nm
ent.
Science in
China E
. 2001
;
31(1): 51-58
.
(,
)
(
,
)
1
(
9
)
2
c
ounter
g
g
Rou
c
ount
e
r
g
g
ij
ij
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
1
2
– 11
7
11
7
[2]
Dave Ferguson
and Anthon
y
Stentz.
Any
time RR
T
s
. Proceedings
of the 2006 I
E
E
E
/RSJ Interna
tio
nal Confer
enc
e
on
Intelligen
t Robots and S
y
s
t
ems. 2
006: 5369-5375
[3]
Xuena Qiu, Jiatao Song and X
u
ejun Zh
ang.
A Complete Coverage Path
Plan
n
ing Method
fo
r Mobile
Robot in
Uncertain Env
i
ronments
.
Proceedings of the 6th World Congres
s on
Intelligent Control a
nd Automatio
n.
2006:
8892-8896
[4]
Yanrong Hu an
d Simon
X
Yang.
A Knowledge Based Genetic
A1gorithm
for Path Planning of a Mobile Robot
.
Proceedings of the 2004 IEEE i
n
terna
tiona
l Conferenc
e
on Robotics & Autom
a
ti
on New Orleans, LA. 2004:4350
-
4355.
[5]
Zhu Qing-Bao
.
Ant Algorithm
for Navigation
of
Multi-Robot
Movem
e
nt in U
nknown Enviro
nm
ent.
Journal of
Software
. 2006;
17(9): 1890-189
8 (in Ch
inese)
.
[6]
Ying-Tung Hsiao, Cheng-Long
Chuang, Che
ng-
Chih Chien. Ant Colon
y
Optimizat
ion for Best
Path Planning.
I
n
t
S
y
mp on Communications and
I
n
formati
on Tech
nologies 2004
. J
a
pan. 2004: 109-
113.
[7]
Dussutour A, Fo
urcassie V, Helb
ing
D, et
l. Opt
i
m
al traffi
c organizati
on
in ants under
crowded conditions.
Natur
e
.
428(6978):70-73
.
Evaluation Warning : The document was created with Spire.PDF for Python.