AMSwarm: An Alternating Minimization Approach for Safe Motion Planning of Quadrotor Swarms in Cluttered Environments
Authors:
- 29 May 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1421-1427
Abstract
This paper presents a scalable online algorithm to generate safe and kinematically feasible trajectories for quadrotor swarms. Existing approaches rely on linearizing Euclidean distance-based collision constraints and on axis-wise decoupling of kinematic constraints to reduce the trajectory optimization problem for each quadrotor to a quadratic program (QP). This conservative approximation often fails to find a solution in cluttered environments. We present a novel alternative that handles collision constraints without linearization and kinematic constraints in their quadratic form while still retaining the QP form. We achieve this by reformulating the constraints in a polar form and applying an Alternating Minimization algorithm to the resulting problem. Through extensive simulation results, we demonstrate that, as compared to Sequential Convex Programming (SCP) baselines, our approach achieves on average, a 72% improvement in success rate, a 36% reduction in mission time, and a 42 times faster per-agent computation time. We also show that collision constraints derived from discrete-time barrier functions (BF) can be incorporated, leading to different safety behaviours without significant computational overhead. Moreover, our optimizer outperforms the state-of-the-art optimal control solver ACADO in handling BF constraints with a 31 times faster per-agent computation time and a 44% reduction in mission time on average. We experimentally validated our approach on a Crazyflie quadrotor swarm of up to 12 quadrotors. The code with supplementary material and video are released for reference.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Fast, On-line Collision Avoidance for Dynamic Vehicles Using Buffered Voronoi CellsIEEE Robotics and Automation Letters, 2017
- Swarm assignment and trajectory optimization using variable-swarm, distributed auction assignment and sequential convex programmingThe International Journal of Robotics Research, 2016
- Variations and extension of the convex–concave procedureOptimization and Engineering, 2015
- Mixed Integer Quadratic Program trajectory generation for a quadrotor with a cable-suspended payload2015
- Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic ProblemsIEEE Transactions on Automatic Control, 2014
- Probabilistic guidance of distributed systems using sequential convex programming2014
- The SHERPA project: Smart collaboration between humans and ground-aerial robots for improving rescuing activities in alpine environments2012
- Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach2012
- ACADO toolkit—An open‐source framework for automatic control and dynamic optimizationOptimal Control Applications and Methods, 2011
- Minimum snap trajectory generation and control for quadrotors2011