Određivanje topološkog svojstva grafa primjenom strojnog učenja i konsenzusa

master's thesis

• Title (english): Determining the topological property of a graph using machine learning and consensus
• Author: Matea Španić
• Mentor: Stjepan Bogdan (mentor)
• Committee member: Zdenko Kovačić (član povjerenstva)
• Committee member: Stjepan Bogdan (predsjednik povjerenstva)
• Committee member: Goran Vasiljević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-09, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Electrical Engineering

Abstract

U ovome se radu obrađuje problem decentralizirnog određivanja minimalnog nezavisnog
dominantnog seta grafa. Nakon uvoda o višeagentnim sustavima i matematičke
podloge, minimalni nezavisni dominantni set definiran je kao topološko svojstvo grafa
povezanosti višeagentnog sustava. Nadalje, konsenzus algoritam je predstavljen kao
alat koji omogućuje da se svi agenti dogovore oko određene odluke. Da bi se ta odluka
donijela, korišteno je potporno učenje. Prvo je upotrijebljen centralizirani algoritam
Q-učenja. Nakon što su dobiveni pozitivni rezultati, decentralizirano Q-učenje je istraženo
i implementirano. Različita poboljšanja decentraliziranog algoritma
testirana su na nekoliko tipičnih klasa grafova. Naposljetku, rezultati različitih metoda
su uspoređeni i analizirani.

Abstract (english)

This thesis is concerned with the problem of decentralized determining the minimal independent dominating set of a graph. After giving the introduction about the multi-agent systems and mathematical preliminaries, the minimum independent dominating set was defined as a topological property of a connectivity graph in a multi-agent system. Next, consensus algorithm was presented as a tool which enables that all of the agents agree on a certain decision. To make that decision, reinforcement learning is used. First, a centralized version of the Q-learning was applied. After receiving positive results, decentralized Q-learning algorithm was investigated and implemented. Furthermore, different improvements to decentralized algorithm were tested on several typical graph classes. Finally, the results of the different methods are compared and analyzed.

• Keywords: minimalni nezavisni dominantni set; višeagentni sustav; Q-učenje; potporno učenje; konsenzus; decentralizacija
• Keywords (english): minimal independent dominating set; multi-agent system; Q-learning; reinforcement learning; consensus; decentralization
• Language: english
• URN:NBN: urn:nbn:hr:168:606214
• 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: 2023-01-13 13:58:31