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

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

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)

Project

<a href="/en/project/GA22-31346S" target="_blank" >GA22-31346S: logicMOVE: Logic Reasoning in Motion Planning for Multiple Robotic Agents</a><br>

Continuities

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

Publication year

2022

Confidentiality

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

Article name in the collection

Proceedings of the Fifteenth International Symposium on Combinatorial Search

ISBN

978-1-57735-873-2

ISSN

—

e-ISSN

—

Number of pages

3

Pages from-to

317-319

Publisher name

Association for the Advancement of Artificial Intelligence (AAAI)

Place of publication

Palo Alto, California

Event location

Vídeň

Event date

Jul 21, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—