Back to search

Institutional Repository of Vilnius University

Daugelio agentų kelio paieškos algoritmų analizė /

Abstract

dc:description

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

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Mečelė, Almantas,. Daugelio agentų kelio paieškos algoritmų analizė /. Institutional Repository of Vilnius University, 2026. https://repository.vu.lt/VU:ELABAETD308337961&prefLang=en_US