Integration of Independence Detection into SAT-based Optimal Multi-Agent Path Finding A Novel SAT-based Optimal MAPF Solver

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://dx.doi.org/10.5220/0006126000850095" target="_blank" >http://dx.doi.org/10.5220/0006126000850095</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5220/0006126000850095" target="_blank" >10.5220/0006126000850095</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Integration of Independence Detection into SAT-based Optimal Multi-Agent Path Finding A Novel SAT-based Optimal MAPF Solver

Popis výsledku v původním jazyce

The problem of optimal multi-agent path finding (MAPF) is addressed in this paper. The task is to find optimal paths for mobile agents where each of them need to reach a unique goal position from the given start with respect to the given cost function. Agents must not collide with each other which is a source of combinatorial difficulty of the problem. An abstraction of the problem where discrete agents move in an undirected graph is usually adopted in the literature. Specifically, it is shown in this paper how to integrate independence detection (ID) technique developed for search based MAPF solving into a compilation-based technique that translates the instance of the MAPF problem into propositional satisfiability formalism (SAT). The independence detection technique allows decomposition of the instance consisting of a given number of agents into instances consisting of small groups of agents with no interaction across groups. These small instances can be solved independently and the solution of the original instance is combined from small solutions eventually. The reduction of the size of instances translated to the target SAT formalism has a significant impact on performance as shown in the presented experimental evaluation. The new solver integrating SAT translation and the independence detection is shown to be state-of-the-art in its class for optimal MAPF solving.

Název v anglickém jazyce

Integration of Independence Detection into SAT-based Optimal Multi-Agent Path Finding A Novel SAT-based Optimal MAPF Solver

Popis výsledku anglicky

The problem of optimal multi-agent path finding (MAPF) is addressed in this paper. The task is to find optimal paths for mobile agents where each of them need to reach a unique goal position from the given start with respect to the given cost function. Agents must not collide with each other which is a source of combinatorial difficulty of the problem. An abstraction of the problem where discrete agents move in an undirected graph is usually adopted in the literature. Specifically, it is shown in this paper how to integrate independence detection (ID) technique developed for search based MAPF solving into a compilation-based technique that translates the instance of the MAPF problem into propositional satisfiability formalism (SAT). The independence detection technique allows decomposition of the instance consisting of a given number of agents into instances consisting of small groups of agents with no interaction across groups. These small instances can be solved independently and the solution of the original instance is combined from small solutions eventually. The reduction of the size of instances translated to the target SAT formalism has a significant impact on performance as shown in the presented experimental evaluation. The new solver integrating SAT translation and the independence detection is shown to be state-of-the-art in its class for optimal MAPF solving.

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

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

ICAART: PROCEEDINGS OF THE 9TH INTERNATIONAL CONFERENCE ON AGENTS AND ARTIFICIAL INTELLIGENCE, VOL 2

ISBN

978-989-758-220-2

ISSN

—

e-ISSN

neuvedeno

Počet stran výsledku

11

Strana od-do

85-95

Název nakladatele

SCITEPRESS

Místo vydání

SETUBAL

Místo konání akce

Porto

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

000413244200008