Naslov
Planiranje gibanja mobilnih robota primjenom računalne geometrije
(Mobile robot motion planning using computational geometry)

Autori
Kaluđer, Hrvoje

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, diplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
15.07

Godina
2010

Stranica
52

Mentor
Petrović, Ivan

Neposredni voditelj
Brezak, Mišel

Ključne riječi
graf vidljvosti; dualna transformacija; poligon vidljvosti; uređeni skup
(visibility graph; duality transform; visibility polygon; arrangement)

Sažetak
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.

Izvorni jezik
Hrvatski

Znanstvena područja
Elektrotehnika, Računarstvo, Temeljne tehničke znanosti

POVEZANOST RADA