Multi-agent Path Finding with Generalized Conflicts: An Experimental Study
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F19%3A00335766" target="_blank" >RIV/68407700:21240/19:00335766 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Multi-agent Path Finding with Generalized Conflicts: An Experimental Study
Original language description
This paper gives an overview of conflict reasoning in generalizations of multi-agent path finding (MAPF). MAPF and derived variants assume items placed in vertices of an undirected graph with at most one item per vertex. Items can be relocated across edges while various constraints depending on the concrete type of relocation problem must be satisfied. We recall a general problem formulation that encompasses known types of item relocation problems such as multi-agent path finding (MAPF), token swapping (TSWAP), token rotation (TROT), and token permutation (TPERM). We then focused on three existing optimal algorithms for MAPF: search-based CBS, and propositional satisfiability (SAT) - based MDD-SAT and SMT-CBS. These algorithms were modified to tackle various types of conflicts. The major contribution of this paper is a thorough experimental evaluation of CBS, MDD-SAT, and SMT-CBS on various types of relocation problems.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-17966S" target="_blank" >GA19-17966S: intALG-MAPFg: Intelligent Algorithms for Generalized Variants of Multi-Agent Path Finding</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Agents and Artificial Intelligence - 11th International Conference (ICAART 2019), Revised Selected Papers
ISBN
978-3-030-37493-8
ISSN
0302-9743
e-ISSN
—
Number of pages
25
Pages from-to
118-142
Publisher name
Springer-Verlag
Place of publication
Berlin
Event location
Praha
Event date
Feb 19, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—