Razvoj i evaluacija efikasnog algoritma planiranja staze u multi-agentskom sustavu

diplomski rad

• Naslov (engleski): Design and Evaluation of Efficient Multi-Agent Path Planning Algorithm
• Autor: Valentina Karolj
• Mentor: Stjepan Bogdan (mentor)
• Član povjerenstva: Stjepan Bogdan (predsjednik povjerenstva)
• Član povjerenstva: Zdenko Kovačić (član povjerenstva)
• Član povjerenstva: Matko Orsag (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2016-04-20, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Elektrotehnika

Sažetak

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.

Sažetak (engleski)

Efficient multi-agent path planning is crucial in order to avoid inter-agent collisions while at the same time optimizing the global cost function for the system. Some of the previous works in this area have taken the approach towards solutions that require a fully connected network which is not always possible in real-time application scenarios with limited communication range. This work focuses on developing a concept that does not require full connection between agents and the network can be either connected or disconnected (where agents do not need to know the total number of agents in the system). For planning individual paths that are represented as distributed constraints, agents are using RRT algorithm and for multi-robot path planning, the developed method works as an extension of Adopt: the algorithm solves a distributed constraint optimization problem while allowing agents act asynchronously using only local communication with a built-in termination protocol which calculates a global optimal solution that minimizes total cost and is collision-free regarding to the connected network. Results are validated with simulations and experiments by proving that the global optimum will always be achieved and that the algorithm is performing very well in sparse networks. Furthermore, designed architecture in this work could be easily extended not only for path planning, but also as an architecture for handling exploration algorithms.

• Ključne riječi: Multi-agentski sustavi; planiranje puta; odabir voditelja; RRT; DFS; Adopt; izbjegavanje sudara; globalni optimum; funkcija troška
• Ključne riječi (engleski): Multi-agent systems; path planning; leader election; RRT; DFS; Adopt; collision avoidance; global optimum; cost function
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:574859
• Studijski program: Naziv: Elektrotehnika i informacijska tehnologija; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka elektrotehnike i informacijske tehnologije (mag. ing. el. techn. inf.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 09:35:50