2020/08/03 by Stepan Dergachev, Dergachev, Stepan, Konstantin Yakovlev +3 · 1 citation
Computer Science · Engineering · #Artificial Intelligence (cs.AI) #Autonomous Vehicle Technology and Safety #FOS: Computer and information sciences #Formal Methods in Verification #I.2.11 #I.2.8 #I.2.9 #Multiagent Systems (cs.MA) #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2008.01227
openalex publication_date 2020/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of multi-agent navigation in static environments when no\ncentralized controller is present. Each agent is controlled individually and\nrelies on three algorithmic components to achieve its goal while avoiding\ncollisions with the other agents and the obstacles: i) individual path planning\nwhich is done by Theta* algorithm; ii) collision avoidance while path following\nwhich is performed by ORCA* algorithm; iii) locally-confined multi-agent path\nplanning done by Push and Rotate algorithm. The latter component is crucial to\navoid deadlocks in confined areas, such as narrow passages or doors. We\ndescribe how the suggested components interact and form a coherent navigation\npipeline. We carry out an extensive empirical evaluation of this pipeline in\nsimulation. The obtained results clearly demonstrate that the number of\noccurring deadlocks significantly decreases enabling more agents to reach their\ngoals compared to techniques that rely on collision-avoidance only and do not\ninclude multi-agent path planning component\n