Efficient Collision-Avoidance for Multi-Robot System with Superquadric Models and Sum-Of-Squares Approximation
Siyi Lu, Sipu Ruan
AI summary
Problem
Existing multi-robot collision avoidance methods rely on simplified circular or elliptical models that fail to accurately represent complex robot geometries, while current superquadric-based approaches use unreliable algorithms for computing velocity obstacles.
Approach
SSCA approximates the complex Minkowski sum of superquadric boundaries using convex sum-of-squares polynomials solved via semidefinite programming, then efficiently computes velocity obstacles and minimal corrective velocities using a novel tangency-finding algorithm and rule-based optimization.
Key results
- Approximates superquadric Minkowski sum boundaries using convex sum-of-squares polynomials via semidefinite programming
- Develops a penalty-function-based tangency point-finding algorithm with superlinear convergence
- Achieves millisecond-level computational efficiency and scales to dozens of robots in dynamic simulations
- Demonstrates superior navigation success rates and trajectory accuracy compared to circular-model baselines
Why it matters
Provides a robust, computationally efficient framework for safe multi-robot navigation in complex environments, benefiting robotics researchers and developers working on social navigation and crowd simulation.
Abstract
Multi-robot motion planning and crowd simu- lations 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) approxi- mating 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 conver- gence 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.