Sparse Decision Diagrams for SAT-based Compilation of Multi-Agent Path Finding (Extended Abstract).

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00360953" target="_blank" >RIV/68407700:21240/22:00360953 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1609/socs.v15i1.21798" target="_blank" >https://doi.org/10.1609/socs.v15i1.21798</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1609/socs.v15i1.21798" target="_blank" >10.1609/socs.v15i1.21798</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Sparse Decision Diagrams for SAT-based Compilation of Multi-Agent Path Finding (Extended Abstract).

Popis výsledku v původním jazyce

Multi-agent path finding (MAPF) represents a task of finding non-colliding paths for agents via which they can navigate from their initial positions to specified goal positions. Contemporary optimal solving algorithms include dedicated search-based methods, that solve the problem directly, and compilation-based algorithms that reduce MAPF to a different formalism for which an efficient solver exists. In this paper, we enhance the existing Boolean satisfiability-based (SAT) algorithm for MAPF via using sparse decision diagrams representing the set of candidate paths for each agent, from which the target Boolean encoding is derived, considering more promising paths before the less promising ones are taken into account. Suggested sparse diagrams lead to a smaller target Boolean formulae that can be constructed and solved faster while optimality guarantees of the approach are kept. Specifically, considering the candidate paths sparsely instead of considering them all makes the SAT-based approach more competitive for MAPF on large maps.

Název v anglickém jazyce

Sparse Decision Diagrams for SAT-based Compilation of Multi-Agent Path Finding (Extended Abstract).

Popis výsledku anglicky

Multi-agent path finding (MAPF) represents a task of finding non-colliding paths for agents via which they can navigate from their initial positions to specified goal positions. Contemporary optimal solving algorithms include dedicated search-based methods, that solve the problem directly, and compilation-based algorithms that reduce MAPF to a different formalism for which an efficient solver exists. In this paper, we enhance the existing Boolean satisfiability-based (SAT) algorithm for MAPF via using sparse decision diagrams representing the set of candidate paths for each agent, from which the target Boolean encoding is derived, considering more promising paths before the less promising ones are taken into account. Suggested sparse diagrams lead to a smaller target Boolean formulae that can be constructed and solved faster while optimality guarantees of the approach are kept. Specifically, considering the candidate paths sparsely instead of considering them all makes the SAT-based approach more competitive for MAPF on large maps.

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/GA22-31346S" target="_blank" >GA22-31346S: logicMOVE: Logické uvažování v plánování pohybu pro mnoho robotických agentů</a><br>

Návaznosti

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

Rok uplatnění

2022

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

Proceedings of the Fifteenth International Symposium on Combinatorial Search

ISBN

978-1-57735-873-2

ISSN

—

e-ISSN

—

Počet stran výsledku

3

Strana od-do

317-319

Název nakladatele

Association for the Advancement of Artificial Intelligence (AAAI)

Místo vydání

Palo Alto, California

Místo konání akce

Vídeň

Datum konání akce

21. 7. 2022

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

WRD - Celosvětová akce

Kód UT WoS článku

—