prikaz prve stranice dokumenta Razvoj i evaluacija efikasnog algoritma planiranja staze u multi-agentskom sustavu
No public access
master's thesis
Razvoj i evaluacija efikasnog algoritma planiranja staze u multi-agentskom sustavu
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2016. urn:nbn:hr:168:574859
Karolj, Valentina
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Karolj, V. (2016). Razvoj i evaluacija efikasnog algoritma planiranja staze u multi-agentskom sustavu (Master's thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:574859

Karolj, Valentina. "Razvoj i evaluacija efikasnog algoritma planiranja staze u multi-agentskom sustavu." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2016. https://urn.nsk.hr/urn:nbn:hr:168:574859

Karolj, Valentina. "Razvoj i evaluacija efikasnog algoritma planiranja staze u multi-agentskom sustavu." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2016. https://urn.nsk.hr/urn:nbn:hr:168:574859

Karolj, V. (2016). 'Razvoj i evaluacija efikasnog algoritma planiranja staze u multi-agentskom sustavu', Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 02 November 2024, https://urn.nsk.hr/urn:nbn:hr:168:574859

Karolj V. Razvoj i evaluacija efikasnog algoritma planiranja staze u multi-agentskom sustavu [Master's thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2016 [cited 2024 November 02] Available at: https://urn.nsk.hr/urn:nbn:hr:168:574859

V. Karolj, "Razvoj i evaluacija efikasnog algoritma planiranja staze u multi-agentskom sustavu", Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2016. Available at: https://urn.nsk.hr/urn:nbn:hr:168:574859

Metadata
TitleRazvoj i evaluacija efikasnog algoritma planiranja staze u multi-agentskom sustavu
Title (english)Design and Evaluation of Efficient Multi-Agent Path Planning Algorithm
AuthorValentina Karolj
MentorStjepan Bogdan (mentor)
Committee memberStjepan Bogdan (predsjednik povjerenstva)
Committee memberZdenko Kovačić (član povjerenstva)
Committee memberMatko Orsag (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2016-04-20, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Electrical Engineering
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languageenglish
URN:NBNurn:nbn:hr:168:574859
Study programmeTitle: Electrical Engineering and Information Technology
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra inženjer/inženjerka elektrotehnike i informacijske tehnologije (magistar/magistra inženjer/inženjerka elektrotehnike i informacijske tehnologije)
Type of resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2018-02-06 09:35:50