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

Autonomous vehicles are expected to travel in urban environments in the future for increased safety and overall efficiency. They could be of different car brands running different navigation & communication systems that do not share their route-choosing processes or travel data, either due to lack of communication or due to privacy restrictions. To avoid traffic congestion, such as those caused by non-cooperating human drivers nowadays, independent autonomous vehicles need to have a method for distributing traffic in the environment without communication. Motivated by this real-world scenario, in this paper we consider the problem of path planning for a large number of privacy-aware robots in a complex, cluttered indoor or urban environment with uncertainties (other unpredictable agents such as pedestrians), where the robots need to be well-distributed throughout the environment and avoid congestion in any region, but are not allowed to communicate or share their location data or intents with other robots. This is relevant to avoiding congestion in distributed vehicle routing problems when a vehicle's location/intent cannot be shared either due to lack of communication or due to privacy restrictions.