Efficient Collision-Avoidance for Multi-Robot System with Superquadric Models and Sum-Of-Squares Approximation

Abstract

Multi-robot motion planning and crowd simulations are crucial in social navigation, enabling agents to avoid collisions with one another in dynamic environments. While existing methods typically use simple circular models for robot and pedestrian boundaries, superquadric models offer greater flexibility in accurately representing non-circular objects. This paper addresses the challenges of employing superquadric models to avoid dynamic obstacles and other moving robots. We tackle three primary challenges: (i) approximating the complex parametric boundary surface of Minkowski sum for easier differentiation; (ii) computing the boundary of velocity obstacles; and (iii) rapidly calculating velocity changes. The approximation of differentiable Minkowski sum boundary is formulated as a semidefinite programming problem using convex sum-of-squares polynomials. We then develop a tangency point-finding algorithm with superlinear convergence speed, and introduce a rule-based collision-avoidance approach, named SSCA (Superquadric-based Sum-of-Squares Collision Avoidance for Multi-Robot Systems) for efficient velocity change calculation. Our proposed method is evaluated through extensive experiments, demonstrating millisecond-level computational efficiency and scalability to dozens of robots. This work provides a more effective solution for collision avoidance algorithm using superquadric models, enhancing the safety and performance of robots in dynamic shared environments.