In this work, I address the challenge of planning reconnaissance trajectories for fixed-wing drones over mountainous terrain. Unlike rotary-wing platforms, fixed-wing drones are subject to stringent maneuverability constraints, such as limited turning radius and climb rate. My goal is to design a closed-loop route that maximizes area coverage while minimizing total flight length. I formulate the problem as a three-dimensional grid-based coverage optimization, incorporating terrain occlusion and no-fly zones. The proposed method combines a random landmark generation scheme, a constrained A* algorithm for path connection, and a simulated annealing framework to iteratively adjust waypoints. Extensive simulations show that the method consistently produces feasible loops with high coverage and short length, outperforming a state-of-the-art evolutionary approach.
The rest of the article is structured as follows. I first describe the modeling of the mission environment, the fixed-wing drone kinematics, and the coverage sensing model. Then, I detail the initial loop construction using a reciprocating scan pattern and a constrained A* algorithm. Next, I present the optimization procedure based on simulated annealing. Finally, I compare simulation results with an estimation of distribution algorithm and draw conclusions.
System modeling
I consider a three-dimensional operational space of dimensions Lx × Ly × Lz. The terrain is discretized into cubic cells of side length L = 100 m. Each cell is marked as occupied if it contains terrain; otherwise, it is free. Coverage is evaluated at the highest point of each cell. For the fixed-wing drone, I use a coarser grid in the horizontal plane: the drone’s waypoints are located at the vertices of rectangular prisms with horizontal dimensions La = 1 km and vertical dimension L = 100 m. The ratio N = La/L = 10 reflects the drone’s limited maneuverability. I define three types of waypoint status:
- -1: occupied by terrain or no-fly zone (forbidden)
- 0: adjacent to forbidden zone (temporary)
- 1: fully available
The drone’s motion is governed by constraints derived from its fixed-wing dynamics. Let the position at step n be (x(n), y(n), z(n)). The displacement from step n-1 to n defines the current direction (dx(n), dy(n), dz(n)). The next waypoint must satisfy directional continuity. In particular, I classify three cases:
Case 1: dx(n) = La, dy(n) = 0. Then the next step can choose sx(n) = dx(n), sy(n) ∈ {-La, 0, La}, sz(n) ∈ {-L, 0, L}.
Case 2: dx(n) = 0, dy(n) = La. Similar to Case 1 with axes swapped.
Case 3: dx(n) = La, dy(n) = La (diagonal flight). Then sx(n) ∈ {0, La}, sy(n) ∈ {0, La} with sx+sy ≠ 0, and sz(n) ∈ {-L, 0, L}.
These rules limit the turning angle to a maximum of 90° per step, which is realistic for fixed-wing drones. The total number of candidate next waypoints is at most nine.
The sensor is a forward-looking camera mounted on the fixed-wing drone. Its instantaneous field of view projects a trapezoidal area on the ground. The coverage footprint depends on the drone’s altitude, pitch, and sensor installation angle. To account for terrain masking, I perform a ray-casting check for every ground cell within the nominal footprint: if the line of sight from the drone to the cell is blocked by any terrain, that cell is considered uncovered. The maximum sensing range is set to 7 km. The coverage function fcov returns the set of cells covered given the current and previous waypoints.
Coverage objective
The mission requires maximizing the global coverage ratio Co (fraction of all non-terrain cells covered) while minimizing the total path length Llen. I combine these two criteria into a scalar objective function:
$$J = w \cdot C_o + (1 – w) \cdot \frac{L_{len}}{L_{max}}$$
where w = 0.35 is the coverage weight, and Lmax = N · Ymax is a normalization constant derived from the scanning pattern (Ymax is the number of vertical columns in the grid). A lower J indicates a better route.
Initial loop generation
I first generate an initial closed loop that approximately covers the area using a simple reciprocating scan pattern. I randomly select a fixed number of landmarks (available waypoints) and order them along a series of horizontal stripes. The order is determined by a sweep that goes back and forth across the region, as illustrated in the classic lawnmower pattern. Between consecutive landmarks, I apply a constrained A* algorithm to find the shortest feasible path.
The A* heuristic uses Euclidean distance, and the neighbor expansion is limited to those positions that satisfy the fixed-wing motion constraints described earlier. Additionally, when connecting two consecutive landmarks A → B, I consider the direction of entry into B required for the subsequent segment B → C. Any candidate path that would make the entry direction incompatible is discarded. This ensures that the entire loop is kinematically feasible.
The initial loop is generated iteratively: landmarks are added until the coverage ratio reaches a threshold of 95%. The resulting loop typically has a length on the order of 1.0 × 106 m and a coverage of 95% or more.
Optimization via simulated annealing
To reduce path length while maintaining acceptable coverage, I employ a simulated annealing (SA) framework. The algorithm starts from the initial loop and iteratively perturbs the set of landmarks. Each perturbation consists of two actions: (1) randomly adding a new available waypoint (subject to proximity constraints to avoid sharp turns), and (2) randomly removing an existing landmark. This keeps the total number of landmarks roughly constant. After a perturbation, the sequence of landmarks is reordered using the reciprocating scan rule, and the constrained A* algorithm recomputes the entire loop. The new objective Jnew is evaluated.
I accept the new solution with probability:
$$P(\text{accept}) = \begin{cases}
1 & \text{if } J_{new} < J_{old} \\
\exp\left(-\frac{J_{new} – J_{old}}{T}\right) & \text{otherwise}
\end{cases}$$
The temperature T decreases geometrically: Tk+1 = K · Tk with K = 0.98. The process stops when T falls below 0.001. The algorithm is run multiple times with different random seeds.
Simulation results
I conduct experiments on two synthetic terrain scenarios. Scenario I has a 50 km × 50 km × 5 km space; Scenario II is 50 km × 30 km × 5 km. No-fly zones are modeled as spherical obstacles. The initial coverage threshold is 95%, and the optimization target is 90% coverage. I compare the simulated annealing method with an estimation of distribution algorithm (EDA).
Table 1 summarizes the statistics of 10 independent runs of the SA method on Scenario I.
| Metric | Value |
|---|---|
| Average improvement in J (%) | 22.06 |
| Maximum improvement (%) | 25.47 |
| Minimum improvement (%) | 19.61 |
| Standard deviation (%) | 1.689 |
| Final coverage (average, %) | 90.3 |
| Final path length (average, m) | 6.2 × 105 |
The SA algorithm consistently reduces the objective by more than 19%, with small variance. Coverage drops from about 95% to 90% (still high), while path length is reduced by approximately 39% (from ~1.0 × 106 m to ~6.2 × 105 m). Figure 1 below shows an example of an optimized loop generated by SA.
In contrast, the EDA method produced an average improvement of only 13.97%, with a final coverage of 94.66% but a much smaller reduction in path length. The EDA converges prematurely because it relies on elite selection that quickly fixes the landmark set, leading to a local optimum. The SA method’s ability to escape local minima via probabilistic acceptance yields superior solutions.
The evolution of the objective function during a typical SA run is shown in Table 2 (numerical values at selected iterations).
| Iteration | Temperature | J | Coverage (%) | Length (105 m) |
|---|---|---|---|---|
| 0 (initial) | 1.000 | 1.192 | 95.0 | 10.1 |
| 50 | 0.364 | 1.042 | 93.2 | 8.5 |
| 100 | 0.133 | 0.957 | 91.5 | 7.2 |
| 150 | 0.048 | 0.905 | 90.4 | 6.4 |
| 200 | 0.018 | 0.889 | 90.3 | 6.2 |
The results demonstrate that the proposed framework effectively balances coverage and path length for fixed-wing drones in complex terrain with occlusion and no-fly zones.
Conclusion
I have presented a complete methodology for area coverage loop planning of fixed-wing drones in mountainous environments. The key contributions include: (1) a 3D grid model that accounts for terrain masking and no-fly zones, (2) a constrained A* algorithm that respects fixed-wing maneuverability constraints, and (3) a simulated annealing optimizer that jointly optimizes coverage and path length. Simulation results show that the method generates feasible loops with over 90% coverage while reducing path length by nearly 40% compared to initial scanning patterns. The approach outperforms an alternative evolutionary method (EDA) in both solution quality and robustness. Future work will investigate reinforcement learning techniques to further improve computational efficiency.