Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F21%3A00356866" target="_blank" >RIV/68407700:21240/21:00356866 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/IROS51168.2021.9636296" target="_blank" >https://doi.org/10.1109/IROS51168.2021.9636296</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/IROS51168.2021.9636296" target="_blank" >10.1109/IROS51168.2021.9636296</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes

Popis výsledku v původním jazyce

Path planning for multiple robots (MRPP) represents a task of finding non-colliding paths for robots via which they can navigate from their initial positions to specified goal positions. The problem is often modeled using undirected graphs where robots move between vertices across edges while no two robots can simultaneously occupy the same vertex nor can traverse an edge in opposite directions. Contemporary optimal solving algorithms include dedicated search-based methods, that solve the problem directly, and compilation-based algorithms that reduce MRPP to a different formalism for which an efficient solver exists, such as constraint programming (CP), mixed integer linear programming (MILP), or Boolean satisfiability (SAT). In this paper, we enhance existing SAT-based algorithm for MRPP via sparsification of the set of candidate paths for each robot from which the target Boolean encoding is derived. Suggested sparsification of the set of paths led to a smaller target Boolean formulae that can be constructed and solved faster while optimality guarantees of the approach have been kept.

Název v anglickém jazyce

Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes

Popis výsledku anglicky

Path planning for multiple robots (MRPP) represents a task of finding non-colliding paths for robots via which they can navigate from their initial positions to specified goal positions. The problem is often modeled using undirected graphs where robots move between vertices across edges while no two robots can simultaneously occupy the same vertex nor can traverse an edge in opposite directions. Contemporary optimal solving algorithms include dedicated search-based methods, that solve the problem directly, and compilation-based algorithms that reduce MRPP to a different formalism for which an efficient solver exists, such as constraint programming (CP), mixed integer linear programming (MILP), or Boolean satisfiability (SAT). In this paper, we enhance existing SAT-based algorithm for MRPP via sparsification of the set of candidate paths for each robot from which the target Boolean encoding is derived. Suggested sparsification of the set of paths led to a smaller target Boolean formulae that can be constructed and solved faster while optimality guarantees of the approach have been kept.

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/RSJ International Conference on Intelligent Robots and Systems (IROS)

ISBN

978-1-6654-1714-3

ISSN

2153-0858

e-ISSN

2153-0866

Počet stran výsledku

8

Strana od-do

7931-7938

Název nakladatele

IEEE

Místo vydání

Piscataway

Místo konání akce

Praha

Datum konání akce

27. 9. 2021

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

WRD - Celosvětová akce

Kód UT WoS článku

000755125506042