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