In recent years, the application of multi-rotor drones in military and civilian fields has expanded significantly due to their maneuverability, controllability, and capabilities such as hover and vertical take-off. One critical technology enabling effective deployment is route planning for drone formation, which enhances survival rates in complex environments. However, dynamic route planning in unknown settings with obstacles remains a challenge, particularly for coordinated drone formation. In this article, I address this issue by proposing an improved hybrid algorithm that combines ant colony optimization (ACO) and Rapidly-exploring Random Tree (RRT) methods. My approach focuses on optimizing both global and local path planning for drone formation, ensuring collision avoidance and time coordination. I will detail the methodology, including environment modeling using Voronoi diagrams, ACO for initial route planning, enhanced RRT for dynamic obstacle avoidance, and a cooperative avoidance-reconstruction strategy for drone formation. Simulation results demonstrate the efficiency and superiority of this hybrid algorithm over conventional methods.
The core problem in dynamic route planning for drone formation involves navigating multiple drones from a start point to a destination while avoiding static and moving obstacles, preventing inter-drone collisions, and meeting time coordination constraints. Traditional algorithms often struggle with real-time adaptability and optimality. To overcome this, I adopt a layered rolling planning framework. This reduces computational complexity by separating the problem into global and local layers. The global layer uses ACO to pre-compute an optimal initial route for the drone formation, considering static threats. The local layer employs an improved RRT algorithm to handle dynamic obstacles in real-time. Additionally, I introduce a cooperative avoidance-reconstruction strategy to maintain drone formation integrity after obstacle avoidance. This integrated approach ensures that the drone formation can adapt to changing environments efficiently.
To model the flight environment, I utilize a weighted Voronoi diagram. This geometric structure divides the space into regions based on obstacle positions, creating a network of nodes and edges that represent feasible flight paths. For a 600 m × 600 m area with static threats, the Voronoi diagram simplifies the environment into a graph, as shown in the following illustration. Each edge in the graph corresponds to a potential route, and I assign a cost to each edge based on threat exposure and fuel consumption. The cost function for an edge $e_i$ is defined as:
$$J_i = k_1 J_{\text{threat},i} + (1 – k_1) J_{\text{fuel},i}$$
where $J_{\text{threat},i}$ represents the threat cost calculated from distances to obstacles at points along the edge, and $J_{\text{fuel},i}$ is proportional to the edge length $L_i$. Specifically, $J_{\text{threat},i}$ is computed as:
$$J_{\text{threat},i} = L_i \sum_{j=1}^{n} \left( \frac{1}{d_{1/6i,j}^4} + \frac{1}{d_{1/2i,j}^4} + \frac{1}{d_{5/6i,j}^4} \right)$$
Here, $d$ denotes distances to threats, and $k_1$ is a weight factor balancing threat and fuel costs. This modeling approach accelerates algorithm convergence by reducing the search space for the drone formation.
For global route planning, I apply the ant colony algorithm. This metaheuristic mimics ant foraging behavior to find optimal paths in a graph. In the context of drone formation, I treat the entire formation as a single entity during initial planning. Ants are placed at the start node, and they move through the Voronoi graph based on a probability function that considers pheromone levels and heuristic information. The transition probability for ant $k$ from node $i$ to node $j$ is:
$$P_{ij}^k = \frac{[\tau_{ij}(t)]^\alpha [\eta_{ij}(t)]^\beta}{\sum_{j \in a_i} [\tau_{ij}(t)]^\alpha [\eta_{ij}(t)]^\beta} \quad \text{if } j \in a_i$$
where $\tau_{ij}(t)$ is the pheromone concentration, $\eta_{ij}(t) = 1/J_i$ is the heuristic function based on edge cost, $\alpha$ and $\beta$ are parameters controlling influence, and $a_i$ is the set of reachable nodes. After each iteration, pheromones are updated to reinforce better paths:
$$\tau_{ij}(t+1) = (1-\rho) \tau_{ij}(t) + \Delta \tau_{ij}$$
with $\Delta \tau_{ij} = \sum_{k=1}^{n} \Delta \tau_{ij}^k$ and $\Delta \tau_{ij}^k = Q/L_k$ if ant $k$ traverses the edge. $Q$ is a constant, and $L_k$ is the path length. This process continues until convergence, yielding an initial route that minimizes overall cost for the drone formation while avoiding static obstacles.
In local dynamic planning, I enhance the RRT algorithm to handle moving obstacles. The standard RRT grows a tree randomly from the start point toward the goal, but it can be inefficient. My improvements include obstacle direction prediction and path pruning. During flight, each drone in the drone formation uses a rolling window to detect obstacles within a radius. If an obstacle is detected, its velocity $\vec{V}_b$ is estimated:
$$\vec{V}_b = (x_2 – x_1 + x_{U1} – x_{U2}, y_2 – y_1 + y_{U1} – y_{U2})$$
where $(x_1, y_1)$ and $(x_2, y_2)$ are obstacle positions at times $t$ and $t+T$, and $(x_{U1}, y_{U1})$ and $(x_{U2}, y_{U2})$ are drone positions. The obstacle’s reachable area is inflated to a circle of radius $T V_b$. The improved RRT then adjusts its search direction by incorporating $\vec{V}_b$ to avoid collisions. The algorithm steps are: initialize with start $q_{\text{init}}$ and goal $q_{\text{goal}}$; generate random nodes $q_{\text{rand}}$ using a chaotic sequence for uniform sampling; extend the tree from the nearest node $q_{\text{near}}$ toward $q_{\text{rand}} + \vec{V}_b$ with a step size $\varepsilon$; check for collisions; and upon reaching the goal, backtrack to extract the path. Redundant waypoints are removed to optimize the route. This enhancement reduces random tree nodes and improves real-time performance for the drone formation.
For multi-drone coordination, I propose a cooperative avoidance-reconstruction strategy. When obstacles disrupt the drone formation, each drone treats others as moving obstacles and uses the improved RRT for local planning. After avoidance, the formation is reconstructed to its original shape. Let $w$ be a reconstruction flag: $w=0$ for normal formation, $w=1$ during avoidance. Once no threats are detected for five steps, reconstruction begins. Consider a three-drone formation with positions $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$, and drone 2 being the last to avoid obstacles. The target positions after reconstruction are computed based on maximum speed $V_{\max}$ and formation geometry. The horizontal displacement $x$ for drone 2 is determined by:
$$
\begin{cases}
x > L_{23} \\
x > L_{12} – H \\
x / t = V_{\max} \\
(x + H – L_{12}) / t < V_{\max} \\
(x – L_{23}) / t < V_{\max}
\end{cases}
\quad \text{solve for } x = \min X, \quad t = \frac{x}{V_{\max}}
$$
where $L_{ij}$ are distances between drones, and $H$ is the desired formation spacing. The control speeds for each drone are:
$$
V_1 = \frac{x}{t}, \quad V_2 = \frac{x + H – L_{12}}{t}, \quad V_3 = \frac{x – L_{23}}{t}
$$
This ensures the drone formation reconverges efficiently while respecting speed constraints.
To validate my approach, I conducted simulations in MATLAB. The environment was a 600 m × 600 m area with static threats, and three drones started from (12 m, 13 m) to (52 m, 47 m). Parameters were set as: ant count $m=10$, iterations $N_{\text{cmax}}=100$, $\alpha=1$, $\beta=5$, $\rho=0.2$, $Q=1$, RRT step size $\varepsilon=2$ m, probability $p_\epsilon=0.5$, and cost weights $k_1=k_2=0.5$. The drones had a maximum speed $V_{\max}=5$ m/s. The global planning using ACO yielded an initial route with an estimated time of arrival (ETA) of 119.23 s and a total cost of 632.82. The planning time was 0.40 s. For local planning, I compared the improved RRT with standard RRT in a 40 m × 45 m sub-environment with moving obstacles. The results are summarized in Table 1.
| Algorithm | Average Planning Time (ms) | Average Local Route Cost |
|---|---|---|
| Improved RRT | 15.60 | 8.33 |
| Standard RRT | 28.60 | 12.56 |
The improved RRT showed faster planning and lower cost due to directional prediction and waypoint pruning. In multi-drone scenarios, the cooperative strategy prevented collisions and enabled formation reconstruction. Over 20 simulation runs, the hybrid A-RRT algorithm was compared with standard RRT for overall dynamic planning. The outcomes are presented in Table 2.
| Algorithm | Success Rate (out of 20) | Average Planning Time (s) | Overall Route Cost |
|---|---|---|---|
| A-RRT Hybrid | 20 | 0.529 | 642.12 |
| Standard RRT | 8 | 1.407 | 718.30 |
The A-RRT hybrid achieved a 100% success rate, with lower planning time and route cost, demonstrating its effectiveness for drone formation in dynamic environments. The layered approach reduced computational load, while the Voronoi modeling simplified the search space. The improved RRT’s real-time capabilities were crucial for handling moving obstacles, and the cooperative strategy maintained formation integrity.
In conclusion, my research presents a robust solution for dynamic route planning in multi-rotor drone formation. By integrating ant colony optimization and an enhanced RRT algorithm, along with a cooperative avoidance-reconstruction strategy, the proposed method addresses both global optimality and local adaptability. The simulations confirm that this hybrid approach outperforms conventional RRT in terms of efficiency and optimality. Future work could explore extending this to larger drone formation with heterogeneous drones or integrating machine learning for obstacle prediction. This contribution advances the field of autonomous drone navigation, paving the way for more reliable and coordinated drone formation operations in complex scenarios.
Throughout this article, I have emphasized the importance of drone formation in route planning, as coordinated movement enhances mission success. The methodologies described here, including cost functions, probability models, and speed control equations, provide a comprehensive framework for implementing dynamic planning. The use of tables and formulas, such as the cost function $J_i$ and transition probability $P_{ij}^k$, helps summarize key concepts. By continually referencing drone formation, I underscore its central role in the planning process. This work not only improves algorithmic performance but also offers practical insights for real-world applications where drone formation must navigate dynamically changing environments safely and efficiently.