On Path Selection for Reduction-Based Solving of Multi-Agent Pathfinding Using Graph Pruning

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10507209" target="_blank" >RIV/00216208:11320/25:10507209 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1609/socs.v18i1.35991" target="_blank" >https://doi.org/10.1609/socs.v18i1.35991</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1609/socs.v18i1.35991" target="_blank" >10.1609/socs.v18i1.35991</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Path Selection for Reduction-Based Solving of Multi-Agent Pathfinding Using Graph Pruning

Popis výsledku v původním jazyce

Multi-agent pathfinding is the task of navigating a set of mo bile agents in a shared environment such that they avoid col lisions. Finding an optimal solution in terms of the length of the plan is known to be a computationally hard problem (NP-Hard). In general, there are two schools of optimal al gorithms: search-based and reduction-based. While search based algorithms excel in solving large maps where few con flicts can be expected, reduction-based algorithms excel in smaller instances even when agents interact often. However, the reduction-based approaches lag behind in large instances, even with few agents. To mitigate this, a subgraph pruning method was introduced to prune unnecessary vertices to de crease the size of the instance. The pruning is based on the shortest paths for each agent. In the original study, the authors randomly selected the shortest routes. In this study, we repli cate the overall approach while selecting the initial shortest path with more care. We provide several approaches for se lecting one of the possible shortest paths and experimentally compare them. We note that when the makespan optimal plan is needed, not all agents are required to use the shortest path, as only the longest path dictates the makespan. Using this observation, we also introduce an approach that selects longer paths for some agents if it helps to reduce the total number of interactions between agents. We provide an experimental comparison of all proposed approaches and show that the lat ter performs significantly better, in most cases outperforming any approach that strictly selects only the shortest path.

Název v anglickém jazyce

On Path Selection for Reduction-Based Solving of Multi-Agent Pathfinding Using Graph Pruning

Popis výsledku anglicky

Multi-agent pathfinding is the task of navigating a set of mo bile agents in a shared environment such that they avoid col lisions. Finding an optimal solution in terms of the length of the plan is known to be a computationally hard problem (NP-Hard). In general, there are two schools of optimal al gorithms: search-based and reduction-based. While search based algorithms excel in solving large maps where few con flicts can be expected, reduction-based algorithms excel in smaller instances even when agents interact often. However, the reduction-based approaches lag behind in large instances, even with few agents. To mitigate this, a subgraph pruning method was introduced to prune unnecessary vertices to de crease the size of the instance. The pruning is based on the shortest paths for each agent. In the original study, the authors randomly selected the shortest routes. In this study, we repli cate the overall approach while selecting the initial shortest path with more care. We provide several approaches for se lecting one of the possible shortest paths and experimentally compare them. We note that when the makespan optimal plan is needed, not all agents are required to use the shortest path, as only the longest path dictates the makespan. Using this observation, we also introduce an approach that selects longer paths for some agents if it helps to reduce the total number of interactions between agents. We provide an experimental comparison of all proposed approaches and show that the lat ter performs significantly better, in most cases outperforming any approach that strictly selects only the shortest path.

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í

2025

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 Symposium on Combinatorial Search

ISBN

978-1-57735-901-2

ISSN

2832-9171

e-ISSN

2832-9163

Počet stran výsledku

5

Strana od-do

186-190

Název nakladatele

AAAI Press

Místo vydání

Neuveden

Místo konání akce

Glasgow, United Kingdom

Datum konání akce

12. 8. 2025

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

WRD - Celosvětová akce

Kód UT WoS článku

—