Multi-agent path planning with the CBS algorithm

Iskanje 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.Finding a path for a group of agents and coordinated movement in a common environment is a fundamental problem of multi-agent systems. Algorithms for multi-agent route planning can be divided into optimal and suboptimal. Finding optimal solutions is challenging as the state space grows exponentially with the number of agents and therefore the problem cannot be solved in polynomial time. Therefore, in the case of a larger number of agents suboptimal algorithms are used which quickly find viable solutions. The CBS (Conflict-Based Search) algorithm is a multi-agent algorithm that works on the basis of searching for conflicts between agents and works on two levels. The low level search is dedicated to find the optimal path of a single agent at a time. At the high level, search is performed on a tree based algorithm with a help of conflicts between agents. Because it is a two-level algorithm, it is much faster than the $A^{*}$ algorithm since the CBS algorithm examines fewer states while still maintaining optimality. A weakness of the algorithm occurs when we have an open space. There are a few optimal paths during this calculation. In this case, the algorithm must examine all of them to see if there is a better one. The purpose of the diploma thesis is to review and learn about the operation of the CBS algorithm and its improvements, as well as to compare the CBS algorithm with some of the other algorithms and to compare the CBS algorithm with its improvements