Velocity Obstacle for Polytopic Collision Avoidance for Distributed Multi-Robot Systems

Obstacle avoidance for multi-robot navigation with polytopic shapes is challenging. Existing works simplify the system dynamics or consider it as a convex or non-convex optimization problem with positive distance constraints between robots, which limits real-time performance and scalability. Additionally, generating collision-free behavior for polytopic-shaped robots is harder due to implicit and non-differentiable distance functions between polytopes. In this letter, we extend the concept of velocity obstacle (VO) principle for polytopic-shaped robots and propose a novel approach to construct the VO in the function of vertex coordinates and other robot's states. Compared with existing work about obstacle avoidance between polytopic-shaped robots, our approach is much more computationally efficient as the proposed approach for construction of VO between polytopes is optimization-free. Based on VO representation for polytopic shapes, we later propose a navigation approach for distributed multi-robot systems. We validate our proposed VO representation and navigation approach in multiple challenging scenarios including large-scale randomized tests, and our approach outperforms the state of art in many evaluation metrics, including completion rate, deadlock rate, and the average travel distance.

I. Introduction

The multi-robot navigation is a challenging task [1], [2] that needs to be solved for various applications such as warehouse delivery and search and rescue operations [3]. The critical challenge of navigation tasks for the multi-robot system is to achieve real-time obstacle avoidance while navigating each robot to its respective destination, as shown in Fig. 1. Existing approaches are not accessible to be deployed for polytopic multi-robot systems, as they usually consider the collision avoidance between polytopes as convex or even non-convex optimizations, whose computational complexity increases dramatically with the number of robots. Velocity obstacle [4], commonly abbreviated VO, is the set of all velocities of a robot that will result in a collision with an obstacle at some moment in time, assuming that the obstacle maintains its current velocity. In this letter, we propose a novel approach in the field of VO to achieve distributed multi-robot navigation with polytopic shapes, which could be deployed in real-time.