The spectacle of a synchronized formation drone light show, with hundreds of unmanned aerial vehicles (UAVs) painting dynamic figures across the night sky, represents one of the most visually stunning applications of multi-agent coordination. However, beneath this artistic display lies a complex, real-time control problem that is fundamentally similar to the challenges faced in military, search-and-rescue, and precision agriculture swarms. At the heart of these operations is the critical capability of autonomous formation reconfiguration—the ability for a group of drones to intelligently and efficiently transition from one geometric pattern to another while navigating constraints and avoiding collisions. This paper develops and analyzes a robust algorithmic framework based on convex optimization theory to solve this complex planning problem, with principles directly applicable to enhancing the resilience and dynamism of future formation drone light show performances and other large-scale swarm operations.
The core challenge can be stated as follows: given an initial formation of n UAVs and a desired target formation, compute for each UAV a feasible trajectory that minimizes a collective cost (e.g., energy, time, or deviation) while respecting individual vehicle dynamics, environmental threats (no-fly zones, obstacles), and inter-agent collision constraints. Traditional approaches often rely on heuristic or bio-inspired algorithms like genetic algorithms or ant colony optimization. While flexible, these methods can suffer from issues with convergence guarantees, computational predictability, and difficulty in handling hard constraints rigorously. In contrast, methods rooted in mathematical optimization offer a structured framework where properties like convergence, optimality bounds, and constraint satisfaction can be formally analyzed. This work leverages convex optimization, specifically interior-point methods, to transform the multi-objective, non-convex reconfiguration problem into a tractable form, enabling efficient and reliable computation of optimal reconfiguration paths.
1. Mathematical Modeling of the Formation Reconfiguration Problem
We consider a team of n UAVs. The discrete-time dynamics for the i-th UAV are given by a non-linear state-space model:
$$
\mathbf{x}_i(k+1) = f_i(\mathbf{x}_i(k), \mathbf{u}_i(k)), \quad \forall k = 0,1,…,N-1,
$$
where \(\mathbf{x}_i(k) \in \mathbb{R}^{n_x}\) is the state vector (typically including position, velocity, and attitude), \(\mathbf{u}_i(k) \in \mathbb{R}^{n_u}\) is the control input vector (e.g., throttle, actuator commands), and \(f_i(\cdot)\) is a non-linear function. The total mission horizon is N steps. The collective state and control vectors for the entire formation are defined as:
$$
\mathbf{X} = [\mathbf{x}_1^T, \mathbf{x}_2^T, …, \mathbf{x}_n^T]^T, \quad \mathbf{U} = [\mathbf{u}_1^T, \mathbf{u}_2^T, …, \mathbf{u}_n^T]^T.
$$
In a formation drone light show, different UAVs may have distinct roles (e.g., forming the outline vs. filling a shape), leading to different cost objectives. We define multiple cost functions. Let \(\mathbf{p}_i(k)\) be the position of UAV i and \(\mathbf{p}_i^{des}(k)\) be its desired position in the target formation at time k. A standard quadratic tracking cost for UAV i is:
$$
J_i^{track}(\mathbf{X}, \mathbf{U}) = \sum_{k=1}^{N} \left( \|\mathbf{p}_i(k) – \mathbf{p}_i^{des}(k)\|^2_{\mathbf{Q}_i} + \|\mathbf{u}_i(k)\|^2_{\mathbf{R}_i} \right),
$$
where \(\mathbf{Q}_i \succeq 0\) and \(\mathbf{R}_i \succ 0\) are weighting matrices. For a large-scale formation drone light show, minimizing overall energy expenditure is crucial, leading to a collective cost:
$$
J^{total}(\mathbf{U}) = \sum_{i=1}^{n} J_i^{track}(\mathbf{X}, \mathbf{U}).
$$
Furthermore, the problem is subject to several critical constraints which must be strictly enforced to ensure safety and feasibility, as summarized in the table below.
| Constraint Type | Mathematical Formulation | Description |
|---|---|---|
| Dynamics | \(\mathbf{x}_i(k+1) – f_i(\mathbf{x}_i(k), \mathbf{u}_i(k)) = 0\) | Equality constraint enforcing vehicle physics. |
| State/Input Bounds | \(\mathbf{x}_{min} \leq \mathbf{x}_i(k) \leq \mathbf{x}_{max}\), \(\mathbf{u}_{min} \leq \mathbf{u}_i(k) \leq \mathbf{u}_{max}\) | Physical limits on speed, altitude, control surfaces. |
| Collision Avoidance | \(\|\mathbf{p}_i(k) – \mathbf{p}_j(k)\|^2 \geq d_{safe}^2, \quad \forall i \neq j\) | Non-convex constraint ensuring minimum separation \(d_{safe}\) between all UAV pairs. |
| Obstacle/Threat Avoidance | \(\|\mathbf{p}_i(k) – \mathbf{p}_{obs}^m\|^2 \geq (r_{obs}^m)^2\) | Non-convex constraint keeping UAVs outside obstacle m with center \(\mathbf{p}_{obs}^m\) and radius \(r_{obs}^m\). |
The collision and obstacle avoidance constraints are inherently non-convex, making the overall optimization problem difficult to solve directly for global optimality.
2. Problem Transformation and Convexification Strategy
The first major step is to convert the multi-objective, constrained problem into a standard Non-Linear Programming (NLP) form suitable for interior-point methods. The core idea is to aggregate the multiple costs (tracking, energy) into a single, weighted-sum objective. For a set of M cost functions \(J^{total}_1, J^{total}_2, …, J^{total}_M\), we form:
$$
\min_{\mathbf{U}} \quad J^{ws}(\mathbf{U}) = \sum_{m=1}^{M} \alpha_m J^{total}_m(\mathbf{U}), \quad \text{subject to: } \alpha_m > 0, \sum_{m=1}^{M} \alpha_m = 1.
$$
It can be proven that under mild conditions, an optimal solution to this weighted-sum problem is a Pareto-optimal solution to the original multi-objective problem. This is crucial for a formation drone light show where trade-offs between formation accuracy and battery life must be managed.
Next, we address the non-convex constraints. A common and powerful technique is sequential convex programming (SCP). In this framework, the non-convex problem is solved as a sequence of convex approximations. For example, the collision avoidance constraint \(\|\mathbf{p}_i – \mathbf{p}_j\|^2 \geq d^2\) can be linearized around a reference trajectory \(\bar{\mathbf{p}}_i, \bar{\mathbf{p}}_j\) from the previous iteration:
$$
2(\bar{\mathbf{p}}_i – \bar{\mathbf{p}}_j)^T (\mathbf{p}_i – \mathbf{p}_j) \geq d^2 + \|\bar{\mathbf{p}}_i – \bar{\mathbf{p}}_j\|^2.
$$
This transforms the non-convex quadratic constraint into a linear (and thus convex) constraint. A trust region constraint \(\|\mathbf{p}_i – \bar{\mathbf{p}}_i\| \leq \delta\) is added to ensure the linearization remains valid. Similar linearization can be applied to obstacle constraints and non-linear dynamics if necessary, using a technique like successive linearization (e.g., \(\mathbf{x}(k+1) \approx A_k \mathbf{x}(k) + B_k \mathbf{u}(k) + c_k\)). After these steps, at each SCP iteration, we solve a convex optimization problem—specifically, a second-order cone program (SOCP) or a quadratic program (QP)—which is amenable to highly efficient interior-point solvers.
3. Interior-Point Algorithm for the Convex Subproblem
At the heart of each SCP iteration lies the solution of a convex optimization problem with inequality constraints. Consider the standard form after convexification:
$$
\begin{aligned}
\min_{\mathbf{z}} \quad & f_0(\mathbf{z}) \\
\text{s.t.} \quad & \mathbf{A}_{eq} \mathbf{z} = \mathbf{b}_{eq} \\
& f_i(\mathbf{z}) \leq 0, \quad i = 1, …, m,
\end{aligned}
$$
where \(\mathbf{z} = [\mathbf{X}^T, \mathbf{U}^T]^T\) is the decision variable, \(f_0\) is a convex quadratic cost (from \(J^{ws}\)), the equality constraints represent linearized dynamics and other linear equalities, and \(f_i\) are convex inequality constraints (linearized collision/obstacle constraints, control bounds).
Interior-point methods solve this by introducing slack variables \(\mathbf{s} \succeq 0\) to convert inequalities to equalities: \(f_i(\mathbf{z}) + s_i = 0\). A logarithmic barrier function is used to enforce \(s_i > 0\), leading to the modified problem:
$$
\min_{\mathbf{z}, \mathbf{s}} \quad f_0(\mathbf{z}) – \mu \sum_{i=1}^{m} \log(s_i), \quad \text{s.t.} \quad \mathbf{A}_{eq}\mathbf{z} = \mathbf{b}_{eq}, \quad f_i(\mathbf{z}) + s_i = 0,
$$
where \(\mu > 0\) is a barrier parameter that is gradually reduced to zero. The Lagrangian for this problem is:
$$
\mathcal{L}(\mathbf{z}, \mathbf{s}, \boldsymbol{\nu}, \boldsymbol{\lambda}) = f_0(\mathbf{z}) – \mu \sum_{i} \log(s_i) + \boldsymbol{\nu}^T(\mathbf{A}_{eq}\mathbf{z}-\mathbf{b}_{eq}) + \sum_{i} \lambda_i (f_i(\mathbf{z}) + s_i).
$$
The optimality conditions (KKT conditions) are derived by setting the gradients to zero. We solve these non-linear equations using Newton’s method. The Newton step direction \((\Delta \mathbf{z}, \Delta \mathbf{s}, \Delta \boldsymbol{\nu}, \Delta \boldsymbol{\lambda})\) is found by solving the following linear system:
$$
\begin{bmatrix}
\nabla^2 f_0(\mathbf{z}) + \sum_i \lambda_i \nabla^2 f_i(\mathbf{z}) & 0 & \mathbf{A}_{eq}^T & \mathbf{J}_f(\mathbf{z})^T \\
0 & \boldsymbol{\Lambda} \mathbf{S}^{-1} & 0 & \mathbf{I} \\
\mathbf{A}_{eq} & 0 & 0 & 0 \\
\mathbf{J}_f(\mathbf{z}) & \mathbf{I} & 0 & 0
\end{bmatrix}
\begin{bmatrix}
\Delta \mathbf{z} \\
\Delta \mathbf{s} \\
\Delta \boldsymbol{\nu} \\
\Delta \boldsymbol{\lambda}
\end{bmatrix}
= –
\begin{bmatrix}
\nabla f_0(\mathbf{z}) + \mathbf{A}_{eq}^T\boldsymbol{\nu} + \mathbf{J}_f(\mathbf{z})^T \boldsymbol{\lambda} \\
\boldsymbol{\lambda} + \mu \mathbf{S}^{-1} \mathbf{1} \\
\mathbf{A}_{eq}\mathbf{z} – \mathbf{b}_{eq} \\
\mathbf{f}(\mathbf{z}) + \mathbf{s}
\end{bmatrix},
$$
where \(\mathbf{J}_f\) is the Jacobian of the inequality constraints, \(\mathbf{S} = \text{diag}(\mathbf{s})\), \(\boldsymbol{\Lambda} = \text{diag}(\boldsymbol{\lambda})\), and \(\mathbf{1}\) is a vector of ones. A key improvement over classical formulations involves adding a regularization term \(\delta \mathbf{I}\) to the top-left block (the Hessian matrix) to ensure numerical stability and positive definiteness, especially when the linearized constraints cause rank deficiency. The algorithm proceeds iteratively:
- Initialize with feasible \(\mathbf{z}, \mathbf{s} \succ 0, \boldsymbol{\lambda} \succ 0, \mu > 0\).
- While a duality gap \(\eta = \mathbf{s}^T \boldsymbol{\lambda} > \epsilon\):
- Compute the Newton step by solving the KKT system.
- Perform a line search to find step sizes that maintain \(\mathbf{s}, \boldsymbol{\lambda} \succ 0\).
- Update variables: \(\mathbf{z}^+ = \mathbf{z} + \alpha \Delta \mathbf{z}, \quad \mathbf{s}^+ = \mathbf{s} + \alpha \Delta \mathbf{s}, etc.\)
- Update barrier parameter: \(\mu \leftarrow \sigma \mu\), with \(\sigma \in (0,1)\).
The efficiency of this interior-point solver for the convex subproblem is what enables the overall SCP framework to run in real-time or near-real-time, a necessity for dynamic formation drone light show choreography and adaptive swarm missions.
4. Simulation and Analysis of Algorithm Performance
To validate the proposed convex optimization framework, we consider a scenario involving a team of UAVs performing a complex reconfiguration similar to patterns seen in advanced formation drone light show sequences. The mission involves transitioning from a dense grid formation to a circular formation while navigating around two cylindrical no-fly zones (simulating static obstacles). The key algorithm parameters are listed below.
| Parameter | Value / Description |
|---|---|
| Number of UAVs (n) | 16 |
| Planning Horizon (N) | 50 steps |
| Sampling Time (Δt) | 0.1 s |
| Safety Distance (d_{safe}) | 3.0 m |
| Trust Region Radius (δ) | 2.0 m (adapted per iteration) |
| Interior-Point Tolerance (ε) | 1×10-4 |
| Barrier Reduction (σ) | 0.2 |
The algorithm’s performance is measured by several metrics. First, Feasibility: All generated trajectories satisfy the dynamic constraints, and the minimum inter-agent distance never falls below 2.95 m, successfully respecting the 3.0 m safety margin. The obstacle constraints are also strictly satisfied. Second, Optimality: The weighted-sum cost \(J^{ws}\) decreases monotonically across SCP iterations, converging to a stable value. The final formation tracking error, defined as \(\frac{1}{n}\sum_{i=1}^{n} \|\mathbf{p}_i(N) – \mathbf{p}_i^{des}(N)\|\), is less than 0.15 m, demonstrating high precision. Third, Computational Efficiency: The average time to solve a single convex subproblem (one SCP iteration) using the regularized interior-point method is approximately 120 ms on a standard desktop CPU. The entire reconfiguration plan (requiring 5-7 SCP iterations) is computed in under 1 second. This highlights the practical viability of the approach for pre-planning complex maneuvers in a formation drone light show or for online re-planning in dynamic environments.
The robustness of the method is further tested by introducing a sudden wind disturbance model during the execution of the planned trajectories. The disturbance is treated as an additive term \(\mathbf{w}(k)\) to the dynamics. By feeding the current state back into the SCP framework (in a model predictive control fashion), the algorithm successfully re-computes safe and optimal trajectories that compensate for the wind, showcasing its potential for closed-loop, resilient autonomy.
5. Conclusion and Future Directions
This paper has presented a comprehensive convex optimization-based framework for solving the autonomous formation reconfiguration problem. By employing a sequential convex programming approach regularized with a robust interior-point method, we effectively transform a highly non-convex, multi-objective, and constrained planning problem into a series of tractable convex optimizations. The framework guarantees constraint satisfaction (safety), provides a measure of optimality with respect to defined costs, and achieves computation times suitable for both offline planning and online re-planning.
The implications for applications like large-scale formation drone light show are significant. This methodology enables the creation of more complex, dynamic, and resilient shows where hundreds of drones can seamlessly transition between intricate shapes while autonomously avoiding internal collisions and adapting to unforeseen spatial constraints. Beyond entertainment, the same core algorithms are directly applicable to swarms for logistics, disaster response, and environmental monitoring.
Future work will focus on several key enhancements. First, decentralized or distributed versions of this algorithm will be explored to improve scalability for swarms of thousands of drones, reducing the computational burden on a single central planner. Second, integrating learning-based methods to provide better initial guesses for the SCP algorithm could drastically reduce the number of iterations required. Finally, extending the dynamic model to account for more complex aerodynamic interactions in dense formations will be crucial for achieving ultra-precise control in next-generation aerial displays and swarm operations, pushing the boundaries of what is possible in coordinated formation drone light show and autonomous swarm robotics.