Design and Evaluation of Efficient Multi-Agent Path Planning Algorithm : master thesis - Karolj, Valentina (V. Karolj, 2016)
Sažetak na hrvatskom: Efikasno planiranje puta u multi-agentskom sustavima je od iznimno važno kako bi se spriječili sudari s drugim agentima uz istovremeno postizanje optimizacije funkcije troška za sustav. Neki od prethodnih radova u ovome području pristupili su rješenju koje zahtjeva potpuno povezanost mreže, uvjet koji nije uvijek lako ostvariv u primjeni zbog ograničenja dometa komunikacije. Ovaj rad se fokusira na razvoj koncepta koji ne zahtijeva potpunu povezanost između agenta. Mreža u sustavu može biti povezana ili nepovezani, pri čemu agentu nije potrebno znanje o ukupnom broju ostalih agenta u sustavu. Za planiranje gibanja roboti primjenu RRT planer puta, uz definiranje puta kao distribuiranog ograničenja u sustavu. Za planiranje gibanja u multi-agentskom sustavu primijenjena je proširena verzija Adopt-a, algoritma s teorijskom potvrdom za postizanje globalnog optimuma i rješavanja distribuiranog optimizacijskog problema, istovremeno dopuštajući pritom agentima da djeluju asinkrono i komuniciraju samo na lokalnoj razini sa svojim susjedima. Adopt ima ugrađeni mehanizam detektiranja završetka algoritma koji garantira da je da će svaki agent odabrati put koji pridonosi globalnom optimumu te da neće biti u sudaru s ostalim agentima koji su dio povezane mreže. Rezultati postignute algoritamske podloge uz odgovarajuću programsku arhitekturu su ispitani i potvrđeni simulacijom te verificirani eksperimentalno. Kao rezultat, dobiveno je da algoritam ostvaruje najbolje rezultate u slabo povezanim mrežama. Zaključno, dizajnirana arhitektura u ovome radu se može lako proširiti ne samo na planiranje puta u multi-agentskim sustavima, nego i kao arhitektura za distribuirano istraživanje jata.