Surveying drones and surveying UAVs face significant challenges in mountainous environments where complex topography and obstacles demand advanced path planning. Conventional A* algorithms struggle with computational inefficiency, excessive node exploration, and failure to incorporate motion constraints, leading to suboptimal or unsafe flight paths. This work addresses these limitations through an improved A* algorithm integrating motion constraints, adaptive heuristic weighting, and B-spline trajectory smoothing.
We model the environment using a 3D grid map where obstacles and no-fly zones are represented as spherical exclusion regions with radii \(r_i\) centered at \((x_i, y_i, z_i)\):
$$R_i: (x – x_i)^2 + (y – y_i)^2 + (z – z_i)^2 = r_i^2$$
The core A* evaluation function combines actual cost \(G(n)\) from start node \(n_{\text{start}}\) and heuristic estimate \(H(n)\) to goal node \(n_{\text{goal}}\):
$$F(n) = G(n) + H(n)$$
Euclidean distance serves as the heuristic for surveying UAVs:
$$H(n) = \sqrt{(x_n – x_{\text{goal}})^2 + (y_n – y_{\text{goal}})^2 + (z_n – z_{\text{goal}})^2}$$
Critical constraints for surveying drones include:
- Range constraint (maximum flight distance \(L_{\max}\)):
$$L = \sum_{i=1}^{n} l_i \leq L_{\max}, \quad l_i = \sqrt{(x_{i+1} – x_i)^2 + (y_{i+1} – y_i)^2 + (z_{i+1} – z_i)^2}$$ - Altitude bounds:
$$z_{\min} \leq z_i \leq z_{\max}$$ - Climb/yaw angle limits:
$$0 \leq \beta \leq \beta_{\max}, \quad 0 \leq \gamma \leq \gamma_{\max} \quad \left(\beta_{\max} = \frac{\pi}{6}, \gamma_{\max} = \frac{\pi}{3}\right)$$
To optimize search efficiency, we dynamically adjust heuristic weights in the evaluation function:
$$F(n) = G(n) + \alpha H(n)$$
Comparative analysis of weighting factors demonstrates efficiency gains:
| Weight (\(\alpha\)) | Open Nodes | Closed Nodes | Path Length (m) |
|---|---|---|---|
| 1.0 (Default) | 2079 | 1651 | 91.0 |
| 1.2 | 1798 | 1455 | 104.0 |
| 1.1 | 1863 | 1569 | 97.0 |
| 0.8 | 2218 | 1856 | 79.0* |
*Failed to reach destination. Weight \(\alpha = 1.1\) reduces node exploration by 8% with minimal path elongation (6m), ideal for surveying drones.
For flight feasibility, sharp trajectories are smoothed using cubic B-spline interpolation:
$$P(t) = \sum_{i=1}^{n} P_i B_{i,k}(t)$$
where \(P_i\) are control points and \(B_{i,k}\) basis functions. Optimization yields:
| Path | Max Turn Angle (°) | Path Length (m) |
|---|---|---|
| Original | 74 | 97.0 |
| B-spline Optimized | 56 | 92.4 |
B-spline processing reduces turn angles by 24.3% and shortens paths by 4.7%, critical for surveying UAV stability.
Simulations in MATLAB R2021b validate the approach across mountainous terrains with randomized peaks and six no-fly zones. For start \((10, 10, 5)\) and goal \((90, 80, 5)\), the algorithm generates continuous paths at near-constant altitudes to conserve surveying drone battery life. Additional tests with varied start/goal positions (e.g., \((20, 30, 4)\) to \((80, 70, 6)\) and altered terrain) confirm robustness with computation times under 2 seconds. The optimized trajectories consistently satisfy all motion constraints while avoiding obstacles.
This enhanced algorithm demonstrates three advantages for surveying drones: 1) Motion-constrained node expansion ensures flight envelope adherence, 2) Adaptive heuristic weighting reduces node exploration by ≥8%, and 3) B-spline smoothing decreases turn angles by 24.3% while shortening paths. Future work will integrate real-time wind compensation for surveying UAV operations in dynamic mountain environments.