Multi-Agent Pathfinding on Large Maps Using Graph Pruning: This Way or That Way?

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10474348" target="_blank" >RIV/00216208:11320/23:10474348 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.5220/0011625100003393" target="_blank" >https://doi.org/10.5220/0011625100003393</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Multi-Agent Pathfinding on Large Maps Using Graph Pruning: This Way or That Way?

Popis výsledku v původním jazyce

Multi-agent pathfinding is the task of navigating a set of agents in a shared environment from their startlocations to their desired goal locations without collisions. Solving this problem optimally is a hard task andvarious algorithms have been devised. The algorithms can generally be split into two categories, search- andreduction-based ones. It is known that reduction-based algorithms struggle with large instances in terms ofthe size of the environment. A recent study tried to mitigate this drawback by pruning some vertices of theenvironment map. The pruning is done based on the vicinity to a shortest path of an agent. In this paper, westudy the effect of choosing such shortest paths. We provide several approaches to choosing the paths and weperform an experimental study to see the effect on the runtime.

Název v anglickém jazyce

Multi-Agent Pathfinding on Large Maps Using Graph Pruning: This Way or That Way?

Popis výsledku anglicky

Multi-agent pathfinding is the task of navigating a set of agents in a shared environment from their startlocations to their desired goal locations without collisions. Solving this problem optimally is a hard task andvarious algorithms have been devised. The algorithms can generally be split into two categories, search- andreduction-based ones. It is known that reduction-based algorithms struggle with large instances in terms ofthe size of the environment. A recent study tried to mitigate this drawback by pruning some vertices of theenvironment map. The pruning is done based on the vicinity to a shortest path of an agent. In this paper, westudy the effect of choosing such shortest paths. We provide several approaches to choosing the paths and weperform an experimental study to see the effect on the runtime.

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

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2023

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

15th International Conference on Agents and Artificial Intelligence

ISBN

978-989-758-623-1

ISSN

2184-433X

e-ISSN

—

Počet stran výsledku

8

Strana od-do

199-206

Název nakladatele

SCITEPRESS

Místo vydání

neuveden

Místo konání akce

Lisbon, Portugal

Datum konání akce

22. 2. 2023

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

WRD - Celosvětová akce

Kód UT WoS článku

—