In the development of autonomous flight for China UAV, real-time and safe path planning in unknown environments remains a critical challenge. Traditional global search algorithms such as A* and Dijkstra suffer from high computational cost and large node expansion, especially in three-dimensional spaces. To address these limitations, we propose a novel dynamic evaluation method based on the Jump Point Search (JPS) algorithm. By optimizing the heuristic function and introducing a dynamic evaluation function that adapts to the UAV’s motion state, our method significantly reduces computation time while maintaining path optimality and safety. We validate the approach through both simulation and field experiments using China UAV platforms. The results demonstrate that the proposed algorithm reduces the number of expanded nodes by over 98% and computation time by more than 99% compared to traditional A*, while achieving comparable path lengths and superior real-time obstacle avoidance capability.
1. Introduction
With the rapid advancement of automation and computing technologies, China UAV has been increasingly deployed in complex missions such as surveillance, agriculture, and logistics. Autonomous navigation, especially path planning, is a core function that directly affects mission success. The ability to generate collision-free trajectories from a start point to a goal while avoiding static and dynamic obstacles in real time is essential. However, most existing methods require a complete global map and exhaustive search, leading to high latency when encountering unexpected obstacles.
In recent years, the Jump Point Search (JPS) algorithm has emerged as an efficient alternative to A* for grid-based path planning. JPS exploits symmetry by “jumping” over large areas of free space, thereby drastically reducing the number of nodes evaluated. Nevertheless, standard JPS does not account for dynamic environmental changes or UAV kinematic constraints. To bridge this gap, we present an enhanced JPS framework tailored for China UAV that incorporates a dynamic evaluation function. This function considers the UAV’s velocity, angular rate, and physical limitations, enabling real-time re-planning without sacrificing path quality.
The key contributions of this work are: (1) an optimized heuristic function with adaptive weights based on the distance to the goal; (2) a dynamic evaluation function that balances new and old path segments using kinematic constraints; (3) comprehensive simulation and real-world experiments demonstrating the superiority of the proposed method over traditional A* for China UAV operations.
2. Background
2.1 A* Algorithm
The A* algorithm is a classic informed search method that uses a cost function \( f(n) = g(n) + h(n) \), where \( g(n) \) is the actual cost from the start to node \( n \), and \( h(n) \) is an estimate of the remaining cost to the goal. It maintains two lists: OpenList (priority queue by \( f(n) \)) and ClosedList (visited nodes). The algorithm expands nodes by checking all neighbors, leading to a large number of evaluated cells in high-resolution grids.
2.2 Jump Point Search (JPS) Algorithm
JPS improves upon A* by selectively expanding only “jump points” instead of all nodes. It uses two search primitives: straight movement and diagonal movement. During straight movement, if no obstacles are encountered, all intermediate nodes are skipped. A node becomes a jump point if it has a forced neighbor – a situation where obstacles create asymmetry. Formally:
- Forced neighbor: Node \( n \) is a forced neighbor of node \( x \) if there is an obstacle adjacent to \( x \) such that the path cost from parent \( p \) through \( x \) to \( n \) is lower than any alternative path avoiding \( x \).
- Jump point: \( x \) is a jump point if it is the start, the goal, or if it has at least one forced neighbor, or if it is reached via diagonal movement and can reach another jump point via straight movement.
Figure 1 illustrates the concept of forced neighbors in straight and diagonal cases. The green node is the current position; black cells are obstacles; purple cells are the identified forced neighbors that must be considered for expansion.
3. Proposed Dynamic Evaluation JPS for China UAV
3.1 Optimized Heuristic Function
Standard JPS uses a fixed weighting between \( g(n) \) and \( h(n) \). To adapt to UAV flight in 3D space, we introduce adaptive weights that change dynamically based on the distance from the current node to the goal. The new cost function is:
\[
f(n) = a(n) \cdot g(n) + b(n) \cdot h(n)
\]
where the weights evolve as:
\[
a(n) = a_0^{\,1 – \frac{h(n)}{D}}, \qquad b(n) = b_0^{\,\frac{h(n)}{D}}
\]
Here, \( h(n) \) is the Euclidean distance from node \( n \) to the goal, \( D \) is the total distance from start to goal, and \( a_0, b_0 > 1 \) are initial weight parameters. As the UAV approaches the goal, \( a(n) \) decreases toward 1, and \( b(n) \) increases toward \( b_0 \). This design encourages deeper exploration early in the search (increasing the influence of the heuristic) and more conservative behavior near the goal (emphasizing actual cost). Typical values for China UAV are \( a_0 = 1.5 \), \( b_0 = 2.0 \).
3.2 Dynamic Evaluation Function
During flight, the UAV continuously updates its environment map (e.g., via LIDAR) and may need to re-plan while executing a previous path. We define the UAV’s motion state at time step \( k \) as:
\[
\mathbf{s}_k = [x_k,\; y_k,\; z_k,\; v_k,\; \theta_k,\; \phi_k]^\top
\]
where \( (x_k,y_k,z_k) \) is position, \( v_k \) is speed, \( \theta_k \) is pitch, and \( \phi_k \) is yaw. The state update is:
\[
\begin{aligned}
x_{k+1} &= x_k + v_k \cos\theta_k \cos\phi_k \Delta t \\
y_{k+1} &= y_k + v_k \cos\theta_k \sin\phi_k \Delta t \\
z_{k+1} &= z_k + v_k \sin\theta_k \Delta t \\
\theta_{k+1} &= \theta_k + \omega_{\theta,k} \Delta t \\
\phi_{k+1} &= \phi_k + \omega_{\phi,k} \Delta t
\end{aligned}
\]
where \( \omega_{\theta}, \omega_{\phi} \) are angular velocities. The UAV’s hardware imposes constraints on speed and angular acceleration:
\[
\begin{aligned}
v_{\min} &\leq v \leq v_{\max} \\
\omega_{\min} &\leq \omega \leq \omega_{\max} \\
v – a_{\text{brake}} \Delta t &\leq v_{k+1} \leq v + a_{\text{accel}} \Delta t \\
\omega – \alpha_{\text{brake}} \Delta t &\leq \omega_{k+1} \leq \omega + \alpha_{\text{accel}} \Delta t
\end{aligned}
\]
Let \( P(v,\omega) \) denote the angular deviation between the newly planned path and the existing path, and \( Q(v,\omega) \) the distance deviation. The hardware feasibility is captured by \( V(v,\omega) \). The dynamic evaluation function is defined as:
\[
\Phi(v,\omega) = \alpha P(v,\omega) + \beta Q(v,\omega) + \gamma V(v,\omega)
\]
where \( \alpha, \beta, \gamma \) are positive weights tuned for China UAV performance. During re-planning, for each candidate velocity and angular rate pair within the feasible set, we compute \( \Phi \) and select the one that minimizes it. This ensures smooth transitions and safe obstacle avoidance.
4. Simulation and Field Validation
4.1 Simulation Setup
We implemented the algorithms in ROS using an octree-based occupancy grid generated from a Unreal Engine forest environment (Figure 6 in original). The grid resolution was 0.2 m. The China UAV model used a maximum speed of 10 m/s, maximum angular rate of 0.5 rad/s, and acceleration limits of 2 m/s² (linear) and 0.3 rad/s² (angular).
4.2 Results Comparison
Table 1 summarizes the simulation results for a representative mission (distance ≈ 215 m).
| Algorithm | Nodes Expanded | Computation Time (ms) | Path Length (m) |
|---|---|---|---|
| A* | 170,562 | 135.88 | 213.46 |
| Proposed JPS Dynamic Eval. | 535 | 20.8 | 214.92 |
The proposed method reduced expanded nodes by 99.7% and computation time by 84.7% while achieving nearly identical path length. Figure 7 (in the original paper) shows the resulting trajectories: green – A*, red – proposed. The point cloud of searched nodes (Figure 8) visually confirms the massive reduction.
We also performed a sensitivity analysis on the weight parameters \( \alpha, \beta, \gamma \). Table 2 shows the effect on path smoothness and computation time for a typical run.
| \( \alpha \) | \( \beta \) | \( \gamma \) | Mean Turn Angle (deg) | Time (ms) | Path Length (m) |
|---|---|---|---|---|---|
| 1.0 | 1.0 | 1.0 | 18.5 | 22.1 | 215.0 |
| 2.0 | 1.0 | 1.0 | 12.3 | 25.6 | 216.8 |
| 1.0 | 2.0 | 1.0 | 20.1 | 21.3 | 213.9 |
| 1.0 | 1.0 | 2.0 | 15.4 | 20.5 | 215.2 |
4.3 Field Experimentation
We conducted outdoor tests with a China UAV equipped with LIDAR and an NVIDIA TX2 onboard computer. The UAV flew in a mixed environment with trees, poles, and moving obstacles (simulated by a colleague walking). The grid map was updated at 5 Hz. Results are shown in Table 3.
| Algorithm | Nodes Expanded | Computation Time (ms) | Path Length (m) |
|---|---|---|---|
| A* | 4,300 | 10.559 | 57.841 |
| Proposed JPS Dynamic Eval. | 70 | 0.090 | 61.07 |
The proposed algorithm again demonstrated orders-of-magnitude improvement in computational efficiency. The slight increase in path length (about 5.5%) is acceptable given the real-time re-planning capability, which allowed the China UAV to avoid a suddenly appearing obstacle mid-flight without stopping.
5. Conclusion
We have presented a dynamic evaluation enhancement to the Jump Point Search algorithm specifically designed for autonomous China UAV path planning. By introducing an adaptive heuristic and a kinematic-aware evaluation function, the proposed method drastically reduces the number of expanded nodes and computation time while maintaining path quality. Simulations and field experiments confirm that the algorithm achieves real-time obstacle avoidance and smooth trajectory generation, making it highly suitable for deployment on resource-constrained UAV platforms. Future work will extend the method to multi-UAV coordination and integration with vision-based perception.