What does reversing your car into a parallel park have to do with robotics?

Car's are interesting because they can't easily move in certain directions, for example you can't just shift a car sideways. It must go forward or backward. This is why parallel parking is so difficult, you just can't shift sideways into the spot.

But after you got your L's you know how to parallel park right? So how does a robot do it?

Robots Can Use Rapidly Exploring Random Trees (RRT)

Rapidly Exploring Random Trees are a fun and conceptually simple algorithm.

They work for arbitrarily complex robots too. Like a snake robot that has to slither around obstacles. All you need to build an RRT is a way to predict your future motion. For example, a way to know where you would end up if you started at one point, turned your steering wheel left and hit the accelerator for half a second.

You then build a tree by repeating the process from where the car ended up.

It Really Is Random

A big problem with this idea is that there is usually an infinite number of actions you can take.

So rather than simulate all of them, the RRT randomly samples a potential action and then sees where it will end up. This way the tree is a random path through the world. Combine this with a system to check if a path might intersect an object and you have a fully featured robot path planning algorithm.

It also makes for very interesting visualisations.

Pictures

The pictures in this post are from the paper "Rapidly Exploring Random Trees" by S. Lavelle. This is one of my favourite algorithms partly because of how interesting its results are.