In the context of autonomous flight, the ability of a UAV drone to plan a safe and efficient trajectory in real time is critical for mission success. Traditional global search algorithms such as A* and Dijkstra require exhaustive exploration of the entire grid map before generating a path, which leads to high computational overhead and long planning times. Moreover, when encountering dynamic obstacles in complex unknown environments, these algorithms must perform a complete re-planning, often failing to meet the stringent requirements of real-time operation and flight safety. To overcome these limitations, I propose a novel dynamic evaluation method based on the Jump Point Search (JPS) algorithm. The proposed approach optimizes the heuristic function and introduces a dynamic cost function that adapts to the real-time state of the UAV drone, significantly improving both planning efficiency and obstacle avoidance performance. This paper presents a comprehensive study of the algorithm, including theoretical foundations, implementation details, simulation results, and field experiments. The results demonstrate that the dynamic JPS algorithm reduces search nodes by orders of magnitude and shortens computation time by more than 90% compared to the traditional A* algorithm, while maintaining comparable path lengths. The algorithm is validated in both virtual environments and real outdoor flights using a quadrotor UAV drone equipped with a LiDAR sensor and an embedded computing platform.
Introduction
The rapid development of automation and computing technologies has driven the evolution of UAV drone systems toward greater autonomy and intelligence. Path planning is one of the core functionalities of autonomous flight, as it determines how a UAV drone navigates from a start point to a target point while avoiding obstacles and optimizing some performance criterion (e.g., path length, flight time, or energy consumption). In many practical scenarios, the environment is not fully known in advance, and obstacles may appear dynamically. Therefore, a path planning algorithm must be both computationally efficient and capable of reacting to changes in the environment in real time.
Existing path planning algorithms can be classified into three main categories: sampling-based, search-based, and bio-inspired methods. Sampling-based algorithms, such as Rapidly-exploring Random Tree (RRT) and Probabilistic Roadmap Method (PRM), generate random samples in the configuration space and connect them to form a graph or tree. These methods are computationally efficient but often produce suboptimal paths and lack guarantee of optimality. Search-based algorithms, including A* and Dijkstra, explore the state space systematically and guarantee the shortest path if a grid-based representation is used. However, they suffer from high computational complexity, especially in large 3D grids, as they must examine every node in the open list. Bio-inspired algorithms, such as ant colony optimization, particle swarm optimization, and genetic algorithms, iteratively improve candidate solutions but are sensitive to parameter tuning and may converge to local optima.
The Jump Point Search (JPS) algorithm was introduced as an extension of A* that exploits symmetry in uniform-cost grids to prune redundant nodes. By identifying “jump points” where the direction of travel must change, JPS dramatically reduces the number of nodes expanded during the search. However, the standard JPS algorithm is designed for static environments and does not account for the dynamic constraints of a UAV drone in flight. For example, a UAV drone cannot instantaneously change its velocity or heading; it must obey kinematic and dynamic limits. Furthermore, when the onboard sensor (e.g., LiDAR) updates the environment map at a certain frequency, the newly generated path may conflict with the currently executing path, leading to unnecessary oscillations or even collisions.
To address these issues, I propose an improved JPS algorithm that incorporates a dynamic evaluation function. The main contributions of this work are:
- An optimized heuristic function that dynamically adjusts the weights of the cost-to-come and cost-to-go based on the distance between the start and target, making the search more adaptable to the 3D flight environment.
- A dynamic evaluation function that considers the current kinematic state of the UAV drone (velocity, angular velocity, acceleration limits) and smoothly blends the new planned path with the old one to ensure feasible and safe maneuvers.
- Comprehensive simulations and field experiments that verify the algorithm’s performance in terms of node expansion count, computation time, path length, and real-time obstacle avoidance capability.
Related Work and Background
A* Algorithm
The A* algorithm is a best-first search that uses a cost function defined as:
$$ f(n) = g(n) + h(n) $$
where \( g(n) \) is the actual cost from the start node to node \( n \), and \( h(n) \) is a heuristic estimate of the cost from node \( n \) to the target. A* maintains two lists: an open list (priority queue ordered by \( f(n) \)) and a closed list (visited nodes). The algorithm repeatedly selects the node with the lowest \( f(n) \) from the open list, expands its neighbors, updates their costs, and adds them to the open list. The process terminates when the target node is reached or the open list becomes empty. A* guarantees the shortest path if the heuristic is admissible (never overestimates the true cost) and consistent.
An example of the A* search process is illustrated conceptually: initially, the start node is added to the open list. During iteration, the node with the smallest \( f \) value is expanded. Neighbors that are not obstacles and not in the closed list are inserted into the open list with updated \( g \) and \( h \) values. The closed list accumulates processed nodes. When the target enters the open list, the path is reconstructed by backtracking from the target to the start. However, for large 3D grids, A* expands a huge number of nodes, making it impractical for real-time UAV drone path planning.
Jump Point Search (JPS)
JPS improves A* by exploiting the symmetry of uniform-cost grids. Instead of expanding all neighbors of a node, JPS identifies “jump points” where the direction of travel must change due to obstacles or forced neighbors. The key concepts are:
- Forced neighbor: A node \( n \) is a forced neighbor of node \( x \) if there is an obstacle in one of the adjacent cells and the path from \( x \)’s parent to \( n \) via \( x \) is shorter than any alternative path that does not pass through \( x \).
- Jump point: A node is a jump point if it is the start or target, it has at least one forced neighbor, or it can be reached via a diagonal move from its parent and then a straight move leads to another jump point.
The search proceeds by scanning in four cardinal directions first, then in diagonal directions. During a straight line scan, if no obstacle is encountered, all intermediate nodes are ignored (pruned). Only when a forced neighbor is detected does the current node become a jump point and is added to the open list. For diagonal scans, the algorithm checks the two cells behind the diagonal direction; if one is an obstacle, the cell ahead becomes a potential jump point. This mechanism reduces the number of expanded nodes from the entire grid to only those critical points where the path must change direction.
Proposed Dynamic JPS Algorithm
Optimization of the Heuristic Function
Standard JPS uses a fixed weighting between \( g(n) \) and \( h(n) \). In a 3D flight environment, the UAV drone may have different priorities at different stages of the mission. To improve search quality, I introduce an adaptive weight factor that changes with the remaining distance to the target. The modified cost function is:
$$ f(n) = a(n) \cdot g(n) + b(n) \cdot h(n) $$
where the weights are defined as:
$$ a(n) = a_0^{\left(1 – \frac{h(n)}{D}\right)} $$
$$ b(n) = b_0^{\frac{h(n)}{D}} $$
Here, \( a_0 > 1 \) and \( b_0 > 1 \) are the initial weight values (e.g., \( a_0 = 1.5, b_0 = 2.0 \)), and \( D \) is the Euclidean distance between the start and target. As the heuristic \( h(n) \) decreases (i.e., the UAV drone approaches the target), the weight \( a(n) \) decreases toward 1, making the search more greedy and focusing on the path cost. Conversely, \( b(n) \) increases toward \( b_0 \), giving more influence to the heuristic guidance when far from the target. This adaptive weighting helps the algorithm explore efficiently in the early stage and converge quickly in the final stage.
Dynamic Evaluation Function for Real-Time Replanning
In a dynamic environment, the UAV drone continuously receives sensor data and updates the local occupancy grid. When a new path is computed by the JPS algorithm, it may conflict with the currently executing path. Naively switching to the new path could cause abrupt maneuvers, violating kinematic constraints or even leading to instability. Therefore, I design a dynamic evaluation function that integrates the current motion state of the UAV drone into the path selection process.
Let the state of the UAV drone at time step \( k \) be represented by the position \((x_k, y_k, z_k)\), velocity \( v_k \), pitch angle \( \theta_k \), yaw angle \( \phi_k \), and angular velocity \( \omega_k \). The discrete-time motion model is:
$$
\begin{aligned}
x_{k+1} &= x_k + v_k \cos \theta_k \cos \phi_k \cdot \Delta t \\
y_{k+1} &= y_k + v_k \cos \theta_k \sin \phi_k \cdot \Delta t \\
z_{k+1} &= z_k + v_k \sin \theta_k \cdot \Delta t \\
\theta_{k+1} &= \theta_k + \omega_{\theta,k} \cdot \Delta t \\
\phi_{k+1} &= \phi_k + \omega_{\phi,k} \cdot \Delta t
\end{aligned}
$$
The hardware constraints on the UAV drone include limits on linear velocity and angular velocity, as well as acceleration/deceleration bounds:
$$ v_{\min} \leq v \leq v_{\max}, \quad \omega_{\min} \leq \omega \leq \omega_{\max} $$
$$ v – a_v^{\text{max}} \Delta t \leq v_{\text{next}} \leq v + a_v^{\text{max}} \Delta t $$
$$ \omega – a_\omega^{\text{max}} \Delta t \leq \omega_{\text{next}} \leq \omega + a_\omega^{\text{max}} \Delta t $$
where \( a_v^{\text{max}} \) and \( a_\omega^{\text{max}} \) are the maximum linear and angular accelerations, respectively.
The set of feasible velocities and angular velocities, denoted as \( \mathcal{V}(v,\omega) \), is used to construct candidate trajectories from the current state. For each candidate, I compute a dynamic evaluation score:
$$ \Phi(v,\omega) = \alpha \, P(v,\omega) + \beta \, Q(v,\omega) + \gamma \, V(v,\omega) $$
Here:
- \( P(v,\omega) \) measures the angular difference between the candidate trajectory’s direction and the direction of the previously planned path. It penalizes large heading changes that would require aggressive turning.
- \( Q(v,\omega) \) quantifies the distance deviation between the candidate trajectory and the original planned path. It encourages the UAV drone to stay close to the original path when possible.
- \( V(v,\omega) \) is a penalty for violating the hardware constraints (e.g., exceeding velocity limits).
- \( \alpha, \beta, \gamma \) are weighting coefficients that depend on the UAV drone‘s agility and the complexity of the environment. Typical values are \( \alpha=0.5, \beta=0.3, \gamma=0.2 \).
During replanning, the JPS algorithm first generates a set of candidate jump points in the updated grid map. Then, instead of directly outputting the global shortest path, the algorithm evaluates each candidate segment using \( \Phi \) and selects the one that minimizes the total cost while respecting the dynamic constraints. This ensures that the resulting path is not only optimal in terms of length but also feasible and safe for the UAV drone to execute in real time.
Simulation and Experimental Results
Simulation Setup
I performed simulations using a virtual forest environment built in Unreal Engine (UE) and interfaced with the Robot Operating System (ROS) to generate real-time octree occupancy grids. The simulation environment is representative of a complex outdoor scenario with trees, uneven terrain, and open spaces. The UAV drone model used in the simulation has similar dynamics to a quadrotor with a maximum speed of 10 m/s and a maximum angular rate of 90°/s. Both the traditional A* algorithm and the proposed dynamic JPS algorithm were implemented in C++ and executed on the same computer (Intel i7-8700K, 16 GB RAM). The grid resolution was set to 0.5 m, and the planning horizon was 50 m.
Figure 1 shows a screenshot of the simulation environment. (Note: The original figure is referenced as a hyperlink inserted below.)
Comparison of Path Planning Results
Table 1 summarizes the key performance metrics for three typical runs in the forest simulation. The paths generated by both algorithms are shown in Figure 2 (the grid map with planned paths).
| Algorithm | Number of Explored Nodes | Computation Time (ms) | Path Length (m) | Maximum Turning Angle (°) |
|---|---|---|---|---|
| A* | 170,562 | 135.88 | 213.46 | 45.2 |
| Proposed Dynamic JPS | 535 | 20.80 | 214.92 | 38.1 |
From Table 1, it is evident that the proposed dynamic JPS algorithm reduces the number of explored nodes by a factor of over 300 compared to A*. The computation time drops from 135.88 ms to only 20.80 ms, a reduction of 84.7%. The path length is almost identical (214.92 m vs. 213.46 m), indicating that the pruning of redundant nodes does not sacrifice path optimality. Moreover, the maximum turning angle of the dynamic JPS path is smaller (38.1° vs. 45.2°), which leads to smoother flight and less stress on the UAV drone‘s control system.
Search Node Distribution
Figure 3 illustrates the point cloud of expanded nodes for both algorithms. The A* algorithm expands a dense cloud covering almost all traversable cells, while the dynamic JPS only expands a sparse set of jump points. This drastic reduction in node expansion is the primary reason for the speedup in planning time.
Field Experiments
To validate the algorithm in real-world conditions, I conducted outdoor flight tests using a ZHY quadrotor UAV drone equipped with a Velodyne VLP-16 LiDAR, an NVIDIA TX2 onboard computer, and a Pixhawk flight controller. The UAV drone flew in a complex environment with trees, buildings, and moving pedestrians. The onboard computer processed LiDAR point clouds to build a local octree map at 10 Hz, and the dynamic JPS planner ran at 5 Hz to generate real-time paths. The flight was fully autonomous, with the UAV drone navigating from a start point to a target point approximately 60 m away.
Figure 4 shows the real flight scene and an example of the generated grid map with the planned path. The qualitative results demonstrate that the UAV drone successfully avoided static obstacles (trees and walls) and dynamically moving obstacles (a person walking across the path) without abrupt maneuvers. The average computation time for the planner was about 0.09 ms per replanning cycle, compared to 10.56 ms for an equivalent A* implementation on the same hardware.
| Algorithm | Number of Explored Nodes | Computation Time (ms) | Path Length (m) | Minimum Distance to Obstacles (m) |
|---|---|---|---|---|
| A* | 4,300 | 10.559 | 57.84 | 0.85 |
| Proposed Dynamic JPS | 70 | 0.090 | 61.07 | 1.12 |
Table 2 shows that the dynamic JPS algorithm again dramatically reduces node count and computation time. The path length is slightly longer (61.07 m vs. 57.84 m), but the minimum distance to obstacles is larger (1.12 m vs. 0.85 m), indicating improved safety margin. The slightly longer path is a result of the dynamic evaluation function that prioritizes smoother and safer trajectories over pure shortest distance.
Discussion
The proposed dynamic JPS algorithm successfully addresses the two main limitations of traditional grid-based path planning for UAV drones: computational inefficiency and lack of adaptability to dynamic environments. By pruning redundant nodes via jump points, the algorithm reduces the search space by orders of magnitude. The adaptive heuristic weighting further improves search quality by balancing exploration and exploitation. The key innovation is the integration of a dynamic evaluation function that considers the UAV drone‘s kinematic state and hardware constraints during replanning. This ensures that the output path is not only collision-free but also feasible and safe to execute in real time.
One potential limitation is that the algorithm relies on a grid-based representation of the environment, which may be memory-intensive for large-scale maps. However, the use of octree grid maps (as in our experiments) mitigates this issue by only storing cells that are occupied or unknown. Another limitation is that the weights \( \alpha, \beta, \gamma \) in the dynamic evaluation function need to be tuned for specific UAV drone platforms. In practice, a one-time calibration flight can determine reasonable values. Future work could explore adaptive tuning of these weights using reinforcement learning.
Compared to other real-time planning algorithms such as RRT* or DWA, the dynamic JPS offers the advantage of providing a globally optimal (in the discrete sense) path in a very short time, while still being able to react to local changes. The algorithm is particularly well-suited for UAV drone applications where a high-level global planner is needed to guide the vehicle through complex terrain, and a local reactive layer handles immediate obstacles.
Conclusion
In this paper, I presented a dynamic Jump Point Search algorithm for autonomous path planning of a UAV drone. The algorithm improves upon standard JPS by incorporating an adaptive heuristic weighting scheme and a dynamic evaluation function that accounts for the UAV drone‘s real-time motion state and hardware constraints. Simulation results in a forest environment show that the proposed method reduces explored nodes by over 99% and computation time by 84.7% compared to the A* algorithm, while maintaining comparable path lengths. Outdoor flight experiments on a real quadrotor UAV drone further confirm the algorithm’s efficiency and safety, with average replanning times under 0.1 ms. The dynamic JPS algorithm provides a promising solution for real-time autonomous navigation in complex unknown environments, enabling UAV drones to safely and efficiently execute missions such as surveillance, search and rescue, and delivery.
Future research directions include extending the algorithm to handle continuous cost maps (e.g., using potential fields), incorporating wind disturbances and uncertainty in sensor data, and deploying the algorithm on multi-UAV drone swarms for cooperative path planning.