Open Access
Lecture Notes in Computer Science, volume 12998 LNAI, pages 1-13
Prioritized SIPP for Multi-agent Path Finding with Kinematic Constraints
Ali Zain Alabedeen
1
,
Yakovlev Konstantin
1, 2
Publication type: Book Chapter
Publication date: 2021-09-24
Journal:
Lecture Notes in Computer Science
Quartile SCImago
Q3
Quartile WOS
—
Impact factor: —
ISSN: 03029743, 16113349, 18612075, 18612083
Abstract
Multi-Agent Path Finding (MAPF) is a long-standing problem in Robotics and Artificial Intelligence in which one needs to find a set of collision-free paths for a group of mobile agents (robots) operating in the shared workspace. Due to its importance, the problem is well-studied and multiple optimal and approximate algorithms are known. However, many of them abstract away from the kinematic constraints and assume that the agents can accelerate/decelerate instantaneously (Fig. 1). This complicates the application of the algorithms on the real robots. In this paper, we present a method that mitigates this issue to a certain extent. The suggested solver is essentially, a prioritized planner based on the well-known Safe Interval Path Planning (SIPP) algorithm. Within SIPP we explicitly reason about the speed and the acceleration thus the constructed plans directly take kinematic constraints of agents into account. We suggest a range of heuristic functions for that setting and conduct a thorough empirical evaluation of the suggested algorithm.
Citations by journals
|
1
|
|
|
IEEE/CAA Journal of Automatica Sinica
|
IEEE/CAA Journal of Automatica Sinica
1 publication, 33.33%
|
|
1
|
Citations by publishers
|
1
|
|
|
IEEE
|
IEEE
1 publication, 33.33%
|
|
1
|
- We do not take into account publications that without a DOI.
- Statistics recalculated only for publications connected to researchers, organizations and labs registered on the platform.
- Statistics recalculated weekly.
{"yearsCitations":{"type":"bar","data":{"show":true,"labels":[2022,2023],"ids":[0,0],"codes":[0,0],"imageUrls":["",""],"datasets":[{"label":"Citations number","data":[2,1],"backgroundColor":["#3B82F6","#3B82F6"],"percentage":["66.67","33.33"],"barThickness":null}]},"options":{"indexAxis":"x","maintainAspectRatio":true,"scales":{"y":{"ticks":{"precision":0,"autoSkip":false,"font":{"family":"Montserrat"},"color":"#000000"}},"x":{"ticks":{"stepSize":1,"precision":0,"font":{"family":"Montserrat"},"color":"#000000"}}},"plugins":{"legend":{"position":"top","labels":{"font":{"family":"Montserrat"},"color":"#000000"}},"title":{"display":true,"text":"Citations per year","font":{"size":24,"family":"Montserrat","weight":600},"color":"#000000"}}}},"journals":{"type":"bar","data":{"show":true,"labels":["IEEE\/CAA Journal of Automatica Sinica"],"ids":[6922],"codes":[0],"imageUrls":["\/storage\/images\/resized\/6scCJegesojp2jubwY3uKCzTAmgsaH2GIFlg6Hfk_medium.webp"],"datasets":[{"label":"","data":[1],"backgroundColor":["#3B82F6"],"percentage":[33.33],"barThickness":13}]},"options":{"indexAxis":"y","maintainAspectRatio":false,"scales":{"y":{"ticks":{"precision":0,"autoSkip":false,"font":{"family":"Montserrat"},"color":"#000000"}},"x":{"ticks":{"stepSize":null,"precision":0,"font":{"family":"Montserrat"},"color":"#000000"}}},"plugins":{"legend":{"position":"top","labels":{"font":{"family":"Montserrat"},"color":"#000000"}},"title":{"display":true,"text":"Journals","font":{"size":24,"family":"Montserrat","weight":600},"color":"#000000"}}}},"publishers":{"type":"bar","data":{"show":true,"labels":["IEEE"],"ids":[6953],"codes":[0],"imageUrls":["\/storage\/images\/resized\/6scCJegesojp2jubwY3uKCzTAmgsaH2GIFlg6Hfk_medium.webp"],"datasets":[{"label":"","data":[1],"backgroundColor":["#3B82F6"],"percentage":[33.33],"barThickness":13}]},"options":{"indexAxis":"y","maintainAspectRatio":false,"scales":{"y":{"ticks":{"precision":0,"autoSkip":false,"font":{"family":"Montserrat"},"color":"#000000"}},"x":{"ticks":{"stepSize":null,"precision":0,"font":{"family":"Montserrat"},"color":"#000000"}}},"plugins":{"legend":{"position":"top","labels":{"font":{"family":"Montserrat"},"color":"#000000"}},"title":{"display":true,"text":"Publishers","font":{"size":24,"family":"Montserrat","weight":600},"color":"#000000"}}}}}
Metrics
Cite this
GOST |
RIS |
BibTex
Cite this
GOST
Copy
Ali Z. A., Yakovlev K. Prioritized SIPP for Multi-agent Path Finding with Kinematic Constraints // Lecture Notes in Computer Science. 2021. Vol. 12998 LNAI. pp. 1-13.
GOST all authors (up to 50)
Copy
Ali Z. A., Yakovlev K. Prioritized SIPP for Multi-agent Path Finding with Kinematic Constraints // Lecture Notes in Computer Science. 2021. Vol. 12998 LNAI. pp. 1-13.
Cite this
RIS
Copy
TY - GENERIC
DO - 10.1007/978-3-030-87725-5_1
UR - https://doi.org/10.1007%2F978-3-030-87725-5_1
TI - Prioritized SIPP for Multi-agent Path Finding with Kinematic Constraints
T2 - Lecture Notes in Computer Science
AU - Ali, Zain Alabedeen
AU - Yakovlev, Konstantin
PY - 2021
DA - 2021/09/24 00:00:00
PB - Springer Nature
SP - 1-13
VL - 12998 LNAI
SN - 0302-9743
SN - 1611-3349
SN - 1861-2075
SN - 1861-2083
ER -
Cite this
BibTex
Copy
@incollection{2021_Ali,
author = {Zain Alabedeen Ali and Konstantin Yakovlev},
title = {Prioritized SIPP for Multi-agent Path Finding with Kinematic Constraints},
publisher = {Springer Nature},
year = {2021},
volume = {12998 LNAI},
pages = {1--13},
month = {sep}
}
Profiles