Coordination-free Multi-robot Path Planning for Congestion Reduction Using Topological Reasoning

We consider the problem of multi-robot path planning in a complex, cluttered environment with the aim of reducing overall congestion in the environment, while avoiding any inter-robot communication or coordination. Such limitations may exist due to lack of communication or due to privacy restriction...

Full description

Saved in:
Bibliographic Details
Published in:Journal of intelligent & robotic systems 2023-07, Vol.108 (3), p.50, Article 50
Main Authors: Wang, Xiaolong, Sahin, Alp, Bhattacharya, Subhrajit
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Collision avoidance
Configuration space path planning
Congestion
Control
Coordination
Electrical Engineering
Engineering
Mechanical Engineering
Mechatronics
Multiple robots
Potential fields
Regular Paper
Robotics
Robots
Topical collection on Unmanned Systems
Trajectory planning
Travel time
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of multi-robot path planning in a complex, cluttered environment with the aim of reducing overall congestion in the environment, while avoiding any inter-robot communication or coordination. Such limitations may exist due to lack of communication or due to privacy restrictions (for example, autonomous vehicles may not want to share their locations or intents with other vehicles or even to a central server). The key insight that allows us to solve this problem is to stochastically distribute the robots across different routes in the environment by assigning them paths in different topologically distinct classes, so as to lower congestion and the overall travel time for all robots in the environment. We outline the computation of topologically distinct paths in a spatio-temporal configuration space and propose methods for the stochastic assignment of paths to the robots. A fast replanning algorithm and a potential field based controller allow robots to avoid collision with nearby agents while following the assigned path. Our simulation and experiment results show a significant advantage over shortest path following under such a coordination-free setup.
ISSN:0921-0296
1573-0409
DOI:10.1007/s10846-023-01878-3