TELKOM
NIKA
, Vol.12, No
.2, June 20
14
, pp. 291~2
9
6
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v12i2.1938
291
Re
cei
v
ed
De
cem
ber 8, 20
13; Re
vised
Ma
rch 19, 20
14; Accepted
April 6, 2014
Estimating Object Location using Particle Clustering on
Rotating Sonar Detection
Harindr
a Wi
snu Pradha
n
a
1
, Sur
y
ono
2
, Achmad Wi
dodo
3
1
Dept. of Information S
y
stem
, Universitas D
i
pon
eg
oro, JL Imam Barjo, Se
maran
g
, Indon
esia
2
Dept. of Ph
y
s
ic, Universit
a
s Dipo
n
e
gor
o,
JL Prof Sudharto
SH, Semaran
g
,
Indonesi
a
3
Dept of Mechanic
a
l Eng
i
n
e
e
r
ing, Un
iversita
s Dipo
neg
oro,
JL Prof Sudh
ar
to SH, Semara
ng, Indo
nesi
a
*Corres
p
o
ndi
n
g
author, E-ma
il:
1
w
i
s
nu@ms
i.und
ip.ac.i
d
,
2
sur
y
o
no@
un
dip.
a
c
.id,
3
aw
id
@u
nd
i
p
.a
c.id
A
b
st
r
a
ct
Particle fi
lter
b
een
us
ed f
o
r l
o
cali
z
a
ti
on
a
n
d
positi
on
esti
ma
tion w
i
th
vari
ou
s ap
plic
atio
ns.
Severa
l
meth
od
ap
pli
e
d in
ord
e
r to r
educ
e the c
o
mp
lexity
of
pa
rticle i
n
for
m
ati
on to
low
e
r pr
ocessi
ng res
o
urce
requ
ire
m
e
n
t while
provi
d
i
ng
a precis
e map
.
Sonar s
ens
o
r
provid
e a ra
nge pr
ecisi
on
w
i
th poor be
ar
ing.
Partial o
b
serva
t
ion ap
pli
ed to gai
n estimatio
n
of objec
t locat
i
on usi
ng sev
e
ral measur
e
m
e
n
t from mu
ltip
l
e
vantag
e p
o
int.
T
h
is pa
per
p
r
opos
e gro
u
p
i
ng of d
e
te
ctio
n partic
l
e fro
m
so
nar s
ens
or usi
ng cl
usterin
g
meth
od
in
ord
e
r to pr
ovid
e e
s
timate
d o
b
j
e
ct positi
on fro
m
a sin
g
le
vant
a
ge p
o
i
n
t. T
he
appr
oach
esti
mat
e
obj
ects usi
ng
eucli
de
an
dista
n
ce tres
hol
d to
sep
a
rate
on
e
obj
ect det
ectio
n
s fro
m
th
e ot
her
and
gro
u
p
al
l
the detectio
n
particl
e into cl
uster contai
nin
g
a set of
numb
e
r. As a result of particle
clusterin
g
, ob
jec
t
locati
on ca
n b
e
esti
mate
d w
i
th their res
pec
tive w
e
ight
of
certainty as
a
n
attributi
on fo
r further decis
i
o
n
mak
i
n
g
.
Ke
y
w
ords
: sonar, particle filter, clustering, slam
1. Introduc
tion
Simultaneo
us locali
zatio
n
and m
appi
ng (SLAM
)
has
bee
n
widely develo
ped a
n
d
impleme
n
ted
usi
ng
seve
ral metho
d
a
nd a
pproa
ch.
SLAM mai
n
pu
rpo
s
e
is
to co
mpo
s
e
a
n
environ
ment map
u
s
in
g
a
mobile rob
o
t while
estim
a
ting it's lo
catio
n
on
the m
a
p
simulta
neo
u
s
ly.
Ref [1] state
that SLAM probl
ems i
s
su
ccessf
ully
solved ove
r
last de
cad
e
usin
g vario
u
s
available ap
p
r
oa
che
s
an
d method
s.
The esse
ntial
of SLAM methods u
s
e e
s
t
i
mati
on and p
r
oba
bility to solve its probl
em [1].
Statistic
cal
c
u
l
ation u
s
e
d
to
analy
z
e l
a
rg
e am
ount
of d
a
ta gath
e
red
by SLAM
syst
em. The
SLA
M
data con
s
ist
of obje
c
t and
environ
ment
detectio
n
fro
m
rob
o
tic se
n
s
ors and mov
e
ment
d
a
ta
from
roboti
c
a
c
tuat
ors fe
edb
ack.
Partic
le filter
approa
ch u
s
e
d
to manag
e
uncertainty in
SLAM data to
estimate th
e
rob
o
t and
o
b
ject
s lo
catio
n
on the
ma
p. Ref [2] co
mpare vario
u
s ap
proach
o
f
locatio
n
estim
a
tion ba
sed o
n
bayesi
an filters.
2. Sensor Ch
arac
teris
t
ic
SLAM metho
d
result highl
y related with
the sen
s
ors
accuracy an
d
detection m
odelin
g
[3].
Different sen
s
o
r
s prod
uce different output
a
c
cording to its
ch
ara
c
teri
stic
a
nd mea
s
u
r
e
m
ent
method. Surf
ace roug
hne
ss of mate
ria
l
detected
al
so interfe
r
e t
he data acqu
ired [4]. Sensor
measurement
often uses
time of flight met
hod. Eq
uation (1)
sh
ows
that di
stance travel
e
d
betwe
en
sen
s
or to obj
ect
and b
a
ck to
sen
s
o
r
in
d
i
s
the
spe
ed
of sign
al in
c
times the fli
ght
duratio
n in
t
.
d = c.t
(1)
Sonar typicall
y has the
ch
eape
st p
r
ice
comp
ared to
others [3]. So
nar sen
s
or re
turn
an
accurate ran
g
ing me
asurement but
p
oor
bea
ring
due to the
wide be
am an
d sid
e
lob
e
s [5].
Figure 1 sho
w
s
se
nsitivity pattern of
sonar
se
ns
or
from differe
nt angle
s
[6]. Due to the l
o
w
spe
ed of
sou
nd wave co
mpared with the
spee
d
of
light, sona
r
sen
s
o
r
re
spo
n
se
are
slo
w
er
comp
ared wit
h
others [3].
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
9
30
TELKOM
NIKA
Vol. 12, No. 2, June 20
14: 291 – 29
6
292
Figure 1. Sonar se
nsor
sen
s
itivity pattern
Laser ra
ngin
g
had the most accu
rat
e
meas
ure
m
ent and also the fastest sensor
available in
market [3]. Typical la
ser
rangin
g
se
nsor do
es d
e
te
ction up to
200m
with 0
.
1
0
resolution
s [3
]. Disadva
n
ta
ges
of usi
n
g
lase
r r
angin
g
are th
at it is expe
nsive
and
spe
n
t hi
gh
energy con
s
u
m
ption [3]. Laser
ran
g
ing
sensor al
so
ha
d probl
e
m
s
with reflecting
surfa
c
e
su
ch
as
mirrors
, windows
etc
[3].
Visual
se
nso
r
like came
ra
provid
es
a
better b
eari
n
g with
poo
r
range [5]. Th
e visual
SLAM metho
d
locate feat
ure from ima
ge captured
by the cam
e
ra as
refe
ren
c
e for lo
cali
zat
i
on
and furth
e
r
mappin
g
. Ref
[7] descri
b
e
s
the a
ppli
c
a
t
ion of active
vision a
ppro
a
ch
within S
L
AM
system
s. Vi
sual a
pproa
ch
in SLAM
re
qu
ire
ea
s
ily di
stingui
s
he
d la
n
d
mark f
r
om
their environm
ent
[7]. Using av
ailable o
b
je
ct as lan
d
ma
rk gene
rate mo
re obj
ect det
ected a
nd m
o
re
comp
utatio
n
compl
e
xity require
d.
Senso
r
u
s
ed
in this re
se
arch is
HC-S
R04 lo
w cost
sona
r sen
s
o
r
wo
rki
ng on
40 kHz
freque
ncy wit
h
effective measure
m
ent
up to 8i
nch [8]. The serv
o mounted o
n
top of hxt900
micro
se
rvo t
hat p
r
ovide
s
180
0
rotation
for ob
se
rvation
p
u
rpos
e. Senso
r
moun
ted
on
roboti
c
cha
s
sis
sho
w
n on Figu
re 2
.
Figure 2. Sonar se
nsor mo
unted on
serv
o
3. Object Lo
calizatio
n Approac
h
es
Due to limita
t
ions of se
nsors avail
able,
many locali
zation method
s introd
uced.
Some
s
y
s
t
e
m
u
s
e
pa
r
t
ia
l ob
se
r
v
atio
n
w
i
th
d
e
l
aye
d
ma
pp
in
g in
or
d
e
r
to
es
tima
te
ob
ject lo
c
a
tion
fr
om
several vanta
ge point [5], [9]. Ref [10] specifi
c
a
lly pro
p
ose rob
u
st
mappin
g
usi
n
g son
a
r data.
As
descri
bed
in
previou
s
se
ct
ion, so
na
r se
nso
r
p
r
ovide
a preci
s
e
ra
n
g
ing
with po
or b
a
rin
g
whi
l
e
visual imagi
n
g
had better
barin
g with p
oor rangi
ng.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
9
30
Estim
a
ting Object Location Usi
ng Parti
c
le
Cl
ustering on ..... (Har
indra Wisn
u Pradhana)
293
Figure 3. Partial observatio
n
(a
)
rang
e-
o
n
ly
(b) ba
ring
only
Figure 3 di
splay partial o
b
se
rvation
s
whi
c
h u
s
e ra
nge only
sen
s
or
and b
e
a
r
ing only
sen
s
o
r
[5]. As the robot
move, more
obje
c
t det
e
c
tion with
m
o
re
vanta
ge points acquired,
resulting a
m
o
re
accu
rate
estimatio
n
o
f
object l
o
cat
i
on. Partial o
b
se
rvation m
e
thod
req
u
ire
s
detectio
n
d
a
ta from
at le
ast two vanta
g
e
point
s.
All th
e information
from eve
r
y de
tection va
nta
ge
point carried
along th
e del
ayed map
p
in
g progress to
estimate
obj
ect lo
cation.
The la
rge
set
s
of
data ca
rri
ed i
n
crea
se com
puting compl
e
xity and spe
n
t more reso
urce and e
n
e
r
gy.
3.1 Particle
Clustering
Clu
s
terin
g
b
een i
n
trod
uced a
s
ma
ss data
s
et
gro
uping
metho
d
. Ref
[11]
descri
b
e
s
clu
s
terin
g
me
thod a
s
a
n
ex
amination
pro
c
e
s
s towa
rd
s colle
ction
s
of data
sets an
d group
s th
e
m
int
o
sev
e
ral cl
ust
e
r
s
wit
h
ce
rt
ain simila
rit
i
es
b
e
twe
en it
s mem
b
e
r
s.
Ref [12] a
ppli
e
s
clu
s
teri
ng
for
effective and
efficient data mining ap
proa
ch b
a
se
d on ran
dom
search by analyzi
ng sp
atial
distrib
u
tion.
Rotating
so
n
a
r sen
s
o
r
ge
nerate
s
h
uge
sets
of
data
that are the
rotation an
gle
over the
resolution. In this
research, 180
0
de
g
r
ee
s
da
ta
w
i
th
1
0
re
solutio
n
s gene
rate
up
to 180
parti
cl
es
for ea
ch ste
p
.
Some angle
might return no value be
cause there i
s
no obje
c
t de
tected. Ref [1
3
]
descri
be
abo
ut buildin
g a
simple
SVG
map to
rep
r
e
s
ent
spatial
i
n
formatio
n a
s
a
re
sult of
non
destructive o
b
se
rvation of
roboti
c
syst
em. Figu
re 4
display a sa
mple map
co
ntaining
spati
a
l
distrib
u
tion of
sona
r se
nsor detection p
a
rticle.
Figure 4. Sonar dete
c
tion sample data
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
9
30
TELKOM
NIKA
Vol. 12, No. 2, June 20
14: 291 – 29
6
294
This
pap
er p
r
opo
se
clu
s
tering of dete
c
ti
on data fo
r e
a
ch
step
re
su
lting estim
a
te
d obje
c
t
positio
n a
nd t
he
weig
ht of
obje
c
t lo
catio
n
certai
nt
y to
r
e
pr
es
e
n
t the a
m
ou
n
t
o
f
pa
r
t
ic
le pr
o
v
id
in
g
the estimatio
n
. Clu
s
ter g
e
nerate
d
by separat
ing
d
e
tection data usin
g
predefi
ned
am
ount of
Euclide
an di
stance th
resho
l
d.
Figure 5
sh
o
w
s t
he
clu
s
te
ring
pro
c
e
s
s f
l
ow. Th
e p
r
o
c
ess
calculate
s
Eu
clide
an d
i
stan
ce
betwe
en two
particl
es a
n
d
com
pares i
t
with pr
ed
efined threshol
d to determi
ne wh
ethe
r they
belon
g to the same clu
s
te
r or not. Object location
ca
n be estimat
ed as the av
erag
e locatio
n
o
f
every parti
cle
in one cl
ust
e
r. Thi
s
re
se
arch u
s
e pol
ar coordinate
system to repre
s
e
n
t sp
a
t
ial
informatio
n.
Euclide
an
di
stance on pol
ar coo
r
din
a
te
system
also
calle
d radial
distan
ce.
Ra
dial
distan
ce of two particl
e
p
a
nd
q
are d
e
scribed in
(2).
(2)
The numb
e
r of
pa
rticle
in the
cl
uste
r re
pre
s
ent
ce
rta
i
nty of the lo
cation
that in
cre
a
sed
along
with a
dditional m
e
a
s
ureme
n
t data esp
e
ci
ally
from different
vantage poi
n
t. To pre
s
e
r
ve
clu
s
ter
compl
e
xity, particle
data ca
n be
store
d
with
th
eir re
sp
ective
clu
s
ter me
m
b
ership
relati
on
for furthe
r a
n
a
lysis
su
ch
a
s
dete
r
mini
ng
obje
c
t
sh
ape
, plannin
g
ob
stacl
e
avoid
a
n
ce
save
pat
h
,
etc.
Figure 5. Clu
s
terin
g
proce
ss flo
w
3.2 Clusterin
g
Resul
t
The e
s
timate
d obje
c
t lo
cat
i
on after
parti
cle
clu
s
terin
g
plotted into t
w
o di
men
s
ion
a
l map
s
with exa
c
t same
scale a
nd
cente
r
p
o
int to com
pare
with
th
e pa
rticle
di
stributio
n b
e
fore
clu
s
terin
g
. As an
exampl
e, parti
cle
cl
usteri
ng
with
thre
shol
d 10
cm a
nd n
o
minimum
ce
rtainty
weig
ht displa
yed in Figure 6.
Figure 6 sho
w
s le
ss d
e
tection particl
e and detecti
o
n
line com
p
ared
with Figure 4
.
As the
distrib
u
ted pa
rticle
clust
e
re
d, the object
estima
ted
po
sition can be
pointed o
n
the map ba
se
d on
singl
e vantag
e point detection. Ce
rtaint
y value displ
a
yed as the weig
ht of the object point and
the dete
c
tion
line. The
wei
ght can
be filt
ered
to ig
no
re dete
c
tion
error sho
w
n
as
clu
s
ter
with l
e
ss
than ce
rtain value of ce
rtai
nty.
d
p
→
q
=
√
r
p
2
+
r
q
2
−
2
r
p
r
q
cos
(
θ
p
−
θ
q
)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
9
30
Estim
a
ting Object Location Usi
ng Parti
c
le
Cl
ustering on ..... (Har
indra Wisn
u Pradhana)
295
Figure 6. Sonar dete
c
tion a
fter clu
s
terin
g
(a)
(b)
Figure 7. Sonar expe
riment
data usin
g di
ffe
rent param
eter (a
) 20
cm
thresh
old an
d no
minimum wei
ght. (b) 10
cm
thresh
old an
d minimum weight 10.
(a)
(b)
Figure 8. Different data al
so sho
w
s less
noisy
map
(a) before
cluste
ring (b) after
clu
s
terin
g
The value of Euclidea
n distan
ce thre
shol
d and min
i
mum weig
ht of certainty can b
e
defined
as fix numbe
r o
r
dynamically
cha
nge
al
on
g with
the m
a
turity of the
data
and
ob
ject
certai
nty. Further artifici
al algorith
m
ca
n
be adde
d for object lo
cali
zation de
cisi
o
n
makin
g
ba
se
d
on the
lo
cati
on
clu
s
ter.
Fi
gure
7
an
d F
i
gure
8
di
spl
a
y the
re
sult
of expe
rimen
t
usin
g diffe
rent
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 2, June 20
14: 291 – 29
6
296
value of threshold an
d mini
mum ce
rtaint
y weight.
The la
rg
er va
lue of th
re
sh
old resulting l
a
rge
r
coi
n
ci
d
ence of t
w
o
particl
es g
r
ou
ped i
n
to
singl
e clu
s
ter, therefore it gener
ate less
clu
s
ter bu
t may accide
ntally reco
gni
ze two different
obje
c
t as on
e
.
With variou
s wei
ght of certaint
y, the highe
r minim
u
m weig
ht wi
ll eliminate m
o
re
uncertain
clu
s
ter resulting
less clu
s
ter di
splaye
d on th
e map.
Ref [14]
de
scribe
s the
com
p
lexity of tracki
ng
3-dimen
s
ion
a
l obj
ect
usin
g 2
-
dime
nsio
na
l
visual. The
clu
s
terin
g
m
e
thod g
ene
rates
singl
e feature
point
for every
obje
c
ts redu
cing
comp
utation compl
e
xity.
4. Conclusio
n
This re
se
ar
ch
su
c
c
e
ssf
ully
simplif
ied
di
st
ribut
ed
pa
rticl
e
an
d form e
s
timation
s of
obje
c
t
locatio
n
a
s
si
ngle fe
ature
point fo
r eve
r
y step
of rob
o
t po
sition. P
a
rticle
cluste
ring all
o
ws
be
tter
view of the map displaying
less data an
d
more inform
ation.
The hig
her v
a
lue in th
re
shold an
d cert
aint
y weight,
the less cl
ust
e
r ge
nerated
lowe
ring
further
comp
utation com
p
l
e
xity but may resultin
g mul
t
iple obje
c
t re
cog
n
ized a
s
one.
Furthe
r rese
arch can b
e
applie
d usi
n
g
several sen
s
or li
ke l
a
ser, imaging a
n
d
inertial
measurement
unit.
Referen
ces
[1]
Durrant-W
h
y
te
H, Bail
e
y
T
.
Simultan
eous
Lo
calizati
o
n
an
d
Mapp
ing
(SLA
M) Part I.
IEEE Robotics
&
Autom
a
tion Maga
z
i
ne.
20
06; 13(2): 99-
10
8.
[2]
F
o
x D,
H
i
ght
o
w
e
r
J, Lia
o
L, Schulz
D,
B
o
rriel
l
o
G. B
a
yesi
an F
i
lters for
Locati
o
n
Estim
a
tion.
IEEE
Pervasiv
e Co
mputin
g.
200
3; 24-33.
[3]
Ruckert EA.
Simulta
neo
us
Loca
lisati
o
n
a
nd M
app
in
g f
o
r Mo
bil
e
R
o
bot
w
i
t
h
R
e
c
ent Se
nso
r
T
e
chnolog
ies.
Master T
hesis
.
Graz: Graz Universit
y
of T
e
chnol
og
y; 20
09.
[4]
Sur
y
on
o, Kusminarto, Sup
a
r
t
a GB. Estimation of
Sol
i
d Materia
l
Surface
Roug
hness u
s
ing T
i
me-of-
F
light Ultras
o
u
nd Immerse T
r
ansd
u
cer.
Jour
nal of Materi
al
s Science a
n
d
Engin
eeri
ng.
201
0;
4(8)
:
35-3
9
.
[5]
Bailey
T
,
Durrant-Why
te H.
Simultaneous
Loca
lization and
Mapping (S
LA
M) Part II.
IEE
E
Robotics &
Autom
a
tion Maga
z
i
ne.
20
06; 13(3): 10
8-1
1
7
.
[6]
Sale
em MM. An Econom
ic Si
multan
eous
Lo
calizati
on
a
nd
Mapp
ing S
y
ste
m
for Remote Mobil
e
Ro
bo
t
Using
SONAR
and
an In
no
vative AI Alg
o
r
ithm.
In
te
rn
a
t
io
n
a
l
Jo
u
r
n
a
l
o
f
Fu
tu
re
C
o
m
p
u
t
e
r
and
Co
mmun
icati
o
n.
2013; 2(
2): 147-1
50.
[7]
Davids
on AJ, Murra
y
DW
. Simulta
eous L
o
c
alizat
i
on a
nd
Map-Bu
ild
ing
usin
g Active Vision.
IEEE
Transactio
n
on
Pattern Analys
is and Mac
h
in
e
Intellig
enc
e.
2002; 24(
7): 865
-880.
[8]
Product User'
s
Manu
al - HC-S
R
04 Ultr
a
son
i
c
Sensor, C
y
tr
o
n
T
e
chnolo
g
ies
,
2013.
[9]
Leo
nard
JJ, R
i
koski RJ,
Rus
D, Sing
h S,
Editors. Incorp
oratio
n of d
e
l
a
yed d
e
cisi
on
mak
i
n
g
int
o
stochastic map
p
in
g
, Ex
perimental Robotics V
II. Ne
w
Y
o
rk: Springler Ver
l
ag,
2001.
[10]
T
a
rdos JD, Neira J, Ne
w
m
an PM, Leo
n
a
rd JJ. Rob
u
s
t Mappin
g
a
nd Loc
aliz
atio
n in Ind
oor
Enviro
nments
Using S
onar D
a
ta.
T
he Intern
ation
a
l Jo
urna
l
of Robotic Re
search.
20
02;
21(4): 31
1-
330.
[11]
Rajar
a
ma
n A,
Ullma
n
JD,
Le
skovec J,
Ed
i
t
or
s
.
Mining of M
a
ssive
Datas
e
ts.
C
a
mb
rid
g
e
:
C
a
mb
rid
dge
Univers
i
t
y
Pr
es
s, 2011.
[12]
Ng RT
, Han J.
Efficient a
nd
Effective Clust
erin
g Metho
d
s
for Spatia
l D
a
ta Min
i
ng.
Proc
eed
ing
of t
h
e
20th VLDB C
o
nferenc
e. 199
4
:
144-15
5.
[13]
Pradh
an
a HW
, Sur
y
o
no, W
i
d
odo A.
Visua
l
i
z
a
t
i
on of Si
mu
l
t
aneo
us Loc
ali
z
a
t
i
on a
nd Ma
ppi
ng usi
n
g
SVG : Non D
e
structive Obse
rvations
an
d
V
i
sual
i
z
a
t
i
on of Rob
o
tic
Syste
m
. Proc
eed
in
g
of the
2nd
Internatio
na
l C
onfere
n
ce o
n
Information S
ystem
s for Business C
o
mp
eti
t
iveness (ICIS
B
C). 201
3:
134-
138.
[14]
Papi
noko
l
o
pou
los
NP, Kh
osl
a
PK, K
ana
de
T
.
Visual T
r
acking
of
a Mo
ving
T
a
rget b
y
a
Came
r
a
Mounte
d
o
n
a
Rob
o
t: A C
o
mbin
ation
of
Contro
l a
nd V
i
sion.
IEEE Tr
ansactions
on Robotics
and
Autom
a
tion.
19
93; 9(1): 14-3
5
.
Evaluation Warning : The document was created with Spire.PDF for Python.