The coordinated flight of unmanned aerial vehicle (UAV) swarms, particularly in the visually stunning context of a formation drone light show, has garnered significant research interest. These swarms hold immense potential across various fields, including surveillance, search and rescue, logistics, and entertainment. In many operational scenarios, such as a dynamic formation drone light show moving through urban canyons or between structures, the swarm must navigate narrow passages like doorways, windows, or building gaps. Simultaneously, collaborative tasks or aesthetic patterns often require the maintenance of specific geometric formations—linear, V-shaped, polygonal, etc. Therefore, enabling a UAV swarm to safely and swiftly traverse confined spaces while preserving a similar formation structure is of paramount importance for practical applications.
The challenge of high-speed, safe passage through narrow corridors can be framed as a problem of approximate formation transformation and maintenance specific to channel-type obstacles, coupled with high-velocity flight that adheres to kinematic limits. This article addresses this integrated challenge by proposing a multi-stage strategy for UAV swarm trajectory planning. The core idea involves a centralized generation of a global reference path and safe formation configurations, followed by a distributed optimization of individual agent trajectories.
Methodology Overview
The proposed framework decomposes the complex problem into sequential, tractable stages. First, the swarm’s centroid is treated as a virtual leader. A smooth, high-speed trajectory for this virtual leader is planned through the narrow corridor using an enhanced Mixed-Integer Linear Programming (MILP) approach, which also computes a safe flight corridor maximizing the distance to obstacles. Second, leveraging this corridor and the virtual leader’s path, a sequence of safe swarm configurations is determined. This stage employs a genetic algorithm to find a minimally deformed, collision-free formation shape at the corridor’s narrowest point, which is then propagated to other trajectory points. Finally, using the virtual leader’s trajectory and the target formation shapes as constraints, a distributed nonlinear optimization problem is solved to generate smooth, kinematically feasible trajectories for each UAV. A cooperative time reallocation algorithm ensures all agents remain synchronized and within velocity/acceleration limits.
Virtual Leader Trajectory and Safe Corridor Generation
We model the virtual leader’s kinematics discretely. Let $N$ be the number of discrete waypoints, and $\Delta t_s$ be the fixed time step between them. For the $i$-th time step $t_i$, the leader’s position, velocity, and acceleration vectors are denoted as $\mathbf{P}_i = [p_{i,x}, p_{i,y}, p_{i,z}]^T$, $\mathbf{U}_i = [u_{i,x}, u_{i,y}, u_{i,z}]^T$, and $\mathbf{A}_i = [a_{i,x}, a_{i,y}, a_{i,z}]^T$, respectively. The discrete dynamics are:
$$\mathbf{U}_{i} = \mathbf{U}_{i-1} + \mathbf{A}_{i} \Delta t_s, \quad \mathbf{P}_{i} = \mathbf{P}_{i-1} + \mathbf{U}_{i-1} \Delta t_s + \frac{1}{2} \mathbf{A}_{i} \Delta t_s^2$$
for $i \in [2, N]$. Start ($\mathbf{P}_1, \mathbf{U}_1$) and desired end ($\mathbf{P}_{end}, \mathbf{U}_{end$) conditions are set as constraints.
The core improvement over standard MILP lies in the objective function and obstacle avoidance. The corridor walls are modeled as inflated rectangular obstacles. We introduce a variable $d_{safe}$ representing the minimum distance the virtual leader maintains from any obstacle throughout the trajectory. The MILP problem is formulated to minimize a composite cost $J$:
$$ J = \lambda_s J_s – \lambda_{safe} d_{safe} + \lambda_f J_f $$
where:
- $J_s = \sum_{i=2}^{N} \sum_{j\in\{x,y,z\}} |a_{i,j}|$ penalizes control effort for smoothness.
- Maximizing $d_{safe}$ pushes the trajectory to the center of the corridor, creating maximum lateral space for the formation.
- $J_f = \sum_{i=N-M}^{N} i \cdot b_i$ encourages early arrival at the goal. Binary variables $b_i$ enforce that the leader reaches $\mathbf{P}_{end}$ exactly once within a predefined window of the final $M$ steps.
Kinematic limits ($v_{max}$, $a_{max}$) are enforced via linearized polygonal approximations of spherical constraints. Obstacle avoidance is formulated using the Big-M method, converting non-convex “stay-outside” conditions into linear constraints with auxiliary binary variables $\mathbf{Z}$. Solving this MILP yields the optimal virtual leader trajectory $\mathbf{P}^*_i$, $\mathbf{U}^*_i$, and the crucial parameter $d_{safe}$.
Subsequently, the safe corridor $\Omega$ is computed. For each waypoint $\mathbf{P}^*_i$, we find the maximum permissible radius $d_i$ such that a circle of that radius remains clear of all obstacles. This is solved via another lightweight linear program using the pre-computed $\mathbf{Z}^*$. The corridor $\Omega$ is the union of these spheres: $\Omega = \bigcup_{i=1}^{N} \{ \mathbf{p} \, | \, \|\mathbf{p} – \mathbf{P}^*_i\| \leq d_i \}$.
| Parameter | Symbol | Description |
|---|---|---|
| Number of Waypoints | $N$ | Discretization resolution of the path. |
| Time Step | $\Delta t_s$ | Fixed duration between waypoints. |
| Max Velocity / Acceleration | $v_{max}$, $a_{max}$ | Kinematic limits of the UAVs. |
| Safe Distance Margin | $d_{safe}$ | Optimized minimum clearance from obstacles. |
| Objective Weights | $\lambda_s, \lambda_{safe}, \lambda_f$ | Tune smoothness, safety, and speed. |
Safe Formation Configuration Generation
Given the virtual leader’s central path and the lateral clearance $d_{safe}$, the next stage determines how the formation should deform to fit through the narrowest section. Let $N_{UAV}$ be the number of drones. Each drone $k$ has a nominal position $\mathbf{S}_k$ relative to the virtual leader in a Frenet frame (lateral offset $h$, longitudinal offset $l$).
The goal is to find a new, contracted set of relative positions $\mathbf{G}_{k}^{min}$ for the swarm at the corridor’s choke point. This configuration must satisfy: 1) All lateral offsets $|h_{k}^{min}| \leq d_{safe}$; 2) Internal collision avoidance between any pair of drones during the transition from $\mathbf{S}_k$ to $\mathbf{G}_{k}^{min}$; 3) Minimal deformation from the original shape.
This is a combinatorial optimization problem solved efficiently via a Genetic Algorithm (GA). A chromosome encodes the $(h, l)$ coordinates of all $\mathbf{G}_{k}^{min}$. The fitness function $F$ evaluates a candidate solution:
$$ F = \lambda_d \sum_{k=1}^{N_{UAV}} \| \mathbf{G}_{k}^{min} – \mathbf{S}_k \| + \lambda_{sa} \sum_{k=1}^{N_{UAV}} \sum_{k’ \neq k} \kappa(\Lambda(\mathbf{E}_k, \mathbf{E}_{k’})) $$
where $\mathbf{E}_k$ is the line segment connecting $\mathbf{S}_k$ to $\mathbf{G}_{k}^{min}$. The first term minimizes total shape change. The second term penalizes proximity between transition segments of different drones, with $\kappa(\cdot)$ being a penalty function active when the distance $\Lambda(\cdot)$ is below a scaled safety threshold $(\sigma_{min} \cdot d_c)$. The scaling factor $\sigma_{min} < 1$ accounts for the maximum possible compression when converting Frenet-frame distances to Cartesian space due to path curvature. The GA searches for the configuration maximizing $F$.
Once $\mathbf{G}_{k}^{min}$ is found, safe configurations $\mathbf{G}_{k,i}$ for all other trajectory points $i$ are computed. For each point $\mathbf{P}^*_i$, we determine the effective lateral clearance $d_{i, safe}$ by checking the minimum corridor radius $d_q$ over a look-ahead distance equal to the formation’s length. If $d_{i, safe}$ is larger than the formation’s original half-width, no deformation is needed ($\mathbf{G}_{k,i} = \mathbf{S}_k$). Otherwise, $\mathbf{G}_{k,i}$ is calculated as the intersection of the line segment $\mathbf{E}_k$ with the lateral bound $|h| \leq d_{i, safe}$. This creates a smooth transition from the nominal formation to the compressed one and back, which is vital for a cohesive formation drone light show even in constrained spaces.
Distributed UAV Trajectory Optimization
With the virtual leader’s trajectory $\boldsymbol{\Pi}(t)$ (a continuous-time fit of $\mathbf{P}^*_i$) and the target formation configurations $\mathbf{G}_{k,i}$, we now plan individual trajectories. The position of drone $k$ in the Cartesian frame, $\mathbf{p}_k(t)$, is related to its Frenet-frame target $\mathbf{g}_k(t)$ (interpolated from $\mathbf{G}_{k,i}$) by a transformation function $\boldsymbol{\Psi}$:
$$ \mathbf{p}_k(t) = \boldsymbol{\Psi}(\boldsymbol{\Pi}(t), \mathbf{g}_k(t)) $$
This function finds the point along the leader’s path corresponding to the longitudinal offset and then applies the lateral offset perpendicular to the path tangent.
Each drone solves a local, constrained nonlinear optimization over its discretized trajectory $\{\mathbf{p}_{k,i}\}$ at times $t_i$. The cost function for drone $k$ is:
$$
\begin{aligned}
\min & \sum_{i=1}^{N} \lambda_o \| \mathbf{p}_{k,i} – \boldsymbol{\Psi}(\boldsymbol{\Pi}(t_i), \mathbf{G}_{k,i}) \|^2 + \lambda_{as} \| \mathbf{p}_{k,i+1} – 2\mathbf{p}_{k,i} + \mathbf{p}_{k,i-1} \|^2 \\
& + \lambda_{vr} \delta_i + \lambda_{ar} \epsilon_i
\end{aligned}
$$
The terms enforce: 1) Tracking the target formation shape ($\lambda_o$); 2) Trajectory smoothness via acceleration minimization ($\lambda_{as}$); 3) Penalization of slack variables $\delta_i, \epsilon_i \geq 1$ that soften the velocity and acceleration constraints ($\lambda_{vr}, \lambda_{ar}$).
The constraints for drone $k$ include:
- External Collision Avoidance: The lateral offset of $\mathbf{p}_{k,i}$ must respect the safe corridor: $\| \mathbf{p}_{k,i} – \boldsymbol{\Psi}(\boldsymbol{\Pi}(t_i), \mathbf{G}_{k,i}) \| \leq d_{i, safe}$.
- Internal Collision Avoidance: The distance from $\mathbf{p}_{k,i}$ to the line segment connecting the mapped positions of $\mathbf{S}_k$ and $\mathbf{G}_{k}^{min}$ must be greater than a threshold derived from the inter-agent safety distance $d_c$ and a geometric scaling factor $\sigma_{max}$.
$$ \Gamma(\mathbf{p}_{k,i}, \boldsymbol{\Psi}(\boldsymbol{\Pi}(t_i), \mathbf{S}_k), \boldsymbol{\Psi}(\boldsymbol{\Pi}(t_i), \mathbf{G}_{k}^{min})) \geq \frac{\sigma_{min} d_c – d_k^{min}}{2\sigma_{max}} $$ - Soft Kinematic Limits:
$$ \| \mathbf{p}_{k,i} – \mathbf{p}_{k,i-1} \| / \Delta t_i \leq \delta_i \cdot v_{max}, \quad \| \mathbf{p}_{k,i+1} – 2\mathbf{p}_{k,i} + \mathbf{p}_{k,i-1} \| / \Delta t_i^2 \leq \epsilon_i \cdot a_{max} $$ - Initial position constraint.
This is a convex optimization problem (Quadratic Program with linear constraints) that can be solved efficiently and in parallel by each drone.
Cooperative Iterative Time Reallocation
The initial distributed optimization uses uniform time intervals $\Delta t_i$. The slack variables may indicate kinematic limit violations. To resolve this while maintaining formation synchronization—a non-negotiable aspect of a formation drone light show—we employ a cooperative time reallocation. Drones communicate their local $\Delta t_i$ and kinematic constraint violations. If any drone violates a constraint on segment $i$, all drones cooperatively and iteratively increase $\Delta t_i$ by a small factor $\kappa_e > 1$ until all constraints are satisfied. This process preserves the spatial path of each drone while uniformly stretching the time profile, ensuring the swarm transits the corridor together at a feasible, synchronized speed.
| Stage | Method | Centralized/Distributed | Key Output |
|---|---|---|---|
| 1. Reference & Corridor | Enhanced MILP | Centralized | Virtual leader path $\boldsymbol{\Pi}(t)$, $d_{safe}$, safe corridor $\Omega$. |
| 2. Formation Shape | Genetic Algorithm | Centralized | Minimal-deformation safe configurations $\mathbf{G}_{k,i}$ for all points. |
| 3. Agent Trajectories | Nonlinear Convex Optimization | Distributed | Individual smooth trajectories $\mathbf{p}_k(t)$ respecting shape and obstacles. |
| 4. Time Synchronization | Iterative Reallocation | Cooperative | Final synchronized time profile satisfying all kinematic limits. |
Simulation Analysis
The proposed framework was validated in a simulation featuring a 22m long corridor with a 4m wide choke point. A swarm of four UAVs with a rectangular initial formation was tasked to traverse it. The enhanced MILP successfully generated a centered virtual leader trajectory with $d_{safe} = 0.88m$, maximizing clearance. Comparative analysis showed this trajectory was safer and faster than one from a standard MILP formulation. The GA efficiently found a compressed “vertical line” formation for the choke point. The distributed optimizer and time reallocation then produced the final trajectories.
The results demonstrated successful, collision-free navigation. The swarm smoothly transformed from its wide rectangle to a narrow line within the choke point and reverted back afterward, effectively maintaining the formation drone light show ethos of cohesive shape preservation despite environmental constraints. Quantitative comparisons with a potential field method [1] and a distributed MPC approach [26] highlighted the advantages:
- Vs. Potential Fields: Our method guaranteed strict obstacle avoidance (hard constraints) whereas potential fields showed minor infringements. The cumulative formation deformation was 26.7% lower, demonstrating superior shape preservation.
- Vs. Distributed MPC: Our method achieved a 10.6% reduction in cumulative formation error and a 50% faster traversal time, though MPC offers better online computation performance.
The key innovation lies in the decoupled strategy: the centralized planning of a high-quality reference and safe shape templates offloads the most complex global reasoning, enabling efficient and robust distributed trajectory refinement. This is especially beneficial for ensuring the reliability and aesthetic precision required in a large-scale formation drone light show operating in complex environments.
Conclusion
This article presented a comprehensive multi-stage strategy for high-speed, safe formation transformation of UAV swarms in narrow corridors. The main contributions are threefold: 1) An enhanced MILP formulation that generates a fast, smooth, and maximally safe reference trajectory for the swarm centroid. 2) A genetic-algorithm-based method for computing minimally deformed, collision-free formation configurations along the path. 3) A distributed nonlinear optimization scheme coupled with cooperative time reallocation to generate kinematically feasible, synchronized trajectories for each agent that respect both external and internal collision constraints.
The method effectively balances the often-competing demands of speed, safety, and formation cohesion. It provides a structured solution for enabling sophisticated swarm maneuvers, such as those needed in a formation drone light show transitioning between different environments or in tactical UAV operations requiring rapid passage through urban terrain. Future work will focus on integrating dynamic obstacles, improving the computational efficiency of the centralized stages for real-time re-planning, and extending the approach to fully 3D deformations for even more complex aerial choreography and navigation tasks.