Congestion-Aware Policy Synthesis for Multi-Robot Systems

Charlie Street; Sebastian Pütz; Manuel Mühlig; Nick Hawes; Bruno Lacerda

In: IEEE Transactions on Robotics (T-RO), Vol. 36, IEEE, 2021.


Multi-robot systems must be able to maintain performance when robots get delayed during execution. For mobile robots, one source of delays is congestion. Congestion occurs when robots deployed in shared physical spaces interact, as robots present in the same area simultaneously must manoeuvre to avoid each other. Congestion can adversely affect navigation performance, and increase the duration of navigation actions. In this paper, we present a multi-robot planning framework which utilises learnt probabilistic models of how congestion affects navigation duration. Central to our framework is a probabilistic reservation table which summarises robot plans, capturing the effects of congestion. To plan, we solve a sequence of single-robot time-varying Markov automata, where transition probabilities and rates are obtained from the probabilistic reservation table. We also present an iterative model refinement procedure for accurately predicting execution-time robot performance. We evaluate our framework with extensive experiments on synthetic data and simulated robot behaviour.

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence