Reduction-based Solving of Multi-agent Pathfinding on Large Maps Using Graph Pruning

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455484" target="_blank" >RIV/00216208:11320/22:10455484 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Reduction-based Solving of Multi-agent Pathfinding on Large Maps Using Graph Pruning

Popis výsledku v původním jazyce

Multi-agent pathfinding is the problem of finding collision-freepaths for a set of agents. Solving this problem optimally is computationally hard, therefore many techniques based on reductions toother formalisms were developed. In comparison to search-basedtechniques, the reduction-based techniques fall behind on largemaps even for a small number of agents. To combat this phenomenon, we propose several strategies for pruning vertices off largeinstances that will most likely not be used by agents. First, weintroduce these strategies conceptually and prove which of themmaintain completeness and optimality. Eventually, we conduct anexhaustive evaluation and show that graph pruning strategies makereduction-based solvers comparable to search-based techniques onlarge maps while maintaining their advantage on small dense maps.

Název v anglickém jazyce

Reduction-based Solving of Multi-agent Pathfinding on Large Maps Using Graph Pruning

Popis výsledku anglicky

Multi-agent pathfinding is the problem of finding collision-freepaths for a set of agents. Solving this problem optimally is computationally hard, therefore many techniques based on reductions toother formalisms were developed. In comparison to search-basedtechniques, the reduction-based techniques fall behind on largemaps even for a small number of agents. To combat this phenomenon, we propose several strategies for pruning vertices off largeinstances that will most likely not be used by agents. First, weintroduce these strategies conceptually and prove which of themmaintain completeness and optimality. Eventually, we conduct anexhaustive evaluation and show that graph pruning strategies makereduction-based solvers comparable to search-based techniques onlarge maps while maintaining their advantage on small dense maps.

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í

2022

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

International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)

ISBN

978-1-71385-433-3

ISSN

—

e-ISSN

—

Počet stran výsledku

9

Strana od-do

624-632

Název nakladatele

International Foundation for Autonomous Agents and Multiagent Systems

Místo vydání

neuveden

Místo konání akce

Auckland, NZ

Datum konání akce

9. 5. 2022

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

WRD - Celosvětová akce

Kód UT WoS článku

—