Planiranje gibanja mobilnih robota primjenom računalne geometrije (CROSBI ID 362835)
Ocjenski rad | diplomski rad
Podaci o odgovornosti
Kaluđer, Hrvoje
Petrović, Ivan
Brezak, Mišel
hrvatski
Planiranje gibanja mobilnih robota primjenom računalne geometrije
Računalna geometrija ima značajnu ulogu u planiranju gibanja vozila. Najčešće se primjenjuju grafovi vidljivosti za planiranje najkraće putanje. U radu je implementiran modificirani Asanov algoritam za određivanje poligona vidljivosti i grafova vidljvosti. Implementacija je provedena pomoću CGAL biblioteke i pripadajućih joj klasa. Iako je ideja određivanja grafa vidljvosti veoma intuitivna postupak je veoma vremenski zahtjevan te je cilj postići što manju složenost algoritma. Algoritam je ostvaren u dva koraka : u prvom se provodi polarno sortiranje točaka korištenjem dualne transformacije, a u drugom se određuje vidljivost među samim točkama. Testiranje algoritma je provedeno nad dva skupa poligona – kvadratnim, pravilnim i gušće raspoređenim te trokutastim, raštrkanim i slučajno raspoređenim. Dobiveni rezultati upućuju da složenost postupka raste s kvadratom broja točaka testnih poligona i nešto je manja za uzorke s raštrkanim (rijeđe rapoređenim) poligonima. Prednost ovdje opisane metode leži u činjenici da se može primjeniti u slučaju dinamičkih promijena u okolini (ne zahtjeva ponovno proračunavanje grafa vidljvosti za sve točke već lokalno osvježava graf) pa je veoma praktična za online proračun grafova vidljvosti.
graf vidljvosti; dualna transformacija; poligon vidljvosti; uređeni skup
nije evidentirano
engleski
Mobile robot motion planning using computational geometry
nije evidentirano
visibility graph; duality transform; visibility polygon; arrangement
nije evidentirano
Podaci o izdanju
52
15.07.2010.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Fakultet elektrotehnike i računarstva
Zagreb