The spectacular sight of hundreds, even thousands, of drones illuminating the night sky in perfect synchrony has transformed from a futuristic vision into a breathtaking reality. This modern art form, known as a formation drone light show, relies on the precise orchestration of individual drones moving as a cohesive aerial ensemble. The core technical challenge enabling these mesmerizing displays is efficient and safe path planning, particularly for the initial phase where drones must launch from dispersed locations and converge into their starting formation positions. This article delves into an intelligent path planning framework based on a Cellular Genetic Algorithm (CGA), designed to generate optimal, collision-free, and time-synchronized routes for a fleet of drones, forming the critical foundation for any successful formation drone light show.
The operational environment for a formation drone light show is rarely an empty void. It contains static no-fly zones (NFZs) or threat areas representing physical obstacles, restricted airspace, or areas with strong signal interference. Therefore, the path for each drone must minimize exposure to these threats. Furthermore, to conserve battery power—a critical resource for electric drones—the total flight path length should be as short as possible. The most distinctive requirement for a coordinated formation drone light show is temporal synchronization. All drones must arrive at their designated formation entry points within a strict, narrow time window to ensure the show begins flawlessly. This introduces a complex layer of speed coordination atop the basic spatial pathfinding problem. Finally, the planned paths for multiple drones must guarantee a safe separation distance throughout the entire flight to prevent mid-air collisions, a paramount safety concern.
To address the single-drone path planning sub-problem, we employ a Cellular Genetic Algorithm. Traditional Genetic Algorithms (GAs) operate on a global population where any individual can mate with any other, which can sometimes lead to premature convergence on sub-optimal solutions. The CGA introduces a spatial structure to the population, enhancing diversity and balancing global exploration with local refinement. The population of candidate paths is distributed across a two-dimensional cellular grid. Each cell (representing one path solution) interacts only with its immediate neighbors, typically defined by a Moore neighborhood (the eight surrounding cells). This local interaction model, with periodic boundary conditions, creates parallel, semi-isolated evolutionary niches, helping to maintain genetic diversity and avoid the dominance of a single sub-optimal path early in the search process.
A candidate path for a drone is represented as a sequence of waypoints in a 2D plane (ignoring altitude for initial planning). The path starts at the launch point $S(x_s, y_s)$ and ends at the formation assembly point $G(x_g, y_g)$, connected by $n$ intermediate waypoints $P_i(x_i, y_i)$. Thus, a path chromosome is encoded as: $(S, P_1, P_2, …, P_n, G)$.
The fitness function $F$ evaluates the quality of a path. A higher fitness indicates a better path. The total cost $C$ of a path is a weighted sum of three key components, and fitness is calculated as $F = \phi – C$, where $\phi$ is a sufficiently large constant.
1. Threat Cost ($C_t$): The path must avoid $q$ circular threat zones centered at $W_j$ with radius $r_j$. For each path segment $\overline{P_i P_{i+1}}$, the shortest distance $d_{ij}$ to each threat $W_j$ is computed. The threat cost for that segment is the sum of penalties for all threats where the drone ventures too close.
$$
d_{ij} = \begin{cases}
\Vert \overrightarrow{P_{ij}W_j} \Vert & \text{if } 0^\circ < \alpha_{ij}, \beta_{ij} \le 90^\circ \\
\Vert \overrightarrow{P_i W_j} \Vert & \text{if } 90^\circ < \alpha_{ij} < 180^\circ \\
\Vert \overrightarrow{P_{i+1} W_j} \Vert & \text{if } 90^\circ < \beta_{ij} < 180^\circ
\end{cases}
$$
$$
s_{ij} = \begin{cases}
0 & \text{if } d_{ij} \ge r_j \\
r_j – d_{ij} & \text{if } d_{ij} < r_j
\end{cases}
$$
$$
C_t = k_t \cdot \sum_{i=0}^{n} \sum_{j=1}^{q} s_{ij}
$$
Here, $\alpha_{ij}$ and $\beta_{ij}$ are the angles at $P_i$ and $P_{i+1}$ respectively, and $k_t$ is a weighting coefficient.
2. Path Length Cost ($C_l$): To minimize energy consumption, the total Euclidean length $L$ of the path is penalized.
$$
L = \sum_{i=0}^{n} \Vert \overrightarrow{P_i P_{i+1}} \Vert
$$
$$
C_l = k_l \cdot L
$$
3. Velocity Cost ($C_v$): This is crucial for time coordination in a formation drone light show. Given a required assembly time $T$, the average speed needed for a path of length $L$ is $v_{req} = L/T$. Drones have a minimum $v_{min}$, maximum $v_{max}$, and an energy-efficient cruise speed $v_c$. The velocity cost penalizes deviation from $v_c$.
$$
C_v = k_v \cdot | v_{req} – v_c | \quad \text{subject to } v_{min} \le v_{req} \le v_{max}
$$
The total cost and fitness are therefore:
$$
C = C_t + C_l + C_v = k_t \cdot \sum \sum s_{ij} + k_l \cdot L + k_v \cdot | L/T – v_c |
$$
$$
F = \phi – C
$$
The coefficients $k_t$, $k_l$, and $k_v$ allow tuning the priority of safety, efficiency, and timeliness for the formation drone light show.
| Cost Component | Symbol | Purpose | Key Parameter |
|---|---|---|---|
| Threat Cost | $C_t$ | Penalize proximity to no-fly zones/obstacles. | Threat radius $r_j$, weight $k_t$ |
| Path Length Cost | $C_l$ | Minimize total flight distance for energy saving. | Weight $k_l$ |
| Velocity Cost | $C_v$ | Encourage paths that allow efficient cruise speed to meet time target. | Assembly time $T$, cruise speed $v_c$, weight $k_v$ |
Initial paths are generated using a forward-looking heuristic. Starting from $S$, each subsequent waypoint $P_i$ is placed at a random distance $l$ (within bounds) and a random bearing offset $\gamma \in [-90^\circ, 90^\circ]$ from the direction toward the goal $G$. This ensures paths are goal-directed yet diverse.
Genetic evolution occurs locally within each cell’s neighborhood:
- Selection: A parent from the central cell’s eight neighbors is chosen using roulette-wheel selection based on fitness $F$.
- Crossover: With probability $p_c$, a single-point crossover occurs between the central path and the selected neighbor path, swapping subsequences of waypoints after a randomly chosen index. The better of the two resulting offspring is kept.
- Mutation: With probability $p_m$, a randomly chosen waypoint $P_e$ in the new path is examined. If it lies inside a threat zone (distance to threat center $< r$), it is mutated by moving it a distance proportional to the intrusion depth $|d-r|$ in a random direction: $P’_e = P_e + \kappa \cdot |d-r| \cdot (\cos\omega, \sin\omega)$, where $\kappa \in [1,2]$ and $\omega$ is random.
The new path replaces the central cell’s path only if it has higher fitness. This process is applied synchronously to all cells in the grid for each generation.
| Genetic Operator | Scope | Action | Purpose |
|---|---|---|---|
| Selection | Local (Neighborhood) | Roulette-wheel based on fitness $F$. | Promote propagation of good genetic material. |
| Crossover | Between two parent paths | Single-point waypoint sequence exchange. | Combine promising path segments from different solutions. |
| Mutation | Single waypoint in a path | Random displacement away from threat zones. | Introduce new genetic diversity and repair infeasible paths. |
After the CGA converges, the raw path may have sharp turns that exceed the drone’s minimum turning radius constraint $\phi_m$. A post-processing smoothing step is applied: for any turn angle sharper than $\phi_m$, the path is adjusted by either merging waypoints or inserting intermediate ones to create a gentler, flyable curve.
The single-drone planner is the building block. For a full formation drone light show, we need multi-drone coordination with two main strategies:
1. Time Synchronization Strategy: The CGA’s velocity cost encourages paths that are compatible with a speed near $v_c$ to meet the global time $T$. For finer control, we implement a waypoint-based speed adjustment protocol. Each waypoint $P_{k,i}$ for drone $k$ is assigned a scheduled arrival time $t_{k,i} = L_{k,i} / v_{k,0}$, where $L_{k,i}$ is the cumulative path length to that point and $v_{k,0}=L_k/T$ is the initial calculated speed. During execution, as drone $k$ reaches $P_{k,i}$ at actual time $t_{k}^{act}$, it computes the required speed for the next leg to catch up or maintain schedule:
$$
v_{k}^{next} = \frac{\Vert \overrightarrow{P_{k,i} P_{k,i+1}} \Vert}{t_{k,i+1} – t_{k}^{act}}
$$
This real-time, leg-by-leg speed modulation ensures all drones converge on the assembly point in perfect synchrony, which is non-negotiable for launching a formation drone light show.
2. Collision Avoidance Strategy: Paths planned independently may cross or come within an unsafe distance $D_s$. Since we initially plan in 2D, we resolve potential conflicts by assigning different altitude layers. Drones with longer 2D paths are assigned lower altitudes to balance energy consumption related to climb. A vertical separation of at least $D_s$ between layers ensures that even if 2D paths intersect, the drones are safely separated in 3D space. This simple yet effective strategy is highly suitable for the structured nature of a formation drone light show where altitude can be used as a discrete resource.
To validate the framework, a simulation was conducted for a three-drone team assembling for a small-scale formation drone light show. Key simulation parameters are summarized below.
| Parameter Category | Values |
|---|---|
| Scene | Start Points: S1(10,10), S2(20,0), S3(0,30) km. Goal: G(100,100) km. 6 Threat Zones with defined centers/radii. |
| Drone Constraints | $v_{min}=40$ km/h, $v_{max}=200$ km/h, $v_c=140$ km/h, $\phi_m=60^\circ$, $D_s=80$ m. |
| Mission | Assembly Time $T=60$ min. |
| CGA Parameters | Population=40 (5×8 grid), Waypoints per path=9, Generations=50, $p_c=0.8$, $p_m=0.1$. |
The CGA successfully generated three distinct, threat-avoiding paths. The calculated initial speeds for UAV1, UAV2, and UAV3 were approximately 137.7, 142.5, and 141.8 km/h respectively, all close to the efficient cruise speed $v_c$ of 140 km/h, demonstrating the effectiveness of the velocity cost function. The table below shows sample scheduled data for key waypoints, illustrating the time-coordinated plan.
| Waypoint | UAV1 (x, y, t) km, min | UAV2 (x, y, t) km, min | UAV3 (x, y, t) km, min |
|---|---|---|---|
| $P_1$ | (13.80, 23.56, 6.14) | (36.65, 5.93, 7.44) | (3.23, 45.19, 6.67) |
| $P_3$ | (40.59, 33.27, 18.89) | (56.40, 23.74, 18.91) | (19.38, 69.02, 19.21) |
| $P_5$ | (60.18, 49.03, 30.96) | (79.15, 31.76, 29.58) | (34.94, 92.05, 31.21) |
| $P_7$ | (81.39, 65.39, 42.71) | (87.59, 56.64, 40.78) | (63.93, 100.13, 44.31) |
| $P_9$ | (92.03, 90.41, 54.57) | (97.81, 83.08, 52.82) | (87.65, 98.92, 54.76) |
The paths were smooth and respected the minimum turning angle. The altitude-based deconfliction strategy would ensure safe separation despite the converging geometry of the paths. The simulation confirmed that the CGA-based planner produces feasible, efficient, and synchronizable paths, meeting all core requirements for initiating a complex formation drone light show.
In conclusion, the integration of a Cellular Genetic Algorithm with specific time and coordination strategies presents a robust solution for the multi-drone assembly path planning problem. The CGA’s structured population effectively maintains diversity, leading to a high success rate in finding quality paths that avoid threats and are energy-efficient. The incorporation of a velocity-based cost function and a waypoint scheduling protocol directly addresses the critical time synchronization requirement inherent to a formation drone light show. Coupled with a layered altitude strategy for collision avoidance, this framework provides a comprehensive off-line planning tool. It ensures that a fleet of drones can autonomously, safely, and punctually navigate from their launch pads to the precise starting positions of their performance, setting the stage for the subsequent, perfectly choreographed aerial ballet that defines a modern formation drone light show. Future work may integrate dynamic obstacle avoidance and real-time replanning to handle unforeseen disturbances during the actual show execution.