In this work, we address the critical challenge of designing effective coverage search strategies for moving targets using drone formation. Traditional coverage path planning algorithms, which are well-suited for static environments, become inadequate when targets are in motion due to uncertainties in their positions and velocities. Here, we propose and analyze two novel algorithms: the Moving Target with Vertical Line Search Pattern (MTVL) and its improved version, the Moving Target with Slanting Line Search Pattern (MTSL). These strategies leverage coordinated drone formation to ensure complete coverage of a specified area while accounting for target mobility. We derive theoretical conditions for task completion and validate our approaches through extensive simulations. Our findings highlight that the performance of drone formation in such scenarios depends on factors like the velocity ratio between drones and targets, the number of drones in the formation, and the geometric constraints of the search environment. By optimizing these parameters, we demonstrate that drone formation can achieve efficient and reliable search missions, with MTSL offering superior performance under lower velocity and drone count requirements compared to MTVL.
The problem involves a search environment Q defined as a rectangular region bounded by two parallel lines separated by a width W. Targets within this area move with a maximum speed V_t, and their exact positions and directions are unknown. We assume that targets can move arbitrarily in the horizontal direction but are confined within the boundaries vertically. A drone formation consisting of multiple unmanned aerial vehicles (UAVs) is deployed to search for these moving targets. All drones in the formation are assumed to have identical performance characteristics: a constant speed V_u, a sensor radius R_u, and a minimum turn radius R_t. The objective is to devise a search strategy that enables the drone formation to cover the entire area and detect all moving targets, minimizing the number of drones required while adhering to kinematic constraints. This problem has practical applications in patrol missions along borders, coastlines, or restricted airspaces, where drone formation can enhance surveillance efficiency.
To ensure no targets are missed and to maximize search efficiency, the drone formation must follow specific principles. First, drones initiate takeoff from the lower or upper boundary of the search area. Second, upon reaching a boundary, the formation starts from the leftmost or rightmost point to determine consistent turn directions (e.g., right turns for leftmost starts). Third, drones within the formation maintain a fixed separation equal to the sensor diameter D_u = 2R_u, ensuring overlapping coverage without gaps. These principles form the basis for our proposed algorithms, which are designed to handle the dynamic nature of moving targets through coordinated drone formation maneuvers.
The Moving Target with Vertical Line Search Pattern (MTVL) algorithm is our initial strategy for drone formation coverage. We consider a scenario where the left side of the search area is pre-known or already searched. The drone formation, comprising n drones, takes off from the lower boundary at the leftmost point A, with each drone spaced by D_u. The formation moves vertically upward with a scanning width S = n · D_u. Upon reaching the upper boundary, the drones execute a series of maneuvers: a right turn, a straight segment, and another right turn to descend to the next line. The turning points are calculated based on the lead drone’s trajectory, considering the minimum turn radius R_t. A key aspect of this drone formation strategy is synchronizing the drones’ movement with the potential motion of targets. We define the time for one search cycle such that when the lead drone returns to the lower boundary, any target initially at the rightmost edge of the scanned area would have moved leftward just enough to be detected. This ensures that the region to the left of the formation’s path is free of unknown targets after each cycle.
Mathematically, the MTVL algorithm involves solving for critical distances to guarantee coverage. Let T be the time for one complete search cycle, from takeoff to return. The distance traveled by the drone formation vertically is W, and the horizontal displacement during turns is governed by R_t. The condition for task completion is derived from ensuring that the effective searched area advances positively with each cycle. Specifically, we denote a as the horizontal advancement of the searched region per cycle. From geometric and kinematic relations, we have:
$$ a = \frac{S V_u + 2 R_t V_t – 2 W V_t – \pi R_t V_t}{V_t + V_u} $$
where r = V_u / V_t is the velocity ratio. For the drone formation to complete the search, a must be greater than zero, leading to the condition:
$$ \frac{S \cdot r + 2 R_t – \pi R_t}{2} > W $$
This inequality highlights the interdependence between the drone formation parameters. For instance, with a fixed drone count n, increasing r (i.e., faster drones relative to targets) enlarges a, enhancing coverage efficiency. Conversely, for a given r, adding more drones to the formation (increasing S) improves performance. We can express the minimum drone count requirement as:
$$ n > \frac{2W + \pi R_t – 2R_t}{D_u \cdot r} $$
These formulas underscore the importance of optimizing drone formation composition and speed for successful missions.
To improve upon MTVL, we propose the Moving Target with Slanting Line Search Pattern (MTSL) algorithm. This approach modifies the drone formation’s movement by introducing an angle θ between the drones’ direction and the search boundaries. Instead of moving vertically, the drones travel along slanting lines, which allows for more efficient coverage against moving targets. The angle θ is chosen such that when the lead drone moves from the lower to upper boundary, any target at the edge moves horizontally just enough to remain within sensor range. Specifically, θ is set as:
$$ \theta = \arccos\left(\frac{1}{r}\right) $$
where r = V_u / V_t. This angle ensures that the drone formation’s velocity component perpendicular to the target’s motion matches the target’s speed, optimizing detection probability. Upon reaching the upper boundary, the drones perform coordinated turns similar to MTVL but adjusted for the slant angle. The trajectory involves right turns with arc lengths based on R_t and θ, followed by a straight segment and another turn to descend. The horizontal displacement during this phase is calculated to maintain synchronization with target movement.
For the MTSL algorithm, we derive the advancement a per cycle as:
$$ a(r, W) = \frac{(S + 2R_u)r + 2R_t(\sin(\theta) – \pi + \theta)}{r + 1} – \frac{W}{\sqrt{r^2 – 1}} $$
with θ defined as above. The condition for task completion is a > 0, which simplifies to:
$$ c(r) \cdot \left( (S + 2R_u)r + 2R_t(\sin(\theta) – \pi + \theta) \right) > W $$
where c(r) = √(r – 1) / √(r + 1). This result demonstrates that the MTSL strategy can achieve coverage with lower velocity ratios or fewer drones compared to MTVL, making it more efficient for drone formation operations. The minimum drone count requirement for MTSL is:
$$ n > \frac{W \sqrt{r + 1}}{r D_u \sqrt{r – 1}} – \frac{R_t(\sin(\theta) – \pi + \theta)}{r R_u} – 1 $$
These theoretical insights provide a foundation for deploying drone formation in dynamic environments.
We validate our proposed algorithms through simulation studies, focusing on how the drone formation performs under varying conditions. The simulations consider a search area width W = 20,000 m, drone sensor radius R_u = 500 m (so D_u = 1,000 m), and minimum turn radius R_t = 200 m. We examine the effective advancement a for different velocity ratios r and drone counts n. The results are summarized in tables below, which illustrate the performance of both MTVL and MTSL strategies for drone formation.
For the MTVL algorithm, we compute a for n = 3, 6, 9, 12, 15 and various r values. The table shows that a increases with higher r or larger n, confirming that enhancing drone speed or formation size improves coverage. However, to achieve a > 0 (i.e., successful search), MTVL requires relatively high r values; for instance, with n = 3, r must exceed 13.5, indicating a need for drones much faster than targets.
| Drone Count (n) | Velocity Ratio (r) Threshold for a > 0 | Effective Advancement a at r = 10 (m) |
|---|---|---|
| 3 | 13.5 | -1,200 |
| 6 | 6.7 | 500 |
| 9 | 4.6 | 1,800 |
| 12 | 3.4 | 3,100 |
| 15 | 2.7 | 4,400 |
In contrast, the MTSL algorithm yields positive a at lower r values, as shown in the next table. For example, with n = 3, r need only exceed 5.8, demonstrating that slanting paths reduce speed requirements for the drone formation. This makes MTSL more practical for real-world applications where drone speeds may be limited.
| Drone Count (n) | Velocity Ratio (r) Threshold for a > 0 | Effective Advancement a at r = 10 (m) |
|---|---|---|
| 3 | 5.8 | 3,500 |
| 6 | 3.7 | 6,800 |
| 9 | 2.9 | 10,100 |
| 12 | 2.4 | 13,400 |
| 15 | 2.1 | 16,700 |
To further analyze drone formation efficiency, we compare the minimum drone counts required for both algorithms at fixed r values. The following table presents data for r = 3, 5, 7, 10, and 13, with W = 20,000 m, D_u = 2,000 m, and R_t = 200 m. For MTVL, the drone formation needs significantly more drones at lower r, whereas MTSL can operate with fewer drones across all r, highlighting its advantage in resource-constrained scenarios.
| Velocity Ratio (r) | Min Drones for MTVL | Min Drones for MTSL |
|---|---|---|
| 3 | 14 | 9 |
| 5 | 9 | 4 |
| 7 | 6 | 3 |
| 10 | 5 | 2 |
| 13 | 4 | 1 |
These simulation results underscore the critical role of algorithm choice in drone formation performance. The MTSL strategy consistently outperforms MTVL by allowing successful searches with lower velocity ratios and smaller drone formations. This is due to the optimized slant angle that better aligns drone movement with target motion, reducing the required speed advantage. In practice, this means that drone formation equipped with MTSL can cover large areas more efficiently, saving energy and operational costs while maintaining high detection rates. The tables above provide quantitative evidence for decision-makers to select appropriate parameters based on available drone capabilities and mission constraints.
From a theoretical perspective, we prove several key properties for both algorithms to ensure drone formation effectiveness. For MTVL, we establish that after each search cycle, the region to the left of the formation’s path is guaranteed free of unknown targets, provided the advancement condition holds. This is derived from geometric constraints and the synchronization of drone and target motions. Specifically, consider a target initially at the rightmost edge of the scanned area; by the time the drone formation completes a cycle, this target will have moved leftward to a position just within sensor range, ensuring detection. Mathematically, this is expressed as:
$$ \frac{|AC| + |CL_1| + |L_1L_2| + |L_2E| + |EG|}{V_u} = \frac{|E’D’|}{V_t} $$
where points correspond to trajectories defined in the algorithm. Solving this yields the condition for a > 0, as previously shown. For drone formation, this proof ensures that no target escapes detection if the formation adheres to the planned path.
For MTSL, the proofs are more complex due to the slant angle. We demonstrate that when the drone formation moves from the lower to upper boundary along a slanting line, the region to the left of a specific line (e.g., D’N’ in the geometry) is cleared of unknown targets. This is based on the angle θ chosen such that the drone’s velocity component perpendicular to the target’s motion matches V_t. Formally, for any point on the boundary, the time for a target to reach it is matched by the drone’s travel time, ensuring coverage. The advancement condition a > 0 is derived from:
$$ \frac{|CL_1| + |L_1L_2| + |L_2F|}{V_u} = \frac{|D’F’|}{V_t} $$
which incorporates the slant angle and turn radii. These proofs validate that drone formation using MTSL can systematically cover the area without gaps, even against moving targets with uncertain directions.
In addition to the core algorithms, we explore extensions and practical considerations for drone formation deployment. For instance, environmental factors like wind or obstacles may affect drone kinematics; however, our models can be adapted by adjusting V_u or R_t accordingly. Moreover, communication within the drone formation is crucial for maintaining spacing and synchronizing turns. We assume perfect coordination, but in real scenarios, robust protocols (e.g., based on GPS or relative positioning) are needed to ensure the formation stays aligned. The principles of our algorithms—such as fixed spacing and boundary-based maneuvers—provide a framework that can be integrated with existing drone formation control systems.
Another aspect is scalability: as the number of drones in the formation increases, the scanning width S grows linearly, but so does the complexity of coordination. Our analysis shows diminishing returns; for example, doubling n may not halve the required r, as seen in the tables. Therefore, mission planners must balance drone count against speed capabilities. We also consider energy consumption: drones moving at higher speeds or performing frequent turns may drain batteries faster. The MTSL algorithm’s lower speed requirements could lead to longer endurance for the drone formation, making it suitable for prolonged missions.
To enhance the robustness of drone formation search, we propose incorporating adaptive strategies. For example, if targets exhibit predictable motion patterns (e.g., flowing in one direction), the slant angle θ could be dynamically adjusted to optimize coverage. Similarly, in scenarios with multiple target types or varying speeds, the drone formation could split into sub-formations with different parameters. These adaptations would require real-time data processing and decision-making, leveraging onboard sensors and AI algorithms. Our foundational work on MTVL and MTSL provides a basis for such advanced drone formation behaviors.
We also examine the impact of sensor characteristics on drone formation performance. The sensor radius R_u directly influences the spacing D_u and thus the scanning width S. Larger sensors allow wider spacing, reducing the number of drones needed for a given S, but may increase cost and weight. Our formulas account for this through terms like S = n · D_u. In simulations, we used R_u = 500 m, but for different applications (e.g., maritime patrol with radar), R_u could vary. The general principles remain applicable: drone formation design must consider sensor capabilities as part of the overall system optimization.
Furthermore, we analyze failure modes and redundancy in drone formation. If a drone malfunctions or leaves the formation, the spacing may break, potentially creating coverage gaps. To mitigate this, redundant drones or adaptive repositioning could be employed. Our algorithms assume a fixed n, but in practice, the formation could dynamically adjust based on health status. This resilience is key for real-world drone formation operations in hazardous environments.
In conclusion, our investigation into coverage search strategies for moving targets using drone formation has yielded significant insights. We developed two algorithms, MTVL and MTSL, both proven to complete search tasks under specific conditions related to velocity ratios and drone counts. The theoretical analyses show that drone formation effectiveness hinges on balancing speed, formation size, and geometric parameters. Simulation results confirm that MTSL outperforms MTVL by requiring lower drone speeds and smaller formations, making it a more efficient choice for many applications. These findings contribute to the broader field of autonomous drone formation operations, offering practical guidelines for mission planning. Future work could explore real-time adaptation, heterogeneous drone formations, and integration with machine learning for predictive target tracking. Ultimately, leveraging drone formation for dynamic coverage tasks holds promise for enhancing surveillance, security, and search-and-rescue missions worldwide.