Motion Planning and Visibility Problems using the Polar Diagram

EUROGRAPHICS 2003 / M. Cho e , H. Hagen and D. Tos Sho P esen a ions Mo ion Planning and Visibili y P oblems using he Pola Diag am C.I. G ima and A. Má quez†L. O ega‡ Abs ac Mo ion planning and isibili y p oblems a e some o he mos impo an opics s udied in Compu e G aphics, Compu a ional Geome y and Robo ics. The e exi s se e al and impo an esul s o hese p oblems. We p opose a new app oach in his pape using a p ep ocessing in he plane, he pola diag am. The pola diag am can be conside ed as a plane essella ion wi h simila cha ac e is ics o he Vo onoi Diag am. The Euclidean dis ance c i e ion is changed by he minimal angle c i e ion in his new app oach. The ad an age o using pola diag ams is an op imal compu ing p ep ocessing ime and hei immedia e applica ions o angle p oblems as isibili y o mo ion planning p oblems. 1. In oduc ion The solu ion o many impo an p oblems in Compu e G aphics equi es angles p ocessing o he da a inpu . In Fig- u e 1a simple isibili y p oblem is p esen ed. The maximum isibili y angle om any poin x, can be easily ound by he compu a ion o angula scanning owa ds he objec s Aand B. Ne e heless, he angula scanning pe o med in his ex- ample is no a p ac ical me hod when he calcula ion is epe - i i e. E e y angula sweep needs a linea p ocessing ime. †Dp o. Ma emá ica Aplicada I, Uni e si y o Se ille, Spain ‡Dp o. In o má ica, Uni e si y o Jaén, Spain x A B C D Figu e 1: Vision angle om he poin x. The locus app oach we p opose, he pola diag am, con- s uc s a essella ion in he plane ha used as p ep ocessing, a oid making exhaus i e sea ches o ind si es wi h mini- mum angle cha ac e is ics. The in o ma ion he pola dia- g am main ain is in insic o i s da a s uc u e in a simila way o he p oximi y p oblem esolu ion using he Vo onoi diag am 16. Bu he aim o his pape is no only he pola diag am de - ini ion o he s udy o op imal algo i hms cons uc ion. This essella ion ha e impo an and in e es ing angle p ope ies. E e y pola egion is he locus o he poin s wi h simila isibili y angle wi h espec o any o he si e. The p oblem p esen ed abo e can be sol ed e icien ly, no only o a de- e mined poin xbu o any poin in he plane. This cha ac e is ic allows us o ace up o he pa h plan- ning p oblem as well. A possible pa h ee o obs acles can be ound sol ing local isibili y p oblems and joining he esul s. This pape p esen he pola diag am o a se o poin s in he plane in Sec ion 2. I s ex ension o any o he geome ic objec is s udied in Sec ion 3. In Sec ion 4we s udy isibili y p oblems and a new me hod o he pa h planning compu a- ion. 2. Pola diag am De ini ion In his sec ion we de ine he pola diag am o a se o poin s in he plane assuming ha his de ini ion can be gene alized o any o he geome ic objec . c The Eu og aphics Associa ion 2003. G ima, Má quez and O ega / Pola Diag ams o Mo ion Planning and Visibili y P si ang Figu e 2: Pola angle. 0 1 2 3 4 S Figu e 3: Pola diag am o S. We in oduce he pola diag am as a plane pa i ion wi h simila ea u es o he Vo onoi diag am. Le us de ine all po- la diag am elemen s. The pola angle o he poin pwi h espec o si, deno ed as angsi(p), is he angle o med by he posi i e ho izon al line o pand he s aigh line joining pand si, as i is shown in Figu e 2. As he pola angle mus be lowe han π,phas less y-coo dina e han si. Gi en a se So npoin s in he plane, he loci o poin s wi h leas posi i e pola angle wi h espec o si∈Sis called pola egion o si, deno ed as PS(si). Thus, PS(si) = n(x,y)∈E2|angsi(x,y)<angsj(x,y),∀j6=io. The plane is di ided in di e en egions in such a way ha i he poin (x,y)∈E2lies in PS(si), i is known ha siis he i s si e ound pe o ming an angula scanning s a ing om (x,y). We can d aw an analogy be ween his angula sweep and he beha io o a ada 9,5. All si∈Scons uc s a pola egion and hese n egions di ide he plane de ining a essella ion we ha e named pola diag am o S, deno ed as P(S). Lines and hal -lines con- s uc ing hese pola egions a e called pola edges. To summa ize, we cons uc a plane essella ion wi h he pola angle c i e ion. Ac ually, he pola diag am cons uc s a pa i ion o he lowes semi-plane. The bounda y is he s aigh ho izon al line c ossing he highes si e o S. In Fig- u e 3is depic ed he pola diag am o a se o poin s in he plane and he inal di ision cons uc ed using he leas pola angle c i e ion. A B C 0 1 2 3 4 5 6 7 0 1 2 3 4 0 1 2 3 4 5 6 7 Figu e 4: Example o polygons pola diag am. 3. Pola diag am o geome ic objec s In 5,9we gi e op imal algo i hms o he pola diag am con- s uc ion using he sweep line and he di ide and conque me hods. O he wise, he e is no jus i ica ion o a plane p e- p ocessing. The as es me hod, he plane sweep, cons uc s he pola egion o si, ones he i−1 poin s wi h g ea e y- coo dina e ha e been p ocessed. As i has been men ioned be o e, plane pa i ions ha e ound lo s o applica ions ields. Howe e in many eal p ob- lems, essella ion gene a o s can no be conside ed elemen- a y poin s. Thus, eali y is ep esen ed using geome ic ob- jec s as segmen s, polygons and ci cles. Some o hese p ob- lems a e p oximi y p oblems, pa h planning and isibili y o illumina ion p oblems. Classical examples o essella ion in he plane a e he Vo onoi diag am o he apezoidal maps. Pola diag am o geome ic objec s is in ac , a new pa i ion o he plane wi h simila cha ac e is ics o he pola diag am o a se o poin s 7,8, and i s de ini ion is eally simila o he gi en o poin s in he plane. Le Obe a se o geome ic ob- jec s in he plane, he pola egion associa ed o oi,PO(oi) is he locus o poin s wi h leas pola angle wi h espec o oi han wi h espec o any o he objec o O, in a posi i e angula scanning s a ing om he ze o angle. The e is an impo an p ope y associa ed o he pola dia- g am o polygons and segmen s: i is con ained in o he pola diag am o he se o poin s made up o hei e ices o end- poin s. An op imal me hod o he pola diag am cons uc ion o a se o geome ic objec s can ollow a sweep inc emen al algo i hm o a se o poin s, bu adding es ic ions in o de o disca d some pola edges o po ions o hem. Following he ollowing ules allows us o elimina e ce ain edges: (1) i he e is any obs acle o he igh o an endpoin , (2) i i spli s wo sec o s o he same pola egion, (3) i an edge po ion lies inside ano he pola egion and (4) i a pola edge lies inside he objec i belongs. We show an example o poly- c The Eu og aphics Associa ion 2003. G ima, Má quez and O ega / Pola Diag ams o Mo ion Planning and Visibili y S a S a R i gh E nd E nd Figu e 5: P ocessed e ices. gons pola diag am in Figu e 4d awing he disca ded edges wi h s iped lines, he es o edges emain. Algo i hm 1desc ibes he echnique o pola diag am cons uc ion o a se o polygons in he plane. The algo i hm ex ension o line segmen s is ob ious, howe e he pola diag am o a se o ci cles needs some o he commen s o each o simila conclusions as we see in 14. Ne e heless, he pola diag am compu a ion o polygons can be imp o ed again because no all e ices belong o a pola edge. The e a e no edges associa ed o e lex e ices and nei he o hose in he le side o a polygon. Only he ollowing e ices, illus a ed in Figu e 5, a e aken in o ac- coun : S a : Ve ex iis a S a e ex i i−1and i+1ha e less y-coo dina e. End: Ve ex iis an End e ex i i−1and i+1ha e g ea e y-coo dina e. Righ : Ve ex iis a Righ e ex i i−1has less y- coo dina e and i+1has g ea e y-coo dina e han i. Algo i hm 1needs an O(nlogn) ime o so all e ices. The inc emen al app oach always wo k in a simila way: e - e y e ex poin is eached om op o bo om and p ocessed acco ding o some condi ions. The e a e n e ices o p o- cess, and hose p elimina y pola egions can be cons uc ed in linea ime. Fo e e y e ex ii is necessa y an addi ional O(logn) ime o ind neighbo s o le and igh in o de o disca d hose edges men ioned be o e, howe e he op imal O(nlogn) ime is no modi ied. To sum up, he pola diag am o polygons can be com- pu ed in a Θ(nlogn) ime, being an op imal p ep ocessing in he plane o isibili y and mo ion planning p oblems. 4. Visibili y p oblems and Mo ion Planning The pola diag am can be conside ed a new geome ic ap- p oach o sol e angle p oblems. This new essella ion ap- plica ions a e he con ex hull o a se o poin s and objec s in he plane 5, isibili y p oblems and i s gene aliza ion o he pa h planning p oblem. The pola diag am ad an ages a e hei obus cons uc ion me hods in op imal compu a- ion ime. Algo i hm 1: Inc emen al Inpu : A se Po Npolygons in E2 Ou pu : P(S) BEGIN 1. So e ices o Pby dec easing o de , ob aining V={ 0, 1,... n−1} 2. Push(s ack, 0) 3. Compu e 0pola edges 4. FOR i=1 o n−1DO a. Be such p ha i∈p b. WHILE op(s ack)oblique edge in e sec s wi h he ho izon al o i i. Pop(s ack) c. Le pRand pLbe he nea es polygons o igh and le o i d. IF iis a con ex and begin e ex THEN i. IF @ano he begin e ex j∈p o he igh o i ii. THEN compu e an ho izon al edge om i eaching o pL i i exis s o o in ini e o he wise iii. IF @pR i . THEN compu e an oblique edge om iwi h g adien op(s ack) ii does no c oss p e. IF iis a con ex and igh e ex THEN i. IF @pRand op(s ack)/∈p ii. THEN compu e an oblique edge om iwi h g adien op(s ack) ii does no c oss p . IF iis con ex and end e ex THEN i. IF op(s ack)/∈pTHEN A. IF ∃pR B. THEN compu e an ho izon al edge om i eaching pLi i exis s o o in ini e o he wise C. ELSE compu e an oblique edge om iwi h g adien op(s ack) i 5. END_FOR 6. Push(s ack,i) END c The Eu og aphics Associa ion 2003. G ima, Má quez and O ega / Pola Diag ams o Mo ion Planning and Visibili y x A B C D Figu e 6: Poin x lies in o he pola egions o A and B. 4.1. Visibili y p oblems Visibili y p oblems a e one o he mos impo an opics in Compu a ional Geome y wi h impo an epe cussions in Compu e G aphics. Some o hese classical p oblems a e he A Galle y 1, Illumina ion 12 and e en he Pa h Planning p oblem 13. We de ine he p oblem shown in Figu e 1as he maximum isibili y angle p oblem in an o hogonal di ec ion. I can be conside ed one o he simples isibili y p oblems, he max- imum isibili y angle om a poin x owa ds any o hogonal di ec ion, Eas , No h, Wes o Sou h. This p oblem can be easily sol ed in linea ime compu ing an angula scanning wi h posi i e and nega i e c i e ia. Bu again, his exhaus i e sea ch can be a oided using pola diag ams. A e he pola diag am de ini ion, i is s aigh o wa d o unde s and ha his isibili y echnique can be imp o ed us- ing his essella ion as p ep ocessing. Objec Ais known o be he i s obs acle ound in a posi i e angula sweep s a - ing om poin x. This in o ma ion is gi en by he pola di- ag am in a loga i hmic ime, he ime we need o loca e his poin in o a pola egion. Howe e , he leas posi i e pola angle c i e ion is no sui able o ind objec B. In ac , i is necessa y a nega i e angula scanning ins ead o a posi i e one. Bu again, po- la diag ams can be use ul in his sea ch, we only need o change he pola diag am c i e ion o cons uc ion o ind a di e en essella ion wi h simila cha ac e is ics. In Figu e 6i has been supe imposed hese wo Eas pola diag ams. Poin xbelongs o di e en pola egions depending on he used c i e ion. When his ci cums ance happens, as we ob- se e in Figu e 7wi h he poin x, i always means ha he isibili y angle is null. Poin pis in bo h cases in Bpola e- x x B A B A p p Figu e 7: Pola diag ams in he ze o angle. gions, so we know his objec hinde s in a ajec o y owa ds he Eas di ec ion, in ac , his is he only objec we should a oid in a Eas ajec o y. Theo em 1 Gi en a se o ngeome ic objec s in he plane, he pola diag am can be used as p ep ocessing o ind he maximum o hogonal isibili y angle p oblem in O(logn) ime. P oo I is s aigh o wa d o p o e his heo em aking in o ac- coun ha o any o hogonal di ec ion, bo h pola diag ams can be compu ed in O(nlogn) ime. A poin loca ion in a pola egion is known o be ound in loga i hmic ime. Ne e heless, no only o hogonal isibili y p oblems can be sol ed using pola diag ams. The gene aliza ion o any o he di ec ion is he key o deal wi h o he geome ic angle p oblems. I we p e end o p o ide a obo wi h au oma ic mo emen , o simula e isi s o i ual scenes gene a ed in a andom way, o o ind a solu ion o collision de ec ion p oblem, pola diag ams can be used as p ep ocessing in he plane o imp o e compu a ion imes. These and o he isibil- i y p oblems applica ions can be aken in o accoun o some in e es a eas in Compu e G aphics. We gi e in he nex sec- ion an in oduc ion o he pa h planning p oblem. 4.2. Pa h planning The mo ion planning pu pose is o p o ide a mobile ob- jec wi h he capaci y o au oma ic decision abou any kind o mo emen among di e en obs acles. This mobile objec uses o be a obo , hus, any new p oposal in he esolu ion o his p oblem can be conside ed a Compu e G aphics and Compu a ional Geome y con ibu ion o he Robo ics. Se e al algo i hms ha e been de eloped o pa h planning p oblems, we ind an exhaus i e su ey in 13. One o he mos impo an cons uc s he isibili y g aph, in which e - e y wo e ices a e connec ed wi h edges i one e ex is isible om he o he . The esul ing g aph is he inpu o he Dijks a algo i hm 2. Using he isibili y g aph, i is possible o ind he mini- mum pa h om an o igin and a des ina ion. Ne e heless he c The Eu og aphics Associa ion 2003. G ima, Má quez and O ega / Pola Diag ams o Mo ion Planning and Visibili y Figu e 8: Pa h planning in a 2D scene. pa h planning solu ion using he isibili y g aph can no be conside ed a as me hod. In some si ua ions i is mo e de- si able a quickes echnique han he bes one. Some o he imes, he minimum pa h does no comply some condi ions. An example o non op imal pa h planning algo i hm is gi en by Kedem 11. This p oposal pe o ms a apezoidal map o he ee obs acles space, compu ing e ical lines om e e y e ex while ano he obs acle is no in e sec ed. Using his O(nlogn)p ep ocessing o he plane, a se o ee obs acles a eas is ound, and a pa h planning algo i hm can be compu ed. The pola diag am echnique o he pa h planning esolu- ion is also based in he iden i ica ion o a se o ee obs a- cles egions. In he p e ious sec ion, we ha e ound a new me hod based on pola diag ams o sol e he maximum is- ibili y angle p oblem. A new pa h planning solu ion can be seen as a chain o poin s in such a way ha each o hem can see i s successo . All hese poin s a e ound using he pai o pola diag ams in a de e mined di ec ion. The esul is a polygonal line joining all hese isible poin s. We use he pola diag am o he ollowing mo ion plan- ning p oblem app oach. I is conside ed a sys em in which he e exis s a se o plana objec s. We assume ha he shape and loca ion o hese objec s a e known. Gi en a ini ial posi- ion oand a des ine poin d, he pa h planning p oblem aim is o ind a ee obs acles ajec o y joining oand d. An ex- ample is shown in Figu e 8. We ocus ou s udy in a simpli ica ion o he p oblem in- oduced abo e: he mo emen o a poin objec in a wo- dimensional en i onmen . Pola diag ams used in isibili y p oblems a e he key o unde s and how we can mo e o- wa ds a de e mined di ec ion. Fo example, whene e poin xlies in o he pola egion o he same objec using he wo Eas di ec ion pola diag ams, we do know ha his objec is he only one obs uc ing any mo emen owa ds his di- ec ion. In he opposi e case, a Eas mo emen is gua an eed and he e a ee obs acles pa h exis s. Howe e , a alid pa h be ween o igin and des ina ion is no always owa ds an o hogonal di ec ion. Obse e Figu e O D Figu e 9: Pa h be ween o igin and des ina ion. Figu e 10: Vec o decomposi ion in o o hogonal compo- nen s. 9, e en hough he ec o joining poin oand dhas a clea ly Sou h di ec ion, a Wes mo emen is necessa y a he end o he ou e. In he gene al case, he ec o −→ od can be decom- posed in wo o hogonal componen s, an ho izon al and a e ical componen . These new ho izon al and e ical ec- o s de e mine he di ec ion o he pai s o pola diag ams o use. As i is depic ed in Figu e 10, ec o −→ od has been decomposed gi ing he pai s o 0 and 3π/2 angle pola dia- g ams. I any isibili y p oblem in an o hogonal di ec ion is sol ed using only a pai o pola diag ams, any o he di ec- ion equi es wo pola diag ams pai s, he ones gi en by he di ec ion ec o . The pa h planning p oblem uses he echnique desc ibed abo e. In o de o de ine a alid pa h be ween a o igin and des ina ion poin , we main ain eigh pola diag ams, wo in e e y o hogonal di ec ion. In e e y s ep a ho izon al, e i- cal o oblique mo emen is decided, depending on he −→ od de- composi ion. A eason o decide one o hese ypes o mo e- men s can be he p oximi y o he des ina ion. Once a alid mo emen ha e been p ocessed he o igin poin changes, and a new ajec o y ec o is ob ained. I is ob ious ha inally he p ocess inishes when he dis ance be ween o igin and des ina ion is ze o. Figu es 11 and 12 show wo di e en examples o ajec- o ies. Bo h cases ha e a common p ope y, he o igin and des ina ion ec o ha e a Sou h-Eas di ec ion, being neces- sa y wo pai s o pola diag ams o he pa h planning eso- lu ion. This ci cums ance and he simplici y o he examples ha e been chosen o unde s anding, howe e he 2D scene complexi y does no modi y he mechanism ollowed. When a pai o pola diag ams ha e p o ided a po ion o ajec- c The Eu og aphics Associa ion 2003. G ima, Má quez and O ega / Pola Diag ams o Mo ion Planning and Visibili y Figu e 11: Eas di ec ion pola diag ams. Figu e 12: Sou h di ec ion pola diag ams. o y, a ed a ow is d awn, o he wise his a ow appea s in g ey colo . Example 1: The i s example is depic ed in Figu es 11 and 12 using a polygonal line wi h 1 as i s sub-index. The ini ial ec o −−−→ o11d1changes e e y ime ha i s o igin changes. The i s mo emen chosen is ho izon al because i ob ains a nea e posi ion o he des ina ion d1. O igin o11 lies in o he bo h pola egions associa ed o Ain he Eas di ec ion. We do know his is he only objec ha obs uc a ho izon al ajec o y. We choose he o hogo- nal mo emen because objec Bcould in e sec s wi h he s aigh line joining o11 and o12. Howe e is i s aigh - o wa d o imp o e hese o hogonal mo emen s because he pola diag am main ains in o ma ion abou adjacen egions and consequen ly abou adjacen objec s. Once poin o12 is eached, he Sou h pai o pola dia- g ams is chosen because o12 and he des ina ion d1belong o he same pai o egions and a ee pa h be ween hen is gua an eed. Example 2: In his o he example, we i s ly choose he Sou h pola diag ams pai o pe o m a mo emen jus owa ds he on ie o he pola egion whe e o21 lies. Again, he e ical ajec o y is mo e in e es ing because o he inal p oximi y o d2. F om poin o22, a pa h ee o obs acles owa ds o23 is gua an eed because o22 belongs o di e en objec s pola egions. Finally, any o he pai s depic ed in bo h igu es allows o each des ina ion d2. In bo h cases, pola egions in which poin s o23 and d2lies, a e exac ly he same ones. The numbe o s eps o inalize he p ocess is as much he numbe o pola egions c ossed whose numbe uses o be lowe han me hods like apezoidal maps. Ano he issue no discussed a he momen a e he local minimum poin s. A e e y momen a e ical o ho izon al pa h mus be decided, i a local minimum is de ec ed, we always ha e an al e na- i e pa h o con inue, adding only an inclusion es o he algo i hm. E en when his me hod does no always ind an op i- mal pa h, some ad an ages ha e o be aken in o accoun : he pola diag am compu a ion is a Φ(nlogn)p ep ocessing ime ha can be compu ed o di e en geome ic objec s and p o ide a in ui i e echnique o sol e isibili y and pa h planning p oblems. Re e ences 1. V. Ch á al.Acombina o ial heo emin plane geome y. J. Combin. Theo y, Se . B. 1975. 4 2. E. W. Dijks a. A no e on wo p oblems in connec ion wi h g aphs . Numbe . Ma h. 1959. 4 3. R. L. G aham. An e icien algo i hm o de e mining he con ex hull o a ini e plana se . In o m. P ocess. Le ., 1:132-133, 1972. 4. C. I. G ima, A. Má quez. Compu a ional Geome y on Su aces. Kulwe Academic Publishe s, 2001. 5. C. I. G ima, A. Má quez y L. O ega. A locus ap- p oach o angle p oblems in compu a ional geome y. 14 h Eu opean Wo kshop in Compu a ional Geome y, Ba celona, 1998. 2,3 6. C. I. G ima, A. Má quez y L. O ega. A locus app oach o angle p oblems in compu a ional geome y. We and Disc e e, Da win (Aus alia), 1998. 7. C. I. G ima, A. Má quez y L. O ega. Diag ama pola de obje os geomé icos. IX Cong eso Español de In o - má ica G á ica, Jaén, 1999. 2 c The Eu og aphics Associa ion 2003. G ima, Má quez and O ega / Pola Diag ams o Mo ion Planning and Visibili y 8. C. I. G ima, A. Má quez y L. O ega. Pola diag ams o geome ic objec s. 15 h Eu opean Wo kshop in Compu- a ional Geome y, An ibes (F ancia), 1999. 2 9. C. I. G ima, A. Má quez y L. O ega. Un p ep oce- samien o pa a p oblemas de ángulos en Geome ía Compu acional. VIII Cong eso Español de In o má ica G á ica, Ou ense, 1998. 2 10. R. A. Ja is. On he iden i ica ion o he con ex hull o a ini e se o poin s in he plane. In o. P oc. Le ., 2:18-21, 1973. 11. K. Kedem y M. Sha i . An e icien algo i hm o plan- ning collision- ee asla ional mo ion o con ex polyg- onal objec in 2-dimensional space amids polygonal obs cles. In P oc. 1s Annu. ACM Sympos. Compu . Geom., 1985. 5 12. V. Klee. Is e e y polygonal egion illumina ed om some poin ?. Ame . Ma h. Mon hly. 1969. 4 13. J. C. La ombe, Robo Mo ion Planning, Academic Pub- lishe s, Bos on 1991. 4 14. L. O ega. El Diag ama Pola . Tesis Doc o al. Uni e - sidad de Se illa. 2002. 3 15. L. O ega, A. Rueda, C. G ima, A. Má quez. Camino en e obs áculos usando diag amas pola es. XI Con- g eso Español de In o má ica G á ica, Ge ona, 2001. 16. G.M. Vo onoi. Nou elles applica ions des pa amè es con inus à la hèo ie des o mes quad a iques. deux- ième Mémoi e: Reche ches su les pa allélloèd es p imi i s. J. Reine Angew. Ma h. 1908. 1 c The Eu og aphics Associa ion 2003.