RRT path planning explained

How a rapidly exploring random tree (RRT) finds a path: sample a point, extend the nearest node towards it, check for collisions, repeat. Watch the tree grow round obstacles, see what the step size and goal bias change, why the route is not the shortest, and how it compares with A*.

Guidefree, runs in your browser

A rapidly exploring random tree (RRT) finds a route through a space full of obstacles by trying random points. It grows a tree from the start: pick a random point, find the point of the tree nearest to it, take one short step from there towards it, and keep that step if it does not hit anything. When the tree reaches the goal, the route is the way back through the tree. Steven LaValle published it in 1998. RRT and the planners built on it are widely used to plan the movements of robot arms, and for drones and self-driving vehicles, where the space is too big to cut into a grid. On this page a small robot plans a route across a 2 metre mat with two walls in the way, the same mat as the A* guide, and each demo below is a real program you can change and run.

On the mat, the blue lines are the tree, the yellow dot is the random point that grew the newest branch, and the red line is the route the planner found through the tree. The chart shows how close the tree has come to the goal: the straight-line distance, in cm, from the green corner to the nearest point of the tree. It reaches zero when the tree touches the goal.

The idea in one loop

start the tree with one node: the start
repeat:
    1. sample: pick a random point (now and then, the goal)
    2. nearest: find the node of the tree closest to it
    3. steer: step a fixed distance from that node towards it
    4. check: if the step hits nothing, add the new node
    5. stop when a new node can reach the goal in one clear step
walk back from the goal to the start, parent by parent

Each point in the tree is a node, and each node remembers the node it grew from, its parent. Every node except the start has exactly one parent, so there is exactly one way back from any node to the start. That walk back, turned round, is the route.

There are three things to choose:

• the step size: how far each new branch reaches;
• the goal bias: how often the planner samples the goal itself instead of a random point;
• how finely to check each branch for collisions.

The sections below take them one at a time.

Configuration space: make the robot a point

An RRT asks "is this spot free?" hundreds or thousands of times, so the question has to be quick. The robot is not a point: it is a 7 cm square, and working out whether the whole body fits somewhere is slow and fiddly. So the planner does that work once, before it starts. It grows every wall outwards by the robot's size plus a margin, and from then on it treats the robot as a single point. In the grown world, "does the robot fit here?" becomes "is this point outside every grown wall?", which is a few comparisons per wall.

The grown world is the configuration space, or C-space. A configuration is the set of numbers that says exactly where the robot is. The BugBot can slide in any direction, and the circle that holds its square body at every angle has a radius of 4.95 cm. If the walls are grown by at least that much, the robot's heading does not matter, and a configuration is just (x, y). The demos grow the walls and the edge of the mat by 10 cm, which leaves room for the robot not driving the plan exactly. The 8 cm walls become 28 cm thick, and the corridor between them is 27 cm wide.

For a robot arm with six joints, a configuration is six angles, and the configuration space has six dimensions. The planner works the same way there: pick six random angles, step towards them, and check whether the arm would hit anything on the way.

Why random points

A grid planner such as A* cuts the space into cells and searches them. On this mat that is 1,600 cells (40 by 40, at 5 cm), and A* is quick. But the number of cells multiplies with every dimension you add. Add the robot's heading, at 5 degrees, and there are 115,200 cells. A six-jointed arm at 5 degrees per joint has 72 to the power 6, about 139 billion.

An RRT never builds the grid. It needs only a test that says whether a point, or a short straight line, is free, and it spends those tests where the tree is growing. That is why it still works in spaces with many dimensions, where a grid could not even be stored.

RRT round two walls

The robot is at the bottom left and the goal is the green corner at the top right. The first wall blocks the way up the middle and the second blocks the way along the top, so every route has to go up, over the first wall, down the corridor between them, under the second, and up again.

from bugbot import *
import math
import random
connect()

# change these numbers and press Run
STEP = 12        # how far each new branch reaches, cm
BIAS = 0.1       # how often to aim at the goal itself
SEED = 4         # another number grows another tree
CHECK = True     # False: test only the new point
random.seed(SEED)

START = (30, 30)         # the robot
GOAL = (170, 170)        # the green corner
GROW = 10                # grow the walls by 10 cm
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]

def free(p):
    # is a point robot at p clear of the grown walls?
    x, y = p
    if not (GROW < x < 200 - GROW and GROW < y < 200 - GROW):
        return False
    for wx, wy, ww, wh in WALLS:
        if (wx - GROW < x < wx + ww + GROW and
                wy - GROW < y < wy + wh + GROW):
            return False
    return True

def clear(a, b):
    # is the whole branch from a to b clear?
    # test a point every 1.5 cm along it
    if not CHECK:
        return free(b)
    n = max(2, int(math.dist(a, b) / 1.5))
    for k in range(n + 1):
        t = k / n
        if not free((a[0] + (b[0] - a[0]) * t,
                     a[1] + (b[1] - a[1]) * t)):
            return False
    return True

def show(sample):
    # draw the tree as one line that runs out
    # along every branch and back again
    kids = [[] for n in nodes]
    for k in range(1, len(nodes)):
        kids[parent[k]].append(k)
    line = []
    def walk(k):
        line.append(nodes[k])
        for c in kids[k]:
            walk(c)
            line.append(nodes[k])
    walk(0)
    draw("tree", line[:2000], "blue", "line", 1)
    draw("sample", [sample], "yellow", "dots", 4)
    plot("cm to the goal",
         min(math.dist(n, GOAL) for n in nodes))
    wait(0.25)

nodes = [START]      # the tree: its points,
parent = [None]      # and the node each grew from
samples, found, due = 0, False, 1
while samples < 3000 and not found:
    samples += 1
    # 1. sample: a random point, now and then the goal
    if random.random() < BIAS:
        s = GOAL
    else:
        s = (random.uniform(0, 200), random.uniform(0, 200))
    # 2. find the node nearest to it
    near = min(range(len(nodes)),
               key=lambda k: math.dist(nodes[k], s))
    n = nodes[near]
    d = math.dist(n, s)
    if d < 0.001:
        continue
    # 3. steer: one step from that node towards it
    r = min(STEP, d)
    new = (n[0] + (s[0] - n[0]) / d * r,
           n[1] + (s[1] - n[1]) / d * r)
    # 4. keep the new node only if the branch is clear
    if not clear(n, new):
        continue
    nodes.append(new)
    parent.append(near)
    # 5. stop when the goal is one clear step away
    if math.dist(new, GOAL) <= STEP and clear(new, GOAL):
        nodes.append(GOAL)
        parent.append(len(nodes) - 2)
        found = True
    if len(nodes) >= due:
        show(s)
        due = len(nodes) + 5 + len(nodes) // 20
show(nodes[-1])

if found:
    # walk back from the goal, parent by parent
    route = []
    k = len(nodes) - 1
    while k is not None:
        route.append(nodes[k])
        k = parent[k]
    route.reverse()
    draw("route", route, "red", "line", 2)
    length = sum(math.dist(a, b)
                 for a, b in zip(route, route[1:]))
    print("samples:", samples)
    print("nodes:", len(nodes))
    print("path:", round(length), "cm")
else:
    print("no route after", samples, "samples")

By its 50th node the tree has reached the corridor between the walls, and the chart has dropped to 58 cm: that node is close to the goal in a straight line, but the second wall is in the way. The chart then stays flat for the next hundred or so nodes while the tree fills the bottom left, the top left and the corridor, none of which gets it any closer in a straight line. Then a branch comes out under the second wall and climbs to the corner. Of the 360 samples, 173 grew a branch. The other 187 were thrown away, because the branch would have hit a grown wall.

The tree depends on the numbers random hands out. Change SEED and you get a different tree and a different route. random.seed makes a run repeat exactly, which is what you want while you are testing a program.

Why the tree spreads out

The nearest-node rule is what makes the tree explore. Picture each node owning the patch of mat that is closer to it than to any other node. A random sample lands in a patch with a chance in proportion to the patch's area, and the node that owns it is the one that grows. Nodes deep inside the tree own small patches, crowded in by their neighbours. Nodes on the edge of the tree own the big empty spaces beyond it. So the edge grows most, and the tree is pulled out into the space it has not visited yet, without being told to. The patches are called Voronoi regions, and this pull is where the name comes from: rapidly exploring.

Goal bias

With BIAS = 0.1, one sample in ten is the goal itself. That makes the node nearest the goal take one step straight towards it. Here is the planner with no bias at all.

from bugbot import *
import math
import random
connect()

# change these numbers and press Run
STEP = 12        # how far each new branch reaches, cm
BIAS = 0         # how often to aim at the goal itself
SEED = 10        # another number grows another tree
CHECK = True     # False: test only the new point
random.seed(SEED)

START = (30, 30)         # the robot
GOAL = (170, 170)        # the green corner
GROW = 10                # grow the walls by 10 cm
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]

def free(p):
    # is a point robot at p clear of the grown walls?
    x, y = p
    if not (GROW < x < 200 - GROW and GROW < y < 200 - GROW):
        return False
    for wx, wy, ww, wh in WALLS:
        if (wx - GROW < x < wx + ww + GROW and
                wy - GROW < y < wy + wh + GROW):
            return False
    return True

def clear(a, b):
    # is the whole branch from a to b clear?
    # test a point every 1.5 cm along it
    if not CHECK:
        return free(b)
    n = max(2, int(math.dist(a, b) / 1.5))
    for k in range(n + 1):
        t = k / n
        if not free((a[0] + (b[0] - a[0]) * t,
                     a[1] + (b[1] - a[1]) * t)):
            return False
    return True

def show(sample):
    # draw the tree as one line that runs out
    # along every branch and back again
    kids = [[] for n in nodes]
    for k in range(1, len(nodes)):
        kids[parent[k]].append(k)
    line = []
    def walk(k):
        line.append(nodes[k])
        for c in kids[k]:
            walk(c)
            line.append(nodes[k])
    walk(0)
    draw("tree", line[:2000], "blue", "line", 1)
    draw("sample", [sample], "yellow", "dots", 4)
    plot("cm to the goal",
         min(math.dist(n, GOAL) for n in nodes))
    wait(0.25)

nodes = [START]      # the tree: its points,
parent = [None]      # and the node each grew from
samples, found, due = 0, False, 1
while samples < 3000 and not found:
    samples += 1
    # 1. sample: a random point, now and then the goal
    if random.random() < BIAS:
        s = GOAL
    else:
        s = (random.uniform(0, 200), random.uniform(0, 200))
    # 2. find the node nearest to it
    near = min(range(len(nodes)),
               key=lambda k: math.dist(nodes[k], s))
    n = nodes[near]
    d = math.dist(n, s)
    if d < 0.001:
        continue
    # 3. steer: one step from that node towards it
    r = min(STEP, d)
    new = (n[0] + (s[0] - n[0]) / d * r,
           n[1] + (s[1] - n[1]) / d * r)
    # 4. keep the new node only if the branch is clear
    if not clear(n, new):
        continue
    nodes.append(new)
    parent.append(near)
    # 5. stop when the goal is one clear step away
    if math.dist(new, GOAL) <= STEP and clear(new, GOAL):
        nodes.append(GOAL)
        parent.append(len(nodes) - 2)
        found = True
    if len(nodes) >= due:
        show(s)
        due = len(nodes) + 5 + len(nodes) // 20
show(nodes[-1])

if found:
    # walk back from the goal, parent by parent
    route = []
    k = len(nodes) - 1
    while k is not None:
        route.append(nodes[k])
        k = parent[k]
    route.reverse()
    draw("route", route, "red", "line", 2)
    length = sum(math.dist(a, b)
                 for a, b in zip(route, route[1:]))
    print("samples:", samples)
    print("nodes:", len(nodes))
    print("path:", round(length), "cm")
else:
    print("no route after", samples, "samples")

It still gets there, because the tree spreads over the whole mat until a branch happens to wander into the corner. Look at the end of the chart: after about 160 nodes the tree is 13 cm from the goal, but the last step to the goal can be no longer than STEP, 12 cm, and it takes another 65 nodes before a branch lands close enough. A goal sample would have made that last step straight away. A single run is one throw of the dice, and this is a different seed from the first demo, so to compare settings fairly the table below ran the same program with 100 seeds for each bias, and gives the middle value (the median).

A little bias saves nodes: at 0.1 the tree needed about a quarter fewer than with none. More than that wastes samples. The goal is behind two walls, so until the tree is round the second one, a goal sample asks the node nearest the goal to step into a wall, and the step is thrown away. At BIAS = 1 the planner is pure greed: the tree steps straight at the goal, stops against the first wall after three steps, and every sample after that is the same wasted step, until the program gives up at 3,000. A bias of about 0.05 to 0.1 is the usual choice.

Step size

The same 100 seeds, with BIAS = 0.1 and different steps:

A small step makes a tree of many short branches. It needs more nodes and more samples, and every sample measures its distance to every node to find the nearest, so the work grows faster than the tree: going from a 12 cm step to 6 cm doubled the nodes and needed about four times as many distance calculations.

A big step needs fewer nodes, and on this mat it even needs fewer samples. The gaps here are wide, and a branch is never longer than the distance to its sample, so a sample close to the tree still gives a short branch that fits. The price is a longer, more crooked route, and more checking: a 30 cm branch takes 21 point tests where a 12 cm branch takes 9. In a cluttered room with narrow gaps, long branches hit something more often and are thrown away. Here 12 cm, under half the width of the corridor, is a fair balance.

Check the whole branch

Step 4 of the loop checks the branch, not just its end. This demo shows why, with a 30 cm step and CHECK = False, so that only the new point is tested.

from bugbot import *
import math
import random
connect()

# change these numbers and press Run
STEP = 30        # how far each new branch reaches, cm
BIAS = 0.1       # how often to aim at the goal itself
SEED = 1         # another number grows another tree
CHECK = False    # False: test only the new point
random.seed(SEED)

START = (30, 30)         # the robot
GOAL = (170, 170)        # the green corner
GROW = 10                # grow the walls by 10 cm
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]

def free(p):
    # is a point robot at p clear of the grown walls?
    x, y = p
    if not (GROW < x < 200 - GROW and GROW < y < 200 - GROW):
        return False
    for wx, wy, ww, wh in WALLS:
        if (wx - GROW < x < wx + ww + GROW and
                wy - GROW < y < wy + wh + GROW):
            return False
    return True

def clear(a, b):
    # is the whole branch from a to b clear?
    # test a point every 1.5 cm along it
    if not CHECK:
        return free(b)
    n = max(2, int(math.dist(a, b) / 1.5))
    for k in range(n + 1):
        t = k / n
        if not free((a[0] + (b[0] - a[0]) * t,
                     a[1] + (b[1] - a[1]) * t)):
            return False
    return True

def show(sample):
    # draw the tree as one line that runs out
    # along every branch and back again
    kids = [[] for n in nodes]
    for k in range(1, len(nodes)):
        kids[parent[k]].append(k)
    line = []
    def walk(k):
        line.append(nodes[k])
        for c in kids[k]:
            walk(c)
            line.append(nodes[k])
    walk(0)
    draw("tree", line[:2000], "blue", "line", 1)
    draw("sample", [sample], "yellow", "dots", 4)
    plot("cm to the goal",
         min(math.dist(n, GOAL) for n in nodes))
    wait(0.25)

nodes = [START]      # the tree: its points,
parent = [None]      # and the node each grew from
samples, found, due = 0, False, 1
while samples < 3000 and not found:
    samples += 1
    # 1. sample: a random point, now and then the goal
    if random.random() < BIAS:
        s = GOAL
    else:
        s = (random.uniform(0, 200), random.uniform(0, 200))
    # 2. find the node nearest to it
    near = min(range(len(nodes)),
               key=lambda k: math.dist(nodes[k], s))
    n = nodes[near]
    d = math.dist(n, s)
    if d < 0.001:
        continue
    # 3. steer: one step from that node towards it
    r = min(STEP, d)
    new = (n[0] + (s[0] - n[0]) / d * r,
           n[1] + (s[1] - n[1]) / d * r)
    # 4. keep the new node only if the branch is clear
    if not clear(n, new):
        continue
    nodes.append(new)
    parent.append(near)
    # 5. stop when the goal is one clear step away
    if math.dist(new, GOAL) <= STEP and clear(new, GOAL):
        nodes.append(GOAL)
        parent.append(len(nodes) - 2)
        found = True
    if len(nodes) >= due:
        show(s)
        due = len(nodes) + 5 + len(nodes) // 20
show(nodes[-1])

if found:
    # walk back from the goal, parent by parent
    route = []
    k = len(nodes) - 1
    while k is not None:
        route.append(nodes[k])
        k = parent[k]
    route.reverse()
    draw("route", route, "red", "line", 2)
    length = sum(math.dist(a, b)
                 for a, b in zip(route, route[1:]))
    print("samples:", samples)
    print("nodes:", len(nodes))
    print("path:", round(length), "cm")
else:
    print("no route after", samples, "samples")

Look at the branch near the top that goes from about (115, 158) to (144, 164). Both of its ends are outside the grown walls, so a test of the new point says it is fine, but the middle of it goes straight through the second wall. This is the most common bug in RRT programs. It hides when the step is short, because a 12 cm branch cannot jump a wall that is 28 cm thick once it is grown. It still does harm: over 100 seeds at STEP = 12 with only the new point tested, 49 of the routes cut into the 10 cm margin round a wall, where the robot would drive closer than it planned to. At STEP = 30, 69 of the 100 routes went straight through a wall.

The fix is the clear function: test points along the branch, closer together than the thinnest thing on the map. The walls are 8 cm thick, 28 cm once grown, so a test every 1.5 cm is plenty. Set CHECK = True and run it again. The same seed now takes 295 samples and 95 nodes, and the route goes round both walls, 487 cm long.

Why the route is not the shortest

The shortest route round the grown walls is made of straight lines between their corners: up to the top left corner of the first grown wall, along its top, down the corridor to the bottom left corner of the second, along its bottom, and up to the goal. It is 311 cm. A* on a 5 cm grid finds 337 cm, the shortest route that moves only from cell to neighbouring cell. The RRT in the first demo found 456 cm.

An RRT stops at the first route it finds, and that route is whatever zigzag the random branches happened to make. Over 100 seeds with STEP = 12 and BIAS = 0.1, the routes ran from 355 to 587 cm, with 452 in the middle, about 45 percent longer than the best. Running for longer does not help. Once a node is in the tree its parent never changes, so the route to it never gets shorter, however many samples come after.

There are two usual fixes.

Shortening, after the plan. Walk along the route and, from each point, jump to the furthest point along it that you can see in a straight line, skipping everything in between. The next demo does this on the route with a point every 2 cm, once from the start and once back from the goal. Over the same 100 seeds, that brought the routes down to between 312 and 371 cm, with 318 in the middle, close to the best. The line-of-sight test has to use the same grown walls as the planner, or the shortcut will cut a corner the planner was careful to avoid.

RRT* (said "RRT star"), from Sertac Karaman and Emilio Frazzoli in 2011, changes how the tree grows. When it adds a node, it looks at every node within a small radius and picks as the parent the one that gives the shortest route from the start, rather than the nearest. Then it rewires: any of those nearby nodes that would have a shorter route through the new node gets the new node as its parent. Crooked branches are straightened out as the tree grows, and as the number of samples goes up, the route gets closer and closer to the shortest one. The price is more work for each sample: a collision check to every nearby node, where RRT does one.

Shorten, then drive

A plan is only useful if the robot can follow it. This program grows the same tree as the first demo, shortens the route, and drives it. The orange line is the route through the tree and the red line is the shortened route the robot drives.

from bugbot import *
import math
import random
connect()

# change these numbers and press Run
STEP = 12        # how far each new branch reaches, cm
BIAS = 0.1       # how often to aim at the goal itself
SEED = 4         # another number grows another tree
CHECK = True     # False: test only the new point
random.seed(SEED)

START = (30, 30)         # the robot
GOAL = (170, 170)        # the green corner
GROW = 10                # grow the walls by 10 cm
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]

def free(p):
    # is a point robot at p clear of the grown walls?
    x, y = p
    if not (GROW < x < 200 - GROW and GROW < y < 200 - GROW):
        return False
    for wx, wy, ww, wh in WALLS:
        if (wx - GROW < x < wx + ww + GROW and
                wy - GROW < y < wy + wh + GROW):
            return False
    return True

def clear(a, b):
    # is the whole branch from a to b clear?
    # test a point every 1.5 cm along it
    if not CHECK:
        return free(b)
    n = max(2, int(math.dist(a, b) / 1.5))
    for k in range(n + 1):
        t = k / n
        if not free((a[0] + (b[0] - a[0]) * t,
                     a[1] + (b[1] - a[1]) * t)):
            return False
    return True

def show(sample):
    # draw the tree as one line that runs out
    # along every branch and back again
    kids = [[] for n in nodes]
    for k in range(1, len(nodes)):
        kids[parent[k]].append(k)
    line = []
    def walk(k):
        line.append(nodes[k])
        for c in kids[k]:
            walk(c)
            line.append(nodes[k])
    walk(0)
    draw("tree", line[:2000], "blue", "line", 1)
    draw("sample", [sample], "yellow", "dots", 4)
    plot("tree to goal cm",
         min(math.dist(n, GOAL) for n in nodes))
    wait(0.25)

nodes = [START]      # the tree: its points,
parent = [None]      # and the node each grew from
samples, found, due = 0, False, 1
while samples < 3000 and not found:
    samples += 1
    # 1. sample: a random point, now and then the goal
    if random.random() < BIAS:
        s = GOAL
    else:
        s = (random.uniform(0, 200), random.uniform(0, 200))
    # 2. find the node nearest to it
    near = min(range(len(nodes)),
               key=lambda k: math.dist(nodes[k], s))
    n = nodes[near]
    d = math.dist(n, s)
    if d < 0.001:
        continue
    # 3. steer: one step from that node towards it
    r = min(STEP, d)
    new = (n[0] + (s[0] - n[0]) / d * r,
           n[1] + (s[1] - n[1]) / d * r)
    # 4. keep the new node only if the branch is clear
    if not clear(n, new):
        continue
    nodes.append(new)
    parent.append(near)
    # 5. stop when the goal is one clear step away
    if math.dist(new, GOAL) <= STEP and clear(new, GOAL):
        nodes.append(GOAL)
        parent.append(len(nodes) - 2)
        found = True
    if len(nodes) >= due:
        show(s)
        due = len(nodes) + 5 + len(nodes) // 20
show(nodes[-1])

if not found:
    print("no route after", samples, "samples")
else:
    # walk back from the goal, parent by parent
    route = []
    k = len(nodes) - 1
    while k is not None:
        route.append(nodes[k])
        k = parent[k]
    route.reverse()
    draw("route", route, "orange", "line", 1)

    def length(path):
        return sum(math.dist(a, b)
                   for a, b in zip(path, path[1:]))

    def dense(path):
        # the same path, with a point every 2 cm
        out = [path[0]]
        for a, b in zip(path, path[1:]):
            m = max(1, int(math.dist(a, b) / 2))
            for j in range(1, m + 1):
                out.append((a[0] + (b[0] - a[0]) * j / m,
                            a[1] + (b[1] - a[1]) * j / m))
        return out

    def shorten(path):
        # from each point, jump to the furthest
        # point along the path it can see
        out, i = [path[0]], 0
        while i < len(path) - 1:
            j = len(path) - 1
            while j > i + 1 and not clear(path[i], path[j]):
                j -= 1
            out.append(path[j])
            i = j
        return out

    # shorten once from the start, once from the goal
    short = shorten(dense(route))
    short = shorten(dense(short[::-1]))[::-1]
    draw("short", short, "red", "line", 2)
    print("RRT route:", round(length(route)), "cm")
    print("plan:", round(length(short)), "cm")

    # drive it: aim at a point on the route and
    # move that point on as the robot comes near
    path = dense(short)
    i = 0
    while True:
        px, py = position()      # cm from the start
        x, y = 30 + px, 30 + py
        tx, ty = path[i]
        d = math.hypot(tx - x, ty - y)
        if d < 8 and i < len(path) - 1:
            i += 1
            continue
        if d < 2:
            break
        plot("robot to goal cm", math.dist((x, y), GOAL))
        # a world velocity of up to 14 cm/s
        v = min(14, 1 + 2 * d) / d
        vx = (tx - x) * v
        vy = (ty - y) * v
        # turn it into the robot's own frame
        a = math.radians(heading())
        fwd = vx * math.sin(a) + vy * math.cos(a)
        side = vx * math.cos(a) - vy * math.sin(a)
        # 100 % is 20 cm/s forward, 15 sideways
        turn = (heading() + 180) % 360 - 180
        drive(fwd * 5, side * 6.7, -turn)
        wait(0.1)
    stop()
    print("stopped at", round(x), round(y))

Shortening takes the route from 456 cm to 324 cm, with six corners. The robot follows the red line with the same simple follower as the A* guide: it can move sideways, so it never needs to turn, and it aims at a point on the route and moves that point on once it is within 8 cm. position() is the overhead camera in the simulator, so the robot always knows where it is. The chart has a second line once the robot moves: its own straight-line distance to the goal, which falls to 93 cm, rises to 109 cm while the robot goes down the corridor away from the goal, then falls to about 3 cm as it stops. For a follower that looks further ahead and turns into bends smoothly, see pure pursuit.

RRT and A*

A* is complete: on a grid it either finds a route or tells you there is none. An RRT is probabilistically complete: if a route exists, the chance that it has found one rises towards certainty as the samples go on, but if there is no route it can never say so. It just keeps sampling. That is why a real planner gives it a budget, a number of samples or a time limit, and a plan for what to do when the budget runs out. The demos stop at 3,000 samples.

Both find narrow gaps hard in their own way. A grid can miss a gap that falls between cell centres. An RRT has to throw a random sample into a small target, and may take a very long time to do it.

On a flat mat with a few walls, A* is the better choice: the grid is small, the route is the shortest the grid allows, and it is the same every time. An RRT earns its place when the configuration space has more dimensions than a grid can hold, such as a robot arm, or a car whose heading matters, or when all you have is a test that says whether a configuration collides.

Questions

What is an RRT in path planning?

A rapidly exploring random tree is a planner that grows a tree of collision-free points from the start by sampling random points. Each new point is one short step from the tree's nearest point towards a random sample. When the tree reaches the goal, the route is read back through the tree from the goal to the start.

How does the RRT algorithm work?

Repeat five steps: sample a random point, sometimes the goal itself; find the node of the tree nearest to it; step a fixed distance from that node towards the sample; if the straight branch to the new point is free of obstacles, add the new point with the nearest node as its parent; stop when a new node can reach the goal in one clear step. Then follow the parents back from the goal to get the route.

Why is it called rapidly exploring?

Because the nearest-node rule pulls the tree out into empty space. A random sample is most likely to land in a large unexplored area, and the node nearest to that area, on the edge of the tree, is the one that grows towards it. In the first demo on this page, the tree reached the corridor between the two walls by its 50th node.

What is the difference between RRT and RRT*?

RRT joins each new node to its nearest node and never changes the tree, so its route stays as crooked as it was first found. RRT* joins each new node to whichever nearby node gives the shortest route from the start, then rewires nearby nodes through the new one when that is shorter. RRT* routes keep getting shorter as samples are added, and approach the shortest route; each sample costs more work.

What is the difference between RRT and A*?

A* searches a grid or graph that is built first, and returns the shortest route on it, the same every time. RRT builds a tree from random samples and returns the first route it finds, which is usually longer and different on every run. A* suits low-dimensional spaces such as a flat map. RRT suits spaces with many dimensions, such as a robot arm's joint angles, where a grid would be far too big. On this page A* found a 337 cm route and a plain RRT found 456 cm, where the shortest possible is 311 cm.

Why does RRT not find the shortest path?

It stops at the first route it finds, and that route follows whatever random branches the tree happened to grow. Once a node is in the tree its parent never changes, so more samples do not improve it. On this page, 100 runs gave routes from 355 to 587 cm against a best of 311 cm. Shortening the route afterwards, or using RRT*, fixes most of this.

What is goal bias in RRT?

The fraction of samples that are the goal itself instead of a random point. A small bias, around 0.05 to 0.1, pulls the tree towards the goal and saves nodes: on this page 0.1 needed about a quarter fewer nodes than 0. Too much bias makes the planner greedy. At a bias of 1 it steps straight at the goal and gets stuck against the first wall.

How do you choose the step size for an RRT?

Small steps make many short branches, so the tree needs more nodes and much more work to find each nearest node. Large steps need fewer nodes but give longer, more crooked routes, need more collision tests per branch, and are thrown away more often in cluttered spaces. Start with a step well under the narrowest gap the robot must get through, then try larger and smaller values and compare.

What is configuration space in path planning?

The configuration space is the set of every configuration the robot can be in, with the configurations that would collide marked as obstacles. For a robot on a flat floor that can slide in any direction and has a round footprint, it is the floor with every obstacle grown by the robot's radius, and the robot becomes a single point. For a robot arm, it is the space of its joint angles.

Is RRT complete?

It is probabilistically complete: if a route exists, the chance of finding it tends to certainty as the number of samples grows. It is not complete in the stronger sense, because if there is no route it keeps sampling for ever and never reports that there is none. Real planners stop it after a set number of samples or a time limit.

How do you write an RRT in Python?

Keep two lists: the nodes as (x, y) points and, for each, the index of its parent. In a loop, pick a sample with random.uniform, or the goal with a small probability, find the nearest node with min and math.dist, step towards the sample by at most the step size, and test points along the new branch against the obstacles. If they are all free, append the new node and its parent. When a node is within one step of the goal and can see it, append the goal and follow the parents back. The first demo on this page is a complete program that does this in about 110 lines, including the drawing.

Where is RRT used?

Mostly where the configuration space has many dimensions: planning the movements of robot arms, and for drones and self-driving vehicles. Motion planning libraries such as the Open Motion Planning Library (OMPL) include RRT, RRT* and many relatives, and MoveIt, the arm planning software used with ROS, uses OMPL for its planning by default.

Is RRT on the A level Computer Science specification?

Not by name. None of the GCSE or A level Computer Science specifications (AQA, OCR, Edexcel, Eduqas) include RRT. The ideas it is built from are on them: trees, graphs, searching, and random numbers in programs. It makes a good A level Computer Science programming project next to a grid search such as A* or Dijkstra's algorithm, because the two can be compared on the same map.

Learn it step by step

These lessons build the same ideas one at a time, each with tasks the simulator marks.

1. U9.1 The configuration space Planning, University
2. U9.6 Sampling: the RRT Planning, University
3. U9.7 Project: plan a route and drive it Planning, University