An algorithm of avoiding obstacles with intelligent objects

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