Multi-Robot Planning Under Uncertainty with Congestion-Aware Models

When planning for multi-robot navigation tasks under uncertainty, plans should prevent robots from colliding while still reaching their goal. Solutions achieving this fall on a spectrum. At one end are solutions which prevent robots from being in the same part of the environment simultaneously at planning time, ignoring the robots' capabilities to manoeuvre around each other, whilst at the other end are solutions that solve the problem at execution time, relying solely on online conflict resolution. Both approaches can lead to inefficient behaviour. In this paper, we present a novel framework in the middle of this spectrum that explicitly reasons over the effect the presence of multiple robots has on navigation performance. We refer to this effect as congestion. We present a structure, called the probabilistic reservation table, which summarises the plans of robots, allowing us to probabilistically model congestion. We show how this structure can be used for planning by proposing an approach that, for each robot, sequentially builds and solves a Markov decision process where the transition probabilities are obtained by querying the probabilistic reservation table. We carry out experiments on synthetic data and in simulation to show the effectiveness of our framework.