Autonomous Systems ★★★★☆ Advanced

🛰️ UAV Path Planning: RRT* & Potential Fields

Plan a collision-free 3D flight path for a drone through boxes, spheres and a no-fly zone. Grow a real RRT* search tree — sampling, nearest-neighbour connection, collision checking and rewiring for asymptotic optimality — or switch to reactive potential-field steering and watch it get trapped in a concave obstacle's local minimum.

Click and drag to orbit · Scroll to zoom

6
1.1
3000
Algorithm
RRT*
Status
Searching…
Nodes explored
0
Path length
—
Iterations
0
Drones
1

RRT* — Rapidly-Exploring Random Tree (star variant)

RRT* incrementally builds a tree from the start: sample a random point, steer from the nearest tree node toward it by one step, and add it if the segment is collision-free. Unlike plain RRT, RRT* also rewires nearby nodes through the new node whenever that lowers their cost-to-come, which makes the extracted path converge toward the shortest collision-free path as sampling continues — a property called asymptotic optimality.

RRT* vs. Potential Fields

RRT* (global, sampling-based) — Explores the whole free space by growing a randomized tree and rewiring it, so it is complete (will find a path if one exists, given enough samples) and asymptotically optimal (the path cost keeps improving toward the true minimum). It has no notion of "getting stuck" — a concave obstacle just costs more tree growth, not failure.

Potential fields (local, reactive) — Sums an attractive pull toward the goal with repulsive pushes away from nearby obstacles into one steering force, computed fresh every frame. It is cheap and reactive to moving obstacles, but it is a purely local method: around a concave "trap" obstacle the attractive and repulsive forces can cancel to zero before the goal is reached, stalling the drone in a local minimum it cannot escape without extra logic (random walks, wall-following, or switching to a global planner like RRT*).

🛰️ UAV Path Planning

About this simulation

Real drones need a collision-free flight path through obstacles and no-fly zones before they take off, or a reactive steering law to fly safely without a full map. This simulation runs both approaches for real, in 3D: a sampling-based global planner (RRT*) that grows and rewires a tree, and a reactive local controller (artificial potential fields) that steers the drone frame by frame.

How it works

Key equations

F_att = k_att · (goal − pos) and F_rep = k_rep · (1/d − 1/d0) · (1/d²) · n̂ for each obstacle within influence radius d0 (Khatib, 1986); the drone moves along F = F_att + Σ F_rep. RRT* rewires when cost(x_near via x_new) < cost(x_near).

Controls

Did you know?

RRT* was introduced by Karaman and Frazzoli in 2011 as an optimal extension of Steven LaValle's 1998 RRT algorithm. Real drone autopilots often combine both ideas: a global planner like RRT* or A* lays out waypoints offline, while a fast reactive layer resembling potential fields handles last-moment dodging of obstacles the map did not know about.