Skip to content

RRT-Star

Rapidly Exploring Random Tree* (RRT*, RRT-Star) is the backbone behind much of the forward-flight pathing algorithm.

Here are some literature:

In brief, the algorithm

  1. randomly samples points in a valid space
  2. attempts to connect towards those points from pre-existing paths (stored in a tree like structure)
    • It will also have a bias that samples the goal directly.
  3. repeats until one path terminates "near" the goal (returns valid path)

The '*' part of RRT* is an evolution on the algorithm that simply rewires the tree - after every new sample (step 2) - to guarantee the tree stores the optimal path between any two points.

Dubins' Pathing

Since a fixed wing plane typically cant move in a straight line between two points, we utilize Dubins' Curves to connect between to waypoints. This has some quirks:

  • Fixed Turning Radius: The plane never makes a shallow turn, instead opting for the tightest turns and straight lines.
  • Loops galore: The algorithm may do unnecessary loops between two points where there can be a direct path with a small angle adjustment.
    1. In practice, we've found that just running the algorithm for longer dramatically smooths out the pathing, so this isn't a big issue

Engineering Decisions

Altitude (Lack)

The algorithm is done in 2D (reduces complexity/sparseness) since flight bounds are functionally 2D. Altitude, however, is part of the competition and waypoints must be hit at specific altitudes - although for 2024, it was static and only there to prevent collision during waypoint missions.

To include altitude, we interpolate altitude gain/loss between waypoints, after the path has been finalized.

Direct Connect

Since there are no obstacles nor sharp corners, the waypoints may often be connected without running RRT*. We try to connect the starting the point to the end point directly before trying RRT*.

Dubins

The distances that the plane travels between waypoints is rarely ever within the bounds for LRL and RLR, so we don't bother calculating them, reducing the cases for Dubins' from 6 to 4.

Epoch Evaluation

With the same reasoning as Direct Connect, building an entire tree isn't computationally efficient, so after a partial tree is built, we try to connect to the goal from that tree. This is done periodically, and the path length is recorded at each evaluation.

If progress (minimization of path length) has slowed/stopped, then RRT* is terminated prematurely, saving the path at the last epoch.

Naive Point Generation

Every time a point is sampled, it is from a uniform distribution over the whole valid flight region. Points that are sampled near the tree may give drastically different information depending on the direction (pointing towards wall vs away from corner).

Heuristic

I've wanted to make a heuristic that could make point generation more efficient but never figured out something that works very well - if you have any ideas, go ahead and try to implement it! To test, you could try to measure how quickly RRT* converges to a smooth solution in a variety of scenarios (small gap, lots of corners, etc).

RRT* Radius

An optimal solution is not necessary, so smoothing is only needed if large gains are evolved. The current heuristic used is: rewiring will only be meaningful for points close to the sample, so rewiring isn't performed on nodes beyond a certain distance from the sample.

RRT* might not be that computationally effective (for smoothing) compared to running RRT more times - but I've never rigorously tested the differences

Note: most of the pathing/RRT was authored by Christopher Lee, so feel free to ask me any questions - or simply improve/refactor the algorithm.