Sparse Real-time Decision Diagrams for Continuous Multi-Robot Path Planning
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F21%3A00356867" target="_blank" >RIV/68407700:21240/21:00356867 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1109/ICTAI52525.2021.00021" target="_blank" >https://doi.org/10.1109/ICTAI52525.2021.00021</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/ICTAI52525.2021.00021" target="_blank" >10.1109/ICTAI52525.2021.00021</a>
Alternative languages
Result language
angličtina
Original language name
Sparse Real-time Decision Diagrams for Continuous Multi-Robot Path Planning
Original language description
Multi-robot path planning (MRPP) is the task of finding non-conflicting paths for robots via which they can navigate themselves to specified individual goal positions. MRPP uses an undirected graph to represent a shared environment in which the robots move instantaneously between vertices in discrete time steps. Such discrete formulation enables relatively simple algorithms, often based on multi-valued decision diagrams (MDDs) that represent possible paths for each robot, but results in an inaccurate modeling of the real robotic task. Recently introduced continuous variant of MRPP assumes fixed trajectories for robots and fully continuous time but is more difficult to be addressed algorithmically. The set of possible paths for individual robots in the continuous variant can be represented in real-time decision diagram (RDD) which however is often too large. An improvement of RDDs based on sparsification that includes paths into RDD according to their heuristic prioritization is suggested in this short paper. We show that sparse RDDs can improve existing compilation-based algorithms significantly while keeping their optimality guarantees.
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
2021
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
2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI)
ISBN
978-1-6654-0898-1
ISSN
1082-3409
e-ISSN
2375-0197
Number of pages
6
Pages from-to
91-96
Publisher name
IEEE Computer Society
Place of publication
Los Alamitos
Event location
Washington
Event date
Nov 1, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000747482300013