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

master's thesis

• Title (english): Design and Evaluation of Efficient Multi-Agent Path Planning Algorithm
• Author: Valentina Karolj
• Mentor: Stjepan Bogdan (mentor)
• Committee member: Stjepan Bogdan (predsjednik povjerenstva)
• Committee member: Zdenko Kovačić (član povjerenstva)
• Committee member: Matko Orsag (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2016-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: Multi-agentski sustavi; planiranje puta; odabir voditelja; RRT; DFS; Adopt; izbjegavanje sudara; globalni optimum; funkcija troška
• Keywords (english): Multi-agent systems; path planning; leader election; RRT; DFS; Adopt; collision avoidance; global optimum; cost function
• Language: english
• URN:NBN: urn:nbn:hr:168:574859
• Study programme: Title: 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 resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 09:35:50