Variants of independence detection in SAT-based optimal multi-agent path finding

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10381950" target="_blank" >RIV/00216208:11320/17:10381950 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/chapter/10.1007%2F978-3-319-93581-2_7" target="_blank" >https://link.springer.com/chapter/10.1007%2F978-3-319-93581-2_7</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-93581-2_7" target="_blank" >10.1007/978-3-319-93581-2_7</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Variants of independence detection in SAT-based optimal multi-agent path finding

Popis výsledku v původním jazyce

In multi-agent path finding (MAPF) on graphs, the task is to find paths for distinguishable agents so that each agent reaches its unique goal vertex from the given start while collisions between agents are forbidden. A cumulative objective function is often minimized in MAPF. The main contribution of this paper consists in integrating independence detection technique (ID) into a compilation-based MAPF solver that translates MAPF instances into propositional satisfiability (SAT). The independence detection technique in search-based solvers tries to decompose a given MAPF instance into instances consisting of small groups of agents with no interaction across groups. After the decomposition phase, small instances are solved independently and the solution of the original instance is combined from individual solutions to small instances. The presented experimental evaluation indicates significant reduction of the size of instances translated to the target SAT formalism and positive impact on the overall performance of the solver.

Název v anglickém jazyce

Variants of independence detection in SAT-based optimal multi-agent path finding

Popis výsledku anglicky

In multi-agent path finding (MAPF) on graphs, the task is to find paths for distinguishable agents so that each agent reaches its unique goal vertex from the given start while collisions between agents are forbidden. A cumulative objective function is often minimized in MAPF. The main contribution of this paper consists in integrating independence detection technique (ID) into a compilation-based MAPF solver that translates MAPF instances into propositional satisfiability (SAT). The independence detection technique in search-based solvers tries to decompose a given MAPF instance into instances consisting of small groups of agents with no interaction across groups. After the decomposition phase, small instances are solved independently and the solution of the original instance is combined from individual solutions to small instances. The presented experimental evaluation indicates significant reduction of the size of instances translated to the target SAT formalism and positive impact on the overall performance of the solver.

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/8G15027" target="_blank" >8G15027: INTEGRACE HEURISTICKÉHO PROHLEDÁVÁNÍ A KOMPILAČNÍCH TECHNIK PRO HLEDÁNÍ CEST S MNOHA AGENTY</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

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

Lecture Notes in Computer Science

ISBN

978-3-319-93580-5

ISSN

0302-9743

e-ISSN

neuvedeno

Počet stran výsledku

21

Strana od-do

116-136

Název nakladatele

Springer Verlag

Místo vydání

Neuveden

Místo konání akce

Porto; Portugal

Datum konání akce

24. 2. 2017

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

WRD - Celosvětová akce

Kód UT WoS článku

000443493600007