Sparse Real-time Decision Diagrams for Continuous Multi-Robot Path Planning

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Sparse Real-time Decision Diagrams for Continuous Multi-Robot Path Planning

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Sparse Real-time Decision Diagrams for Continuous Multi-Robot Path Planning

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-17966S" target="_blank" >GA19-17966S: intALG-MAPFg: Inteligentní algoritmy pro zobecněné varianty multi-agetního hledání cest</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI)

ISBN

978-1-6654-0898-1

ISSN

1082-3409

e-ISSN

2375-0197

Počet stran výsledku

6

Strana od-do

91-96

Název nakladatele

IEEE Computer Society

Místo vydání

Los Alamitos

Místo konání akce

Washington

Datum konání akce

1. 11. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000747482300013