Solving Multi-Agent Pathfinding with Stochastic Local Search SAT Algorithms

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

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Solving Multi-Agent Pathfinding with Stochastic Local Search SAT Algorithms

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Solving Multi-Agent Pathfinding with Stochastic Local Search SAT Algorithms

Popis výsledku anglicky

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.

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

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2024

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

21st International Conference on Informatics in Control, Automation and Robotics - Volume 1

ISBN

978-989-758-717-7

ISSN

2184-2809

e-ISSN

—

Počet stran výsledku

12

Strana od-do

67-78

Název nakladatele

Science and Technology Publications, Lda

Místo vydání

Setúbal

Místo konání akce

Porto

Datum konání akce

18. 11. 2024

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

WRD - Celosvětová akce

Kód UT WoS článku

—