Recen Inno a ions in Mecha onics (RIiM) Vol. 2. (2015). No. 1-2.
DOI: 10.17667/ iim.2015.1-2/14.
1
An algo i hm o a oiding obs acles wi h
in elligen objec s
Şahin YILDIRIM
Mecha onic Enginee ing
E ciyes Uni e si y
Kayse i, TURKEY
[email p o ec ed]
Ebubeki YAŞAR
Voca ional School, Compu e P og amming Dep .
Gaziosmanpaşa Uni e si y
Toka , TURKEY
ebubeki .yasa @gop.edu.
Abs ac —In his esea ch a pa h planning which is he i s s ep
o mo ion planning in obo ic applica ions, away om an obs acle
in an en i onmen whe e exis many obs acles is de eloped.
Di e en om he algo i hms in li e a u e, a pa h away om an
obs acle is planned wi hou de e mining he con igu a ion ee
space in a place ha con ains many di e en shaped obs acles
wi h he help o in elligen objec s ha a e c ea ed objec
o ien ed p og amming(OOP). Wi h he help o his de eloped
algo i hm no only he p obable pa hs bu also inding he
sho es pa h and co ec ing i wi h he help o in elligen objec s
a e e alua ed a he same ime. This algo i hm is so p o ound
ha i can o m he basic p inciples o many o iginal Wo ks wi h
he addi ional in u u e wo ks.
Keywo ds—A oiding obs acles, pa h planning
I. INTRODUCTION
The mo ion planning p ocess always p oduces mo ion in
o de o combine s a ing poin wi h he a ge poin a oiding
obs acles. Robo mo ion planning ocuses on only obo
changes and necessa y u ns unde aluing he dynamic
s uc u es and limi a ions [2].
Pa h planning Wo ks a e based on inding a pa h away om
an obs acle. In his si ua ion esea che s a e ocused on
p oducing an algo i hm which p o ides a pa h wi hou any
c ash. Planning a pa h is highly needed o mobile obo s in
acco dance wi h he concep ha a obo can make i s du ies
wi h he help o mo ion in eal wo ld. Many me hods a e
de eloped in his subjec .
Mo ion planning a e sea ched om many esea ches du ing
1970‘s. Fo he i s ime in 1969 Nilsson made a mobil obo
de ini ion which had he abili y o mo ion planning. Nilsson
in oduced he isibili y g aph me hod which was combined
wi h A* sea ching algo i hm, ha p o ides a poin obo ind
he sho es way away om obs acles wi hin he polygonal and
geome ical shaped obs acles. This me hod emained e y
popula [8].
Udupa sugges ed he idea o making he obo as small as a
poin o a oiding obs acle algo i hms. Wi h he help o his
idea Lozano Pe ez and Wesley sugges ed a mo e gene al and
sys ema ic idea in o de o plan a pa h o polyhed al/polygonal
obo s wi hou ouching polyhed al/polygonal obs acles [10].
This wo k pa e he way o he idea o con igu a ion space.
This con igu a ion idea exp esses he obo o be ep esen jus
one poin in pa ame e space ha de ines obo ‘s deg ees o
eedom[8].
While he ep esen ing o bidden a eas in con igu a ion
space, he opposi e pa o con igu a ion space ep esen s ee
space [8]. This is he p obable mo ion a ea o he obo . In 1979
Tomas Lozano- Pe ez and Michael A. Wesley in es iga ed he
sho es way in hei wo ks changing he me hod named
isibili y diag am in o g aph heo y hanks o line which is
o med combining he whole obs acles‘ ace o ace co ne s.
And ews and Hogan in 1983 and Kha ip[6] in1985
de eloped he po en ial ield me hod by hinking he a ea,
whe e he obo is wo king is in he imagina y po en ial ield.
In his po en ial ield whe e he obo is in, a ge poin o ms
a ac i e and obs acles o m a p opulsi e po en ial ield. The
obo in his po en ial ield goes owa ds o he a ge a oiding
he obs acles e ec ed by a ac i e and p opulsi e o ces as i
he e is a slope in he ield. Ha ing local minimums is he
bigges p oblem o his po en ial ield me hod. This si ua ion
b ings ou he esul ha as i he obo eaches he a ge be o e
i eaches he a ge and his si ua ion is named local minimum.
In 1987 B Chazelle in es iga ed he pa h ha goes he
a ge o e he cells ha didn‘ ouch he obs acles wi h a
echnique he de eloped by di iding he wo king a ea, whe e
he obs acles also exis in, in o app oxima e decomposi ion
cells. I he cells ouching he obs acles doesn‘ each he a ge ,
he ac ion o di iding is epea ed by making he cells smalle .
One o di e en applica ion o cell algo i hm is e ical
decomposi ion me hod. He e, cen e poin o he line connec ed
be ween he wo obs acles o obs acles and any co ne s is
obs acles- ee poin s. The sho es pa h is in es iga ed changing
hese poin s in o g aph heo y like in isibili y diag am
me hod[2].
In 1991 F Au enhamme ‘s o onoi diag am me hod di ides
he plane acco ding o nea es neighbo ule. This ule is each
poin is ela ed o nea es plane ield. The diag am is o med
combining he poin s ha exis a he same dis ance o i s wo
nea es obs acles. The sho es pa h is in es iga ed among he
p obable pa hs wi h his diag am.
In 1994 Ka aki e al. T ied o combine he nea co ne s
wi h a line he help o local planne accep ing he poin , which
is andomly aken om con igu a ion space as a co ne poin i
he poin belongs o ee space (C ee) in hei p obabili y based
pa h inding me hod (PRM). Local planne con ols he o med
line i hey a e on he obs acles o no . Valid combina ions a e
added o g aph heo y.
LaValle and Knu e [13] in 1998 o med ee s uc u es
inding and connec ing he nea es poin s and s ep by s ep
widening he i s example which is aken om con igu a ion
space in hei algo i hm. Tha hey de eloped in hei andom
h ee s uc u ed as sea ching me hod(RRT). In his h ee
s uc u e new poin s exis andomly. The ield is o med om
Recen Inno a ions in Mecha onics (RIiM) Vol. 2. (2015). No. 1-2.
DOI: 10.17667/ iim.2015.1-2/14.
2
h ee s uc u es which had connec ing b anches as many as he
epe i ions in his way.
In hese men ioned wo ks he sho es poin s ha connec
he s a ing and he a ge a e ound a e de e mining he
p obable poin s away om he obs acles. A pa h is o med by
connec ing hese poin s. This pa h has discon inuous
cha ac e is ic. La e his discon inuous pa h is changed o a
con inues pa h wi hou any sha p u ns and away om
obs acles by s aigh ening.
II. FINDING A PATH AWAY FROM OBSTACLE
In his wo k a di ec -line connec ion is c ea ed be ween he
s a ing poin and he a ge by connec ing he in elligen
objec s each o he which a e p oduced wi h Delphi one o
objec o ien ed p og amming language. Thanks o ha
unimpo an obs acles can be igno ed while de e mining he
pa h o he a ge . I isn‘ needed also o de e mine he
con igu a ion space ha educes he obo as small as a poin .
Because i he size o he objec s a e de e mined acco ding o
he obo ‘s maneu e abili y, ime spen con igu a ion space
isn‘ needed. In his wo k he en i onmen is accep ed being
wo dimensions and he obs acles andomly may ha e any
shape, posi ion and edge numbe .
A. In elligen Objec s Algo i hm
1. Fi s he obs acles ha exis in he en i onmen a e
educed o wo colo s wi h h eshold me hod ha includes
s a ing and he a ge poin and hen s a ing poin and a ge
poin a e ed colo ed a e added.
Fig. 1, En i onmen wi h obs acles
2. The shape and size o he objec s should be de e mined.
In ou applica ion he shape o he objec s is ound and i s size
is 10x10 pixels. The size can be de e mined acco ding o obo
link size.
3. De e mined amoun o ound objec s a e c ea ed on a
linea line om s a ing poin o he a ge wi h he help o he
equa ion below. Amoun o he in elligen objec s a e
de e mined obs acles size, amoun and shape si ua ions.
2
2
12
12 xx
yy
xx
yy





(1)
Slope is coun ed like below.
12
12 xx
yy
m


(2)
In his o mula (x1,y1) a e s a ing coo dina ion and (x2,y2)
a e a ge coo dina ion.
Fig. 2, Placemen o objec s acco ding o he equa ion 1
4. In his s ep an objec will pass o e he obs acle ha is
unde he objec mo ing up o down acco ding o he igu e
below. The equa ion o he lines o each objec which a e
o med o be igh o he line which has a mo ion line o med
acco ding o equa ion 1 can be ound below.
).( 11 xxmyy n

Abo e he slope is ound acco ding o he slope in he
equa ion 2
1
n
mxm
(4)
Fig. 3, The lines ha objec s can go down
Recen Inno a ions in Mecha onics (RIiM) Vol. 2. (2015). No. 1-2.
DOI: 10.17667/ iim.2015.1-2/14.
3
Fig. 4, The lines ha objec s can go up
I he edge o he obs acle is cong uen wi h he
en i onmen ‘s bo de , he e is only one op ion o his obs acle.
Because he obo canno pass be ween he obs acle and
en i onmen bo de . The e isn‘ any si ua ion like his in he
igu e abo e.
5. While de e mining he di ec ion o he mo ion, he
mo ion ha doesn‘ go u he om he obs acle will ake he
minimum dis ance. Any minimum dis ance me hods o
de e mine he di ec ion can be use in he li e a u e. In elligen
objec s can be di ec ly used pa o de e mining he minimum
dis ance me hods. While going on he de e mined di ec ion, he
objec s should ealize one o he objec s in on o hem a
leas ( he e shouldn‘ be any obs acle). I hey don‘ see he
obs acle hey should go on he same di ec ion un il hey ealize
he obs acle. The objec s ha a e mo ed like his a e shown
illed objec s below. I se e al objec s don‘ see each o he ,
amoun o in elligen objec s can be enhanced.
I he objec s don‘ i be ween wo obs acles (i i ouches
bo h o he obs acles) i goes on he same di ec ion un il he end
o he ollowing objec s.
Fig. 5, Objec s go o e he obs acles.
6. A e de e mining he minimum dis ance now i ‘s ime o
co ec he pa h hose a e o med by he objec s. S a ing wi h
he s a ing poin , he objec s ha a e si ua ed be ween he wo
edges o ace o ace objec s should be placed on he same
di ec ion. In his way he local cu es a e co ec ed.
Fig. 6, Le , co ec ing he pa h and igh , de e mining he
dis ance.
ACKNOWLEDGMENT
In his wo k a di e en algo i hm is c ea ed and used o
de e mine a pa h away om obs acles. This algo i hm, di e en
om p e ious me hods, wholly co e ee con igu a ion space
(no needed), de e mining he poin s away om obs acles,
de e mining he sho es pa h, co ec ing he de e mined pa h
p ocesses.
While de e mining a pa h away om an obs acle p oduced
wi h objec o ien ed me hod, he pa h is de e mined conside ing
he size o he obo . Tha p epa ed p og am can be used
wi hou showing i wan ed. As a esul isual d awing ha e
meaning o he use s. Fi s , o iginal cha ac e is ic o he
p og am is ha i can de e mine he sho es dis ance away
om he obs acle using he s uc u e ha belongs objec
o ien ed p og amming. Second, o iginal cha ac e is ic is ha i
in es iga es he sho es pa h wi hou e ealing he whole
p obable pa hs. The hi d one is ha i can combine he
co ec ing pa h wo k wi h he same objec model. In adi ional
me hods all hese wo k a e analyzed using di e en me hods
o each wo ks.
In ollowing wo ks o example as obo s, like snake, goes
as e in la ge en i onmen s, some imes he sho es dis ance
canno be a eled ma hema ically in he leas ime. Changing
he obo ‘s size he a ea ha big obo s i in can be used o
de e mine he a ea ha snake like obo ‘s can go as e .
REFERENCES
[1] T. Lozano-Pe ez e M. A., Wesley, ―An algo i hm o planning
collision- ee pa hs among polyhed al obs acles,‖ Commun. O ACM,
22 (1979), 560-570
[2] S e en M. LaValle, Planning Algo i hms, Camb idge Uni e si y P ess,
2006, ISBN 0-521-86205-1.
[3] B. Chazelle, ―App oxima ion and decomposi ion o shapes,‖ In J. T.
Schwa z and C. K. Yap, edi o s, Algo i hmic and Geome ic Aspec s o
Robo ics, pages 145–185. Law ence E lbaum Associa es, Hillsdale, NJ,
1987.
[4] F. Au enhamme , ‗‗Vo onoi diag ams—a su ey o a undamen al
geome ic da a s uc u e,‘‘ ACM Compu . Su ., ol. 23, no. 3, pp. 345–
405, 1991.
[5] J.C. La ombe, Robo Mo ion Planning, Kluwe Academic Publishe s
1991
[6] O.Kha ib, ―Real- ime obs acle a oidance o manipula o s and mobile
obo s,‖ The In e na ional Jou nal o Robo ics Resea ch, Vol. 5, No. 1,
1986
[7] Nilsson N.J., ―A mobile au oma on: an applica ion o a i icial
in elligence echniques,‖ P oc. 1. In . Join Con . On A i icial
In elligence Washing on D.C, 509-520 1969
Recen Inno a ions in Mecha onics (RIiM) Vol. 2. (2015). No. 1-2.
DOI: 10.17667/ iim.2015.1-2/14.
4
[8] J.C. La ombe, ―Mo ion planning: a jou ney o obo s molecules digi al
ac o s and o he a i ac s,‖ The In e na ional Jou nal o Robo ics
Resea ch 30: 846-894 1999
[9] Udupa,S., ―Collision de ec ion and a oidance in compu e con olled
manipula o s,‖ Ph.D. Disse a ion, Dep . o Elec ical Enginee ing,
Cali o nia Ins i u e o Technology Pasadena, CA. 1977
[10] Lozano Pe ez T. e Wesley M.A., ―An algo i hm o planning collision
ee pa hs among polyhed al obs acles,‖ Comm. ACM 22(10):560-570
1979
[11] Lozano Pe ez T., ―S a ial planning: a con igu a ion space app oach,‖
IEEE T . Compu e s, C-32(2):108-120 1983
[12] Ka aki, L. E., P. S es ka, J-C. La ombe, e M. O e ma s,
"P obabilis ic oadmaps o pa h planning in high dimensional
con igu a ion spaces," IEEE T ansac ions on Robo ics and Au oma ion,
ol. 12, issue 4, no. 4, pp. 566-580, 1996.
[13] S. M. LaValle and J. J. Ku ne , ―Randomized kinodynamic planning In
P oceedings,‖ IEEE In e na ional Con e ence on Robo ics and
Au oma ion, pages 473--479, 1999