In recent years, unmanned aerial vehicles (UAVs) have gained widespread use as aerial platforms for reconnaissance, rescue, and observation tasks in both military and civilian domains. Thanks to the high efficiency and reliability of drone formation operations, UAVs hold even broader application prospects. However, more extensive applications and complex missions impose higher demands on the technologies and performance of drone formations. Path planning, as the foundation for ensuring safe and efficient completion of assigned tasks, is a key focus in UAV research. Particularly during drone formation flights, real-time avoidance path planning for sudden threats is of significant importance. This paper addresses the pop-up threat avoidance problem for multiple UAV formations in complex environments, proposing a real-time path planning method based on convex optimization algorithms. The approach models the threat avoidance problem as a constrained optimization problem, transforms it into convex sub-problems via equivalent transformations, and solves them iteratively. Simulation results validate the algorithm’s effectiveness and efficiency in achieving real-time threat avoidance for drone formations.
The core challenge in drone formation path planning lies in balancing safety, efficiency, and real-time performance. Traditional methods often rely on intelligent algorithms like genetic algorithms or particle swarm optimization, which can be computationally intensive and unsuitable for real-time applications in dynamic environments. In contrast, convex optimization offers a framework for efficient and guaranteed solutions, making it ideal for onboard computation in UAVs. This paper explores how convex optimization can be leveraged to handle pop-up threats—sudden, unforeseen obstacles such as enemy radars or missiles—while maintaining formation cohesion and minimizing path length. The drone formation must adapt quickly to these threats, requiring a planning algorithm that is both agile and robust. By formulating the problem mathematically and applying convex techniques, we demonstrate a practical solution for real-world scenarios.
To begin, we model the drone formation and threat environment. Consider a formation of \( n \) drones operating in a two-dimensional plane. Each drone \( i \) is described by its position \((x_i, y_i)\) and heading angle \(\theta_i\). The dynamics of drone \( i \) are given by the following nonlinear equations, which capture basic motion constraints:
$$ \dot{x}_i = V_i \cos \theta_i $$
$$ \dot{y}_i = V_i \sin \theta_i $$
$$ \dot{\theta}_i = u_i $$
Here, \( V_i \) is the constant speed of drone \( i \), and \( u_i \) is the control input governing the turning rate. These equations assume a simplified kinematic model, which is sufficient for path planning at a higher level. The drone formation must adhere to performance constraints, including minimum turning radius \( r_{\text{min}} \) and maximum flight distance \( L_{\text{max}} \). Additionally, to avoid collisions within the drone formation, a minimum separation distance \( d_{\text{min}} \) is enforced between any two drones \( i \) and \( j \). These constraints ensure feasible and safe paths for the entire drone formation.
Pop-up threats are modeled as circular regions in the plane. Two types of threats are considered: detection threats and strike threats. Detection threats represent areas where the drone formation might be detected by enemy sensors; drones should minimize exposure time in these zones. Strike threats represent areas where drones would be engaged and destroyed; drones must completely avoid these zones. For a threat \( k \), let its center be \((x_{\text{poi},k}, y_{\text{poi},k})\) and radius be \( r_{\text{poi},k} \). The threat region is defined as:
$$ (x – x_{\text{poi},k})^2 + (y – y_{\text{poi},k})^2 \leq r_{\text{poi},k}^2 $$
In practice, the drone formation detects these threats in real-time via onboard sensors, necessitating rapid replanning. The goal is to plan paths for all drones from initial positions \((x_i^s, y_i^s)\) to final positions \((x_i^f, y_i^f)\) while avoiding threats and satisfying constraints. This can be formulated as a constrained optimization problem. For each drone \( i \), we seek a path \((x_i(t), y_i(t))\) over time \( t \in [0, T] \) that minimizes a cost function, subject to boundary conditions and constraints.
The cost function combines multiple objectives: minimizing path length, minimizing exposure to detection threats, and completely avoiding strike threats. Let \( L_i \) be the total path length for drone \( i \), given by:
$$ L_i = \int_0^T \sqrt{\left( \frac{dx_i(t)}{dt} \right)^2 + \left( \frac{dy_i(t)}{dt} \right)^2 } dt $$
To account for detection threats, we define an equivalent exposure length \( L_{i,\text{equ}} \) that penalizes travel through detection zones. For strike threats, a binary indicator function \( f_{i3} \) is used, where \( f_{i3} = 0 \) if the path intersects a strike threat, and 1 otherwise. The overall cost for drone \( i \) is a weighted sum:
$$ f_i = f_{i3} \left[ \eta f_{i1} + (1 – \eta) f_{i2} \right] $$
where \( f_{i1} = L_i \), \( f_{i2} = L_{i,\text{equ}} \), and \( \eta \in [0,1] \) is a weighting coefficient. The constrained optimization problem for the drone formation is then:
$$ \min \sum_{i=1}^n f_i $$
subject to:
$$ (x_i(0), y_i(0)) = (x_i^s, y_i^s) $$
$$ (x_i(T), y_i(T)) = (x_i^f, y_i^f) $$
$$ L_i \leq L_{\text{max}}, \quad \text{for all } i $$
$$ r_i \geq r_{\text{min}}, \quad \text{for all } i $$
$$ d_{ij} \geq d_{\text{min}}, \quad \text{for all } i \neq j $$
Here, \( r_i \) refers to the effective turning radius along the path, and \( d_{ij} \) is the distance between drones \( i \) and \( j \). This problem is non-convex due to the nonlinear dynamics and threat constraints, making direct solution computationally expensive. To enable real-time planning for the drone formation, we transform it into a series of convex optimization problems via equivalent constraints and iterative methods.
The key idea is to discretize the path into \( m \) nodes and use a reference line approach. For each drone \( i \) at node \( k \), consider the straight line from its current position \((x_i(k), y_i(k))\) to the final goal \((x_i^f, y_i^f)\). Let \( \delta_i(k) \) be the deviation angle from this reference line, as shown in Figure 1. Minimizing path length corresponds to minimizing \( \delta_i(k) \), since smaller deviations yield shorter paths. The cost function over all drones and nodes can be approximated as:
$$ F = \boldsymbol{\delta}^T \mathbf{E} \boldsymbol{\delta} $$
where \( \boldsymbol{\delta} = [\delta_1(k), \delta_2(k), \ldots, \delta_n(k)]^T \) and \( \mathbf{E} \) is an identity matrix. Constraints are then reformulated in terms of \( \delta_i(k) \). The minimum turning radius constraint limits the allowable deviation angle to a range \( \delta\theta_i(k) = [\delta\theta_{i,a}(k), \delta\theta_{i,b}(k)] \). Threat avoidance constraints are handled by computing tangent lines from the current position to threat circles, defining safe angular sectors \( \delta s_i(k) = [\delta s_{i,a}(k), \delta s_{i,b}(k)] \). The feasible region for \( \delta_i(k) \) is the intersection of \( \delta\theta_i(k) \) and \( \delta s_i(k) \), denoted as \( \delta\theta s_i(k) = [\delta\theta s_{i,a}(k), \delta\theta s_{i,b}(k)] \).
To convexify the problem, we apply a sine transformation. Let \( \varepsilon_i(k) = \sin(\delta_i(k)) \). Then the constraint \( \delta\theta s_{i,a}(k) \leq \delta_i(k) \leq \delta\theta s_{i,b}(k) \) becomes:
$$ a_i(k) \leq \varepsilon_i(k) \leq b_i(k) $$
where \( a_i(k) = \sin(\delta\theta s_{i,a}(k)) \) and \( b_i(k) = \sin(\delta\theta s_{i,b}(k)) \). This transformation yields linear constraints on \( \varepsilon_i(k) \), which are convex. The cost function becomes quadratic in \( \boldsymbol{\varepsilon} = [\varepsilon_1(k), \varepsilon_2(k), \ldots, \varepsilon_n(k)]^T \). Thus, at each node \( k \), we solve a convex optimization problem:
$$ \min \frac{1}{2} \boldsymbol{\varepsilon}^T \mathbf{P} \boldsymbol{\varepsilon} $$
subject to:
$$ \mathbf{G} \boldsymbol{\varepsilon} \leq \mathbf{h} $$
Here, \( \mathbf{P} = 2\mathbf{E} \), and \( \mathbf{G} \), \( \mathbf{h} \) encode the bounds \( a_i(k) \) and \( b_i(k) \). Specifically, \( \mathbf{G} \) is a block diagonal matrix with entries \( 1 \) and \( -1 \) for each drone, and \( \mathbf{h} = [b_1(k) – a_1(k), b_2(k) – a_2(k), \ldots, b_n(k) – a_n(k)]^T \). This problem can be solved efficiently using standard convex optimization solvers, such as those based on interior-point methods.
The overall algorithm proceeds iteratively over nodes. Starting from the initial position, each drone selects a deviation angle \( \delta_i(k) \) by solving the convex problem, then moves a distance \( l_i(k) \) in that direction. The distance \( l_i(k) \) is randomly chosen within a range (e.g., \( [0.3 r_i(k), 0.5 r_i(k)] \), where \( r_i(k) \) is the distance to the goal) to introduce variability and avoid collisions in the drone formation. This process repeats until the line from the current node to the goal no longer intersects any threats. The resulting sequence of nodes forms a piecewise-linear path. To generate smooth trajectories suitable for drone dynamics, we fit a continuous path function using cubic interpolation over time \( T \). Time coordination ensures that drones maintain safe separations; if minimum distances are violated, time allocations are adjusted and paths are refitted.
The step-by-step algorithm for the drone formation is as follows:
- Initialize parameters: drone initial positions \((x_i^s, y_i^s)\), goal positions \((x_i^f, y_i^f)\), threat parameters \((x_{\text{poi},k}, y_{\text{poi},k}, r_{\text{poi},k})\), minimum turning radius \( r_{\text{min}} \), minimum separation \( d_{\text{min}} \), and time horizon \( T \).
- Begin iteration over path nodes \( k = 1, 2, \ldots, m \).
- For each drone \( i \), compute the reference line \( r_i(k) \) from current position to goal, and identify threats intersecting this line.
- Determine the feasible angular sector \( \delta\theta s_i(k) \) based on turning constraints and threat tangents.
- Formulate the convex optimization problem for node \( k \) as described above.
- Solve the convex problem to obtain optimal deviation angles \( \delta_i(k) \).
- Select a travel distance \( l_i(k) \) randomly within a specified range.
- Update each drone’s position according to \( \delta_i(k) \) and \( l_i(k) \).
- Repeat steps 3-8 until no threats intersect the reference lines for all drones.
- Divide the total time \( T \) into \( m-1 \) segments corresponding to nodes, and fit cubic path functions \((x_i(t), y_i(t))\) for each drone.
- Check if minimum separations \( d_{ij} \geq d_{\text{min}} \) are maintained over time; if not, adjust time segmentation and refit paths.
- Output the final path functions for the drone formation.
This algorithm leverages convex optimization for efficiency, ensuring real-time performance crucial for pop-up threat avoidance in drone formations. The use of random step lengths enhances robustness by preventing synchronous movements that could lead to collisions.
To validate the algorithm, simulations were conducted in MATLAB using the CVX toolbox. The environment is a 2000 m × 2000 m area with a drone formation of \( n = 4 \) drones. Initial and goal positions are set as follows, representing a typical formation scenario:
| Drone | Initial Position (m) | Goal Position (m) |
|---|---|---|
| 1 | (150, 100) | (1600, 1850) |
| 2 | (250, 100) | (1600, 1750) |
| 3 | (100, 150) | (1550, 1900) |
| 4 | (100, 250) | (1450, 1900) |
The minimum turning radius equivalent angle is \( \theta_r = \pi/3 \), and the minimum separation distance is \( d_{\text{min}} = 10 \) m. Pop-up threats are randomly generated: 8 threats with radii between 100 and 150 m, and centers between 400 and 1600 m. Specific threat parameters are summarized in Table 1.
| Threat ID | Center (m) | Radius (m) |
|---|---|---|
| 1 | (429.32, 1316.68) | 122.62 |
| 2 | (948.22, 781.19) | 121.13 |
| 3 | (781.02, 1288.78) | 117.98 |
| 4 | (1184.42, 1292.42) | 127.91 |
| 5 | (1548.32, 527.10) | 137.13 |
| 6 | (1522.88, 1217.87) | 121.22 |
| 7 | (949.46, 955.91) | 121.47 |
| 8 | (688.57, 654.59) | 106.24 |
The total time for threat avoidance and reformation is \( T = 150 \) s. Simulation results show that the drone formation successfully avoids all threats while maintaining constraints. The planned paths, derived from convex optimization iterations, are shown in Figure 2(a)—drones adjust their trajectories along threat tangents, minimizing path length. After cubic interpolation, smooth trajectories are obtained (Figure 2(b)), demonstrating feasibility for drone dynamics. The relative distances between drones over time are plotted in Figures 3-5; all distances remain above \( d_{\text{min}} = 10 \) m, confirming collision avoidance within the drone formation.
To further test algorithm agility, a second scenario with drones starting from dispersed positions was simulated. Initial positions are: Drone 1 at (600, 500) m, Drone 2 at (750, 800) m, Drone 3 at (300, 1250) m, and Drone 4 at (1150, 250) m, with the same goals and threats. Results in Figure 6 show that drones quickly react to nearby pop-up threats, taking near-optimal detours, and eventually reform the formation. Relative distance plots (Figures 7-9) indicate safe separations, though distances shrink near goals due to convergence—this is managed by time coordination in the path fitting step.
We analyzed algorithm performance under varying threat densities and drone speeds. Success rate is defined as the percentage of runs where the drone formation achieves threat-free paths satisfying all constraints. For a fixed threat radius of 150 m and random centers in [400, 1600] m, Table 2 shows success rates over 100 runs for different threat counts, without considering threat clustering.
| Number of Threats | Success Rate (%) |
|---|---|
| 2 | 100 |
| 4 | 100 |
| 6 | 89 |
| 8 | 91 |
| 10 | 70 |
| 12 | 64 |
| 14 | 63 |
| 16 | 55 |
| 18 | 60 |
| 20 | 49 |
Success rate generally decreases with more threats, but fluctuations occur due to random threat placement. To account for clustering, we introduce \( d_{\text{cent}} \) as the minimum distance between threat centers. Figure 10 plots success rate against threat count for different \( d_{\text{cent}} \) values. When threats are sparse (\( d_{\text{cent}} \) large) or few (\( \leq 4 \)), rates are near 100%. As threats increase and cluster more tightly (\( d_{\text{cent}} \) small), success drops, reflecting the increased difficulty for the drone formation to find feasible paths.
Drone speed influences the minimum turning radius constraint. We equivalently vary the turning angle limit \( \theta_r \). Figure 11 shows success rate versus \( \theta_r \). Rate improves with larger \( \theta_r \) (i.e., smaller turning radius), as drones have more maneuverability to avoid threats. Beyond \( \theta_r \approx \pi/2 \), gains diminish, indicating a saturation point for the drone formation’s agility.
Computational efficiency is critical for real-time application. On a PC with Intel Core i7-4510U CPU and MATLAB 2010b, average runtimes over 100 trials for varying threat counts are:
| Number of Threats | Average Runtime (s) |
|---|---|
| 2 | 0.0117 |
| 4 | 0.0159 |
| 6 | 0.0208 |
| 8 | 0.0380 |
| 10 | 0.0436 |
All runtimes are under 0.05 seconds, meeting real-time requirements for pop-up threat avoidance in drone formations. The increase with threat count is due to more complex feasible region calculations, but remains manageable.
In conclusion, this paper presents a convex optimization-based path planning algorithm for drone formations facing pop-up threats. By modeling the problem as a constrained optimization and transforming it into convex sub-problems via equivalent constraints and sine transformations, we achieve efficient iterative solutions. The algorithm generates smooth, collision-free paths that respect drone dynamics and formation safety, as validated through simulations. Key advantages include real-time performance, high success rates under varying conditions, and adaptability to different threat scenarios. Future work could extend the method to three-dimensional environments, incorporate uncertain threat information, or integrate with model predictive control for dynamic replanning. This approach offers a practical tool for enhancing the autonomy and resilience of drone formations in complex missions.
The drone formation paradigm is rapidly evolving, and robust path planning is essential for its success. Convex optimization provides a solid mathematical foundation for such tasks, balancing optimality and computational tractability. As drone technologies advance, algorithms like this will play a crucial role in enabling safe and efficient operations in contested airspace.