We address the problem of employing a fixed-wing UAV (fixed-wing UAV) for rapid and complete coverage search of submarines in large, irregular sea areas. Traditional coverage search methods for convex regions are inadequate for complex concave polygonal boundaries, leading to excessive invalid turns and wasted resources. In this work, we propose a novel Dubins path search strategy combined with a selective concave point removal method. By formulating a mathematical model of the UAV search detection cost, incorporating the turning characteristics of the fixed-wing UAV, and developing an improved concave point removal algorithm that uses both edge length and angle thresholds, we transform irregular concave polygons into regular convex shapes. We then apply a span‑direction scan with Dubins curves to minimize turning costs. Simulation results demonstrate significant reductions in invalid flight time and energy consumption compared to conventional methods, providing theoretical support for efficient submarine search operations.
1. Introduction
The detection of submarines is a critical challenge in modern naval operations. With advancements in noise reduction and stealth technology, submarines have become increasingly difficult to detect acoustically. Non‑acoustic detection methods, such as magnetic anomaly detectors, infrared sensors, and radar, offer fast and wide‑area search capabilities when the submarine is near the surface. These sensors are typically carried by fixed‑wing platforms, including fixed‑wing unmanned aerial vehicles (fixed‑wing UAVs). The use of fixed‑wing UAVs for submarine search is appealing due to their long endurance, high speed, and large coverage capacity. However, the motion constraints of fixed‑wing UAVs—specifically their minimum turning radius and inability to hover—require careful path planning to ensure complete coverage while minimizing unnecessary flight segments.
Most existing research on coverage search for fixed‑wing UAVs focuses on convex polygonal regions or simple rectangular areas. For complex, concave, and irregular search zones, a common approach is to apply a “brute‑force” removal of all concave points, converting the region into its convex hull. While this simplifies the problem, it often adds a large amount of redundant search area, leading to wasted resources. Moreover, when the minimum turning radius of the fixed‑wing UAV exceeds half the sensor swath width, a simple U‑turn creates blind spots. In such cases, Dubins curves provide the optimal turning path that respects the curvature constraint.
To overcome these limitations, we propose a selective concave point removal strategy that uses both a distance ratio threshold and an interior angle threshold to decide whether to remove a concave point. Only those concave points that lead to narrow, inefficient strips are eliminated, preserving the original shape as much as possible while enabling efficient convex‑region search methods. After the polygon is processed into a convex shape, we compute the minimum span (width) of the region and align the scan direction perpendicular to that width. The fixed‑wing UAV then executes a back‑and‑forth scanning pattern with Dubins turns at the boundaries. We formulate the total search cost—including travel time, energy consumption, and path length—and prove that the proposed method significantly reduces these costs compared to both unprocessed concave regions and brute‑force convexification.
The remainder of this paper is organized as follows. Section 2 presents the UAV detection model and the mathematical formulation of the search cost. Section 3 details the coverage search strategy for convex polygons, including span calculation, scan direction determination, and Dubins curve generation. Section 4 introduces the improved concave point removal algorithm for irregular concave polygons. Section 5 provides simulation results and comparative analysis. Finally, Section 6 concludes the paper.
2. UAV Search Detection Model
2.1 Environment Assumptions
We assume that the submarine is stationary or moving very slowly compared to the fixed‑wing UAV, so we treat it as a static target. The search area is a two‑dimensional horizontal plane, and the altitude of the fixed‑wing UAV is constant. The internal area of the region is fully traversable (no obstacles or forbidden zones). The submarine is assumed to be near the surface such that non‑acoustic sensors are effective; hence we ignore depth variations.
2.2 UAV Field of View
When the fixed-wing UAV flies at a constant altitude h, its onboard sensor covers a rectangular footprint on the sea surface. The length Dl and width Ds of the footprint are given by:
$$
D_l = h \cdot \left[ \cot(\eta – \lambda) – \cot(\eta + \lambda) \right]
$$
$$
D_s = \frac{2h \tan \gamma}{\sin \eta}
$$
where γ is the half‑angle of the maximum width direction, λ is the half‑angle of the maximum length direction, and η is the sensor projection angle. The footprint is assumed to be centered directly below the fixed‑wing UAV.
2.3 Fixed‑Wing UAV Motion Model
We treat the fixed‑wing UAV as a point mass moving at constant altitude. Its planar kinematic model is:
$$
\begin{aligned}
\dot{x}(t) &= v(t) \cos \phi(t) \\
\dot{y}(t) &= v(t) \sin \phi(t) \\
\dot{\phi}(t) &= \omega(t) \theta_{\max}
\end{aligned}
$$
where (x, y) are the UAV coordinates, v(t) is the velocity, φ(t) is the heading angle, ω(t) is the normalized turn rate with \( |\omega(t)| \le 1 \), and θmax is the maximum yaw rate. The minimum turning radius is \( R_t = v / \theta_{\max} \). For a fixed‑wing UAV, we have \( R_t > 0 \), and the UAV cannot perform a spot turn.
2.4 Submarine Motion Model
Although we treat the submarine as stationary for search planning, its underwater motion model (for completeness) is:
$$
\begin{aligned}
\dot{x}_t(t) &= v_t(t) \cos \phi_t(t) \cos \varphi_t(t) \\
\dot{y}_t(t) &= v_t(t) \cos \phi_t(t) \sin \varphi_t(t) \\
\dot{z}_t(t) &= v_t(t) \sin \phi_t(t)
\end{aligned}
$$
where φt is the pitch angle and φt is the yaw angle of the submarine. In our coverage search scenario, the submarine’s speed is negligible compared to the fixed‑wing UAV’s speed, so we assume \( v_t = 0 \).
2.5 Search Cost Formulation
The total cost of the fixed‑wing UAV’s search mission comprises three components: straight‑line travel, scanning, and turning. Let:
- Ls – distance from base to the start of the search area.
- Ll – total straight‑line scanning distance (inside the region).
- Lc – total curved path length during turns.
The total path length L is:
$$
L = L_s + L_l + L_c
$$
The time cost T is:
$$
T = \frac{L_s + L_l}{v_l} + \frac{L_c}{v_t}
$$
where vl is the straight‑line speed and vt is the turn speed.
The energy consumption P is:
$$
P = \int_0^{(L_s+L_l)/v_l} P_l(t) \, dt + \int_0^{L_c/v_t} P_t(t) \, dt
$$
where Pl(t) and Pt(t) are the power during straight flight and turning, respectively. For simplicity we assume constant powers: Pl = 2 kW, Pt = 6.5 kW in our simulations.
The overall search cost C is a weighted sum:
$$
C = \omega_1 L + \omega_2 T + \omega_3 P
$$
We set equal weights in this study: \( \omega_1 = \omega_2 = \omega_3 = 1 \).
3. Coverage Search Strategy for Convex Polygonal Regions
3.1 Determination of Search Direction
For a fixed sensor swath width Ds, the number of turns required to cover a convex polygon is directly related to the width of the polygon in the direction perpendicular to the scan. The optimal scan direction is the one that minimizes the number of turns, i.e., the direction perpendicular to the polygon’s minimum span (width).
Definition 1 (Span of a convex polygon): Given a convex polygon, draw two parallel lines far apart such that the polygon lies between them. Move the lines towards the polygon until each touches the polygon (at a vertex or along an edge). The distance between these two support lines is called a span of the polygon.
Definition 2 (Width of a convex polygon): The width W is the minimum span over all orientations of the support lines. That is, \( W = \min_i \text{span}_i \).
The search direction is chosen to be parallel to the support lines that produce the width, so that the scan lines are perpendicular to that direction, minimizing the number of back‑and‑forth passes.
3.2 Algorithm for Computing Convex Polygon Width
We use a “point‑edge” method to compute the width. Let the convex polygon have vertices \( \{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\} \) in counter‑clockwise order. For each edge \( \mathbf{v}_i \mathbf{v}_{i+1} \), we compute the perpendicular distances from all other vertices to that edge. The maximum distance for that edge is the span associated with that edge direction. The width is the minimum of these spans.
The algorithm proceeds as follows:
- Input vertex sequence \( \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n, \mathbf{v}_1 \).
- For each edge \( \mathbf{v}_i \mathbf{v}_{i+1} \):
For each vertex \( \mathbf{v}_j \) (j ≠ i, j ≠ i+1):
Compute perpendicular distance \( d_{ij} \):
$$
d_{ij} = \frac{ \left| (y_{i+1} – y_i) x_j – (x_{i+1} – x_i) y_j + x_{i+1} y_i – x_i y_{i+1} \right| }{ \sqrt{(y_{i+1} – y_i)^2 + (x_{i+1} – x_i)^2} }
$$
- For edge i, find the maximum distance \( d_{i,\max} \) and the corresponding vertex index.
- The width \( W = \min_i d_{i,\max} \).
- Output \( W \) and the corresponding edge and vertex.
3.3 Scan Pattern and Dubins Turns
Once the scan direction (parallel to the width support lines) is determined, the fixed‑wing UAV follows a back‑and‑forth (zigzag) pattern inside the polygon. At the end of each scan line, it must turn around to start the next line. If the minimum turning radius \( R_t \le D_s/2 \), a semicircular turn suffices without leaving gaps. However, in many practical cases \( R_t > D_s/2 \), which creates uncovered strips (blind zones) if a simple turn is used. In such cases, we employ Dubins curves to connect two consecutive scan lines with minimal path length while respecting the curvature constraint.
A Dubins path is a combination of arcs of radius \( R_t \) and straight segments. There are six possible types: LSL, RSR, RSL, LSR, RLR, LRL (where L = left turn, R = right turn, S = straight). Given the starting configuration \( (x_s, y_s, \alpha) \) and ending configuration \( (x_e, y_e, \beta) \) where α and β are the heading angles, the Dubins algorithm finds the shortest smooth path among the six types. The length of each candidate path is expressed analytically, and we select the one giving the minimum length.
For a fixed‑wing UAV, the turn is performed entirely outside the search region to avoid intruding into uncovered areas. The Dubins path is computed such that the fixed‑wing UAV exits the region at the end of one scan line, executes the turn, and re‑enters at the start of the next scan line, with the sensor swath covering the entire width.
4. Boundary Processing for Irregular Concave Polygonal Regions
4.1 Identification of Concave Vertices
Given a polygon with vertices listed counter‑clockwise, a vertex \( \mathbf{v}_k \) is concave if the cross product of the two incident edges is negative (assuming standard orientation). For three consecutive vertices \( \mathbf{v}_{k-1}, \mathbf{v}_k, \mathbf{v}_{k+1} \), compute:
$$
\overrightarrow{\mathbf{v}_k \mathbf{v}_{k-1}} \times \overrightarrow{\mathbf{v}_k \mathbf{v}_{k+1}} = (x_{k-1} – x_k)(y_{k+1} – y_k) – (x_{k+1} – x_k)(y_{k-1} – y_k)
$$
If the cross product is negative, the vertex is a concave point.
4.2 Basic Concave Point Removal (Brute‑Force)
A straightforward method repeatedly removes concave points: delete the concave vertex and connect its two neighbors, then update the polygon. This continues until all remaining vertices are convex, i.e., the polygon becomes a convex hull. While simple, this method often adds large areas that are not part of the original search region, leading to wasteful scanning.
4.3 Improved Selective Concave Point Removal
To avoid “violent” removal of every concave point, we propose a selective removal strategy based on two criteria: a distance ratio threshold and an interior angle threshold.
Decision distance: For a concave vertex \( p \), we consider the set of its two neighboring vertices \( q = \{q_1, q_2\} \). The decision distance \( D_d(p,q) \) is the minimum distance from \( p \) to the line segment connecting its neighbors (or to the vertices themselves). In practice we compute the perpendicular distance from \( p \) to the line through the two neighbors.
Define the ratio:
$$
R = \frac{ \text{length of the edge } p q_1 }{ D_d(p,q) }
$$
If \( R < N \) (where \( N \) is a user‑defined threshold), the concave point is removed because the indentation is shallow and removing it adds little extra area. If \( R \ge N \), we further check the interior angle \( \theta \) at the concave point. If \( \theta < \Theta \) (another threshold), we remove the point; otherwise we keep it. This dual‑condition avoids removing deep narrow notches that would significantly expand the search area.
The improved algorithm steps:
- Input vertex sequence \( \mathbf{v}_1, \dots, \mathbf{v}_n \) and thresholds \( N, \Theta \).
- Initialize flag = true.
- While flag is true:
Set flag = false.
For each vertex \( \mathbf{v}_k \):
If \( \mathbf{v}_k \) is concave:
Compute \( R \) as above.
If \( R < N \): remove \( \mathbf{v}_k \), update list, set flag = true.
Else compute interior angle \( \theta \) at \( \mathbf{v}_k \).
If \( \theta < \Theta \): remove \( \mathbf{v}_k \), update list, set flag = true.
Else keep \( \mathbf{v}_k \).
End for.
End while. - Output the resulting polygon (now convex or nearly convex).
Appropriate threshold values are determined empirically; in our simulations we set \( N = 2.5 \) and \( \Theta = 120^\circ \).
5. Simulation and Verification
5.1 Simulation Setup
We implemented the algorithms in MATLAB and performed comparisons on a concave polygonal search region (approximately 30 km × 20 km). The fixed‑wing UAV parameters were:
| Parameter | Value |
|---|---|
| Sensor swath width \(D_s\) | 2 km |
| Sensor length \(D_l\) | 5 km |
| Minimum turning radius \(R_t\) | 1.5 km |
| Straight speed \(v_l\) | 600 km/h |
| Turn speed \(v_t\) | 350 km/h |
| Straight power \(P_l\) | 2 kW |
| Turn power \(P_t\) | 6.5 kW |
We designed four scenarios for comparison:
- Scenario A: Original concave polygon, non‑span search direction (90° off).
- Scenario B: Original concave polygon, span direction with Dubins turns (our method without concave removal).
- Scenario C: Concave polygon processed by brute‑force convex hull, non‑span direction.
- Scenario D: Concave polygon processed by our selective removal, span direction with Dubins (final proposed method).
5.2 Results and Analysis
Table 1 summarizes the key performance metrics for each scenario.
| Metric | A (Original, non‑span) | B (Original, span) | C (Brute convex hull) | D (Selective + span) |
|---|---|---|---|---|
| Total path length (km) | 2 409 | 2 443 | 3 247 | 3 085 |
| Invalid time cost \(T_{tc}\) (h) | 1.11 | 1.06 | 0.94 | 0.88 |
| Invalid energy cost \(P_{tc}\) (×10⁴ units) | 10.3 | 9.72 | 9.84 | 9.16 |
| Number of turns | — | — | — | — |
(*Note: Number of turns varies with direction; the span direction gave minimal turns for each polygon.)
Comparing A and B, applying the span direction (B) actually increased total path length slightly due to a required connecting segment, but reduced invalid turn path length, leading to lower time and energy costs. Comparing B (original concave) and D (selective removal + span), D had a longer total path (3 085 vs 2 443 km) because of the added convex area, but the number of turns dropped dramatically, resulting in 17% lower invalid time cost and 6.5% lower energy cost. Compared to the brute‑force convex hull (C), our selective method (D) reduced total path by 5% and energy by 7% while achieving similar turn reduction, confirming the advantage of selective removal over brute‑force convexification.
The simulation also showed that for the fixed‑wing UAV with \( R_t > D_s/2 \), Dubins turns eliminated all blind spots that would occur with simple U‑turns. The path symmetry between left and right turns was excellent, indicating robustness of the Dubins approach.
6. Conclusion
We have presented a comprehensive coverage search path planning method for a fixed‑wing UAV operating over complex irregular sea areas to find submarines. The key contributions are: (1) a complete analytical framework for modeling the search cost of a fixed‑wing UAV; (2) a selective concave point removal algorithm that uses both distance ratio and interior angle thresholds to transform irregular concave polygons into convex shapes while minimizing added redundant area; and (3) integration of Dubins curve turns to respect the fixed‑wing UAV’s minimum turning radius and avoid coverage gaps. Simulation results demonstrate that combining polygon span‑direction scanning with Dubins turns and selective concave removal significantly reduces invalid flight time and energy consumption compared to naive convexification or non‑optimal scan directions. The proposed method offers a practical and efficient solution for autonomous submarine search missions using fixed‑wing UAVs.