Solving Multi-Agent Pathfinding with Stochastic Local Search SAT Algorithms
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00379350" target="_blank" >RIV/68407700:21240/24:00379350 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.5220/0012944800003822" target="_blank" >https://doi.org/10.5220/0012944800003822</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.5220/0012944800003822" target="_blank" >10.5220/0012944800003822</a>
Alternative languages
Result language
angličtina
Original language name
Solving Multi-Agent Pathfinding with Stochastic Local Search SAT Algorithms
Original language description
This paper explores the suitability of Stochastic Local Search (SLS) solvers for Multi-Agent Pathfinding (MAPF) translated into the SAT domain. Traditionally, SAT encodings of MAPF have been tackled using Conflict-Driven Clause Learning (CDCL) solvers, but this work investigates the potential of SLS solvers, particularly ProbSAT, in solving MAPF under the makespan objective. By employing the MDD-SAT approach and comparing the performance of ProbSAT against the Glucose 4 CDCL solver, the effects of eager and lazy encodings are evaluated, as well as the benefit of providing initial variable assignments. Results show that ProbSAT can effectively solve MAPF instances, especially when initial assignments based on agents' shortest paths are provided. This study suggests that SLS solvers can compete with CDCL solvers in specific MAPF scenarios and highlights future research directions for optimizing SLS performance in MAPF.
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
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2024
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
21st International Conference on Informatics in Control, Automation and Robotics - Volume 1
ISBN
978-989-758-717-7
ISSN
2184-2809
e-ISSN
—
Number of pages
12
Pages from-to
67-78
Publisher name
Science and Technology Publications, Lda
Place of publication
Setúbal
Event location
Porto
Event date
Nov 18, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—