Načrtovanje gladke poti v trirazsežnem okoljuKrižmančič, Klemen (Avtor) Klančar, Gregor (Mentor) mobilni sisteminačrtovanje potiDijkstrov algoritemalgoritem A*potencialno poljetrilinearna interpolacijaNačrtovanje poti predstavlja postopek določanja optimalne poti od začetne do končne točke. Igra ključno vlogo pri zagotavljanju gibanja mobilnega sistema skozi okolje. Načrtovanje gladke poti predstavlja svojevrsten izziv. Dobljena pot mora upoštevati različne omejitve, predvsem se mora izogibati oviram. Obenem mora biti čim bolj optimalna. Zglajena pot zagotavlja boljše delovanje mobilnega sistema. Cilj magistrskega dela je razvoj algoritma, ki nam generira zglajeno pot v trirazsežnem statičnem okolju. Okolje enakomerno razdelimo na celice v obliki kock, ki jih imenujemo voksli. Celice, na katerih ležijo ovire, so zasedene, ostale so proste. Z uporabo algoritma za iskanje poti, kot je Dijkstrov algoritem ali algoritem A*, za vsako prosto celico določimo razdaljo do ciljne celice. Okolje obravnavamo kot potencialno polje, medtem ko so vrednosti potencialnega polja razdalje, ki smo jih dobili z uporabo Dijkstrovega algoritma ali algoritma A*. Potencialno polje si lahko predstavljamo kot navidezno višino in kroglico, ki se bo v smeri negativnega gradienta pomikala proti globalnemu minimumu. Potencial in gradient v poljubni točki trirazsežnega diskretnega potencialnega polja dobimo z uporabo trilinearne interpolacije potencialnega polja. Zaradi uporabe linearne interpolacije dobljeni negativni gradient ni zvezen in nam ne zagotavlja gladke poti. Za zagotovitev gladke poti uporabimo dodatno interpolacijo gradienta. Rezultat je gladka pot od začetne točke do končne točke, ki se izogne oviram. V rezultatih sta podani primerjava dolžine poti in gladkosti pri uporabi različnih metod iskanja poti ter njihova računska zahtevnost. Ugotovimo, da najkakovostnejšo pot dobimo z uporabo Dijkstrovega algoritma, ki je računsko najzahtevnejši. Računsko zahtevnost lahko zmanjšamo z izbiro manjšega števila sosednjih vozlišč, pri iskanju poti ali z uporabo A* algoritma in ustrezno izbiro hevristike.20242024-07-05 12:45:00Magistrsko delo/naloga159308sl