Spectral Clustering in Rule-Based Algorithms for Multi-Agent Path Finding
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Spectral Clustering in Rule-Based Algorithms for Multi-Agent Path Finding
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA22-31346S" target="_blank" >GA22-31346S: logicMOVE: Logic Reasoning in Motion Planning for Multiple Robotic Agents</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 20th International Conference on Informatics in Control, Automation and Robotics
ISBN
978-989-758-670-5
ISSN
2184-2809
e-ISSN
—
Number of pages
8
Pages from-to
258-265
Publisher name
SciTePress
Place of publication
Madeira
Event location
Rome
Event date
Nov 13, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—