We address the challenge of reconnaissance route planning for fixed-wing drones in mountainous terrains. Our objective is to design an optimal circular route that balances high area coverage with minimal path length, while respecting the maneuverability constraints of fixed-wing drones. Our methodology integrates a grid-based spatial model, a constrained A* algorithm for path generation, and a Simulated Annealing (SA) optimization framework to refine the route.
1. Problem Modeling and Spatial Discretization
We first define the three-dimensional mission space with dimensions \( L_x \times L_y \times L_z \). To manage complexity, we discretize this space into uniform cubic cells. A cell is classified as terrain-occupied if it contains any part of the digital elevation model. The coverage problem then becomes a binary 0-1 optimization, determining whether each terrain cell is observed by the fixed-wing drone’s sensor.
Given the flight dynamics of a fixed-wing drone, we use a coarser grid for flight path nodes. The vertical grid resolution matches the terrain cells, while the horizontal resolution is larger, with a ratio \( N = L_{grid} / L_{cell} \). The vertices of this coarser grid represent possible waypoints. The state of each waypoint is initialized as:
- -1: Occupied by terrain or no-fly zones (inaccessible).
- 0: Adjacent to obstacles (temporary waypoints).
- 1: Normal, accessible waypoints.
The flight model for our fixed-wing drone imposes strict turning constraints. The position at the next waypoint \( \mathbf{P}_{n+1} = (x_{n+1}, y_{n+1}, z_{n+1}) \) is determined by the current point \( \mathbf{P}_n = (x_n, y_n, z_n) \) and the previous point \( \mathbf{P}_{n-1} \). The heading direction vector is defined as \( \mathbf{d}_n = (dx, dy, dz) \). The allowable steps for the next move are constrained by:
| Current Direction \( \mathbf{d}_n \) | Allowable Steps \( (sx, sy, sz) \) | Explanation |
|---|---|---|
| \( dx = L_{grid}, dy = 0 \) | \( sx = L_{grid}, sy \in \{L_{grid}, 0, -L_{grid}\}, sz \in \{L, 0, -L\} \) | Moving horizontally; can turn slightly or change altitude. |
| \( dx = 0, dy = L_{grid} \) | \( sx \in \{L_{grid}, 0, -L_{grid}\}, sy = L_{grid}, sz \in \{L, 0, -L\} \) | Similar constraints, symmetric for vertical movement. |
| \( dx = L_{grid}, dy = L_{grid} \) | \( sx \in \{0, dx\}, sy \in \{0, dy\}, sx+sy \neq 0, sz \in \{L, 0, -L\} \) | Diagonal movement; cannot reverse direction. |
This movement model ensures the maximum turning angle is limited, simulating the turning radius of a fixed-wing drone.
For the sensor model, we consider a forward-looking camera with a trapezoidal footprint on the ground. The field of view depends on flight altitude, pitch angle, and sensor mounting. Crucially, we account for terrain masking. For every potential ground cell within the geometric footprint, we perform a line-of-sight check. A cell is considered covered only if:
- It lies within the projected footprint.
- The line from the drone to the cell’s center is not intersected by any other terrain cell.
- The distance from the drone to the cell is less than the maximum sensor range \( S \).
This is formalized by a coverage function \( f_{cov}(\mathbf{P}_n, \mathbf{P}_{n-1}) \) which outputs the set of cells successfully observed from waypoint \( \mathbf{P}_n \) given the previous waypoint’s direction.
2. Optimization Objective
Our goal is to find a closed-loop path, starting and ending at the same point, that maximizes coverage and minimizes path length. The objective function for a given route is defined as:
$$
f(C_o, L_{len}) = K_1 \cdot w \cdot C_o + K_2 \cdot (1-w) \cdot L_{len}
$$
where:
- \( C_o \) is the global coverage rate, the fraction of terrain cells covered at least once.
- \( L_{len} \) is the total length of the flight path.
- \( w \) is a weight factor balancing coverage and length (e.g., \( w=0.35 \) during optimization).
- \( K_1 \) and \( K_2 \) are normalization constants.
A lower \( f \) value indicates a better route. The optimization problem is: minimize \( f \) subject to constraints on waypoint connectivity, no-fly zone avoidance, and drone performance.
3. Algorithm: Random Experiment-Based Loop Planning
We develop a two-stage algorithm: initial loop generation using random waypoints and a scanning strategy, followed by iterative optimization using Simulated Annealing (SA). The entire process is designed to exploit random experimentation for efficient exploration.
3.1 Initial Loop Generation
An initial loop is generated by:
- Random Waypoint Selection: A set of waypoints is randomly selected from accessible nodes (state 1).
- Ordering via Reciprocating Scan: To impose structure similar to a boustrophedon path, the waypoints are sorted based on their x-y coordinates, following a back-and-forth “lawnmower” pattern. This naturally defines a TSP-like visiting order.
- Inter-Waypoint Connection: Adjacent waypoints are connected by a path optimal for the fixed-wing drone, computed using a constrained A* algorithm.
The constrained A* algorithm incorporates the flight dynamics of our fixed-wing drone directly into the search. The cost function is:
$$
f(n) = g(n) + h(n)
$$
where \( g(n) \) is the actual path cost from the start to node \( n \), and \( h(n) \) is the Euclidean distance heuristic. The key constraint is that when expanding a node, we only consider successor nodes that satisfy the turning rules defined in Section 1. This ensures the resulting path is flyable. Additionally, when connecting waypoints, the algorithm considers the entry direction into the next waypoint to ensure seamless transitions. This process is repeated until a global coverage threshold (e.g., 95%) is met, generating the initial flyable loop.
3.2 Optimization via Simulated Annealing
Starting from the initial loop, we apply a Simulated Annealing (SA) framework to optimize the route. The energy function is the objective function defined earlier. At each iteration, a new solution is generated by a “random experiment” on the current loop:
- Waypoint Mutation: A new waypoint is randomly added to the loop, provided it is accessible and not too close to existing waypoints (to maintain turning feasibility). Simultaneously, a random existing waypoint is removed. This keeps the number of waypoints relatively stable but perturbs the route.
- Loop Re-order and Evaluation: The order of all waypoints is recalculated using the reciprocating scan rule. The constrained A* algorithm reconnects all adjacent waypoints, producing a new flyable loop. The new coverage \( C_{o,new} \) and length \( L_{len,new} \) are computed, yielding a new objective value \( f_{new} \).
- Acceptance Criterion: The Metropolis criterion is used:
$$
P_{accept}(f_{old} \rightarrow f_{new}) =
\begin{cases}
1, & \text{if } f_{new} < f_{old} \\
e^{-\frac{f_{new} – f_{old}}{T}}, & \text{otherwise}
\end{cases}
$$
where \( T \) is the current temperature. A random number is generated; if it is less than \( P_{accept} \), the new loop is accepted, even if it is worse, preventing premature convergence. The temperature is decremented geometrically: \( T_{k+1} = \alpha \cdot T_k \), with \( \alpha = 0.98 \). The algorithm terminates when \( T < 0.001 \).
4. Simulation Results and Analysis
We tested our method on two simulation scenarios. The parameters are summarized in Table 2.
| Parameter | Symbol | Scenario I Value | Scenario II Value |
|---|---|---|---|
| Space Dimensions | \( L_x \times L_y \times L_z \) | 50 km × 50 km × 5 km | 50 km × 30 km × 5 km |
| Terrain Cell Size | \( L \) | 100 m | 100 m |
| Flight Node Grid Size | \( L_{grid} \) | 1 km | 1 km |
| Grid Ratio (H / W) | \( N \) | 10 | 10 |
| Max Sensor Range | \( S \) | 7 km | 7 km |
| Coverage Weight (Optim.) | \( w \) | 0.35 | 0.35 |
| Initial Coverage Threshold | \( C_{o,init} \) | 95% | 95% |
The initial loop achieved a very high coverage (around 95%) but had a path length of over 1000 km, which is inefficient for a long-endurance fixed-wing drone.
After applying the SA-based optimization, we observed a significant improvement. Table 3 quantifies the improvement for a single representative run on Scenario I.
| Metric | Initial Loop | Optimized Loop (SA) | Improvement |
|---|---|---|---|
| Global Coverage \( C_o \) | 95.03% | 90.27% | -4.76% (within tolerance) |
| Path Length \( L_{len} \) | 1,014,000 m | 616,216 m | 39.22% reduction |
| Objective Value \( f \) | – | 0.8884 | 25.47% optimization |
The SA algorithm successfully traded a small decrease in coverage for a massive 39.22% reduction in flight path. This is critical for a fixed-wing drone, as it directly translates to lower fuel consumption and risk of detection. The altitude of the flight path also converged to a narrower band, eliminating unnecessary spiraling to gain altitude seen in the initial loop.
We performed 10 independent runs of the algorithm on Scenario I to test reliability. The results for the optimization rate are shown in Table 4.
| Metric | Value |
|---|---|
| Average Optimization Rate | 22.06% |
| Maximum Optimization | 25.47% |
| Minimum Optimization | 19.61% |
| Standard Deviation | 1.69% |
The low standard deviation confirms the robustness of our method. The random experiments within the SA framework consistently found high-quality solutions for the fixed-wing drone’s route.
4.1 Comparison with Estimation of Distribution Algorithm (EDA)
To benchmark our approach, we compared it against an Estimation of Distribution Algorithm (EDA). The EDA was initialized with 10 initial paths and used an elite group to update a probability model for waypoint selection. The results are summarized in Table 5.
| Metric | Simulated Annealing (Our Method) | Estimation of Distribution Algorithm |
|---|---|---|
| Best Objective Value \( f \) | 0.8884 | 1.0374 |
| Best Coverage \( C_o \) | 90.27% | 94.66% |
| Max Optimization Rate | 25.47% | 13.97% |
| Algorithm Characteristic | Exploration with controlled degradation | Greedy exploitation of elite solutions |
The EDA converged too quickly, leading to a local optimum with a high coverage but a relatively long and inefficient path. In contrast, our SA-based method, with its random waypoint addition and removal experiments, was able to escape local minima and find a better global compromise between coverage and length. The final objective value is significantly better (lower) for our method.
5. Conclusions
We have developed a novel and effective method for planning efficient area coverage loops for fixed-wing drones operating in complex 3D terrains. Our key contributions include:
- A realistic, constraint-aware model for a fixed-wing drone’s flight and sensor, including terrain masking.
- A “random experiment” strategy within a Simulated Annealing framework that generates and mutates waypoints to explore the solution space effectively.
- A constrained A* algorithm that guarantees the generated paths are flyable by a fixed-wing drone.
Simulation results demonstrate that our method consistently generates high-quality loops that provide over 90% area coverage while significantly reducing the required flight path length compared to initial, non-optimized routes. The method outperformed a competing metaheuristic (EDA), showing its superiority in balancing the crucial trade-off between coverage and energy efficiency for modern fixed-wing drone operations. Future work will explore the integration of reinforcement learning to further automate the learning of optimal loop structures.