{"id":{"repo_id":"vilnius","oai_identifier":"oai:vu.lt:elaba:308337961"},"canonical_url":"https://search.ndltd.org/etd/vilnius/oai:vu.lt:elaba:308337961","repository":{"repo_id":"vilnius","name":"Vilnius University","base_url":"https://epublications.vu.lt/oai"},"display":{"title":"Daugelio agentų kelio paieškos algoritmų analizė /","abstract":"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.","abstract_html":"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&#x27;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.","abstract_has_math":false,"creators":["Mečelė, Almantas,"],"institution":"Institutional Repository of Vilnius University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-11-19T10:12:59Z","subjects":[],"languages":["lit"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://repository.vu.lt/VU:ELABAETD308337961&prefLang=en_US","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://repository.vu.lt/VU:ELABAETD308337961&prefLang=en_US","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":"open","embargo_until":null,"access_note":null},"source_record":{"url":"https://epublications.vu.lt/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Avu.lt%3Aelaba%3A308337961","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Mečelė, Almantas,"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2026"]},{"key":"dc:publisher","label":"Institution","values":["Institutional Repository of Vilnius University"]},{"key":"dc:relation","label":"Dc Relation","values":["https://epublications.vu.lt/object/elaba:308337961/308337961.pdf"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/bachelorThesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["lit"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://repository.vu.lt/VU:ELABAETD308337961&prefLang=en_US"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Daugelio agentų kelio paieškos algoritmų analizė /","Analysis of multi-agent pathfinding algorithms."]}]}],"canonical_facts":{"dc:creator":["Mečelė, Almantas,"],"dc:date":["2026"],"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."],"dc:format":["application/pdf"],"dc:identifier":["https://repository.vu.lt/VU:ELABAETD308337961&prefLang=en_US"],"dc:language":["lit"],"dc:publisher":["Institutional Repository of Vilnius University"],"dc:relation":["https://epublications.vu.lt/object/elaba:308337961/308337961.pdf"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:title":["Daugelio agentų kelio paieškos algoritmų analizė /","Analysis of multi-agent pathfinding algorithms."],"dc:type":["info:eu-repo/semantics/bachelorThesis"]},"updated_at":"2026-11-19T10:12:59Z"}