A Combination of Theta*, ORCA and Push and Rotate for Multi-agent Navigation
We study the problem of multi-agent navigation in static environments when no centralized controller is present. Each agent is controlled individually and relies on three algorithmic components to achieve its goal while avoiding collisions with the other agents and the obstacles: i) individual path...
Main Authors: | , , |
---|---|
Format: | Article in Journal/Newspaper |
Language: | unknown |
Published: |
arXiv
2020
|
Subjects: | |
Online Access: | https://dx.doi.org/10.48550/arxiv.2008.01227 https://arxiv.org/abs/2008.01227 |
id |
ftdatacite:10.48550/arxiv.2008.01227 |
---|---|
record_format |
openpolar |
spelling |
ftdatacite:10.48550/arxiv.2008.01227 2023-05-15T17:53:33+02:00 A Combination of Theta*, ORCA and Push and Rotate for Multi-agent Navigation Dergachev, Stepan Yakovlev, Konstantin Prakapovich, Ryhor 2020 https://dx.doi.org/10.48550/arxiv.2008.01227 https://arxiv.org/abs/2008.01227 unknown arXiv arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ Multiagent Systems cs.MA Artificial Intelligence cs.AI FOS Computer and information sciences I.2.11; I.2.8; I.2.9 Article CreativeWork article Preprint 2020 ftdatacite https://doi.org/10.48550/arxiv.2008.01227 2022-03-10T15:35:53Z We study the problem of multi-agent navigation in static environments when no centralized controller is present. Each agent is controlled individually and relies on three algorithmic components to achieve its goal while avoiding collisions with the other agents and the obstacles: i) individual path planning which is done by Theta* algorithm; ii) collision avoidance while path following which is performed by ORCA* algorithm; iii) locally-confined multi-agent path planning done by Push and Rotate algorithm. The latter component is crucial to avoid deadlocks in confined areas, such as narrow passages or doors. We describe how the suggested components interact and form a coherent navigation pipeline. We carry out an extensive empirical evaluation of this pipeline in simulation. The obtained results clearly demonstrate that the number of occurring deadlocks significantly decreases enabling more agents to reach their goals compared to techniques that rely on collision-avoidance only and do not include multi-agent path planning component : This is a preprint of the paper accepted to ICR'20. It contains 12 pages and 7 figures Article in Journal/Newspaper Orca DataCite Metadata Store (German National Library of Science and Technology) |
institution |
Open Polar |
collection |
DataCite Metadata Store (German National Library of Science and Technology) |
op_collection_id |
ftdatacite |
language |
unknown |
topic |
Multiagent Systems cs.MA Artificial Intelligence cs.AI FOS Computer and information sciences I.2.11; I.2.8; I.2.9 |
spellingShingle |
Multiagent Systems cs.MA Artificial Intelligence cs.AI FOS Computer and information sciences I.2.11; I.2.8; I.2.9 Dergachev, Stepan Yakovlev, Konstantin Prakapovich, Ryhor A Combination of Theta*, ORCA and Push and Rotate for Multi-agent Navigation |
topic_facet |
Multiagent Systems cs.MA Artificial Intelligence cs.AI FOS Computer and information sciences I.2.11; I.2.8; I.2.9 |
description |
We study the problem of multi-agent navigation in static environments when no centralized controller is present. Each agent is controlled individually and relies on three algorithmic components to achieve its goal while avoiding collisions with the other agents and the obstacles: i) individual path planning which is done by Theta* algorithm; ii) collision avoidance while path following which is performed by ORCA* algorithm; iii) locally-confined multi-agent path planning done by Push and Rotate algorithm. The latter component is crucial to avoid deadlocks in confined areas, such as narrow passages or doors. We describe how the suggested components interact and form a coherent navigation pipeline. We carry out an extensive empirical evaluation of this pipeline in simulation. The obtained results clearly demonstrate that the number of occurring deadlocks significantly decreases enabling more agents to reach their goals compared to techniques that rely on collision-avoidance only and do not include multi-agent path planning component : This is a preprint of the paper accepted to ICR'20. It contains 12 pages and 7 figures |
format |
Article in Journal/Newspaper |
author |
Dergachev, Stepan Yakovlev, Konstantin Prakapovich, Ryhor |
author_facet |
Dergachev, Stepan Yakovlev, Konstantin Prakapovich, Ryhor |
author_sort |
Dergachev, Stepan |
title |
A Combination of Theta*, ORCA and Push and Rotate for Multi-agent Navigation |
title_short |
A Combination of Theta*, ORCA and Push and Rotate for Multi-agent Navigation |
title_full |
A Combination of Theta*, ORCA and Push and Rotate for Multi-agent Navigation |
title_fullStr |
A Combination of Theta*, ORCA and Push and Rotate for Multi-agent Navigation |
title_full_unstemmed |
A Combination of Theta*, ORCA and Push and Rotate for Multi-agent Navigation |
title_sort |
combination of theta*, orca and push and rotate for multi-agent navigation |
publisher |
arXiv |
publishDate |
2020 |
url |
https://dx.doi.org/10.48550/arxiv.2008.01227 https://arxiv.org/abs/2008.01227 |
genre |
Orca |
genre_facet |
Orca |
op_rights |
arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
op_doi |
https://doi.org/10.48550/arxiv.2008.01227 |
_version_ |
1766161261826932736 |