The choreography of a large-scale formation drone light show presents a unique and complex challenge in aerial robotics. It requires the precise, coordinated movement of dozens, sometimes hundreds, of unmanned aerial vehicles (UAVs) to create intricate, illuminated patterns in the night sky. The core technological enabler for such a spectacle is robust and intelligent route planning. Unlike pre-programmed static paths, a dynamic route planner must allow the drone swarm to adapt its flight in real-time to unforeseen obstacles—like sudden wind gusts, communication dropouts with individual drones, or even birds—while maintaining the integrity of the light show’s visual formation and ensuring absolute collision-free operation. My research addresses this critical problem by developing a layered, hybrid algorithmic strategy specifically tailored for the demands of a dynamic formation drone light show.
The challenge extends beyond simple point-to-point navigation. We must consider formation flight, where drones maintain specific geometric relationships (e.g., a grid, a circle, a complex shape). The planning must be dynamic, reacting to obstacles detected during the performance. It must ensure time coordination so that all drones reach their formation waypoints simultaneously to create a cohesive image. Finally, it must optimize for overall safety (staying far from threats) and efficiency (conserving battery life). A single algorithm often struggles with all these constraints; global planners like Ant Colony Optimization (ACO) are good at finding optimal long paths but are slow to react, while local planners like Rapidly-exploring Random Trees (RRT) are quick and reactive but can produce sub-optimal, jerky paths.
Therefore, I propose a hybrid A-RRT (ACO-RRT) algorithm that synergistically combines the strengths of both. The core idea is a hierarchical, receding-horizon framework: First, a global plan establishing the optimal show sequence and formation transitions is created offline using ACO. Then, during the live formation drone light show, an improved RRT algorithm handles local, real-time deviations to avoid dynamic obstacles, followed by a swift reformation of the intended pattern. This approach effectively decomposes the high-dimensional planning problem into more manageable layers.
Problem Statement and System Architecture for Formation Choreography
Formally, the dynamic route planning problem for a formation drone light show is defined as follows: For a swarm of N drones launching from the same or coordinated starting points, plan a set of 3D trajectories that transition the swarm from an initial formation to a target formation (or through a sequence of formations). These trajectories must satisfy multiple constraints: avoid static no-fly zones and threats (modeled from the performance venue map), avoid dynamic obstacles detected in real-time, prevent inter-drone collisions, coordinate the arrival time at key waypoints, and respect each drone’s kinematic limits (maximum velocity, acceleration). The objective is to minimize a composite cost function, J, which typically penalizes proximity to threats and total path length (fuel/battery cost).
Our system architecture employs a two-layer, receding-horizon control strategy to solve this problem efficiently:
- Global Show Sequence Planning Layer: Before the show, we treat the entire drone swarm as a single entity moving through a discretized representation of the airspace. Using an ACO algorithm, we compute the globally optimal sequence of “formation holding points” that minimizes the overall cost J while avoiding all known static obstacles. This provides the master choreography timeline.
- Local Dynamic Trajectory Correction Layer: During execution, each drone operates within a local planning “window.” It continuously senses its immediate environment. If a dynamic obstacle (e.g., another drone off-course, a bird) is detected within this window, the local planner—an improved RRT algorithm—takes over to compute a short, collision-free detour. This planning is real-time and reactive.
- Formation Reconstruction Logic: After a local detour, drones will be out of their intended formation positions. A dedicated “cooperative avoidance-reconstruction” strategy is triggered once the obstacle is cleared. This module calculates new, time-synchronized velocities for each drone to smoothly and quickly restore the original formation geometry, ensuring the visual pattern of the formation drone light show is recovered with minimal disruption.
Performance Environment Modeling and Cost Function
To apply graph-search algorithms like ACO, we first need a discrete model of the continuous 3D airspace. We construct this model using a 3D Weighted Voronoi Diagram. Imagine the performance volume populated with known static threat sources (like tall buildings, communication towers around the venue). The Voronoi diagram partitions this space into cells, where every point within a cell is closer to one specific threat source than to any other. The edges (or facets in 3D) of this diagram, which are equidistant from the nearest threats, naturally represent safer navigable corridors for the formation drone light show. This transforms the continuous planning problem into searching a graph G = (V, E), where vertices V are Voronoi edge intersections and edges E are the navigable paths between them.
Each navigable edge e_i in the graph is assigned a cost J_i that reflects its desirability. The cost is a weighted sum of threat cost and fuel cost:
$$ J_i = k_1 J_{\text{threat},i} + (1 – k_1) J_{\text{fuel},i} $$
where k_1 ∈ [0,1] is a tuning parameter prioritizing safety over efficiency. The fuel cost is simply proportional to the edge’s length, L_i: $$ J_{\text{fuel},i} = L_i $$.
The threat cost for an edge is approximated by sampling points along it. For an edge e_i, we sample at three points (1/6, 1/2, and 5/6 of its length) and sum the inverse of the fourth power of the distance to all known threats j:
$$ J_{\text{threat},i} = L_i \sum_{j=1}^{M} \left( \frac{1}{d_{1/6,i,j}^4} + \frac{1}{d_{1/2,i,j}^4} + \frac{1}{d_{5/6,i,j}^4} \right) $$
This formulation heavily penalizes edges that pass close to any threat, guiding the planner towards the center of safe corridors, which is paramount for a reliable formation drone light show over public spaces.
Global Show Sequence Planning via Ant Colony Optimization
With the environment graph defined, we use Ant Colony Optimization to find the optimal global path for the swarm’s center or a reference trajectory. ACO is inspired by the foraging behavior of ants. Artificial “ants” probabilistically construct paths through the graph, depositing “pheromone” on the edges they traverse. Over iterations, shorter, lower-cost paths accumulate more pheromone, attracting more ants and leading to the convergence of the colony on an optimal route. For our formation drone light show, this finds the best sequence of safe corridors for the overall show flow.
The probability P_{ij}^k(t) that ant k at node i chooses node j is given by:
$$ P_{ij}^k(t) = \begin{cases}
\frac{[\tau_{ij}(t)]^\alpha \cdot [\eta_{ij}(t)]^\beta}{\sum_{l \in \mathcal{N}_i^k} [\tau_{il}(t)]^\alpha \cdot [\eta_{il}(t)]^\beta}, & \text{if } j \in \mathcal{N}_i^k \\
0, & \text{otherwise}
\end{cases} $$
Here, τ_{ij}(t) is the pheromone concentration on edge (i,j) at time t. η_{ij}(t) is the heuristic desirability of that edge, which we define as the inverse of its cost: η_{ij} = 1 / J_{ij}. α and β are parameters controlling the relative influence of pheromone versus heuristic information. \mathcal{N}_i^k is the set of nodes adjacent to i that ant k has not yet visited.
After all ants complete a tour, pheromone is updated through evaporation and deposition:
$$ \tau_{ij}(t+1) = (1 – \rho) \cdot \tau_{ij}(t) + \Delta \tau_{ij} $$
where ρ is the evaporation rate (0 < ρ < 1) and Δτ_{ij} is the sum of pheromone deposited by all ants:
$$ \Delta \tau_{ij} = \sum_{k=1}^{m} \Delta \tau_{ij}^k, \quad \Delta \tau_{ij}^k = \begin{cases} Q / L_k, & \text{if ant } k \text{ used edge } (i,j) \\ 0, & \text{otherwise} \end{cases} $$
Q is a constant, and L_k is the total cost of the path taken by ant k. This process, repeated over many iterations, yields the optimal global path for the formation drone light show’s master trajectory.
| Parameter | Symbol | Typical Value | Role |
|---|---|---|---|
| Number of Ants | m | 20-50 | Exploration breadth |
| Pheromone Influence | α | 1.0 | Weight of existing trail strength |
| Heuristic Influence | β | 5.0 | Weight of edge cost (greediness) |
| Pheromone Evaporation | ρ | 0.2 | Prevents stagnation, forgets poor paths |
| Pheromone Constant | Q | 1.0 | Scales deposited pheromone amount |
Real-Time Obstacle Avoidance and Trajectory Correction with Improved RRT
During the live formation drone light show, drones must handle unexpected dynamic obstacles. This is the domain of local planners. The standard Rapidly-exploring Random Tree (RRT) algorithm is well-suited for this: it incrementally builds a tree of feasible trajectories from the drone’s current state, randomly exploring the space until it connects to a local goal (a point on the global path ahead). However, vanilla RRT can be slow and produce erratic, non-optimal paths—unacceptable for a smooth, visually appealing show.
We introduce three key improvements to create an “Improved RRT” for dynamic formation drone light show applications:
- Obstacle Velocity Prediction: When a dynamic obstacle is detected, its velocity vector V_b is estimated. The RRT’s random sampling is then biased away from the obstacle’s predicted future location. The random direction for tree growth is adjusted from the naive direction (q_near → q_rand) to (q_near → q_rand + μ V_b), where μ is a scaling factor. This intelligent bias dramatically reduces wasted exploration towards imminent danger.
- Chaotic Sampling for Coverage: Instead of purely random sampling, we use a Logistic Map chaotic sequence to generate sample points q_rand. This ensures the samples uniformly cover the local planning space, improving exploration efficiency and reducing the chance of getting stuck.
- Path Pruning: The raw path from RRT can be jagged with redundant waypoints. We apply a post-processing step: starting from the current node, we look several steps ahead and check if a direct connection is collision-free. If so, the intermediate nodes are pruned. This results in a much smoother trajectory, conserving energy and improving the visual fluidity of the formation drone light show.
The core RRT growth step remains: from the nearest tree node q_near, extend a step of length ε towards the target sample q_rand to get a new candidate node q_new. This node is added only if the edge (q_near, q_new) is collision-free.
Cooperative Obstacle Avoidance and Formation Reconstruction Strategy
In a multi-drone context, avoidance becomes more complex. When an obstacle disrupts the formation, individual drones taking independent avoidance paths might collide with each other. Our solution is the “Cooperative Avoidance-Reconstruction” strategy. During local avoidance, each drone treats all other drones in the swarm as dynamic obstacles with known trajectories. This is integrated into the improved RRT’s collision-checking routine, ensuring inter-drone separation is maintained even during evasion maneuvers.
Once all drones have cleared the obstacle, a “reconstruction flag” is set. The goal is to restore the original formation geometry as quickly as possible while respecting maximum velocity constraints. Let’s consider a simple three-drone line formation. After avoidance, drones 1, 2, and 3 are at positions P1, P2, P3. The desired formation has them aligned with a fixed spacing H. We calculate the required longitudinal offset x for the last drone to clear the obstacle (say, drone 2) to move to a new alignment line. The reconstruction positions become: P2′ = P2 + (x, 0), P1′ = P1 + (H – L12 + x, 0), P3′ = P3 + (x – L23, 0), where L12 and L23 are the current separations. The value x and the reconstruction time t are chosen to satisfy:
$$ \begin{cases} x > 0 \\ x > L_{12} – H \\ \frac{x}{t} \leq V_{\text{max}} \\ \frac{|x + H – L_{12}|}{t} \leq V_{\text{max}} \\ \frac{|x – L_{23}|}{t} \leq V_{\text{max}} \end{cases} $$
We solve for the minimum feasible t (fastest reconstruction) and then assign velocities V1, V2, V3 accordingly. This mathematical strategy ensures the formation drone light show recovers its iconic pattern with synchronized, optimal motions.
Simulation Experiments and Performance Analysis
To validate our A-RRT hybrid algorithm, we conducted extensive simulations in a MATLAB environment mimicking a formation drone light show venue. The static environment was a 600m x 600m area with several threat zones, modeled by a Voronoi graph. A swarm of three drones started from a common point with a target formation destination. Dynamic obstacles were introduced during the simulated flight.
1. Global Planning Result: The ACO layer successfully computed an optimal global path avoiding all static threats. For a sample start (12,13)m to goal (52,47)m, the algorithm converged to a path with a total cost J_global = 632.82 and an estimated time of arrival (ETA) of 119.23 seconds for the swarm, computed offline in approximately 0.40 seconds. This provides the baseline choreography for the formation drone light show.
2. Local Dynamic Avoidance Performance: We compared our Improved RRT against a standard RRT in a cluttered local window (40m x 45m). The Improved RRT, with its direction bias and path pruning, consistently found smoother, shorter detours faster. A statistical summary over multiple trials is shown below:
| Metric | Improved RRT | Standard RRT |
|---|---|---|
| Average Planning Time (ms) | 15.60 | 28.60 |
| Average Local Path Cost | 8.33 | 12.56 |
| Tree Nodes Generated | ~25 | ~45 |
The results clearly demonstrate the enhanced real-time capability and path quality of the Improved RRT, which is crucial for maintaining the seamless flow of a formation drone light show when surprises occur.
3. Full Swarm Dynamic Planning with Reconstruction: We tested the complete A-RRT hybrid framework with the cooperative strategy on the three-drone swarm encountering a dynamic obstacle. Without the inter-drone collision check, drones 1 and 3 would have collided during avoidance. With our strategy, all drones avoided both the external obstacle and each other. After clearing the obstacle, the reconstruction module successfully calculated new velocities and restored the original line formation within seconds. The overall performance of the hybrid approach was compared against using a standard RRT for the entire problem (both global and local planning):
| Metric | A-RRT Hybrid Algorithm | Standard RRT Algorithm |
|---|---|---|
| Successful Collision-Free Missions | 20 / 20 | 8 / 20 |
| Average Total Planning Time (s) | 0.529 | 1.407 |
| Average Overall Path Cost | 642.12 | 718.30 |
The A-RRT hybrid achieved a 100% success rate, significantly lower planning time, and more optimal overall paths. The standard RRT struggled due to its lack of global guidance and poor reactivity in multi-agent settings.
Conclusion
This research presents a robust and efficient solution to the dynamic route planning problem central to modern, ambitious formation drone light shows. By proposing the A-RRT hybrid algorithm—which synergistically combines the global optimization power of Ant Colony Optimization with the real-time reactivity of an Improved Rapidly-exploring Random Tree algorithm—we address the dual need for pre-show optimal choreography and in-flight adaptability. The introduction of the “cooperative avoidance-reconstruction” strategy further ensures that the aesthetic and geometric integrity of the formation is maintained even after disruptions. Simulation results confirm that this layered approach significantly outperforms conventional single-algorithm methods in terms of path optimality, planning speed, and operational reliability. This work provides a solid algorithmic foundation for enabling safer, more complex, and more resilient autonomous formation drone light shows, pushing the boundaries of what is possible in aerial entertainment and coordinated multi-robot systems.