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.
|
