Congestion-Aware Policy Synthesis for Multirobot Systems

Multirobot 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 maneuver to avoid each other. Congestion can adversely affect navigation performance and increase the duration of navigation actions. In this article, we present a multirobot planning framework that utilizes learnt probabilistic models of how congestion affects navigation duration. Central to our framework is a probabilistic reservation table, which summarizes 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 behavior.