Motion planning through graphs [Part 1]

So, for my very first blog post, I wanted to start off with something that I most recently did. Mainly for the reason that it is still fresh in my head, but also because it’s a perfect example of something that can seem really complicated, but actually isn’t. A lot of what I write may sound intimidating at first, but if you would be so kind as to bear with me, I will promise to break down that jargon into examples that anyone can understand.

I recently took a robotics course where I learnt about combinatorial and probabilistic road maps. Today, I want to write about probabilistic road mapping with RRTs.

First and foremost, if you aren’t familiar with a graph, it is a really popular data structure that is used in robotics but also in many every day applications that you and I both use (Google maps, Uber, Facebook, etc.). Each graph is defined as a set of vertices and edges. A perfect analogy for this can be to think of a graph as a cartesian plane. A vertex would be a point (x, y) and an edge would be the line segment that connects 2 such points. There are many ways to represent such a data structure, but the most popular way is an adjacency list (set of key-value pairs). We will basically correspond each vertex with an index number, and then for each index number, we maintain a list of all the other index numbers that you directly connect to.

A quick example of how graphs can be used. Try to imagine each turn as a vertex, and each straight line as an edge. We can build a path from a start point to an end point through a graph search algorithm.

If you are unfamiliar with data structures, fret not! Visualgo is a pretty neat way to get started on graphs and to get an understanding of what they are, the different ways to represent them, and the common traversal algorithms for them. Take a look at this website to familiarize yourself with graphs before proceeding with this post.

Once you have had a chance to familiarize yourself with graphs, let’s proceed with RRTs.

RRT stands for rapidly-exploring random trees. Wait, I just made you read about graphs, and now I’m talking about trees? I should have mentioned, a tree is a special kind of graph with no cycles in it. With RRTs, you can think of it as a graph that keeps growing until it is able to connect your start point and your end point to the graph.

An example of how a simple RRT grows in an environment with no obstacles. We will actually be building this!

Sampling based methods for planning paths are really useful when the space you are dealing with is fairly complex or large. Although it is not optimal (not the most efficient), computing all possible combinations of paths would take too long. In fact, for large enough spaces, it can take an indefinite amount of time to compute.

In the next part of this series, we will take a deeper look at writing some actual code. In the mean time, if you are interested in learning more about RRTs, definitely check out this link. All of my understanding of RRTs comes from this source as well as my professor’s lecture slides.

Read part 2!