Večagentno planiranje poti z algoritmom CBSLOVŠIN, JAN (Avtor) Klančar, Gregor (Mentor) CBS algoritemoptimalne potivečagentni algoritemiskanje trkovCCBS algoritemICBS algoritemIskanje poti za skupino agentov in koordinirano gibanje v skupnem okolju je osnovni problem večagentnih sistemov. Algoritme za večagentno planiranje poti lahko delimo v optimalne in podoptimalne. Iskanje optimalnih rešitev je zahtevno, saj prostor stanj raste eksponentno s številom agentov in zato problem ni rešljiv v polinomskem času. V primeru večjega števila agentov se uporabljajo podoptimalni algoritmi, ki hitro najdejo izvedljive rešitve. CBS (angl. Conflict-Based Search) algoritem je večagentni algoritem, ki deluje na osnovi iskanja trkov med agenti in deluje na dveh nivojih. Nižji nivo je namenjen iskanju optimalne poti posameznega agenta. Višji nivo pa preverja konflikte med agenti, gradi drevo konfliktov z detekcijo trkov med agenti in išče najboljšo rešitev brez trkov. Zaradi delovanja na dveh nivojih je veliko hitrejši od algoritma $A^{*}$, saj algoritem CBS ne upošteva opcij, kjer ne more priti do optimalne poti. Slabost algoritma se pokaže, ko imamo prostor, kjer je med računanjem do neke točke optimalnih poti več. Takrat mora algoritem preveriti vse poti in preveriti, če je katera izmed njih boljša. Namen diplomske naloge je pregled in spoznavanje delovanja algoritma CBS in njegovih nadgradenj, prav tako pa primerjati algoritem CBS z nekaterimi ostalimi algoritmi ter primerjanje algoritma CBS z njegovimi izboljšavami.20222022-09-15 14:50:00Diplomsko delo/naloga140551VisID: 59601COBISS_ID: 122259203sl