Cooperative Patrol Coverage Path Planning for Fixed-Wing UAVs

In this study, we investigate the cooperative patrol coverage path planning problem for fixed-wing Unmanned Aerial Vehicles (UAVs) operating in complex mountainous environments. Unlike traditional approaches that focus on complete area coverage in a single pass, our objective is to enable multiple fixed-wing UAVs to continuously patrol a designated region, ensuring that every ground location is revisited within acceptable time intervals. We design a collaborative framework where all UAVs share a common situational awareness matrix and dynamically adjust their paths based on the recency of coverage. To address emergency situations that require rapid access to a specific area, we introduce a dynamic target point strategy combined with a small-scale crossing coverage algorithm. This approach allows the designated UAV to balance the efficiency of routine patrol tasks while meeting the time constraints of the emergency mission. Through a series of simulations, we validate the effectiveness of the proposed algorithm and demonstrate the superiority of the dynamic target point strategy over static alternatives.

1. Introduction

With the rapid advancement of UAV technology, fixed-wing UAVs have become indispensable in reconnaissance, surveillance, and patrolling missions due to their high speed, long endurance, and ability to carry sophisticated sensors. However, the path planning problem for fixed-wing UAVs differs significantly from that of rotary-wing UAVs because of constraints such as minimum turning radius, limited vertical maneuverability, and the need for continuous forward motion. Moreover, when multiple fixed-wing UAVs are deployed for cooperative patrol coverage, the coordination must account for collision avoidance, information sharing, and balanced workload distribution.

Previous research on coverage path planning often assumes a two-dimensional environment and treats the entire area as a flat surface. In contrast, our work considers a three-dimensional terrain with obstacles and no-fly zones. We also move beyond the conventional “complete coverage in one sweep” paradigm. Instead, we aim for persistent surveillance, where each ground grid cell is monitored repeatedly over time. The key metric is the interval between successive visits to a cell, and we prioritize those cells that have not been visited for a long time.

In this paper, we present a comprehensive framework for cooperative patrol coverage path planning using fixed-wing UAVs. Our contributions include:

  • A grid-based spatial model that represents both ground and air spaces, with state variables indicating the recency of coverage.
  • A multi-UAV coordination mechanism that uses simulated annealing to resolve conflicts and a sequential planning rule to avoid duplicate coverage of high-value areas.
  • A dynamic target point strategy for emergency tasks that allows a UAV to simultaneously approach the emergency area while maintaining patrol efficiency.
  • An improved A* algorithm with directional constraints to generate feasible paths for fixed-wing UAVs.
  • A two-round crossing coverage algorithm to achieve complete coverage of an emergency region.

2. Problem Formulation and Spatial Model

2.1 Grid-Based Environment Representation

We discretize the mission area into two sets of grids: a fine ground grid (size \(a_g \times b_g\)) for representing terrain details and a coarser air grid (size \(a \times b \times h\)) for UAV navigation. Each ground cell stores its elevation (maximum height within the cell) and a state variable \(sv_k(s)\) that quantifies how long ago the cell was last observed. The air grid cells are classified into three states: -1 (obstacle or no-fly zone, prohibited), 0 (near obstacle, can be used as waypoint but not start/end), and 1 (free space).

The UAV motion model is defined in a non-uniform hexahedral grid where horizontal dimensions are equal (\(a = b\)) and larger than the vertical dimension \(h\). At each time step, a UAV moves from the center of one air cell to the center of a neighboring cell. The possible movements are represented by a control vector \(\mathbf{n}_t = [n_x, n_y, n_z]\), where each component belongs to \(\{-1, 0, 1\}\) and not all zero. To ensure coordination, all UAVs are required to complete each step in the same time duration, which implies variable ground speeds.

\[
\begin{cases}
x_i(t+1) = x_i(t) + n_x(t) \cdot a \\
y_i(t+1) = y_i(t) + n_y(t) \cdot b \quad i=1,2,\dots,N_d\\
z_i(t+1) = z_i(t) + n_z(t) \cdot h
\end{cases}
\]

2.2 UAV Sensing Model

The fixed-wing UAV carries a downward-looking camera mounted with a fixed angle relative to the fuselage. The field of view is bounded by left/right/front/back angular limits \(\theta_{le}, \theta_{ri}, \theta_{fr}, \theta_{ba}\) and a maximum sensing range \(R\). The actual visible region also depends on the UAV’s pitch angle \(\theta_{pit}\) and heading angle \(\theta_{head}\). We compute the set of ground cells that satisfy three conditions: (i) the cell’s four corners lie within the angular field, (ii) the distance from the UAV to each corner is less than \(R\), and (iii) there is no terrain blockage along the line of sight.

For a given UAV position \((x_0, y_0, z_0)\) and heading, the ground cells that can be observed are determined by projecting the field of view onto the ground plane. The resulting coverage area is a rectangular region (or rotated rectangle) whose boundaries depend on the heading and pitch. Table 1 summarizes the \(x\) and \(y\) ranges for different heading angles.

Table 1: Boundary of the coverage square for different heading angles \(\theta_{head}\) (with parameters \(R=5\) km, \(\theta_{pit}=0^\circ\), \(\theta_x = 30^\circ\))
\(\theta_{head}\) \(x\) direction range \(y\) direction range
\(0^\circ\) \([x_0,\ \min\{L_x, x_0 + R\sin(75^\circ+\theta_{pit})\}]\) \([\max\{0,y_0 – R\sin\theta_x\},\ \min\{L_y, y_0 + R\sin\theta_x\}]\)
\(45^\circ\) \([x_0,\ \min\{L_x, x_0 + R\sin(75^\circ+\theta_{pit})\cos\theta_x\}]\) \([y_0,\ \min\{L_y, y_0 + R\sin(75^\circ+\theta_{pit})\sin\theta_x\}]\)
\(90^\circ\) \([\max\{0,x_0 – R\cos\theta_x\},\ \min\{L_x, x_0 + R\cos\theta_x\}]\) \([y_0,\ \min\{L_y, y_0 + R\sin(75^\circ+\theta_{pit})\}]\)
\(135^\circ\) \([\max\{0,x_0 + R\sin(75^\circ+\theta_{pit})\cos\theta_x\},\ x_0]\) \([y_0,\ \min\{L_y, y_0 + R\sin(75^\circ+\theta_{pit})\sin\theta_x\}]\)
\(180^\circ\) \([\max\{0,x_0 – R\sin(75^\circ+\theta_{pit})\},\ x_0]\) \([\max\{0,y_0 – R\sin\theta_x\},\ \min\{L_y, y_0 + R\sin\theta_x\}]\)
\(225^\circ\) \([\max\{0,x_0 + R\sin(75^\circ+\theta_{pit})\cos\theta_x\},\ x_0]\) \([\max\{0,y_0 – R\sin(75^\circ+\theta_{pit})\sin\theta_x\},\ y_0]\)
\(270^\circ\) \([\max\{0,x_0 + R\cos\theta_x\},\ \min\{L_x, x_0 – R\cos\theta_x\}]\) \([\max\{0,y_0 – R\sin(75^\circ+\theta_{pit})\},\ y_0]\)
\(315^\circ\) \([0,\ \min\{x_0, x_0 + R\sin(75^\circ+\theta_{pit})\cos\theta_x\}]\) \([\max\{0,y_0 + R\sin(75^\circ+\theta_{pit})\sin\theta_x\},\ y_0]\)

The condition for a ground point to be within the field of view is given by:

\[
\omega_{\min} \le \arccos\frac{\mathbf{P}_h \cdot \mathbf{h}}{\|\mathbf{P}_h\| \|\mathbf{h}\|} \le \omega_{\max}
\]

\[
\arccos\frac{\mathbf{P}_g \cdot \mathbf{g}}{\|\mathbf{P}_g\| \|\mathbf{g}\|} \le \theta_{head} – \theta_x
\]

where \(\mathbf{P} = [x_p – x_0,\ y_p – y_0,\ z_p – z_0]^T\), \(\mathbf{h}=[0,0,-1]^T\), and \(\mathbf{g}\) is the horizontal direction vector of the UAV.

2.3 Coverage State and Patrol Objective

Each ground cell \(k\) maintains a state variable \(sv_k(s)\) that decays over time since its last observation:

\[
sv_k(s) = 1 – \frac{t_v}{t_c(s)}
\]

where \(t_v\) is the last time the cell was visited, and \(t_c(s)\) is the current planning step time. If never visited, \(t_v = 0\) and \(sv_k(s)=1\). The patrol objective at step \(s\) is to maximize the sum of \(sv\) values over all cells that will be covered by the chosen waypoint:

\[
J(s) = \sum_{m=1}^{g(s)} sv_m(s)
\]

where \(g(s)\) is the number of ground cells covered from the candidate air cell. For cells that have not been visited for longer than a threshold \(\Delta T_v\), we apply a weighting factor to prioritize them:

\[
J(s) = g(s) \times \max\{ sv_1(s), sv_2(s), \dots, sv_{g(s)}(s) \}
\]

3. Cooperative Patrol Coverage Path Planning Algorithm

3.1 Sequential Planning and Conflict Resolution

All UAVs share a common coverage state matrix. To prevent multiple UAVs from simultaneously targeting the same high-value area, we implement a sequential planning rule. At each step, UAVs are sorted using a simulated annealing-based approach. The highest-priority UAV plans its path first and immediately updates the state matrix. Subsequent UAVs then plan based on the updated information, which implicitly discourages duplicate coverage of recently visited cells.

Collision avoidance is handled locally by considering two types of conflicts: node collisions (two UAVs arriving at the same air cell at the same time) and path collisions (two crossing trajectories). The conditions for detecting these conflicts are:

\[
\begin{aligned}
\text{Node collision: } & (x_i(t+1), y_i(t+1), z_i(t+1)) = (x_j(t+1), y_j(t+1), z_j(t+1)) \\
\text{Path collision: } & (x_i(t)+x_i(t+1), y_i(t)+y_i(t+1), z_i(t)+z_i(t+1)) = (x_j(t)+x_j(t+1), y_j(t)+y_j(t+1), z_j(t)+z_j(t+1))
\end{aligned}
\]

When a conflict is detected, the lower-priority UAV must select an alternative waypoint that avoids the conflict.

2.4 Emergency Task Path Planning

When an emergency area is designated (e.g., a region that has been unvisited for too long or requires immediate reconnaissance), the nearest UAV is selected and given higher priority. The selected UAV must reach the emergency region within a maximum path length \(L_{max}\):

\[
L_{max} = 2 \times \sqrt{(x_c – x_0)^2 + (y_c – y_0)^2 + (z_c – z_0)^2}
\]

where \((x_c, y_c, z_c)\) is the centroid of the emergency area. During the approach, the UAV employs a dynamic target point strategy. At each step, it identifies the nearest point on the boundary of the emergency region as a temporary target. It then uses the improved A* algorithm to find a path that satisfies both the distance constraint and the patrol objective. The dynamic target is updated each step until the remaining distance to the region is too large to allow further detours, at which point the UAV switches to direct flight to the emergency area.

The improved A* algorithm incorporates turning angle constraints. Each candidate node is checked for:

  • Node state not -1 or closed.
  • Compliance with turning angle limits.
  • Ability to continue flying for at least a few steps (to avoid dead ends).
  • If adjacent to the goal, direction must match the entry angle.

Once the UAV reaches the emergency area, it performs a two-round coverage mission. In the first round, it visits all cone-shaped spaces above the emergency ground cells (each ground cell’s possible observation cone). The UAV uses the improved A* to fly from one cone to another, covering as many cells as possible. After the first round, cones corresponding to already-covered ground cells are removed. In the second round, the UAV re-enters the remaining cones with a constrained terminal direction to ensure full coverage of the associated ground cells. This process continues until the entire emergency area is covered.

4. Simulation Results and Analysis

4.1 Simulation Setup

We conducted simulations in a 50 km × 50 km × 5 km airspace with a ground grid resolution of 100 m × 100 m and an air grid resolution of 1000 m × 1000 m × 100 m. The fixed-wing UAV sensor parameters are: \(\theta_{fr}=\theta_{ba}=\theta_{le}=\theta_{ri}=30^\circ\), maximum range \(R=5\) km. The revisit threshold \(\Delta T_v = 20\) steps. The number of UAVs \(N_d\) is varied from 3 to 10 to study the effect of fleet size. Key model parameters are summarized in Table 2.

Table 2: Model Parameters
Parameter Symbol Value
Front/back/left/right angle limit \(\theta_{fr},\theta_{ba},\theta_{le},\theta_{ri}\) \(30^\circ\)
Air grid horizontal size \(a=b\) 1000 m
Air grid vertical size \(h\) 100 m
Ground grid size \(a_g\times b_g\) 100 m × 100 m
Mission area size \(L_x\times L_y\) 50 km × 50 km
Altitude range \([z_{\min},z_{\max}]\) [0, 5] km
Revisit threshold \(\Delta T_v\) 20 steps
Number of UAVs \(N_d\) 5 (default), varied
Maximum sensing range \(R\) 5 km
Pitch angle (cruise) \(\theta_{pit}\) 0°

4.2 Persistent Coverage without No-Fly Zones

We first tested the algorithm with 5 fixed-wing UAVs in a clear environment. The UAVs started from random positions sufficiently separated (Table 3). After 1500 planning steps, the coverage map showed that all ground cells were visited multiple times, with higher elevations receiving more frequent coverage due to fewer terrain occlusions. The average \(sv\) value decreased rapidly within the first 200 steps and stabilized around 0.2 after 800 steps, indicating successful persistent surveillance.

Table 3: Initial Positions of UAVs (Clear Environment)
UAV ID Initial Position (km)
1 (13.5, 27.5, 4.75)
2 (47.5, 24.5, 4.05)
3 (39.5, 47.5, 3.25)
4 (33.5, 37.5, 3.75)
5 (2.5, 4.5, 4.15)

4.3 Impact of No-Fly Zones

We introduced randomly placed no-fly zones at various altitudes. The UAVs adapted by avoiding these zones, which created coverage gaps on the ground directly below the affected airspace. The average \(sv\) curve showed slightly higher fluctuations but still converged to a stable value. The algorithm maintained its effectiveness, although coverage of cells near no-fly zones was degraded. This suggests that emergency task planning is necessary to cover those shadowed areas.

4.4 Optimal Number of UAVs

We varied the number of UAVs from 3 to 10 and measured the average \(sv\) after 1500 steps. The results (Figure 21 in the original paper, but not referenced here) indicate that with 8 UAVs, the performance saturates; further increases provide negligible improvement. For our mission area, the optimal fleet size is 8, balancing coverage efficiency and operational cost.

\[
\text{Average }sv \text{ after 1500 steps: } \text{3 UAVs: } 0.35,\ \text{5 UAVs: } 0.22,\ \text{8 UAVs: } 0.15,\ \text{10 UAVs: } 0.14
\]

4.5 Emergency Task Simulation

We introduced an emergency area at step 200 of the mission. The nearest UAV (UAV 5) was selected. Using the dynamic target point strategy, the UAV continued to patrol while approaching the emergency area. It reached the region at step 229 and performed the two-round crossing coverage. The entire emergency area was covered by step 235. In comparison, a static target point strategy (where the UAV immediately flies straight to the area) resulted in a higher peak of average \(sv\) (worse performance) during the emergency phase. The dynamic strategy maintained a lower average \(sv\) because it continued to visit other cells during the approach. Table 4 compares the two strategies.

Table 4: Comparison of Dynamic vs. Static Target Point Strategies
Metric Dynamic Target Static Target
Time to reach emergency area (steps) 29 20
Peak average \(sv\) during emergency (steps 200-235) 0.31 0.38
Coverage efficiency (lower is better) 0.22 0.27

5. Conclusion

We presented a comprehensive cooperative patrol coverage path planning framework for fixed-wing UAVs operating in complex three-dimensional environments. Our approach integrates a dynamic state representation for persistent surveillance, a sequential planning mechanism with collision avoidance, and a novel dynamic target point strategy for emergency response. Simulations validated that the algorithm effectively maintains continuous coverage over a large area while adapting to no-fly zones and urgent tasks. The two-round crossing coverage algorithm ensures complete coverage of emergency regions within time constraints. The dynamic target point strategy outperforms traditional static approaches by better preserving overall patrol efficiency. Future work will extend this framework to heterogeneous UAV teams and dynamic threat environments.

References

Since this article is a self-contained summary of our research, the detailed references can be found in the original publication. The key concepts, including the grid-based spatial model, the sequential planning with simulated annealing, the improved A* with direction constraints, and the two-round coverage algorithm, are fully described in the above sections.

Scroll to Top