Inter
national
J
our
nal
of
Electrical
and
Computer
Engineering
(IJECE)
V
ol.
6,
No.
6,
December
2016,
pp.
3262
–
3275
ISSN:
2088-8708
3262
A
No
v
el
of
Repulsi
v
e
Function
on
Artificial
P
otential
Field
f
or
Robot
P
ath
Planning
H.
H.
T
riharminto,
O.
W
ah
yunggor
o,
T
.
B.
Adji,
A.
I.
Cah
yadi,
and
I.
Ardiyanto
Electrical
Engineering
and
Information
T
echnology
Department,
Uni
v
ersitas
Gadjah
Mada,
Y
ogyakarta,
Indonesia
Article
Inf
o
Article
history:
Recei
v
ed
Jul
27,
2016
Re
vised
Aug
30,
2016
Accepted
Sep
15,
2016
K
eyw
ord:
APF
Local
Minima
GNR
ON
Potential
Function
ABSTRA
CT
In
this
paper
,
the
issue
of
local
minima
associated
with
GNR
ON
(Goal
Nonreachable
with
Obstacles
Nearby)
has
been
solv
ed
on
the
Artificial
P
otential
Field
(APF)
for
robot
path
planning.
A
no
v
el
of
repulsi
v
e
potential
function
is
proposed
to
solv
e
the
problem.
The
considerat
ion
of
surrounding
repulsi
v
e
forces
gi
v
es
a
trigger
to
escape
from
the
local
mi-
nima.
Addition
of
signum
function
on
the
repulsi
v
e
force
which
considers
relati
v
e
distance
between
the
robot
and
the
goal
ensures
that
the
goal
position
is
the
global
optima
of
the
total
potential.
Simulation
conducted
to
pro
v
e
that
the
proposed
algorithm
can
solv
e
GNR
ON
and
local
minima
problem
on
APF
.
Scenario
of
each
simulation
set
in
dif
ferent
type
of
obs-
tacle
and
goal
condition.
The
results
sho
w
that
the
proposed
method
is
able
to
handle
local
minima
and
GNR
ON
probl
em.
Copyright
c
2016
Institute
of
Advanced
Engineering
and
Science
.
All
rights
r
eserved.
Corresponding
A
uthor:
Hendri
Hima
w
an
T
riharminto
Electrical
Engineering
and
Information
T
echnology
Department,
Uni
v
ersitas
Gadjah
Mada
Jl.
Grafika
No.
2
Kampus
UGM,
Y
ogyakarta,
Indonesia
(+6280274)547506,
510983
kanghima
w
an@gmail.com
1.
INTR
ODUCTION
A
path
planner
on
robot
applications
plays
an
important
role
for
fulfilling
the
objecti
v
e
of
t
he
robot,
such
as
find
out
the
feasible
path
starting
from
the
initial
and
goal
position
and
a
v
oiding
collision
with
obsta-
cles.
The
process
of
path
planning
algorithm
can
be
described
as
follo
ws:
first,
start
with
data
en
vironment
acquisition,
then
set
the
mission
planning,
after
that
de
v
elop
the
path
planni
ng,
and
finally
,
control
the
robot
based
on
the
generated
path
planning
[1].
Hence,
the
path
planning
aims
to
guide
the
controller
to
reach
the
mission
planning.
There
are
se
v
eral
parameters
which
ha
v
e
to
be
considered
in
the
path
planning
field,
e.g.
distance,
safety
,
and
applicability
to
the
real
robot
and
en
vironments
[2].
The
distance
metric
as
the
measurement
means
that
the
path
which
gi
v
es
the
shortest
distance
to
w
ard
a
goal
will
be
considered
as
the
optimal
path.
The
safety
parameter
means
the
robot
must
ensure
the
trajectory
to
w
ard
to
the
goal
is
not
colliding
with
the
other
objects.
The
applicability
relates
to
the
application
in
the
rea
l-time
system
which
means
the
algorithm
does
not
generate
a
path
that
does
not
fulfill
kinematic
constraint
.
The
e
xamples
of
kinematic
constraint
are
minimum
turning
radius,
maximum
linear
and
angular
v
elocities
[3].
Dynamic
constraints
ha
v
e
tw
o
paradigms
i.e.
the
dynamic
en
vironment
which
means
the
en
vironment
that
changes
dynamically
that
could
be
mo
ving
obstacle
or
alteration
of
the
en
vironment
while
the
robot
w
as
running
[4].
On
the
other
hands,
dynamic
constraint
means
the
force
is
used
as
consideration
including
mass
and
dimension.
In
this
paper
,
for
simplicity
,
the
robot
is
ass
umed
to
be
a
point
mass
and
mo
v
e
in
a
tw
o-
dimensional
(2-D)
w
orkspace.
The
forces
of
the
robot
that
depend
on
mass,
dimension,
inertia
are
ne
glected.
J
ournal
Homepage:
http://iaesjournal.com/online/inde
x.php/IJECE
,
DOI:
10.11591/ijece.v6i6.11980
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3263
1.1.
Related
W
orks
Some
approaches
e
xist
to
solv
e
path
planning
problem.
Heuristic
search
algorithm
such
as
Genet
ic
algorithm,
Ant
Colon
y
,
P
article
Sw
arm
Optimization
and
Artificial
Bee
Colon
y
were
used
in
term
of
planning
problem
[5]
[6]
[7]
[8]
[9].
The
weakness
of
heuristic
algorithm
is
in
online
path
condition
which
the
algorithms
are
computationally
e
xpensi
v
e
to
be
pre-planned
and
it
means
that
the
global
optimum
cannot
be
achie
v
ed
easily
[10].
Kinematic
constraints
require
feasible
a
nd
continuous
paths.
Planning
algorithm
based
on
curv
ature
path
considers
continuous
maneuv
ers,
i.e.
clothoids
arcs,
B-spline
curv
es,
and
Dubin’
s
path
[11]
[12]
[13].
The
B-spline
curv
e
has
a
limitation
on
the
number
of
control
points.
Generally
,
the
planning
algorithm
based
on
curv
e
merely
used
on
the
of
f-line
path.
One
of
the
e
xamples
of
the
curv
e
algorithm
for
the
dynamic
en
vironment
w
as
proposed
by
T
riharminto
et.
al.
[14].
One
of
the
well-kno
wn
path
planning
algorithm
is
Artificial
Potential
Field
(APF).
APF
is
a
planning
algorithm
that
is
designed
as
a
reacti
v
e
path
planning
for
obstacle
a
v
oidance.
Therefore,
the
APF
is
suitable
to
use
for
of
fline
and
online
path
generation.
The
basic
concept
of
APF
follo
ws
the
natural
characteristic
of
electrostatic
potential
which
in
the
case
robot
of
path
planning,
t
he
goal
position
becomes
the
lo
west
while
the
initial
position
is
the
representati
v
e
of
the
highest
potential
[15].
Consequently
,
the
potential
ener
gy
will
mo
v
e
from
the
highest
to
the
lo
west
follo
wing
t
he
nature
of
the
potenti
al
field.
F
or
a
v
oiding
collision
with
the
obsta-
cle,
the
obstacle
is
set
as
opposite
direction
force
that
refuses
the
robot
from
the
obstacles.
The
APF
method
is
particularly
attracti
v
e
because
its
ef
fecti
v
eness
as
real-time
obstacle
a
v
oidance
beside
its
mathematical
ele
g
ance
and
simplicity
[16].
Ho
we
v
er
,
the
APF
has
a
problem
based
on
mathematical
analysis
that
is
trap
situations
due
to
local
minima
[17]
[18].
Additionally
,
GNR
ON
problem
has
a
close
correlation
with
local
minima
problem
[19].
Some
researchers
tried
to
solv
e
local
minima
b
ut
the
algorithms
usually
do
not
consider
GNR
ON
problem
[20]
[21]
[22]
[23].
All
of
the
proposed
algorithms
used
APF
blended
with
an
e
v
olutionary
algorithm
to
na
vig
ate
in
an
autonomous
form
without
being
trapped
in
local
minima.
Lei
et
al.
solv
ed
local
minima
method
based
on
gra
vity
chain
that
connects
initial
and
goal
points
[24].
The
gra
vity
chain
has
a
role
in
guiding
the
robot.
The
other
solution
handles
the
local
minima
on
APF
is
by
using
harmonic
potential
[25]
[26].
This
local
minima
problem
is
solv
ed
by
forcing
local
potential
e
xtrema
to
lie
on
the
boundaries
of
ob
s
tacles
through
the
use
of
harmonic
potentials,
that
is,
of
potential
functions
V
satisfying
Laplace’
s
equation,
r
2
V
=
0
.
Disadv
antage
of
these
methods
is
that
Laplaces
equation
has
to
be
solv
ed
numerically
o
v
er
the
whole
state
space
and
it
raises
the
dif
ficulty
to
find
solutions
in
real-time
for
dynamic
en
vironments
[27].
Stream
function
is
used
to
determined
the
path
without
local
minima
and
GNR
ON
problem
[28]
[29].
Similar
to
harmonic
potential
field,
Laplace’
s
equation
has
to
be
solv
ed
in
the
stream
function
which
means
that
the
algorithm
computationally
e
xpensi
v
e.
The
solution
proposed
eliminating
the
local
minima
problem
by
defining
the
obstacles
potential
with
e
xponential
function
is
proposed
by
Sfeir
et
al.
[30].
Thus,
the
potential
is
inacti
v
e
e
xcept
when
the
robot
is
v
ery
close
to
the
goal.
The
essential
structure
of
the
potential
field
is
also
modified
which
the
total
force
is
null
when
the
robots
at
the
goal
point
in
term
of
GNR
ON
problem.
In
the
research,
the
issue
that
w
ould
be
interesting
is
the
choice
of
g
ain
parameters.
The
v
alue
of
parameters
is
selected
by
trial
and
error
.
The
addition
of
force
implemented
to
handle
local
minima
[31].
The
total
force
will
drag
the
robot
to
escape
from
the
local
minima.
Another
weakness
appears
when
the
distance
bet
ween
the
robot
and
the
goal
equals
to
the
distance
between
the
robot
and
the
obstacle.
Mer
ging
between
APF
and
e
v
olutionary
algorithm
is
one
of
the
solution
to
handle
the
problems
in
APF
including
determination
of
g
ain
parameter
[32].
Mei
et.
al.
used
h
ybrid
algorithm
APF
and
Bug
algorithm
[33].
The
b
ug
algorithm
w
as
used
to
escape
from
GNR
ON
and
local
minima
[34].
Hybrid
algorithm
switches
from
APF
to
the
e
v
olutionary
algorithm
and
the
trade-of
f
is
cost
of
computational
comple
xity
.
This
paper
proposed
an
adhoc
solution
to
sol
v
e
the
GNR
ON
and
local
minima
problems
in
APF
.
Therefore,
this
paper
has
a
contrib
ution
to
de
v
eloping
a
ne
w
potential
field
function
to
cope
both
local
minima
and
GNR
ON
problem.
The
or
g
anization
of
this
paper
is
as
follo
ws.
Section
2
e
xplains
the
APF
and
the
e
xisting
both
of
local
minima
and
GNR
ON
problem,
the
third
section
describes
the
ne
w
repulsi
v
e
function
and
ho
w
to
cope
both
of
the
problems.
And
finally
,
the
last
tw
o
sections
deli
v
er
simulation
result,
discussion,
and
the
rest
is
the
conclusion
of
the
research
with
possible
future
w
ork.
A
No
vel
of
Repulsive
Function
on
Artificial
P
otential
F
ield
for
Robot
P
ath
Planning
(H.
H.
T
riharminto)
Evaluation Warning : The document was created with Spire.PDF for Python.
3264
ISSN:
2088-8708
2.
LOCAL
MINIMA
AND
GNR
ON
PHENOMEN
A
As
in
the
e
xplanations,
the
APF
has
tw
o
dif
ferent
potential
functions
[35].
Let
the
position
of
the
robot
in
the
w
orkspace
is
denoted
by
q
=
[
x
y
]
T
,
the
most
commonly
at
tracti
v
e
force
of
APF
[36]
can
be
modeled
as
F
att
(
q
)
=
r
V
att
(
q
)
;
(1)
where
V
att
(
q
)
=
1
2
2
(
q
;
q
g
oal
)
:
(2)
V
ariable
is
an
attracti
v
e
g
ain
parameter
which
has
positi
v
e
v
alue
and
(
q
;
q
g
oal
)
=
jj
q
g
oal
q
jj
is
the
distance
between
robot
(
q
)
in
a
certain
position
and
the
goal
point
(
q
g
oal
)
.
From
the
mathematical
formulation,
i
t
can
be
seen
that
the
att
racti
v
e
force
con
v
er
ges
linearly
t
o
w
a
rd
zero
as
the
robot
approaches
the
goal.
That
characteristic
will
be
applicable
for
the
control
system
which
means
it
will
not
harm
the
actuator
of
the
robot.
The
other
potential
function
is
on
the
obstacle
which
the
formula
for
a
single
point
obstacle
is
F
r
ep
(
q
)
=
r
V
r
ep
(
q
)
;
(3)
where
V
r
ep
(
q
)
=
(
p
(
q
;q
obs
)
;
if
(
q
;
q
obs
)
o
0
;
if
(
q
;
q
obs
)
>
o
(4)
V
ariable
is
a
repulsi
v
e
g
ain
parameter
and
(
q
;
q
obs
)
is
the
distance
between
the
robot
and
the
obstacle
position
and
o
is
a
positi
v
e
constant
denoting
the
c-obstacle
of
robot
dimension.
From
the
repulsi
v
e
and
attracti
v
e
force,
the
total
of
the
force
field
can
be
determined
as
sum
of
attrac-
ti
v
e
and
repulsi
v
e
force
F
total
=
F
att
+
F
r
ep
:
(5)
The
total
force
represents
the
path
of
the
robot.
2.1.
Local
Minima
According
to
the
used
force,
the
essential
problem
of
the
APF
is
the
trap
in
local
minima.
The
problem
can
be
found
when
F
total
=
0
.
F
or
insta
n
c
e,
when
the
robot
initial
position,
q
=
[
a
0]
T
,
for
some
positi
v
e
number
a
collinear
with
the
goal,
q
g
oal
=
[
a
11]
T
as
sho
wn
in
Figure
2.
In
between
the
robot
and
the
obstacle,
there
are
tw
o
obstacles
in
q
obs
=
[8
10]
T
and
q
obs
=
[10
10]
T
respecti
v
ely
.
Thus,
F
att
in
the
x
axis
can
be
computed
equal
to
0
if
f8
>
0
g
.
Assuming
t
hat
=
1
,
it
is
clear
that
the
F
att
=
1
for
q
obs
=
[10
10]
T
and
F
att
=
1
for
q
obs
=
[10
10]
T
.
Consequently
,
in
the
x
axis,
F
r
ep
=
0
,
although
f8
>
0
g
.
Let
focus
on
the
y
axis,
if
the
robot
mo
v
es
to
w
ard
goal
point,
for
instance,
no
w
,
the
robot
is
at
q
=
[9
9]
T
which
means
the
v
alue
of
(
q
;
q
obs
)
=
1
.
Then,
the
v
alue
of
F
r
ep
=
1
for
both
of
the
obstacle
and
the
total
of
F
r
ep
=
2
in
a
positi
v
e
v
alue.
The
condition
of
local
minima
is
met
when
the
attracti
v
e
g
ain
parameter
has
been
set
of
1
which
means
F
att
=
2
in
a
ne
g
ati
v
e
v
alue
due
to
the
ne
g
ati
v
e
gradient
of
the
attracti
v
e
potential.
Therefore,
the
total
force
(
F
total
)
based
on
(5)
will
be
0
as
illustrated
in
Figure
1.
From
the
Figure
1,
it
sho
ws
that
the
robot
trap
at
q
=
[9
4]
which
F
total
0
and
cannot
reach
the
goal.
The
robot
assumes
that
the
local
minima
is
the
global
optimum.
It
has
to
be
noted
that,
in
that
case
with
an
assumption
that
the
dimension
of
the
robot
is
1
unit
square
in
the
w
orkspace,
i
t
is
ob
viously
that
the
alteration
v
alue
of
attract
i
v
e
and
repulsi
v
e
will
yield
tw
o
conditions,
i.e.
the
robot
will
hit
the
obstacle
or
the
robot
will
meet
local
minima.
T
o
escape
the
local
minima,
the
e
xternal
force
has
to
be
proposed
that
will
be
e
xplained
in
Section
3.
2.2.
GNR
ON
The
GNR
ON
problem
is
part
of
local
minima
problem.
This
problem
e
xists
when
the
goal
is
v
ery
close
to
the
obstacle.
F
or
e
xample,
consider
the
scenario
is
almost
similar
to
local
minima
as
in
the
aforementioned
b
ut
the
goal
point
is
set
of
q
g
oal
=
[9
8]
T
as
in
Figure
2.
If
the
robot
is
mo
ving
along
y
axis
and
reaching
the
goal,
then
F
att
=
0
for
the
x
and
y
ax
es.
On
the
repulsi
v
e
force,
similar
to
local
minima
in
the
x
axis,
F
r
ep
=
0
while
in
the
y
axis,
the
total
of
repulsi
v
e
force
of
both
obstacle
is
F
r
ep
=
2
.
Based
on
the
rules
(4)
and
(5),
at
IJECE
V
ol.
6,
No.
6,
December
2016:
3262
–
3275
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3265
Figure
1.
T
otal
potential
function
with
respect
to
y
axis
in
local
minima
problem
q
=
[9
8]
T
,
the
corresponding
repulsi
v
e
is
gi
v
en
by
(
q
;
q
obs
)
o
.
Then,
e
v
en
though
the
robot
should
reach
the
goal
b
ut
it
is
repulsed
a
w
ay
by
the
repulsi
v
e
force.
The
strate
gy
of
this
problem
is
set
the
repulsi
v
e
force
equal
to
0
when
the
robot
reaches
the
goal
as
in
Section
3.
Figure
2.
Location
of
the
robot,
goal
in
local
minima
and
GNR
ON
problem,
and
Obstacle
in
a
2-D
case
3.
NEW
REPULSIVE
PO
TENTIAL
FUNCTIONS
3.1.
Repulsi
v
e
Function
f
or
Local
Minima
Pr
oblem
The
local
minima
problem
arises
because
the
total
force
of
potential
field
equals
to
0.
The
probl
em
will
mak
e
the
robot
does
not
mo
v
e
or
in
static
condition
due
to
insuf
ficient
force.
As
mentioned
before,
the
e
xternal
force
is
a
solution
to
escape
from
the
local
minima.
It
has
to
be
considered
that
the
e
xternal
force
in
attracti
v
e
force
is
not
possible
due
to
the
global
optimum
is
met
when
F
att
=
0
.
Thus,
an
addition
of
force
in
the
attracti
v
e
will
mak
e
the
robot
does
not
meet
the
goal.
Alternati
v
ely
,
an
e
xternal
force
is
applied
to
the
repulsi
v
e
force.
The
moti
v
ation
is
to
construct
a
ne
w
repulsi
v
e
potential
function
as
V
r
ep
(
q
)
=
(
p
(
q
;q
obs
)
+
(
q
;
)
;
if
(
q
;
q
obs
)
o
0
;
if
(
q
;
q
obs
)
>
o
(6)
In
comparison
with
(4),
the
introduction
of
A
No
vel
of
Repulsive
Function
on
Artificial
P
otential
F
ield
for
Robot
P
ath
Planning
(H.
H.
T
riharminto)
Evaluation Warning : The document was created with Spire.PDF for Python.
3266
ISSN:
2088-8708
(
q
+
)
=
p
((
q
+
)
;
(
q
+
)
obs
)
;
(7)
ensures
that
the
e
xternal
force
tak
es
the
robot
escape
from
local
minima.
As
the
comparison,
the
total
force
from
the
original
potential
function
and
the
total
force
of
the
ne
w
potential
function
can
be
seen
in
Figure
3a
and
3b.
Figure
3a
sho
ws
the
total
force
in
the
original
scenario
without
an
e
xternal
force.
Figure
3b
sho
ws
the
total
potential
at
the
local
minima
is
not
equal
to
0
because
of
the
addition
of
(
q
+
)
.
It
is
s
een
by
the
total
force
is
bigger
than
the
original
one
and
mo
v
es
to
the
other
place.
(a)
(b)
Figure
3.
T
otal
potential
when
(a)
the
local
minima
e
xist
(b)
the
local
minima
mo
ving
from
the
original
place
The
repulsi
v
e
potential
function
F
r
ep
(
q
)
should
ha
v
e
the
property
that
the
sum
of
repulsi
v
e
force
and
e
xternal
force
pushes
the
robot
a
w
ay
from
the
local
minima.
Since
F
att
=
0
and
F
r
ep
=
0
,
the
parameter
has
to
be
set
properly
in
order
to
drag
the
robot
escape
from
local
minima.
Let
set
that
F
min
i.
e.,
the
minimum
force
to
mo
v
e
the
robot
when
the
robot
trapped
in
the
local
minima,
F
min
=
(
q
+
)
=
q
2
(
q
x
+
)
+
2
(
q
y
+
)
;
(8)
(
q
x
+
)
and
(
q
y
+
)
is
denoted
as
repulsi
v
e
force
in
the
position
(
x
+
)
and
(
y
+
)
respecti
v
ely
.
Defining
c
obs
is
the
safety
distance
between
the
robot
and
the
obstacle
that
consist
of
q
x
and
q
y
as
c
2
obs
=
q
2
x
+
q
2
y
:
(9)
F
or
simplicity
,
let
assumes
that
q
x
=
q
y
=
&
.
Then,
gradient
of
(
@
V
r
ep
(
q
+
)
=@
x;
@
V
r
ep
(
q
+
)
=@
y
)
are
2
(
q
x
+
)
=
&
((
&
+
)
2
+
&
2
)
3
=
2
;
(10)
2
(
q
y
+
)
=
&
(
&
2
+
(
&
+
)
2
)
3
=
2
:
(11)
Substituting
(10)
and
(11)
puts
into
(8)
leads
to
F
2
min
=
2
&
(2
&
2
+
2
&
+
2
)
3
=
2
:
(12)
Let
simplifies
right
hand
and
left
hand
side
by
po
wer
(2
=
3)
,
F
4
=
3
min
=
2
(2
=
3)
(
&
)
2
=
3
(2
&
2
+
2
&
+
2
)
:
(13)
Therefore,
can
be
computed
as
follo
ws.
2
&
2
F
4
=
3
min
2
(2
=
3)
(
&
)
2
=
3
+
2
&
F
4
=
3
min
2
(2
=
3)
(
&
)
2
=
3
+
F
4
=
3
min
2
(2
=
3)
(
&
)
2
=
3
2
=
0
;
(14)
IJECE
V
ol.
6,
No.
6,
December
2016:
3262
–
3275
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3267
=
2
&
c
p
4
&
2
c
2
8
&
2
c
2
2
c
;
(15)
where
c
=
F
4
=
3
min
2
(2
=
3)
(
&
)
2
=
3
and
&
=
c
obs
p
2
:
(16)
From
(16),
there
are
tw
o
solutions
of
which
mean
the
tendenc
y
of
robot
turning.
F
or
e
xample
in
the
Figure
5a,
the
positi
v
e
v
alue
will
tak
e
the
robot
tak
es
right
turning
and
the
ne
g
ati
v
e
v
alue
will
tak
e
the
robot
chooses
left
turning.
The
ne
w
potential
field
for
local
minima
problem
will
tak
e
as
a
basic
potential
field
for
the
GNR
ON
problem.
It
m
eans
that
the
function
must
be
considered
and
remained
the
result
for
local
minima
problem.
The
e
xtension
of
potential
function
for
the
GNR
ON
problem
will
be
e
xplained
belo
w
.
3.2.
Repulsi
v
e
Function
f
or
GNR
ON
Pr
oblem
The
GNR
ON
problem
occurs
because
the
total
force
of
potential
field
in
the
goal
is
not
zero
in
conse-
quence
of
the
repulsi
v
e
force.
The
distance
influences
repulsi
v
e
force
due
to
the
f
act
as
the
robot
approaches
the
goal,
the
repulsi
v
e
potential
increases
as
well.
There
are
se
v
eral
things
that
ha
v
e
to
be
considered
in
the
GNR
ON
problem
as
described
as
follo
ws.
1.
Re
g
arding
local
minima
problem,
the
addition
function
in
the
GNR
ON
problem
has
not
to
be
influenced
significantly
in
the
computation
with
the
repulsi
v
e
function
in
the
local
minima
problem.
Consequently
,
an
e
xtended
function
has
to
be
set
properly
.
2.
Some
parameters
that
can
be
used
in
order
to
construct
the
e
xtended
of
potential
function
are
(
q
;
q
obs
)
,
(
q
;
q
g
oal
)
,
and
(
q
obs
;
q
g
oal
)
.
It
has
to
be
noted
that
in
v
olving
the
q
obs
is
not
applicable
in
the
real
time
platform
due
the
f
act
that
there
are
no
w
ay
(sensor)
which
is
able
to
detect
infinite
distance
of
an
obstacle.
Consequently
,
(
q
;
q
obs
)
and
(
q
obs
;
q
g
oal
)
are
ne
glected
and
it
merely
uses
(
q
;
q
g
oal
)
.
3.
GNR
ON
problem
arises
at
location
which
is
based
on
the
rule
on
(4)
and
it
can
be
said
the
goal
is
in
the
border
area
the
rule
on
(4).
Thus,
in
that
location,
it
is
ob
vious
F
att
=
0
since
(
q
;
q
g
oal
)
=
0
b
ut
in
contrast,
F
r
ep
6
=
0
.
Thus,
the
solution
is
to
mak
e
the
F
r
ep
=
0
.
Based
on
the
things
as
in
the
aforementioned,
its
moti
v
ate
to
de
v
elop
ne
w
repulsi
v
e
potential
function
as
V
r
ep
(
q
)
=
8
>
<
>
:
sgn
(
(
q
;
q
g
oal
))
p
(
q
;
q
obs
)
+
sgn
(
(
q
;
q
g
oal
))
p
((
q
+
)
;
(
q
+
)
obs
)
;
if
(
q
;
q
obs
)
o
0
;
if
(
q
;
q
obs
)
>
o
(17)
where
sgn
(
(
q
;
q
g
oal
))
(
1
if
(
q
;
q
g
oal
)
6
=
0
0
if
(
q
;
q
g
oal
)
=
0
:
(18)
On
(17)
and
(18),
the
signum
function
is
used
to
solv
e
GNR
ON
problem
whene
v
er
(
q
;
q
g
oal
)
6
=
0
then
F
r
ep
6
=
0
and
(
q
;
q
g
oal
)
=
0
then
F
r
ep
=
0
.
W
ith
the
F
r
ep
=
0
at
the
goal
position,
it
means
that
the
robot
has
no
force
when
meets
the
goal
and
finds
the
global
optimum.
In
order
to
illustrate
the
total
force
for
both
local
minima
and
GNR
ON
problem
using
the
ne
w
potential
function,
Figure
4
is
utili
zed
to
e
xplain
the
applied
force
in
the
ne
w
potential
function.
From
t
he
Figure
4,
in
the
local
minima
problem,
F
att
=
F
r
ep
1
and
the
additional
function
generates
a
ne
w
repulsi
v
e
force
F
r
ep
2
.
Thus,
in
the
local
minima
problem,
F
total
=
F
r
ep
2
.
On
the
other
hands,
in
the
GNR
ON
problem,
the
log
arithmic
function
yield
l
og
1
=
0
,
then
force
of
F
r
ep
1
and
F
r
ep
2
will
be
disappear
or
equal
to
0.
From
the
Figure
4,
it
is
pro
v
en
that
the
ne
w
repulsi
v
e
potential
field
can
handle
local
minima
and
GNR
ON
Problems.
A
No
vel
of
Repulsive
Function
on
Artificial
P
otential
F
ield
for
Robot
P
ath
Planning
(H.
H.
T
riharminto)
Evaluation Warning : The document was created with Spire.PDF for Python.
3268
ISSN:
2088-8708
Figure
4.
T
otal
force
deri
v
ed
by
the
ne
w
potential
function
3.3.
Con
v
er
gence
analysis
The
total
force
of
potential
field
is
as
mentioned
on
(5).
Substituting
(17)
into
(5)
leads
to
F
total
(
q
)
=
r
V
att
(
q
)
+
r
V
r
ep
(
q
)
=
(
q
;
q
g
oal
)+
sgn
(
(
q
;
q
g
oal
))
(
q
;
q
obs
)
0
(
q
;
q
obs
)
3
=
2
+
sgn
(
(
q
;
q
g
oal
))
((
q
+
)
;
(
q
+
)
obs
)
0
((
q
+
)
;
(
q
+
)
obs
)
3
=
2
:
(19)
From
(18),
there
are
tw
o
v
alues
of
sgn
(
(
q
;
q
g
oal
))
,
i.e.
0
and
1.
If
the
v
alue
is
0,
then
the
repulsi
v
e
force
will
be
0.
When
F
r
ep
=
0
,
it
is
ob
viously
that
the
system
is
stable
remaining
(
q
;
q
g
oal
)
=
0
which
af
fect
to
F
att
=
0
.
Consequently
,
F
total
=
0
while
the
robot
reaches
the
final
point.
Let
assumes
that
sgn
(
(
q
;
q
g
oal
))
=
1
for
simplicity
,
equation
(19)
will
be
F
total
(
q
)
=
r
V
att
(
q
)
+
r
V
r
ep
(
q
)
=
(
q
;
q
g
oal
)
+
!
(
q
;
q
obs
)
0
c
obs
+
((
q
+
)
;
(
q
+
)
obs
)
0
((
q
+
)
;
(
q
+
)
obs
)
3
=
2
;
(20)
remains
that
the
robot
position
ag
ainst
the
obstacle
is
(
q
;
q
obs
)
=
c
obs
and
c
obs
>
0
.
As
((
q
+
)
;
(
q
+
)
obs
)
=
jj
q
obs
(
q
+
)
jj
>
0
(al
w
ays
positi
v
e
v
alue),
it
can
be
replaced
with
v
ariable
that
coined
as
,
where
>
0
.
Then,
(20)
can
be
simplified
as
F
total
(
q
)
=
r
V
att
(
q
)
+
r
V
r
ep
(
q
)
=
(
q
;
q
g
oal
)
+
!
(
q
;
q
obs
)
0
c
obs
+
((
q
+
)
;
(
q
+
)
obs
)
0
:
(21)
No
w
,
(21)
can
be
elaborated
into
state
function
in
tw
o
dimensional
(x
and
y),
i.e.
F
total
(
x;
t
)
and
F
total
(
y
;
t
)
.
If
it
assumes
that
F
total
(
x
)
=
_
x
and
F
total
(
y
)
=
_
y
,
then
(21)
is
_
x
=
(
x
x
T
)
+
(
x
x
o
)
c
obs
+
(
x
x
o
)
_
y
=
(
y
y
T
)
+
(
y
y
o
)
c
obs
+
(
y
y
o
)
;
(22)
where
(
x
o
;
y
o
)
is
obstacle’
s
pos
ition
and
(
x
T
;
y
T
)
is
goal
posit
ion
or
origin
point.
Since
c
obs
and
are
al
w
ays
positi
v
e,
then
it
can
be
ne
glected
and
is
assumed
equal
to
1.
Position
(0,0)
is
set
as
goal
position
for
simplicity
.
IJECE
V
ol.
6,
No.
6,
December
2016:
3262
–
3275
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3269
Thus,
(22)
is
modified
_
x
=
x
+
(
x
x
o
)
+
(
x
x
o
)
:
(23)
Di
viding
left
and
right
hands
with
x
,
(23)
becomes
_
x
x
=
+
2
2
x
o
x
;
(24)
or
in
another
form
dx
x
=
+
2
2
x
o
x
dt
:
(25)
by
inte
grating
left
and
right
hands,
R
d
x
x
=
R
+
2
2
x
o
x
d
t
l
n
(
x
)
=
(
+
2
2
x
o
x
)
t:
(26)
In
order
to
obtain
e
xplicit
form,
e
xponential
function
applies
on
the
left
and
right
hands,
R
d
x
x
=
R
+
2
2
x
o
x
d
t
e
l
n
(
x
)
=
e
(
+2
2
x
o
x
)
t
:
(27)
Therefore,
the
function
x
in
the
time
domain
x
(
t
)
=
e
(
+2
2
x
o
x
)
t
x
(
t
)
=
e
(
2
)
t
:
e
2
x
o
x
)
t
:
(28)
W
ith
the
same
process
of
_
x
,
_
y
is
obtained
y
(
t
)
=
e
(
+2
2
y
o
y
)
t
y
(
t
)
=
e
(
2
)
t
:
e
2
y
o
y
)
t
:
(29)
Equation
(28)
and
(29)
are
e
xponential
function
which
means
that
a
gradient
function.
Con
v
er
gent
sys
tem
is
acquired
by
defining
2
>
0
>
2
;
(30)
Based
on
conditions
of
,
if
are
positi
v
e,
then
(2
x
o
+
)
x
>
0
2
x
o
>
(31)
and
if
are
ne
g
ati
v
e,
then
(2
x
o
)
x
>
0
2
x
o
>
:
(32)
F
or
_
y
,
(31)
becomes
(2
y
o
)
y
>
0
2
y
o
>
(33)
and
(2
y
o
+
)
y
>
0
2
y
o
>
:
(34)
It
can
be
concluded
that
satisfying
(30)
until
(34)
will
mak
e
a
curv
e
response
of
the
s
ystem
which
monotonically
to
zero.
Thus,
the
system
is
asymptotically
con
v
er
gent.
A
No
vel
of
Repulsive
Function
on
Artificial
P
otential
F
ield
for
Robot
P
ath
Planning
(H.
H.
T
riharminto)
Evaluation Warning : The document was created with Spire.PDF for Python.
3270
ISSN:
2088-8708
(a)
red
asterisk-obstacle,
dash
line-robot’
s
path
(b)
red
asterisk-obstacle,
dash
line-robot’
s
path
(c)
red
asterisk-obstacle,
blue
line-robot’
s
path
Figure
5.
(a)
Result
of
the
F
r
ep
[36]
(b)
Result
of
the
F
r
ep
[37]
(c)
Result
of
the
proposed
F
r
ep
4.
RESUL
T
AND
DISCUSSION
In
order
to
pro
v
e
the
performance
of
the
proposed
algorithm,
the
test
conducted
in
the
loop
s
imulation.
The
simulations
are
di
vided
into
the
scenario.
The
first
scenario
has
been
pro
v
en
for
local
minima
problem,
the
second
scenario
has
been
sho
wn
ho
w
the
algorithm
handles
the
GNR
ON
problem,
and
the
last
scenario
check
ed
the
rob
ustness
of
the
algorithm
by
using
a
random
position
for
initial,
goal,
and
obstacles.
4.1.
Scenario
1
The
first
e
xperiment
is
the
application
of
the
original
APF
that
can
be
seen
in
Figure
5a.
P
arameter
and
are
0.2
and
5
respecti
v
ely
.
Figure
5a
sho
ws
that
the
robot
w
as
used
the
original
repulsi
v
e
function
[36].
It
yielded
that
the
robot
is
stuck
and
trap
in
the
local
minima.
The
robot
cannot
mo
v
e
since
the
F
total
=
0
.
In
the
scenario,
the
robot
assumed
as
a
point
mass
and
the
safety
area
(
c
obs
)
is
set
to
2
unit.
Figure
5b
used
the
proposed
method
of
repulsi
v
e
force
[37].
The
result
of
[37]
demonstrates
that
the
method
cannot
solv
e
local
minima
problem.
Moreo
v
er
,
the
path
w
as
going
to
the
opposite
direction
of
the
goal
and
system
is
unstable
since
the
robot
cannot
reach
the
global
optimum.
The
application
of
proposed
F
r
ep
for
local
minima
can
be
depicted
as
in
Figure
5c.
Figure
5c
sho
ws
the
simulation
result
where
the
robot
can
escape
from
the
local
minima.
The
proposed
repulsi
v
e
function
dri
v
es
the
robot
to
the
goal
while
a
v
oiding
the
obstacles.
One
of
the
dra
wbacks
of
the
proposed
method
is
that
oscillation
phenomena
still
occurred
that
can
be
seen
in
Figure
5c.
The
second
thing
is
that
the
resulting
path
is
not
the
shortest
since
turning
radius
of
the
robot
is
f
ar
a
w
ay
from
the
c
obs
.
4.2.
Scenario
2
The
other
scenario
w
as
conducted
re
g
arding
GNR
ON
problem.
F
or
simplicity
,
the
obstacle
w
as
re-
duced
into
1
obstacle
at
(9,10)
as
il
lustrated
in
Figure
6a.
Figure
6a
is
the
e
xample
of
GNR
ON
phenomena
that
IJECE
V
ol.
6,
No.
6,
December
2016:
3262
–
3275
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3271
(a)
red
asterisk-obstacle,
dash
line-robot’
s
path
(b)
red
asterisk-obstacle,
blue
line-robot’
s
path
Figure
6.
(a)
Result
of
the
F
r
ep
[36]
(b)
Result
of
the
F
r
ep
[37]
and
proposed
F
r
ep
in
this
research
the
global
optimum
(goal
point)
is
not
reachable
due
to
the
repulsi
v
e
force
of
[36].
It
means
that
F
total
=
F
r
ep
when
the
robot
at
the
goal
and
the
robot
has
been
repulsed
a
w
ay
from
the
goal.
Si
milar
results
are
sho
wn
by
the
proposed
repulsi
v
e
force
of
[37]
and
the
proposed
method
of
equation
(19).
The
implementation
of
[37]
and
equation
(19)
handle
GNR
ON
problem
that
can
be
seen
in
Figure
6b.
The
e
xperiments
demonstrate
both
of
the
proposed
methods
can
solv
e
GNR
ON
problem.
The
dif
ferent
arises
in
total
potential
deri
v
ed
to
the
robot.
The
total
potential
distrib
ution
of
GNR
ON
problem
w
as
depicted
in
the
Figure
7a,
7b
and
7c.
Figure
7a
illustrates
the
total
function
equal
to
0
before
the
robot
reaches
the
goal.
Figure
7b
and
7c
e
xplain
the
both
of
the
proposed
method
can
meet
the
goal
and
global
optimum.
The
signum
function
drags
the
robot
escape
from
the
GNR
ON
problem
and
impacting
to
g
ain
the
potential
force.
Figure
7a
sho
ws
that
the
total
potential
dropped
belo
w
the
goal
point
at
y
=
8
and
by
conducting
t
he
signum
function
in
the
repulsi
v
e,
the
robot
can
reach
the
goal
as
seen
in
Figure
7c.
Although
it
can
reach
t
he
goal,
b
ut
the
curv
e
of
the
total
function
is
not
smooth.
Smooth
function
is
obtained
by
the
proposed
potential
function
of
[37].
It
has
to
be
noted
that
the
x
axis
can
be
ne
glected
since
the
goal
and
robot
in
the
same
x
position.
Therefore,
the
robot
potential
function
merely
influences
to
the
y
position.
4.3.
Scenario
3
In
this
scenario,
the
obstacles
were
set
randomly
in
the
unstructured
shape.
The
obstacle
itself
w
as
constructed
by
se
v
eral
points
and
represented
three
objects
in
the
real
s
cenario.
The
initial
and
goal
point
were
A
No
vel
of
Repulsive
Function
on
Artificial
P
otential
F
ield
for
Robot
P
ath
Planning
(H.
H.
T
riharminto)
Evaluation Warning : The document was created with Spire.PDF for Python.