UAV Path Planning: RRT* & Potential Fields

Two families of planner, one job

Getting a drone from A to B through obstacles is the motion planning problem, and almost every solution belongs to one of two families. Sampling-based planners build a discrete graph of feasible states by randomly sampling the free space and connecting nearby samples; reactive planners compute a force or gradient at the drone's current position and follow it, one instant at a time, with no map of the whole space. RRT* is the workhorse of the first family, artificial potential fields the classic instance of the second, and this simulation runs both on the same 3D obstacle field so you can watch the trade-off directly.

RRT*: growing a tree toward the goal

Rapidly-exploring Random Trees (RRT, LaValle 1998) build a tree rooted at the start pose. Each iteration samples a random point in the 3D volume, finds the nearest existing tree node, and extends a fixed-length step from that node toward the sample. If the new edge is collision-free it joins the tree. Repeat for a few thousand iterations and the tree's leaves are, with high probability, dense enough that one of them is close to the goal.

loop:
  x_rand  = sample_free_space()
  x_near  = nearest(tree, x_rand)
  x_new   = steer(x_near, x_rand, step)      // move one fixed step toward x_rand
  if collision_free(x_near, x_new):
    tree.add(x_new, parent = x_near)
    if in_goal_region(x_new): done

Plain RRT finds a path fast, but it is rarely a good one — it zig-zags because it never revisits a decision. RRT* (Karaman & Frazzoli, 2011) fixes this with two extra steps at every iteration: when a new node is added, it looks at all tree nodes within a shrinking radius and (1) picks the parent among them that gives the cheapest path from the root, then (2) rewires any of those nearby nodes through the new node if that lowers their own cost. This local re-optimisation, repeated over thousands of samples, provably converges to the shortest collision-free path as the sample count grows — RRT* is asymptotically optimal, plain RRT is not.

The cost is more bookkeeping per iteration (a nearest-neighbour and a radius query instead of one), which is why practical implementations keep tree nodes in a k-d tree rather than a flat array — without it, each of those queries degrades to O(n) and the whole planner becomes O(n squared) over a run.

Potential fields: no planning, just gradient descent

Artificial potential fields (Khatib, 1986) skip the graph entirely. The goal exerts an attractive potential that pulls the drone toward it like a valley; every obstacle exerts a repulsive potential that pushes the drone away, strong up close and vanishing beyond a safety radius. At every instant the drone simply flies down the combined gradient — no tree, no memory of the space, negligible compute per step, which is why it is the default choice for a real quadrotor's fast inner control loop reacting to a lidar it just read.

F_total(x) = -grad(U_attract(x)) - sum_i grad(U_repel_i(x))
U_attract(x) = 0.5 * k_att * ||x - x_goal||^2
U_repel(x)   = 0.5 * k_rep * (1/d(x) - 1/d0)^2   if d(x) < d0, else 0

The catch is the reason this demo pairs the two methods: a purely reactive controller has no lookahead, so it can be trapped in a local minimum — a point where the attractive pull toward the goal is exactly cancelled by the repulsive push of a concave obstacle, such as the inside of a U-shaped wall. The drone sits there, net force zero, goal unreached, no matter how long you wait. Sampling-based planners do not have this failure mode because they explore the whole space rather than descending a single scalar field; the price is that RRT* needs a global map up front and takes measurably longer to produce a path.

What real UAV stacks actually do

Production autonomy stacks rarely pick one and discard the other. A common architecture runs a sampling-based or search-based global planner (RRT*, or a lattice/A* variant) at a low rate over the known map to produce a coarse waypoint corridor, and a fast reactive layer — potential fields, or its smoother cousin velocity obstacles — for local, high-rate collision avoidance against obstacles the global map does not yet know about. The global planner supplies the lookahead that escapes local minima; the reactive layer supplies the millisecond reaction time a moving obstacle or a global replanning cycle cannot.

The other practical detail is kinodynamic feasibility: a quadrotor cannot instantaneously change velocity or turn on a dime, so a raw RRT* path built from straight-line steers must be smoothed and re-parametrised against the vehicle's actual acceleration limits (typically with a minimum-snap or minimum-jerk trajectory fit) before it is flyable. A geometrically shortest path is not the same as a flyable one.

Frequently asked questions

Try it live

Everything above runs in your browser — open UAV Path Planning and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.