  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.
