I study the problem of autonomous three-dimensional path planning for a UAV drone that must fly through a dense urban environment. In my view, the core difficulty is not simply finding any collision-free route, but finding a route that is fast to compute, short in length, smooth enough for a real UAV drone controller, and robust when the environment contains many vertical obstacles, narrow corridors, and irregular building clusters. The classical Rapidly-exploring Random Tree, its asymptotically optimal variant RRT*, and the hybrid Artificial Potential Field RRT* method all provide useful foundations, but each of them leaves a practical gap for a UAV drone operating in a complex city model. I therefore formulate an improved APF-RRT* planner that uses direction-optimized dynamic sampling, artificial potential field guidance, redundant node removal, and cubic B-spline trajectory smoothing. I evaluate the method with repeated simulations and compare it against RRT, RRT*, and APF-RRT*. The results show that my improved planner reduces planning time, shortens the path, reduces the number of waypoints, and maintains a high success rate for the UAV drone.
For a UAV drone, path planning is a coupling of geometry, kinematics, and computation. The planner must respect the fixed-wing or multirotor dynamic limits of the UAV drone, including maximum turn rate, maximum acceleration, and bounded curvature. It must also avoid treating the city as a two-dimensional plane, because the vertical dimension is where many safe corridors appear. I therefore treat the problem as a three-dimensional motion planning problem over a bounded volume. The input is a start point, a goal point, a set of static obstacles, and a maximum iteration budget. The output is a sequence of waypoints that is collision-free and can be converted into a smooth reference trajectory for the UAV drone. I use the following general notation throughout my formulation.
| Symbol | Meaning |
|---|---|
| \(X_{start}\) | Initial position of the UAV drone |
| \(X_{goal}\) | Target position of the UAV drone |
| \(X_{new}\) | Newly generated tree node |
| \(X_{near}\) | Nearest existing tree node |
| \(X_{rand}\) | Random or biased sample point |
| \(T\) | Search tree maintained by the planner |
| \(O\) | Obstacle set in the urban map |
| \(step\) | Extension length of the UAV drone tree |
| \(d(X,Y)\) | Euclidean distance between two points |
| \(c(X,Y)\) | Path cost from point X to point Y |
| \(U_{att}\) | Attractive potential from the goal |
| \(U_{rep}\) | Repulsive potential from obstacles |
| \(F_{total}\) | Total artificial force felt by the UAV drone |
| \(\kappa\) | Curvature of the planned trajectory |
I begin from the standard RRT construction, because my improved APF-RRT* planner inherits its probabilistic completeness and tree-based exploration logic. In RRT, I initialize the tree with \(X_{start}\). At each iteration, I draw a sample \(X_{rand}\) from the free space, find the nearest node in the current tree, and extend a new node toward the sample by a fixed step. The nearest node is computed as
$$x_{near} = \arg\min_{x \in T} \|x – x_{rand}\|_2.$$
If the distance between \(x_{near}\) and \(x_{rand}\) is smaller than the step size, I set \(x_{new}=x_{rand}\). Otherwise, I steer from \(x_{near}\) toward \(x_{rand}\) by the step size:
$$x_{new} = x_{near} + \frac{step}{\|x_{rand}-x_{near}\|_2}(x_{rand}-x_{near}).$$
I then perform collision checking along the segment between \(x_{near}\) and \(x_{new}\). If the segment does not intersect any obstacle, I add \(x_{new}\) to the tree. The process repeats until the tree reaches the goal region or the maximum iteration count is exhausted. The goal test can be written as
$$\exists x \in T: \|x – x_{goal}\|_2 \le \epsilon,$$
where \(\epsilon\) is a small acceptance radius. This simple logic is attractive for a UAV drone because it does not require a complete grid decomposition of the city. However, I observe that RRT spends many iterations exploring directions that are not useful, and the resulting path often contains many unnecessary nodes. For a UAV drone, those extra nodes imply extra turns, extra acceleration changes, and extra energy consumption.
| Planner | Core idea | Strength | Limitation for UAV drone |
|---|---|---|---|
| RRT | Random tree expansion with nearest-node steering | Simple, fast to implement, probabilistically complete | No asymptotic optimality, many redundant nodes, slow convergence in dense 3D cities |
| RRT* | RRT plus parent selection and rewiring | Asymptotically optimal, better path quality | High computational load, uniform sampling lacks goal guidance |
| APF-RRT* | Artificial potential field combined with RRT* | Improved goal direction and smoother early paths | Local minima, oscillatory paths near concave obstacles, still slow in complex maps |
| My improved APF-RRT* | Direction-optimized sampling, APF bias, pruning, B-spline | Fast convergence, fewer nodes, smooth and controllable UAV drone path | Designed mainly for static obstacles in the current study |
RRT* improves RRT by considering the cost of connecting a new node to nearby nodes. After generating \(x_{new}\), I search a neighborhood \(N_r(x_{new})\) and choose the parent that minimizes the total cost from the start:
$$x_{parent}^* = \arg\min_{x \in N_r(x_{new})} \{ c(x_{start},x) + \|x – x_{new}\|_2 \}.$$
I then rewire the neighbors of \(x_{new}\). For each neighbor \(x\), I test whether routing through \(x_{new}\) reduces its cost:
$$c_{new}(x) = c(x_{start},x_{new}) + \|x_{new}-x\|_2.$$
If \(c_{new}(x) < c(x_{start},x)\), I replace the parent of \(x\) with \(x_{new}\). This mechanism gives RRT* asymptotic optimality, but it also increases the number of collision checks and cost evaluations. For a UAV drone in a large city map, the uniform sampling strategy still dominates the early search, and the tree often grows in directions that are irrelevant to the goal. I therefore keep the optimality-oriented structure of RRT* but change how samples are generated and how the final path is refined.
The artificial potential field method provides a natural way to bias a UAV drone toward the goal. I define the attractive potential as
$$U_{att}(X)=\frac{1}{2}k_{att}\|X-X_{goal}\|^2,$$
and the corresponding attractive force as
$$F_{att}(X)=-\nabla U_{att}(X)=k_{att}(X_{goal}-X).$$
For obstacle avoidance, I use a repulsive potential that grows as the UAV drone approaches an obstacle:
$$U_{rep}(X)=
\begin{cases}
\frac{1}{2}k_{rep}\left(\frac{1}{d(X)}-\frac{1}{d_0}\right)^2, & d(X) \le d_0,\\
0, & d(X) > d_0,
\end{cases}$$
where \(d(X)\) is the distance from the UAV drone to the nearest obstacle and \(d_0\) is the influence radius. The total potential is
$$U(X)=U_{att}(X)+U_{rep}(X),$$
and the total force is
$$F_{total}(X)=F_{att}(X)+F_{rep}(X).$$
The UAV drone moves along the negative gradient of the total potential. This idea is useful because it injects goal information into the sampling process. However, I also observe that in concave urban canyons or between two tall buildings, the attractive and repulsive forces can cancel each other. The UAV drone can then become trapped in a local minimum. My improved APF-RRT* planner uses the potential field only as a biased sampling and expansion guide, not as a standalone controller, so the tree can still escape through random exploration when the force field becomes unhelpful.
| Component | Expression | Effect on UAV drone |
|---|---|---|
| Attractive potential | \(U_{att}=\frac{1}{2}k_{att}\|X-X_{goal}\|^2\) | Pulls the UAV drone toward the goal |
| Attractive force | \(F_{att}=k_{att}(X_{goal}-X)\) | Reduces unnecessary detours |
| Repulsive potential | \(U_{rep}=\frac{1}{2}k_{rep}(1/d-1/d_0)^2\) | Pushes the UAV drone away from obstacles |
| Repulsive force | \(F_{rep}=-\nabla U_{rep}\) | Maintains safety clearance |
| Total force | \(F_{total}=F_{att}+F_{rep}\) | Biases tree expansion toward safe goal-directed regions |
The first major contribution of my method is direction-optimized dynamic sampling. Instead of drawing every sample from the entire map, I construct a local sampling space between the newest node \(X_{new}\) and the goal \(X_{goal}\). This space is divided into several regions. I discard the region that points away from the goal, because sampling there mainly creates redundant tree growth. I then assign different probabilities to the remaining regions. The region that contains the goal receives the highest probability, while the side regions receive smaller probabilities to preserve exploration. I define the sampling regions in a compact form as
$$V_1 = \{ p : x_{new,x} \le p_x \le x_{goal,x},\ y_{new,y} \le p_y \le y_{goal,y},\ 0 \le p_z \le z_{max} \},$$
$$V_2 = \{ p : x_{new,x} \le p_x \le x_{goal,x},\ y_{goal,y} \le p_y \le y_{new,y},\ 0 \le p_z \le z_{max} \},$$
$$V_3 = \{ p : x_{goal,x} \le p_x \le x_{new,x},\ y_{new,y} \le p_y \le y_{goal,y},\ 0 \le p_z \le z_{max} \},$$
$$V_4 = \{ p : x_{goal,x} \le p_x \le x_{new,x},\ y_{goal,y} \le p_y \le y_{new,y},\ 0 \le p_z \le z_{max} \}.$$
I discard \(V_4\) because it lies on the side opposite to the goal direction. The remaining regions satisfy
$$P(V_1)=f_1,\quad P(V_2)=f_2,\quad P(V_3)=f_3,\quad f_1+f_2+f_3=1.$$
Since the goal is located in \(V_2\), I set \(f_2\) as the largest probability. This simple rule increases the density of samples in the forward cone toward the goal, which accelerates the growth of the tree. I also make \(f_2\) adaptive. When the UAV drone node is far from the goal, I increase goal-directed sampling strongly. When the node is already close to the goal, I reduce the bias so that the planner can perform local adjustment and avoid overshooting. I use
$$f_2 = f_{2,min} + (f_{2,max}-f_{2,min})\exp\left(-\alpha \frac{d(X_{new},X_{goal})}{d_0}\right),$$
and then set
$$f_1=f_3=\frac{1-f_2}{2}.$$
The sample is drawn from the selected region,
$$X_{rand} \sim \mathcal{U}(V_k),\quad k \sim \mathrm{Categorical}(f_1,f_2,f_3).$$
After sampling, I apply an APF-based perturbation. If the total force is not zero, I move the sample slightly along the normalized force direction:
$$X_{rand}^{b} = X_{rand} + \eta \frac{F_{total}(X_{rand})}{\|F_{total}(X_{rand})\|+\varepsilon}.$$
I then project the biased sample back into the free space if necessary. This step makes the sample both goal-oriented and obstacle-aware. The UAV drone tree therefore grows with a stronger directional preference while still preserving the random exploration needed to escape local minima.
| Region | Position relative to goal direction | Sampling probability | Purpose for UAV drone |
|---|---|---|---|
| \(V_1\) | Forward side region | \(f_1\) | Explores lateral alternatives near the goal direction |
| \(V_2\) | Goal-containing forward region | \(f_2\), largest | Accelerates convergence toward the target |
| \(V_3\) | Forward cross region | \(f_3\) | Maintains local flexibility around obstacles |
| \(V_4\) | Backward region | Discarded | Avoids redundant sampling away from the goal |
The second contribution is the integration of APF guidance with RRT* expansion. In my implementation, I do not let the artificial force directly move the UAV drone. Instead, I use the force to update the random sample before the nearest-neighbor and steering steps. This is important because direct force control can produce oscillations and local minima. By embedding the force into the sampling distribution, I keep the probabilistic completeness of the tree while gaining the goal-directed behavior of the potential field. The expansion step becomes
$$X_{near} = \arg\min_{x \in T} \|x – X_{rand}^{b}\|_2,$$
$$X_{new} = X_{near} + \frac{step}{\|X_{rand}^{b}-X_{near}\|_2}(X_{rand}^{b}-X_{near}).$$
I then perform collision checking on the segment from \(X_{near}\) to \(X_{new}\). If the segment is free, I add \(X_{new}\) to the tree. After that, I apply the RRT* parent selection and rewiring rules. In this way, my improved APF-RRT* keeps the asymptotic optimization behavior of RRT* while reducing the number of samples that are wasted on irrelevant regions.
The third contribution is redundant node removal. Even with better sampling, the raw tree path may contain many intermediate nodes that do not improve the route. I start from the goal node and attempt to connect it directly to earlier nodes along the path. For a candidate connection between \(X_i\) and \(X_j\), I parameterize the segment as
$$L(t)=X_i+t(X_j-X_i),\quad t\in[0,1].$$
If \(L(t)\) does not intersect any obstacle for all \(t\in[0,1]\), I remove the nodes between \(X_i\) and \(X_j\). Otherwise, I keep the intermediate node and continue the backtracking process. This pruning step reduces the path length and the number of waypoints. For a UAV drone, fewer waypoints mean fewer commanded heading changes and a lower computational burden for the downstream trajectory tracker.
The fourth contribution is trajectory smoothing with cubic uniform B-spline interpolation. A pruned path can still contain sharp corners that are infeasible for a UAV drone. I therefore fit a cubic B-spline through the remaining control points. The uniform cubic B-spline segment can be written in matrix form as
$$C_i(u)=\frac{1}{6}
\begin{bmatrix}
u^3 & u^2 & u & 1
\end{bmatrix}
\begin{bmatrix}
-1 & 3 & -3 & 1\\
3 & -6 & 3 & 0\\
-3 & 0 & 3 & 0\\
1 & 4 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
P_{i-1}\\
P_i\\
P_{i+1}\\
P_{i+2}
\end{bmatrix},
\quad u\in[0,1].$$
The B-spline has local support, which means that moving one control point affects only a limited portion of the curve. This property is valuable for a UAV drone because it allows local repair near obstacles without changing the entire route. I also compute the curvature of the smoothed path,
$$\kappa(t)=\frac{\|r'(t)\times r”(t)\|}{\|r'(t)\|^3},$$
and I enforce a maximum curvature constraint,
$$|\kappa(t)| \le \kappa_{max}.$$
In addition, I consider velocity and acceleration bounds,
$$\|v(t)\| \le v_{max},\quad \|a(t)\| \le a_{max}.$$
These constraints connect the geometric path to the physical capability of the UAV drone. A path that is short but violates curvature or acceleration limits is not useful for a real UAV drone. My smoothing stage therefore improves both safety and flyability.
| Operation | Mathematical form | Benefit for UAV drone |
|---|---|---|
| Redundant node removal | \(L(t)=X_i+t(X_j-X_i)\) | Reduces waypoint count and path length |
| Collision test | \(L(t)\cap O=\emptyset,\ t\in[0,1]\) | Maintains obstacle-free flight |
| Cubic B-spline | \(C_i(u)=\frac{1}{6}[u^3,u^2,u,1]M[P_{i-1},P_i,P_{i+1},P_{i+2}]^T\) | Produces continuous curvature |
| Curvature bound | \(|\kappa(t)|\le \kappa_{max}\) | Respects UAV drone turning limits |
| Velocity bound | \(\|v(t)\|\le v_{max}\) | Keeps the trajectory within dynamic limits |
| Acceleration bound | \(\|a(t)\|\le a_{max}\) | Reduces aggressive maneuvers and energy use |
I summarize the complete logic of my improved APF-RRT* planner in a procedural table. I initialize the tree with the start node. I set the step size, maximum iterations, obstacle map, and goal threshold. At each iteration, I select the newest node and construct the dynamic sampling space. I choose a region according to the adaptive probabilities, draw a random sample, and bias it with the total artificial force. I find the nearest tree node and extend a new node. I check collision. If the segment is free, I add the node and perform RRT* parent selection and rewiring. If the new node is within the goal threshold, I stop and extract the path. I then remove redundant nodes and smooth the path with a cubic B-spline. The output is a smooth reference trajectory for the UAV drone.
| Step | Action | UAV drone relevance |
|---|---|---|
| 1 | Initialize tree with \(X_{start}\), step, max iteration, obstacle set, goal threshold | Defines the flight planning problem |
| 2 | Select newest node \(X_{new}\) and build dynamic sampling regions | Focuses exploration in useful space |
| 3 | Draw \(X_{rand}\) using adaptive probabilities | Improves goal-directed growth |
| 4 | Bias \(X_{rand}\) using \(F_{total}\) | Adds obstacle-aware guidance |
| 5 | Find \(X_{near}\) and steer to \(X_{new}\) | Expands the tree by a safe step |
| 6 | Check collision; if free, add node | Keeps the UAV drone away from obstacles |
| 7 | Apply RRT* parent selection and rewiring | Improves asymptotic path cost |
| 8 | Test goal region | Terminates when a route is available |
| 9 | Remove redundant nodes | Reduces waypoint count |
| 10 | Fit cubic B-spline and check curvature limits | Produces a flyable UAV drone trajectory |
I now describe my simulation setup. I used a three-dimensional urban map of size \(500 \times 500 \times 500\). The start point was \((10,10,5)\), and the goal point was \((450,450,50)\). The initial step size was \(5\). I generated obstacle locations randomly and placed them in two map categories. The simple map contained 50 obstacles, while the complex map contained 115 obstacles. The complex map represents a denser urban environment with more constrained corridors and more opportunities for local minima. I set the maximum iteration count to 5000 for each run. I conducted repeated trials and recorded the mean values of the evaluation metrics.
| Parameter | Value |
|---|---|
| Map size | \(500 \times 500 \times 500\) |
| Start point | \((10,10,5)\) |
| Goal point | \((450,450,50)\) |
| Initial step size | \(5\) |
| Maximum iterations | \(5000\) |
| Simple map obstacles | \(50\) |
| Complex map obstacles | \(115\) |
| Evaluation metrics | Planning time, path length, waypoint count, success rate, iteration count |
I evaluate the planners with five metrics. The first is search time, which measures how long the planner takes to produce a valid path. The second is path length, which measures the geometric cost of the route. The third is path point count, which measures the topological complexity of the route. The fourth is success rate, which measures the percentage of trials that reach the goal. The fifth is iteration count, which measures how many expansion steps are needed. For each metric, I compute the mean over repeated runs:
$$\bar{M}=\frac{1}{N}\sum_{i=1}^{N}M_i.$$
The success rate is
$$SR=\frac{N_{success}}{N_{total}}\times 100\%.$$
To compare my improved APF-RRT* with a baseline, I use the relative improvement
$$\Delta M=\frac{M_{base}-M_{new}}{M_{base}}\times 100\%.$$
A positive \(\Delta M\) means that my method reduces the metric. I also examine path smoothness qualitatively and through curvature reasoning. For a UAV drone, a lower path point count is not automatically better if the path is jagged. I therefore consider the combination of fewer waypoints, shorter length, and B-spline smoothing as the practical indicator of trajectory quality.
| Metric | Definition | Desired direction |
|---|---|---|
| Search time | Time to find a valid path | Lower |
| Path length | Sum of segment lengths | Lower |
| Path point count | Number of waypoints before smoothing | Lower |
| Success rate | Percentage of successful trials | Higher |
| Iteration count | Number of tree expansion iterations | Lower |
In the simple map, I compared RRT, RRT*, APF-RRT*, and my improved APF-RRT*. The simple map still contains three-dimensional obstacles, but the free space is more generous than in the complex map. Even in this setting, I observed that RRT and RRT* produce many waypoints and require more iterations. APF-RRT* improves the goal direction and reduces the path point count, but it still takes more time than my method. My improved planner reaches the goal with the shortest mean path and the smallest number of path points. The success rate remains 100% for all compared methods in the simple map, which indicates that the map is not so restrictive that the baseline methods fail. The advantage of my method is therefore primarily efficiency and path compactness.
| Algorithm | Search time / s | Path length / mm | Path points | Success rate / % | Iterations |
|---|---|---|---|---|---|
| RRT | 0.253 | 782.77 | 75 | 100 | 3026 |
| RRT* | 0.272 | 713.21 | 73 | 100 | 2925 |
| APF-RRT* | 0.207 | 669.48 | 43 | 100 | 2421 |
| My improved APF-RRT* | 0.124 | 619.24 | 15 | 100 | 1236 |
The simple map results already show the benefit of direction-optimized sampling. My planner reduces the iteration count to 1236, which is less than half of the APF-RRT* iteration count. This reduction is important for a UAV drone because fewer iterations mean less computation and faster onboard response. The path point count drops to 15, which means that the smoothed trajectory can be represented with a small number of control points. A smaller number of control points makes trajectory tracking easier for the UAV drone autopilot and reduces the chance of aggressive heading changes.
In the complex map, the difference becomes more pronounced. The complex map contains 115 obstacles, which creates narrow passages and many concave regions. RRT and RRT* both achieve a 90% success rate, which means that they occasionally fail to find a path within the iteration limit. APF-RRT* achieves 100% success but still has a relatively high search time and a large number of path points. My improved APF-RRT* achieves 100% success and reduces the search time to 0.131 s, the path length to 627.44 mm, and the path point count to 16. The iteration count also drops to 1474. These results indicate that the dynamic sampling strategy helps the UAV drone tree focus on the forward corridor while the APF bias helps it avoid dangerous regions.
| Algorithm | Search time / s | Path length / mm | Path points | Success rate / % | Iterations |
|---|---|---|---|---|---|
| RRT | 0.245 | 800.59 | 79 | 90 | 3326 |
| RRT* | 0.286 | 721.39 | 77 | 90 | 3125 |
| APF-RRT* | 0.214 | 693.46 | 46 | 100 | 2644 |
| My improved APF-RRT* | 0.131 | 627.44 | 16 | 100 | 1474 |
I next compute the relative improvements for the complex map. Compared with RRT, my method reduces search time by about 46.53%, path length by about 21.62%, path points by about 79.74%, and iterations by about 55.68%. Compared with RRT*, my method reduces search time by about 54.20%, path length by about 13.02%, path points by about 79.22%, and iterations by about 52.83%. Compared with APF-RRT*, my method reduces search time by about 38.78%, path length by about 9.52%, path points by about 65.21%, and iterations by about 44.25%. These improvements show that the combination of direction-optimized sampling, artificial potential field guidance, redundant node removal, and cubic B-spline smoothing produces a practical gain for the UAV drone.
| Baseline | Search time reduction | Path length reduction | Path point reduction | Iteration reduction |
|---|---|---|---|---|
| RRT | 46.53% | 21.62% | 79.74% | 55.68% |
| RRT* | 54.20% | 13.02% | 79.22% | 52.83% |
| APF-RRT* | 38.78% | 9.52% | 65.21% | 44.25% |
I also compare the simple and complex maps for my method. In the simple map, my planner takes 0.124 s, produces a path of 619.24 mm, uses 15 path points, and needs 1236 iterations. In the complex map, my planner takes 0.131 s, produces a path of 627.44 mm, uses 16 path points, and needs 1474 iterations. The small increase in time and path length shows that my method degrades gracefully as the environment becomes denser. This is important for a UAV drone because urban airspace can change from open corridors to dense building clusters within a short distance. A planner that becomes unstable or extremely slow in dense regions is not suitable for practical UAV drone missions.
| Map | Search time / s | Path length / mm | Path points | Iterations |
|---|---|---|---|---|
| Simple map | 0.124 | 619.24 | 15 | 1236 |
| Complex map | 0.131 | 627.44 | 16 | 1474 |
The path smoothing result is a key part of my contribution. A raw RRT path is a polyline. Even if it is collision-free, it can contain sharp turns that are not feasible for a UAV drone. The cubic B-spline converts the polyline into a continuous curve with continuous first and second derivatives. This means that the heading angle and curvature change smoothly along the trajectory. For a UAV drone, smooth curvature reduces the need for sudden roll or yaw commands. It also reduces the risk of overshoot when the UAV drone follows the reference path. I use the B-spline control points as a compact representation of the flight corridor, and I check that the smoothed curve remains outside the obstacle set.
I define the smoothness energy of a trajectory as
$$E_s=\int_{0}^{T}\|r”(t)\|^2\,dt.$$
A lower smoothness energy means that the path bends more gently. I do not claim that smoothness alone guarantees safety, because a very smooth curve can still collide with an obstacle. Therefore, I combine the smoothness term with a collision penalty and a length term in my design objective:
$$J=w_1 L + w_2 E_s + w_3 N_{collision} + w_4 T_{plan}.$$
Here \(L\) is path length, \(E_s\) is smoothness energy, \(N_{collision}\) is the number of collision violations, and \(T_{plan}\) is planning time. The weights \(w_1,w_2,w_3,w_4\) allow me to balance competing goals. In my experiments, I keep collision avoidance as a hard constraint, so \(N_{collision}\) must be zero for the final path. The other terms guide the selection among feasible paths. This cost structure is useful for a UAV drone because it reflects the practical trade-off between energy, time, and safety.
| Indicator | Expression | Why it matters |
|---|---|---|
| Path length | \(L=\sum_{i=1}^{n-1}\|p_{i+1}-p_i\|\) | Affects energy and mission time |
| Smoothness energy | \(E_s=\int \|r”(t)\|^2dt\) | Reduces aggressive maneuvers |
| Curvature | \(\kappa=\|r’\times r”\|/\|r’\|^3\) | Must remain below UAV drone limit |
| Waypoint count | \(N_p\) | Affects tracking and communication load |
| Planning time | \(T_{plan}\) | Affects real-time autonomy |
I observe that my method is especially effective in the complex map because the dynamic sampling space prevents the tree from expanding backward. In standard RRT and RRT*, many samples are drawn behind the current growth front. Those samples can occasionally help with exploration, but in a dense city they mostly increase the iteration count. By discarding the backward region and assigning a high probability to the goal-containing region, I reduce wasted computation. The APF bias further improves the sample quality by pushing samples away from obstacles. The RRT* rewiring then improves the path cost among the nodes that are actually useful. The pruning step removes the remaining unnecessary nodes, and the B-spline step makes the final trajectory flyable.
The local minimum problem is a well-known weakness of artificial potential field methods. In my approach, the potential field is not the sole decision maker. The tree still contains random samples, and the direction-optimized sampling includes side regions \(V_1\) and \(V_3\). If the UAV drone node enters a concave obstacle region and the total force becomes nearly zero, the random component can still generate a sample that moves the tree out of the trap. The RRT* rewiring can also reconnect the tree through a different branch. This hybrid behavior is why I prefer APF-RRT* as the base and then improve its sampling distribution rather than replacing it with a pure potential field controller.
I also consider the computational cost of neighborhood search in RRT*. For each new node, I search nearby nodes within a radius \(r\). The number of neighbors depends on the local node density. In a dense city map, a large radius increases the number of cost evaluations. I keep the neighborhood radius moderate and rely on the improved sampling to reduce the total number of nodes. Since my method needs fewer iterations and fewer path points, the downstream cost of trajectory optimization is also reduced. This is important for a UAV drone with limited onboard computation. A planner that finds a path quickly but then requires a heavy post-processing step may not be suitable for real-time flight. My method integrates pruning and smoothing in a way that keeps the final representation compact.
I evaluate the success rate as a reliability measure. In the complex map, RRT and RRT* both achieve 90% success, while APF-RRT* and my method achieve 100% success. The improvement from 90% to 100% is important for a UAV drone because a failed planning attempt can force a replanning cycle, which increases latency and may endanger the mission. My method maintains the high success rate while reducing time and path length. In other words, the improvement in efficiency does not come at the cost of reliability in the tested scenarios.
| Algorithm | Success rate / % | Search time / s | Path points | Overall observation |
|---|---|---|---|---|
| RRT | 90 | 0.245 | 79 | Fast but unreliable and redundant |
| RRT* | 90 | 0.286 | 77 | Better cost but high computation |
| APF-RRT* | 100 | 0.214 | 46 | Reliable but still has many waypoints |
| My improved APF-RRT* | 100 | 0.131 | 16 | Fast, reliable, and compact |
The experimental trends are consistent with my design intent. Direction-optimized sampling reduces the search space. APF guidance improves the quality of samples near obstacles. RRT* parent selection and rewiring preserve path cost optimization. Redundant node removal reduces the number of waypoints. Cubic B-spline smoothing improves curvature continuity. Each component addresses a specific weakness of the baseline UAV drone planners. The combination is greater than the sum of the parts because the sampling improvement reduces the number of nodes that the RRT* rewiring stage must process, and the pruning stage reduces the number of control points that the B-spline stage must smooth.
I now discuss the limitations of my current study. I focus on static obstacles. A real urban environment may contain dynamic obstacles such as other UAV drones, birds, temporary cranes, or moving vehicles. My current planner does not explicitly model time-varying obstacle motion. In a dynamic environment, the UAV drone must predict or react to moving objects, and the planner must support frequent replanning. I also do not fully address multi-UAV drone coordination. When several UAV drones share the same airspace, path planning becomes a coupled problem with deconfliction constraints. My current method plans for a single UAV drone. These limitations define clear directions for future work.
| Current scope | Limitation | Future extension |
|---|---|---|
| Static obstacle map | No moving obstacle prediction | Dynamic APF and rolling-horizon replanning |
| Single UAV drone | No inter-UAV deconfliction | Multi-UAV drone cooperative planning |
| Offline simulation | Limited onboard validation | Embedded implementation and sensor fusion |
| Geometric cost | Limited energy model | Wind-aware and battery-aware cost functions |
| Fixed obstacle set | No uncertainty model | Probabilistic obstacle maps and robust planning |
For future work, I plan to extend the dynamic sampling space to include time as a fourth dimension. In that formulation, the UAV drone path becomes \(X(t)=(x(t),y(t),z(t))\), and the obstacle set becomes \(O(t)\). The collision test becomes
$$X(t)\notin O(t),\quad \forall t\in[0,T].$$
I also plan to include a replanning trigger based on sensor updates. When a new obstacle is detected, I can reuse the existing tree and rewire only the affected branches. This incremental repair is more efficient than planning from scratch. For multi-UAV drone coordination, I can add a separation constraint between UAV drone \(i\) and UAV drone \(j\):
$$\|X_i(t)-X_j(t)\|_2 \ge d_{safe},\quad \forall t.$$
This constraint can be incorporated into the sampling and pruning stages. The B-spline representation is convenient for this extension because it provides a compact and differentiable trajectory that can be checked at discrete time samples. I can also add energy terms that depend on wind, payload, and battery state. Such terms would make the planner more relevant to long-endurance UAV drone missions.
In my view, the most important lesson from this study is that path planning for a UAV drone should not be judged only by whether a path exists. The planner should produce a path that is fast to compute, short enough for the mission, smooth enough for the controller, and reliable enough for repeated operation. My improved APF-RRT* addresses these requirements by combining goal-directed sampling with obstacle-aware potential fields and then refining the result with pruning and B-spline smoothing. The experimental results support this claim. In the complex map, my method reduces search time by 38.78%, path length by 9.52%, and path point count by 65.21% compared with APF-RRT*, while maintaining a 100% success rate. The iteration count is also substantially lower, which means that the UAV drone can spend less computation on tree expansion and more computation on tracking, perception, and safety monitoring.
I also note that the improvement in path point count is particularly valuable. A path with 16 points is much easier to store, transmit, and track than a path with 46 or 79 points. For a UAV drone, a compact waypoint list reduces the communication load between the ground station and the vehicle. It also simplifies the trajectory generation step because the B-spline can be computed from a small set of control points. The smoothed curve can then be sampled at the controller rate. This layered structure, from tree planning to pruning to spline smoothing, is practical for real UAV drone autonomy.
My method inherits the probabilistic completeness of RRT because it still samples the free space. It inherits the asymptotic optimality tendency of RRT* because it still performs parent selection and rewiring. It gains goal direction from APF because the sample is biased by the artificial force. It gains computational efficiency from direction-optimized sampling because the backward region is discarded and the goal region is emphasized. It gains trajectory quality from pruning and B-spline smoothing because the final path has fewer redundant nodes and continuous curvature. These properties are complementary. The combination explains why the improved APF-RRT* planner performs well across the tested maps.
| Component | Main effect | Metric influenced |
|---|---|---|
| Direction-optimized sampling | Focuses samples toward the goal | Search time, iterations |
| Adaptive region probabilities | Balances exploration and exploitation | Success rate, convergence |
| Artificial potential field bias | Improves obstacle-aware sample quality | Path length, safety |
| RRT* parent selection and rewiring | Optimizes path cost among tree nodes | Path length |
| Redundant node removal | Simplifies the path topology | Path point count |
| Cubic B-spline smoothing | Ensures curvature continuity | Flyability, smoothness |
I conclude that the improved APF-RRT* planner is a feasible and efficient solution for UAV drone path planning in three-dimensional urban environments. It improves convergence speed, reduces path redundancy, and produces smoother trajectories while preserving a high success rate. The method is especially suitable for scenarios in which a UAV drone must navigate between buildings with limited onboard computation. Although dynamic obstacles and multi-UAV drone coordination remain open problems, the static planning framework developed here provides a strong foundation for further extension. I will continue to refine the dynamic sampling probabilities, incorporate sensor-based replanning, and test the method on embedded hardware. In my future work, I aim to make the UAV drone planner more adaptive, more robust, and more directly connected to real flight constraints.