Institutional Repository of Vilnius University
Daugelio agentų kelio paieškos algoritmų analizė /
Abstract
dc:descriptionThis work is dedicated to examining the multi-agent pathfinding Conflict-Based Search (CBS) and Improved Conflict-Based Search algorithms. The work first explores and defines what the multi-agent pathfinding problem is, whereby agents have to move in a graph to reach their destination vertices in the shortest amount of time without colliding with one another. With that, this paper describes the CBS and ICBS algorithms for the given problem definition and conditions. Every part of the CBS algorithm, which consists of high-level and low-level searches, is described in an understandable and implementable manner. Along with CBS, its improved variant, ICBS, is also detailed in this work, describing the improvements that make up the algorithm, such as bypassing conflicts and prioritization of conflicts. The described algorithms were implemented to be used in an experiment to measure and compare their performance in terms of time. The conducted experiment's, which consisted of three sets of 880 multi-agent pathfinding tasks, results show that ICBS is faster and is capable of solving more tasks in under a minute than standard CBS.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Mečelė, Almantas,
Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- lit
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD308337961&prefLang=en_US