The coordinated operation of multiple unmanned aerial vehicles (UAVs) has become a cornerstone of modern aerial systems, offering significant advantages in mission efficiency, robustness, and capability over single-agent operations. A fundamental prerequisite for many cooperative missions, such as collaborative reconnaissance, distributed sensing, or coordinated strikes, is the successful and timely assembly of the UAV group into a specified formation at a designated rendezvous point. This process, known as formation rendezvous, necessitates sophisticated path planning that must satisfy not only the individual kinematic constraints and threat avoidance requirements of each drone but also critical multi-agent coordination constraints, primarily simultaneous time-of-arrival and inter-agent collision avoidance. The complexity of this problem lies in its high-dimensional, coupled search space where the optimal path for one agent is dependent on the paths chosen by others, all operating within a common, potentially hostile environment. Traditional path planning algorithms often struggle with the dual challenges of global optimization and satisfying intricate multi-constraint conditions inherent in drone formation assembly.
This work addresses the multi-UAV formation rendezvous route planning problem by proposing a hierarchical and synergistic approach. At the core is a novel single-UAV path planning method based on a Cellular Genetic Algorithm (CGA), enhanced with a time-constraint-aware cost function. This algorithm is designed to efficiently navigate complex threat environments while inherently considering the temporal requirements for rendezvous. Building upon this robust single-agent planner, a centralized cooperative strategy is formulated to harmonize the individually planned paths, enforcing precise time coordination through velocity modulation and guaranteeing safety via a layered altitude-based collision avoidance scheme. The integrated framework ensures that the final set of paths is executable, synchronized, and safe, fulfilling the critical requirements for autonomous drone formation assembly.
1. Problem Statement and Formulation
The formation rendezvous problem for a fleet of m UAVs is defined within a two-dimensional operational environment. For each UAVk (where k = 1, 2, …, m), the planning task is to find a feasible path from its unique start point Sk(xsk, ysk) to a common goal/rendezvous point G(xg, yg). The environment contains q known threat zones, each modeled as a disc with center Wj(xj, yj) and radius rj. Each UAV is subject to its own kinematic constraints, including a minimum turning angle φmin, and a bounded velocity range [vmin, vmax] with a preferred cruise velocity vc.
The multi-objective nature of the problem requires minimizing the following for the collective drone formation:
- Threat Exposure: The cumulative proximity of all UAV paths to all threat zones.
- Total Path Length: The sum of distances traveled by all UAVs to conserve energy.
- Velocity Deviation: The deviation from the ideal cruise speed for each UAV.
Furthermore, the solution must enforce two critical cooperative constraints:
- Time Coordination: All UAVs must arrive at the rendezvous point G within a specified time window, ideally simultaneously at time T. This imposes a coupling between path length and allowable velocity for each agent.
- Collision Avoidance: During the entire mission, the physical separation between any two UAVs must be greater than a specified safety distance Ds to prevent mid-air collisions.
The primary challenge is to solve this coupled, constrained, multi-objective optimization problem efficiently.
2. Single-UAV Path Planning via Cellular Genetic Algorithm
The foundation of our cooperative strategy is a reliable and efficient path planner for a single UAV. We employ a Cellular Genetic Algorithm, a population-based evolutionary algorithm with a structured spatial topology, known for maintaining population diversity and balancing global exploration with local refinement—a crucial property for navigating complex, constrained search spaces typical in drone formation member routing.
2.1 Path Encoding and Initialization
A candidate path for a UAV is represented as a sequence of (n+2) waypoints in 2D space: Path = {P0, P1, …, Pn, Pn+1}, where P0 ≡ S (start), Pn+1 ≡ G (goal), and Pi(xi, yi) for i=1,…,n are the navigational waypoints. The number of intermediate waypoints n is fixed per planning instance to simplify the search space dimensionality.
Population initialization uses a directed, heuristic method to promote feasible and diverse initial paths. Each waypoint Pi is generated from its predecessor Pi-1 as follows:
$$ x_i = x_{i-1} + l \cdot \cos(\theta_{i-1} + \gamma) $$
$$ y_i = y_{i-1} + l \cdot \sin(\theta_{i-1} + \gamma) $$
where:
- $l$ is a variable segment length, randomly chosen but satisfying $l \geq \frac{\overrightarrow{SG}}{n}$ to ensure progress toward the goal.
- $\theta_{i-1}$ is the bearing angle from Pi-1 to the goal G.
- $\gamma$ is a random perturbation angle uniformly drawn from $[-90^\circ, 90^\circ]$.
This method biases path growth towards the goal while introducing randomness, creating an initial population of forward-progressing, geometrically varied paths suitable for the CGA to refine.
2.2 Fitness Function Design
The fitness function quantitatively evaluates the quality of a single UAV’s path. A higher fitness indicates a better path. The total cost $C$ of a path is a weighted sum of three penalty terms: Threat Cost $S$, Path Length Cost $L$, and Velocity Cost $V$.
$$ C = k_s \cdot S + k_l \cdot L + k_v \cdot V $$
where $k_s$, $k_l$, and $k_v$ are user-defined weighting coefficients that balance the importance of each objective. The fitness $F$ is then computed as:
$$ F = F_{max} – C $$
where $F_{max}$ is a sufficiently large constant to ensure positive fitness values.
1. Threat Cost (S): This cost penalizes proximity to threat zones. For each path segment $\overrightarrow{P_i P_{i+1}}$ and each threat center $W_j$, the minimum distance $d_{ij}$ from the threat to the segment is calculated. The geometry involves finding the perpendicular foot $P_{ij}’$ from $W_j$ to the line containing the segment. Let $\alpha_{ij}$ be the angle between $\overrightarrow{P_i P_{i+1}}$ and $\overrightarrow{P_i W_j}$, and $\beta_{ij}$ the angle between $\overrightarrow{P_{i+1} P_i}$ and $\overrightarrow{P_{i+1} W_j}$.
$$ d_{ij} = \begin{cases}
\|\overrightarrow{P_{ij}’ W_j}\| & \text{if } 0^\circ < \alpha_{ij}, \beta_{ij} \le 90^\circ \text{ (foot on segment)}\\
\|\overrightarrow{P_i W_j}\| & \text{if } 90^\circ < \alpha_{ij} < 180^\circ\\
\|\overrightarrow{P_{i+1} W_j}\| & \text{if } 90^\circ < \beta_{ij} < 180^\circ
\end{cases} $$
The threat cost for this segment-threat pair is:
$$ s_{ij} = \begin{cases}
0 & \text{if } d_{ij} \ge r_j \\
r_j – d_{ij} & \text{if } d_{ij} < r_j
\end{cases} $$
The total threat cost for the path is the sum over all segments and all threats:
$$ S = \sum_{i=0}^{n} \sum_{j=1}^{q} s_{ij} $$
2. Path Length Cost (L): This is simply the total Euclidean distance of the path:
$$ L = \sum_{i=0}^{n} \|\overrightarrow{P_i P_{i+1}}\| $$
3. Velocity Cost (V) – The Time Coordination Enabler: This is a critical component for drone formation rendezvous. Given a desired rendezvous time $T$, the required average speed $v_{req}$ for a path of length $L$ is:
$$ v_{req} = \frac{L}{T} $$
The velocity cost penalizes deviation from the UAV’s preferred cruise speed $v_c$, but only if $v_{req}$ lies within the feasible speed range $[v_{min}, v_{max}]$. If $v_{req}$ is outside this range, the path is assigned a prohibitively high cost. Otherwise:
$$ V = | v_{req} – v_c | $$
This formulation encourages the single-agent planner to find paths whose required speed (for on-time arrival) is close to the energy-efficient cruise speed, making time coordination practically achievable without extreme velocity adjustments.
2.3 Cellular Genetic Algorithm Framework
The CGA operates on a population of $N$ candidate paths, spatially arranged in a 2D toroidal grid (u × w cells, where N = u·w). Each cell holds one individual (path). The algorithm’s power comes from its structured neighborhood interaction, defined by a Moore neighborhood (the eight surrounding cells). Evolution occurs locally within these neighborhoods.
Genetic Operators within the Cellular Framework:
- Selection: For the central individual in a neighborhood, a partner is selected from among its eight neighbors using a roulette-wheel selection based on their fitness values. The probability $p_s^{(c)}$ of selecting neighbor $c$ is:
$$ p_s^{(c)} = \frac{F_c}{\sum_{d=1}^{8} F_d} $$ - Crossover: With probability $p_c$, a crossover operation occurs between the central individual $Q_{cen}$ and the selected neighbor $Q_{ngb}$. A random crossover point $c$ (a waypoint index between 1 and n-1) is chosen. The path segments after point $c$ are exchanged between the two parents, and the new path with the higher fitness between the two possible offspring is retained as $Q_{new}$.
- Mutation: With probability $p_m$, the new individual $Q_{new}$ undergoes mutation. A random waypoint $P_e$ is selected. Its distance to the nearest threat is calculated: $h_{min} = \min_j(\|\overrightarrow{P_e W_j}\| – r_j)$. If $h_{min} > 0$, the point is safe and mutation may be skipped. If $h_{min} \le 0$, the point is inside or on the edge of a threat and is mutated outward:
$$ x_e’ = x_e + k_e \cdot |h_{min}| \cdot \cos(\omega) $$
$$ y_e’ = y_e + k_e \cdot |h_{min}| \cdot \sin(\omega) $$
where $k_e \in [1, 2]$ is a random gain and $\omega$ is a random angle. This directed mutation pushes waypoints away from threats, accelerating convergence to safe paths. - Replacement: The fitness of the newly generated individual $F_{new}$ is compared to the fitness of the original central individual $F_{cen}$. Replacement occurs only if $F_{new} > F_{cen}$, ensuring monotonic improvement within each cell.
This localized evolution, performed synchronously for all cells, allows promising genetic material to diffuse slowly across the grid, preserving diversity and preventing premature convergence—a common pitfall in standard genetic algorithms when applied to complex drone formation member path planning.
2.4 Path Smoothing
Paths generated by the CGA may contain sharp turns that violate the UAV’s minimum turning radius constraint, derived from $φ_{min}$. A post-processing smoothing step is applied. For any three consecutive waypoints $(P_{i-1}, P_i, P_{i+1})$ creating a turn angle less than $φ_{min}$, a check is performed. If the direct line $\overrightarrow{P_{i-1}P_{i+1}}$ does not intersect a threat zone, $P_i$ is moved to the midpoint of this line. If the direct line is unsafe, two new waypoints are inserted at fractions (e.g., 1/3 and 2/3) along the original segments $P_{i-1}P_i$ and $P_iP_{i+1}$, and these new points are connected, creating a gentler, feasible turn.
3. Multi-UAV Cooperative Formation Strategy
The single-UAV CGA planner produces a set of $m$ high-quality, time-aware paths. The cooperative strategy then acts as a supervisor to ensure these paths work harmoniously for the drone formation. This involves two sequential steps: Time Coordination and Collision Avoidance.
3.1 Time Coordination via Velocity Scheduling
The initial CGA planning ensures each path’s required average speed $v_{k, req} = L_k / T$ is near $v_c$ and within $[v_{min}, v_{max}]$. To handle real-world uncertainties and provide precise control, a waypoint-based velocity schedule is created for each UAV. Each waypoint $P_{k,i}$ in the smoothed path is augmented with a scheduled arrival time $t_{k,i}$:
$$ t_{k,i} = \frac{L_{k,i}}{v_{k, req}} $$
where $L_{k,i}$ is the cumulative path length from the start Sk to waypoint $P_{k,i}$. During execution, as UAVk reaches $P_{k,i}$ at actual time $t_{k, actual}$, it calculates the required speed for the next leg to meet the schedule for $P_{k,i+1}$:
$$ v_{k, next} = \frac{\|\overrightarrow{P_{k,i} P_{k,i+1}}\|}{t_{k,i+1} – t_{k, actual}} $$
This closed-loop, leg-by-leg speed adjustment allows each UAV to compensate for small deviations (e.g., wind, minor course corrections) and ensures the entire drone formation converges on the rendezvous point G at precisely the desired time T, fulfilling the synchronized assembly requirement.
3.2 Collision Avoidance via Layered Altitude Allocation
Independently planned 2D paths may cross or come within the safety distance $D_s$. To resolve this without computationally expensive re-planning, we leverage the third dimension: altitude. UAVs with intersecting or proximitous 2D paths are assigned to different flight levels (altitudes). A simple rule is applied: the UAV with the longest 2D path $L_k$ is assigned the lowest altitude, and others are assigned incrementally higher altitudes, with a vertical separation $\Delta H \ge D_s$. This strategy effectively eliminates the risk of collision in the 3D airspace, as paths now occupy distinct horizontal layers. It is a pragmatic and efficient solution for drone formation assembly, transforming a complex 4D (space-time) conflict resolution problem into a simple ordinal assignment based on path length.
4. Simulation Experiments and Analysis
To validate the proposed integrated framework, a simulation scenario involving a three-UAV drone formation was constructed. The environment and parameters are summarized below.
| Parameter | Value / Description |
|---|---|
| UAV Start Points | S1(10,10) km, S2(20,0) km, S3(0,30) km |
| Rendezvous Point (G) | (100, 100) km |
| Number of Threats (q) | 6 |
| Threat Centers & Radii (Wj, rj) | W1(15,88), r1=10km; W2(23,50), r2=15km; W3(25,15), r3=10km; W4(57,10), r4=10km; W5(68,65), r5=15km; W6(55,75), r6=20km |
| UAV Kinematic Constraints | φmin = 60°, vmin=40 km/h, vmax=200 km/h, vc=140 km/h |
| Safety Distance (Ds) | 0.08 km (80 m) |
| Rendezvous Time (T) | 60 minutes (1 hour) |
| CGA Parameters | Population N=40 (5×8 grid), Waypoints per path n=9, Max Generations=50, pc=0.8, pm=0.1, ks=100, kl=1, kv=10 |
The CGA successfully planned three distinct paths for the UAVs. The calculated required speeds were: v1,req = 137.69 km/h, v2,req = 142.49 km/h, v3,req = 141.84 km/h. All values are within the operational bounds and closely clustered around the cruise speed vc = 140 km/h, demonstrating the effectiveness of the velocity cost term in generating time-coordination-friendly paths.
The generated paths show intelligent threat avoidance, taking detours around high-risk areas while maintaining progress toward the goal. The velocity scheduling mechanism would use the waypoint times derived from these paths and speeds to guide real-time velocity adjustments. Furthermore, since the 2D paths of UAV1 and UAV3 come relatively close in certain sectors, the altitude layering strategy would be invoked. Based on path lengths (L2 > L3 > L1 in this case), UAV2 would fly at the lowest altitude, UAV3 at a medium altitude (+ΔH), and UAV1 at the highest altitude (+2ΔH), ensuring complete 3D separation.
| Waypoint | UAV1: P1,i (x, y, t) km, km, min | UAV2: P2,i (x, y, t) km, km, min | UAV3: P3,i (x, y, t) km, km, min |
|---|---|---|---|
| P1 | (13.80, 23.56, 6.14) | (36.65, 5.93, 7.44) | (3.23, 45.19, 6.67) |
| P3 | (40.59, 33.27, 18.89) | (56.40, 23.74, 18.91) | (19.38, 69.02, 19.21) |
| P5 | (60.18, 49.03, 30.96) | (79.15, 31.76, 29.58) | (34.94, 92.05, 31.21) |
| P7 | (81.39, 65.39, 42.71) | (87.59, 56.64, 40.78) | (63.93, 100.13, 44.31) |
| P9 | (92.03, 90.41, 54.57) | (97.81, 83.08, 52.82) | (87.65, 98.92, 54.76) |
The simulation confirms the core capabilities of the framework. The CGA-based single-path planner demonstrates high search success and stability, consistently finding safe, efficient, and time-feasible routes. The integrated cooperative strategy then seamlessly enforces the critical multi-agent constraints necessary for a successful drone formation rendezvous. The paths respect all kinematic limits, are synchronized for simultaneous arrival via velocity control, and are rendered collision-free through altitude deconfliction.
5. Conclusion
This work presented a comprehensive solution to the multi-UAV formation rendezvous path planning problem. The proposed methodology combines a robust single-agent path planner with a pragmatic multi-agent coordination layer. The single-agent planner, built upon a Cellular Genetic Algorithm, excels in finding high-quality paths in complex threat environments due to its inherent ability to maintain population diversity and avoid local optima. Its fitness function is uniquely augmented with a velocity cost term that embeds time-constraint awareness directly into the search process, priming each path for easy temporal coordination.
The cooperative strategy completes the solution by addressing the two defining challenges of drone formation assembly. The velocity scheduling protocol provides a dynamic mechanism for precise time synchronization, compensating for execution variances. The layered altitude assignment offers an efficient and deterministic solution to inter-agent collision avoidance, transforming potential conflicts into safe vertical separation.
The simulation results validate the effectiveness and stability of the integrated approach. The algorithm successfully plans a set of paths that satisfy UAV kinematic constraints, minimize threat exposure and fuel consumption, and—most importantly—meet the stringent requirements of time-coordinated and safe assembly for the drone formation. Future work may focus on extending the approach to dynamic environments with pop-up threats, integrating real-time communication constraints into the coordination layer, and exploring decentralized versions of the cooperative strategy for enhanced scalability and robustness in large-scale drone formation operations.