IEEE International Conference on Automation Science and Engineering, volume 2021-August, pages 1489-1494

Distributed Multi-Agent Navigation Based on Reciprocal Collision Avoidance and Locally Confined Multi-Agent Path Finding

Dergachev Stepan ¹

Yakovlev Konstantin ¹

Hide authors affiliations Show authors affiliations: 1 affiliation

HSE University and Federal Research Center for Computer Science and Control of Russian Academy of Sciences,Moscow,Russia

National Research University Higher School of Economics

Federal Research Center Computer Science and Control of the Russian Academy of Sciences

Publication type: Proceedings Article

Publication date: 2021-08-23

—

DOI: 10.1109/CASE49439.2021.9551564

Copy DOI

Abstract

Avoiding collisions is the core problem in multiagent navigation. In decentralized settings, when agents have limited communication and sensory capabilities, collisions are typically avoided in a reactive fashion, relying on local ob-servations/communications. Prominent collision avoidance techniques, e.g. ORCA, are computationally efficient and scale well to a large number of agents. However, in numerous scenarios, involving navigation through the tight passages or confined spaces, deadlocks are likely to occur due to the egoistic behaviour of the agents and as a result, the latter can not achieve their goals. To this end, we suggest an application of the locally confined multi-agent path finding (MAPF) solvers that coordinate sub-groups of the agents that appear to be in a deadlock (to detect the latter we suggest a simple, yet efficient ad-hoc routine). We present a way to build a grid-based MAPF instance, typically required by modern MAPF solvers. We evaluate two of them in our experiments, i.e. Push And Rotate and a bounded-suboptimal version of Conflict Based Search (ecbs), and show that their inclusion into the navigation pipeline significantly increases the success rate, from 15% to 99% in certain cases.

By date By citations

Citations by journals

	1 2
IEEE Robotics and Automation Letters	IEEE Robotics and Automation Letters, 2, 33.33% IEEE Robotics and Automation Letters 2 publications, 33.33%
Symmetry	Symmetry, 1, 16.67% Symmetry 1 publication, 16.67%
Artificial Intelligence Review	Artificial Intelligence Review, 1, 16.67% Artificial Intelligence Review 1 publication, 16.67%
	1 2

Citations by publishers

	1 2 3 4
IEEE	IEEE, 4, 66.67% IEEE 4 publications, 66.67%
Multidisciplinary Digital Publishing Institute (MDPI)	Multidisciplinary Digital Publishing Institute (MDPI), 1, 16.67% Multidisciplinary Digital Publishing Institute (MDPI) 1 publication, 16.67%
Springer Nature	Springer Nature, 1, 16.67% Springer Nature 1 publication, 16.67%
	1 2 3 4

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,2024],"ids":[0,0,0],"codes":[0,0,0],"imageUrls":["","",""],"datasets":[{"label":"Citations number","data":[1,3,2],"backgroundColor":["#3B82F6","#3B82F6","#3B82F6"],"percentage":["16.67","50","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 Robotics and Automation Letters","Symmetry","Artificial Intelligence Review"],"ids":[12376,21974,4329],"codes":[0,0,0],"imageUrls":["\/storage\/images\/resized\/6scCJegesojp2jubwY3uKCzTAmgsaH2GIFlg6Hfk_medium.webp","\/storage\/images\/resized\/MjH1ITP7lMYGxeqUZfkt2BnVLgjkk413jwBV97XX_medium.webp","\/storage\/images\/resized\/voXLqlsvTwv5p3iMQ8Dhs95nqB4AXOG7Taj7G4ra_medium.webp"],"datasets":[{"label":"","data":[2,1,1],"backgroundColor":["#3B82F6","#3B82F6","#3B82F6"],"percentage":[33.33,16.67,16.67],"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","Multidisciplinary Digital Publishing Institute (MDPI)","Springer Nature"],"ids":[6953,202,8],"codes":[0,0,0],"imageUrls":["\/storage\/images\/resized\/6scCJegesojp2jubwY3uKCzTAmgsaH2GIFlg6Hfk_medium.webp","\/storage\/images\/resized\/MjH1ITP7lMYGxeqUZfkt2BnVLgjkk413jwBV97XX_medium.webp","\/storage\/images\/resized\/voXLqlsvTwv5p3iMQ8Dhs95nqB4AXOG7Taj7G4ra_medium.webp"],"datasets":[{"label":"","data":[4,1,1],"backgroundColor":["#3B82F6","#3B82F6","#3B82F6"],"percentage":[66.67,16.67,16.67],"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 |

Cite this

GOST Copy

Dergachev S., Yakovlev K. Distributed Multi-Agent Navigation Based on Reciprocal Collision Avoidance and Locally Confined Multi-Agent Path Finding // IEEE International Conference on Automation Science and Engineering. 2021. Vol. 2021-August. pp. 1489-1494.

GOST all authors (up to 50) Copy

RIS |

Cite this

RIS Copy

TY - CPAPER

DO - 10.1109/CASE49439.2021.9551564

UR - https://doi.org/10.1109%2FCASE49439.2021.9551564

TI - Distributed Multi-Agent Navigation Based on Reciprocal Collision Avoidance and Locally Confined Multi-Agent Path Finding

T2 - IEEE International Conference on Automation Science and Engineering

AU - Dergachev, Stepan

AU - Yakovlev, Konstantin

PY - 2021

DA - 2021/08/23 00:00:00

SP - 1489-1494

VL - 2021-August

ER -

BibTex

Cite this

BibTex Copy

@inproceedings{2021_Dergachev,

author = {Stepan Dergachev and Konstantin Yakovlev},

title = {Distributed Multi-Agent Navigation Based on Reciprocal Collision Avoidance and Locally Confined Multi-Agent Path Finding},

year = {2021},

volume = {2021-August},

pages = {1489--1494},

month = {aug}

}

Found error?

Publisher

—

Profiles