PRVO: Probabilistic Reciprocal Velocity Obstacle for multi robot navigation under uncertainty

Abstract

We present PRVO, a probabilistic variant of Reciprocal Velocity Obstacle (RVO) for decentralized multi-robot navigation under uncertainty. PRVO characterizes the space of velocities that would allow each robot to fulfill its share in collision avoidance with a specified probability. PRVO is modeled as chance constraints over the velocity level constraints defined by RVO and takes into account the uncertainty associated with both state estimation as well as the actuation of each robot. Since chance constraints are in general computationally intractable, we propose a series of reformulations which when combined with time scaling based concepts leads to a closed form characterization of solution space of PRVO for a given probability of collision avoidance. We validate our formulation through numerical simulations in which we highlight the advantages of PRVO over the related existing formulations.