In recent years, the rapid advancement of UAV drone technology has significantly expanded applications in maritime reconnaissance and surveillance. However, efficient coverage of vast ocean areas, obstacle avoidance, and safe navigation remain challenging due to complex marine environments. Existing path planning methods often suffer from high energy consumption, unstable communication links, and a tendency to become trapped in local optima, leading to stagnation in coverage rate. To address these issues, we propose a novel path planning method based on an improved sparrow search algorithm (SSA) for UAV drone swarms. Our approach integrates dynamic grid map modeling, multi-constraint evaluation functions, and a dead-zone escaping mechanism, enabling robust coverage optimization in realistic maritime scenarios. This paper presents the complete methodology, detailed mathematical formulations, and comparative simulation results.
1. Introduction
UAV drone swarms have become indispensable for maritime patrol, search and rescue, and ocean monitoring. The core challenge lies in planning paths that maximize area coverage while minimizing energy consumption, maintaining reliable inter-drone communication, and avoiding obstacles. Traditional genetic algorithms (GA) and basic SSA often neglect the influence of dynamic sea winds, battery constraints, and communication requirements. Furthermore, when a swarm converges to a dead zone—where the coverage rate ceases to increase—conventional methods fail to re-explore uncovered regions. Our work tackles these limitations by introducing a multi-dimensional evaluation function and a novel discoverer-follower mechanism inspired by sparrow foraging behavior. The proposed method is validated through three distinct simulation scenarios, demonstrating superior performance in coverage efficiency, energy reduction, and obstacle avoidance.
2. Methodology
2.1 Grid Map Modeling and Dynamic Update
We represent the target ocean area as a uniform grid map, balancing environmental perception accuracy and computational efficiency. Two types of maps are maintained:
- Obstacle map: Identifies no-fly zones (e.g., islands, restricted areas).
- Coverage map: Tracks detected and undetected cells, updated dynamically as UAV drones scan the area.
The obstacle status of cell $(m,n)$ is defined as:
$$
u_{mn} =
\begin{cases}
0, & (m,n) \in \Omega_1 \quad (\text{flyable})\\
1, & (m,n) \notin \Omega_1 \quad (\text{forbidden})
\end{cases}
$$
where $\Omega_1$ is the set of no-fly zones. The coverage status $v_{mn}$ at time $k$ is:
$$
v_{mn} =
\begin{cases}
0, & (m,n) \in \Omega_2 \quad (\text{uncovered})\\
1, & (m,n) \in \Omega_3 \quad (\text{covered})
\end{cases}
$$
Table 1 summarizes grid map notations.
| Symbol | Description | Value |
|---|---|---|
| $u_{mn}$ | Obstacle indicator for cell $(m,n)$ | 0: flyable; 1: forbidden |
| $v_{mn}^k$ | Coverage indicator at time $k$ | 0: uncovered; 1: covered |
| $\Omega_1$ | Set of no-fly zones | — |
| $\Omega_2$ | Uncovered region | — |
| $\Omega_3$ | Covered region | — |
2.2 UAV Drone Motion Model and Candidate Path Generation
We model each UAV drone as a point mass moving at constant altitude with combined airspeed and wind speed. The discrete-time motion equation is:
$$
\begin{bmatrix}
x_i(k+1)\\
y_i(k+1)
\end{bmatrix}
=
\begin{bmatrix}
x_i(k)\\
y_i(k)
\end{bmatrix}
+ (v_{\text{air}}^i + v_{\text{wind}}^i)\Delta t
\begin{bmatrix}
\cos\theta(k)\\
\sin\theta(k)
\end{bmatrix}
$$
where $(x_i(k), y_i(k))$ is the position of UAV $i$, $v_{\text{air}}^i$ is its airspeed (constant), $v_{\text{wind}}^i$ is the wind velocity component along the flight direction, $\Delta t$ is the time step, and $\theta(k)$ is the heading angle. The candidate heading at the next step is constrained by the maximum turn angle $\phi_{\max}$:
$$
\theta(k+1) \in [\theta(k) – \phi_{\max},\ \theta(k) + \phi_{\max}]
$$
To generate a sufficient number of candidate paths, we discretize the heading range using a sliding-window method. We then apply a pruning strategy that retains only smoothly varying paths, limiting the total to under 100,000 paths for computational efficiency.
2.3 Dynamic Obstacle Avoidance
For each candidate path, we check collisions with no-fly zones. Let $R$ be the minimum turn radius of the UAV drone. The path segment of straight flight has length $\alpha$, and when turning, the tangent point to the obstacle is $a$. The flight distance during a turn of $\beta$ degrees is $(2\pi R\beta)/360$, requiring time $T_2$. A collision risk is flagged if any segment satisfies:
$$
L < \frac{180(v_{\text{air}} + v_{\text{wind}})}{\phi_{\max}\prod\tan(\phi/4)}
$$
where $L$ is the length of the dangerous segment. The physical meaning is that when the segment length is less than the safe avoidance distance under maximum turn angle constraints, the UAV drone cannot avoid the obstacle by turning, so we discard that path.
2.4 Multi-Dimensional Evaluation Function
We select the optimal path using a weighted sum of five reward/penalty terms:
$$
J_p = w_1 J_1 + w_2 J_2 + w_3 J_3 + w_4 J_4 + w_5 J_5
$$
where $w_1,\dots,w_5$ are weight coefficients. The five sub-functions are described below.
2.4.1 Coverage Reward $J_1$
This reward encourages paths that cover many undetected cells:
$$
J_1 = \frac{1}{J_{1\max}} \sum_{h \in H_p} \lambda_h \sum_{(m,n)_h \in G_h} u_{m,n}^2
$$
$H_p$ is the set of steps along path $p$, $\lambda_h$ is the weight of node $h$, and $G_h$ is the set of cells detectable from node $h$. Normalization by $J_{1\max}$ ensures fair comparison.
2.4.2 Wind Reward $J_2$
We reward downwind flight to save energy. No penalty for upwind to avoid biasing coverage:
$$
J_2 = \frac{2\arccos\left(\frac{v_{\text{air}} \cdot v_{\text{wind}}}{\|v_{\text{air}}\|\|v_{\text{wind}}\|}\right)}{J_{2\max} \times \prod}
$$
The product in denominator is a placeholder for path-specific scaling; the term rewards alignment with wind direction.
2.4.3 Turn Penalty $J_3$
Turning increases energy consumption. The penalty grows with turn angle:
$$
J_3 = \frac{|\phi_s|}{\phi_{\max} \times J_{3\max}}
$$
where $\phi_s$ is the turn angle of path $s$, assumed constant for all time steps of that path.
2.4.4 Communication Attraction Penalty $J_4$
To maintain reliable inter-drone communication, we penalize large distances between UAV drones. The penalty decreases as coverage increases, avoiding excessive attraction in later stages:
$$
J_4 = J_{4\max} \sum_{h \in H_p} \sum_{j \in Q_h} \frac{1 – \text{Cover}(k)}{C_{\max} – D_{ij}},\quad D_{ij} \in [C_{\min}, C_{\max}]
$$
$\text{Cover}(k)$ is the coverage rate at time $k$, $D_{ij}$ is the distance between UAV $i$ and $j$, and $C_{\min}, C_{\max}$ are communication bounds.
2.4.5 Communication Repulsion Penalty $J_5$
To prevent UAV drones from clustering too closely, we add a repulsive term using an artificial potential field:
$$
J_5 = J_{5\max} \sum_{h \in H_p} \sum_{j \in Q_h} \frac{1 – \text{Cover}(k)}{D_{ij} – C_{\min}},\quad D_{ij} \in [C_{\min}, C_{\max}]
$$
Table 2 shows the default weight configuration used in our experiments.
| Weight | Value | Purpose |
|---|---|---|
| $w_1$ | 0.5 | Coverage reward |
| $w_2$ | 0.15 | Wind benefit |
| $w_3$ | 0.1 | Turn penalty |
| $w_4$ | 0.15 | Communication attraction |
| $w_5$ | 0.1 | Communication repulsion |
2.5 Improved Sparrow Search for Dead-Zone Escape
When the swarm’s coverage rate increase stays below 1% for $T$ consecutive time steps, we activate a dead-zone escape mechanism based on the sparrow search algorithm’s discoverer-follower strategy.
2.5.1 Improved A* Path Planning
We use a modified A* algorithm to plan a path toward the centroid of the largest uncovered region. The cost function is:
$$
f(n) = g(n) + h(n)
$$
where $g(n)$ is the actual flight distance from the start to node $n$, and $h(n)$ is the Euclidean distance from $n$ to the target. We optimize smoothness by penalizing sharp turns in the heuristic.
2.5.2 Discoverer-Follower Coordination
Initially, all UAV drones search using the improved A* algorithm. If any drone increases the overall coverage rate by at least 5%, it becomes the discoverer and broadcasts its coordinates and new detection data. The system calculates Euclidean distances from other drones to the discoverer and selects the three nearest as followers. Followers suspend independent tasks and switch to follow mode, forming a triangular formation with a fixed spacing of 20 m. The followers use the velocity obstacle method to plan collision-free paths while maintaining the formation. This triangular formation stabilizes communication links and reduces aerodynamic interference. The dead-zone escape terminates when the cluster coverage rate improves by 15% or more.
3. Simulation Results and Analysis
3.1 Experimental Scenarios
We design three simulation scenarios to validate our method:
- Scenario A (Basic coverage): No obstacles, constant sea wind at 5 m/s.
- Scenario B (Complex environment): Random 10% no-fly zones, dynamic wind varying 2–8 m/s.
- Scenario C (Dead-zone escape): A long narrow uncovered strip causing coverage stagnation.
We compare our method against traditional genetic algorithm (GA) and basic sparrow search algorithm (SSA) without dead-zone escape or dynamic communication constraints. Each scenario runs 10 Monte Carlo simulations; average results are reported.
3.2 Results and Discussion
3.2.1 Scenario A: Basic Coverage
Table 3 presents the coverage rate and energy consumption after 300 seconds.
| Method | Coverage Rate (%) | Average Energy (J/s) | Obstacle Avoidance Success (%) |
|---|---|---|---|
| GA | 89.2 | 168 | 100 |
| Basic SSA | 92.5 | 142 | 100 |
| Proposed | 98.7 | 125 | 100 |
The proposed method achieves 98.7% coverage, 10% higher than basic SSA, and reduces energy by 12% compared to SSA. The wind reward and turn penalty effectively lower energy consumption.
3.2.2 Scenario B: Complex Environment
With dynamic wind and obstacles, our method maintains robust performance (Table 4).
| Method | Coverage Rate (%) | Obstacle Avoidance Success (%) | Average Energy (J/s) |
|---|---|---|---|
| GA | 68.5 | 87 | 195 |
| Basic SSA | 79.1 | 93 | 160 |
| Proposed | 92.3 | 100 | 138 |
Our method achieves 92.3% coverage with zero obstacle collisions, validating the dynamic avoidance strategy and communication-aware evaluation.
3.2.3 Scenario C: Dead-Zone Escape
In the narrow uncovered strip scenario, GA and basic SSA both become trapped with coverage stagnating at around 75%. Our proposed method activates the discoverer-follower mechanism after detecting stagnation for $T=5$ steps. The discoverer finds a new uncovered area, three followers form a triangular formation, and coverage reaches 92% within 28 seconds. Table 5 summarizes the escape performance.
| Method | Stagnation Coverage (%) | Escape Time (s) | Final Coverage (%) |
|---|---|---|---|
| GA | 75.0 | ∞ (failed) | 75.0 |
| Basic SSA | 75.0 | ∞ (failed) | 75.0 |
| Proposed | 75.0 | 28 | 92.0 |
The rapid escape demonstrates the effectiveness of the improved sparrow search algorithm with discoverer-follower coordination.
4. Conclusion
We have presented an improved sparrow search algorithm for UAV drone swarm maritime coverage path planning. By integrating dynamic grid mapping, a multi-dimensional evaluation function (wind, turn, communication, coverage), and a discoverer-follower dead-zone escape mechanism, our method significantly outperforms traditional GA and basic SSA. Simulation results show a coverage increase of up to 16% and energy reduction of over 10% in complex environments. The approach ensures reliable obstacle avoidance and maintains stable inter-drone communication. Future work will extend the framework to three-dimensional oceanic environments and incorporate real-time wind field updates from onboard sensors.