Combining Strengths of Optimal Multi-Agent Path Finding Algorithms

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10408108" target="_blank" >RIV/00216208:11320/19:10408108 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Combining Strengths of Optimal Multi-Agent Path Finding Algorithms

Popis výsledku v původním jazyce

The problem of multi-agent path finding (MAPF) is studied in this paper. Solving MAPF optimally is a computationally hard problem and many different optimal algorithms have been designed over the years. These algorithms have good runtimes for some problem instances, while performing badly for other instances. Interestingly, these hard instances are often different across the algorithms. This leads to an idea of combining the strengths of different algorithms in such a way that an input problem instance is split into disjoint subproblems and each subproblem is solved by appropriate algorithm resulting in faster computation than using either of the algorithms for the whole instance. By manual problem decomposition we will empirically show that the above idea is viable. We will also sketch a possible future work on automated problem decomposition.

Název v anglickém jazyce

Combining Strengths of Optimal Multi-Agent Path Finding Algorithms

Popis výsledku anglicky

The problem of multi-agent path finding (MAPF) is studied in this paper. Solving MAPF optimally is a computationally hard problem and many different optimal algorithms have been designed over the years. These algorithms have good runtimes for some problem instances, while performing badly for other instances. Interestingly, these hard instances are often different across the algorithms. This leads to an idea of combining the strengths of different algorithms in such a way that an input problem instance is split into disjoint subproblems and each subproblem is solved by appropriate algorithm resulting in faster computation than using either of the algorithms for the whole instance. By manual problem decomposition we will empirically show that the above idea is viable. We will also sketch a possible future work on automated problem decomposition.

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/GA19-02183S" target="_blank" >GA19-02183S: Chytré roje: od teorie k praxi</a><br>

Návaznosti

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

Rok uplatnění

2019

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

Proceedings of the 11th International Conference on Agents and Artificial Intelligence

ISBN

978-989-758-350-6

ISSN

—

e-ISSN

—

Počet stran výsledku

6

Strana od-do

226-231

Název nakladatele

scitepress

Místo vydání

neuveden

Místo konání akce

Prague

Datum konání akce

19. 2. 2019

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

WRD - Celosvětová akce

Kód UT WoS článku

—