Spectral Clustering in Rule-based Algorithms for Multi-agent Path Finding (Extended Abstract).

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00381395" target="_blank" >RIV/68407700:21240/24:00381395 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Spectral Clustering in Rule-based Algorithms for Multi-agent Path Finding (Extended Abstract).

Popis výsledku v původním jazyce

We address rule-based algorithms for multi-agent path finding (MAPF). MAPF is a task of finding non-conflicting paths connecting agents' initial and goal positions in a shared environment specified via an undirected graph. Rule-based algorithms use a fixed set of predefined primitive operations to move agents to their goal positions in a complete manner. We propose to apply spectral clustering on the underlying graph to decompose the graph into highly connected components and move agents to their goal cluster first before the rule-based algorithm is applied. The benefit of this approach is twofold: (1) the rule-based algorithms are often more efficient on highly connected clusters and (2) we can potentially run the algorithms in parallel on individual clusters.

Název v anglickém jazyce

Spectral Clustering in Rule-based Algorithms for Multi-agent Path Finding (Extended Abstract).

Popis výsledku anglicky

We address rule-based algorithms for multi-agent path finding (MAPF). MAPF is a task of finding non-conflicting paths connecting agents' initial and goal positions in a shared environment specified via an undirected graph. Rule-based algorithms use a fixed set of predefined primitive operations to move agents to their goal positions in a complete manner. We propose to apply spectral clustering on the underlying graph to decompose the graph into highly connected components and move agents to their goal cluster first before the rule-based algorithm is applied. The benefit of this approach is twofold: (1) the rule-based algorithms are often more efficient on highly connected clusters and (2) we can potentially run the algorithms in parallel on individual clusters.

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/GA22-31346S" target="_blank" >GA22-31346S: logicMOVE: Logické uvažování v plánování pohybu pro mnoho robotických agentů</a><br>

Návaznosti

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

Rok uplatnění

2024

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 Seventeenth International Symposium on Combinatorial Search (SoCS 2024)

ISBN

978-1-57735-891-6

ISSN

2832-9171

e-ISSN

2832-9163

Počet stran výsledku

2

Strana od-do

281-282

Název nakladatele

AAAI Press

Místo vydání

Menlo Park

Místo konání akce

Kananaskis

Datum konání akce

6. 6. 2024

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

WRD - Celosvětová akce

Kód UT WoS článku

—