  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 paper, 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.
