Chance constraint based multi agent navigation under uncertainty
Bharath Gopalakrishnan, Arun Kumar Singh, Meha Kaushik, K. Madhava Krishna, Dinesh Manocha · 2017
In this paper, we present an algorithm for navigating multiple robots under perception and ego-motion uncertainty. Our approach is based on the concept of the Reciprocal Velocity Obstacle which defines a set of constraints for characterizing the space of collision avoidance velocities available to each robot at a given instant in a multi-robot setting. We present a probabilistic variant of RVO obtained by defining chance constraints over the deterministic RVO constraints. Since chance constraints are in general computationally intractable, we present a family of surrogate constraints that can be used as a substitution for the original chance constraints. We show that satisfaction of surrogate constraints ensures satisfaction of original chance constraints with a specific low bound probability. We validate our formulations through numerical simulations in which we highlight the advantages of the proposed formulation over the existing methods, which handle the effect of uncertainty by using conservative bounding volumes.