  We present Probabilistic Reciprocal Velocity Obstacle or PRVO as a general
algorithm for navigating multiple robots under perception and motion
uncertainty. PRVO is defined as the space of velocities that ensures dynamic
collision avoidance between a pair of robots with a specified probability. Our
approach is based on defining chance constraints over the inequalities defined
by the deterministic Reciprocal Velocity Obstacle (RVO). The computational
complexity of the proposed probabilistic RVO is comparable to the deterministic
counterpart. This is achieved by a series of reformulations where we first
substitute the computationally intractable chance constraints with a family of
surrogate constraints and then adopt a time scaling based solution methodology
to efficiently characterize their solution space. Further, we also show that
the solution space of each member of the family of surrogate constraints can be
mapped in closed form to the probability with which the original chance
constraints are satisfied and thus consequently to probability of collision
avoidance. We validate our formulations through numerical simulations where we
highlight the importance of incorporating the effect of motion uncertainty and
the advantages of PRVO over existing formulations which handles the effect of
uncertainty by using conservative bounding volumes.
