Večagentno iskanje poti z algoritmom CCBSSedej, Matic (Avtor) Klančar, Gregor (Mentor) načrtovanje potivečagentno iskanje potivarni intervalizaznavanje konfliktovalgoritem CBSalgoritem SIPPalgoritem CCBSMagistrsko delo obravnava problem večagentnega iskanja poti za skupino transportnih vozil, kjer je okolje predstavljeno z zemljevidom cest in nato pretvorjeno v graf prehajanja stanj. Iskanja v grafu izvedemo po zgledu sodobnih, v literaturi nedavno objavljenih, algoritmov iskanja v grafu na osnovi reševanja konfliktov, kot sta CCBS in CBS. Poleg svoje izvedbe algoritma predlagamo tudi nadgradnjo za učinkovitejše zaznavanje in reševanje konfliktov. Algoritem CCBS (ang. Continuous Conflic Based Search) je dvonivojski algoritem in temelji na iskanju konfliktov med agenti, pri čemer upošteva njihovo geometrijsko obliko. Algoritem CCBS deluje v zveznem časovnem prostoru in zato omogoča optimalnejšo rešitev, kot na primer CBS (ang. Conflic Based Search), ki deluje v diskretnem prostoru. CCBS na spodnjem nivoju uporablja algoritem SIPP (ang. Safe Interval Path Plannnig), ki je nadgradnja algoritma A* na način, da med iskanjem optimalne poti upošteva tudi varne intervale vozlišč ter povezav. Na zgornjem nivoju pa se izvaja iskanje najboljšega vozlišča v drevesu omejitev. Vozlišča v drevesu omejitev se ustvarijo z vsakim novo odkritim konfliktom med agenti. Učinkovitost in hitrost algoritma CCBS sta odvisni tudi od zaznavanja konfliktov. V ta namen smo predstavili dve različni obliki zaznavanja konfliktov, ki delujeta skupaj. Prva deluje na osnovi prilagodljivega vzorčenja poti agentov in zazna vse vrste konfliktov, tudi tiste, ki se zgodijo v različnih vozliščih in povezavah, vendar je zaradi vzorčenja računsko zahtevna. Druga deluje na osnovi preverjanja zasedenosti intervalov vozlišč in povezav agentov ter je računsko veliko manj zahtevna, vendar zazna le konflikte v istih vozliščih in povezavah. Algoritem CCBS je, tako kot podobni optimalni algoritmi, zaradi računske zahtevnosti v praktičnih primerih omejen na manjše število agentov in preprostejše oziroma manjše grafe prehajanja stanj. Njihova računska zahtevnost se namreč veča eksponentno z večanjem števila agentov.20232023-12-18 10:00:00Magistrsko delo/naloga153106VisID: 62557COBISS_ID: 180790019sl