Spectral Clustering in Rule-Based Algorithms for Multi-Agent Path Finding

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00371966" target="_blank" >RIV/68407700:21240/23:00371966 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Spectral Clustering in Rule-Based Algorithms for Multi-Agent Path Finding

Popis výsledku v původním jazyce

We focus on rule-based algorithms for multi-agent path finding (MAPF) in this paper. MAPF is a task of finding non-conflicting paths connecting agents’ specified initial and goal positions in a shared environment specified via an undirected graph. Rule-based algorithms use a fixed set of predefined primitives 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 component and move agents to their goal cluster first before the rule-based algorithm is applied. The benefit of this approach is twofold: (1) the 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

Popis výsledku anglicky

We focus on rule-based algorithms for multi-agent path finding (MAPF) in this paper. MAPF is a task of finding non-conflicting paths connecting agents’ specified initial and goal positions in a shared environment specified via an undirected graph. Rule-based algorithms use a fixed set of predefined primitives 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 component and move agents to their goal cluster first before the rule-based algorithm is applied. The benefit of this approach is twofold: (1) the 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í

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

Proceedings of the 20th International Conference on Informatics in Control, Automation and Robotics

ISBN

978-989-758-670-5

ISSN

2184-2809

e-ISSN

—

Počet stran výsledku

8

Strana od-do

258-265

Název nakladatele

SciTePress

Místo vydání

Madeira

Místo konání akce

Rome

Datum konání akce

13. 11. 2023

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

WRD - Celosvětová akce

Kód UT WoS článku

—