What is Sampling-Based Motion Planning?

If you’re a robotics expert or enthusiast you probably have heard of the motion planning problem and some of the techniques for solving it such as Sampling-Based methods, popular of which are PRM and RRT* planners. Also, if you have experience with ROS, you might have heard of the Open Motion Planning library which contains a variety of sampling-based planners. This article will help shed some light on what exactly is sampling-based motion planning, its pros/cons, and some examples to drive home the concept. So without further ado let’s get into it.

The Motion Planning Problem

Before delving into the concepts of sampling-based motion planning, let’s briefly go over the definition of the motion planning problem (feel free to skip this section if you’re familiar with this topic). The definition from Wikipedia goes as follows:

Motion planning, also path planning (also known as the navigation problem or the piano mover’s problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination.

So motion planning is essentially the problem of finding a path (a sequence of configurations) that is valid through an environment. To better understand this let’s consider the classical piano mover’s problem, where let’s say you’re trying to move a large piano into your tiny apartment fitting it through your narrow building staircase and corridors. The piano has 6 degrees of freedom in space, (x,y,z) representing the translational position and (roll, pitch, yaw) representing the rotational position. The “configuration” will then be formed of all the above components combined { x, y, z, roll, pitch, yaw }. In order for us to be able to move the piano, we have to figure out a set of configurations that gets our piano from the starting position (your mover’s truck downstairs) to the goal position (your apartment) without colliding with any obstacles (i.e. it has to fit through the staircase, corridors .. etc). This sequence of configurations is what we call a “path”, and it has to be continuous in space, i.e. we can’t have any jumps in any of the components of the configuration (because our piano can’t just teleport in space). This is essentially the essence of motion planning, but instead of moving a piano, we’re trying to move our robot through the environment without colliding with any obstacles. The configuration for every robot will also be different, for example, a robotic arm will have a configuration that captures the positions of all of its joints { j1, j2, …, jn }, while a Roomba-like robot will have a configuration of just { x, y, yaw } (only moves in the floor plane).

Now that we’ve explained the motion planning problem, the question of “how do we solve it?” arises. There are several families of techniques that exist for solving the motion planning problem, such as grid-based methods (like A*), potential field methods, and sampling-based motion planning. You could read more about the different families of techniques in this Wikipedia article.

Sampling-Based Motion Planning

Sampling-based planning is an approach that doesn’t require fully exploring the configuration space (configuration space is the set of all possible configurations) which significantly increases the planning performance. Unlike traditional approaches like grid-based methods which require decomposing the entire configuration space into grid cells and searching through it for a solution, sampling-based approaches involve just randomly sampling the configuration space and reasoning about a much smaller set of sampled configurations. The process of finding a solution usually starts with creating the random samples, meaning that for our piano example above, we’ll just sample random values for each of { x, y, z, roll, pitch, yaw }. Then, the sampled configuration is usually checked for validity (i.e check piano doesn’t collide with anything) and if it is valid then it is connected to neighboring valid configurations (using some connectivity function). The set of all valid configurations and their connections is usually stored in some sort of graph or tree structure that can be queried for a solution. Since sampling-based approaches don’t require fully exploring the configuration space, they can be extremely efficient, but that usually comes at a cost, which is a reduction in the quality of the solution. Some of the most popular sampling-based motion planners are PRM and RRT*, let’s go over how PRM works to drive home the concept.

Example — PRM (Probabilistic Roadmap)

One of the first sampling-based motion planners ever developed was PRM. PRM works by randomly sampling the configuration space, and then connecting nearby valid configurations to each other (only if the connection is also collision free). By doing so we build what’s called a “roadmap”, which is analogous to an actual street road network in any city. The roadmap will be stored in a Graph, with the vertices of the graph representing the valid configurations we sampled, and the edges connecting the vertices representing the valid connections between configurations (the roads).

To illustrate further, let’s consider this simple 2D scenario where we have start and goal configurations. We assume here that the robot is just a point (not very realistic but it helps illustrate the concept). The shaded regions are obstacles that the robot can’t navigate through.

The first step of solving PRM is randomly sampling in this configuration space, which will yield something like the following (assuming we sample uniformly in x and y). Any configuration that falls in the shaded obstacles is automatically rejected since it results in a collision.

The second step is connecting each of the sampled configurations to its neighbors (usually within a specific radius in the vanilla version of PRM), this will form our roadmap, if a connection between 2 states results in a collision with the shaded obstacles it is rejected and not added to the roadmap.

Finally, to find the path we search the roadmap (using an algorithm like A* or Dijkstra) for the shortest path between the start and the goal (highlighted in green below).

It’s worth noting that I just presented the Vanilla version of PRM here, but there are several other modified versions like PRM* and LazyPRM that improve upon the above concepts to increase the efficiency of planning. Also, PRM is just one approach from many sampling-based planners, I will let you read up on other popular ones (RRT* for example).

Pros & Cons of Sampling-Based Approaches

Ok hope by now you’ve got the idea and you’ve probably recognized some of its pros and cons.

Pros:

• Feasible for high-dimensional spaces — Sampling-based planners are powerful if the configuration space is extremely large or high in dimensionality. Traditional methods like grid-based methods usually require decomposing the entire space into grid cells which the planner could reason about it, decomposing the space and searching through it for a solution can be very expensive or infeasible. Sampling-based methods on the other hand don’t have to reason about the entire configuration space, it just has to reason about a much smaller set of randomly sampled configurations to find a solution, this makes them feasible where grid-based methods aren’t.
• Finds a solution fast — In situations where you’d want to find a path very fast sampling-based methods shine because even if grid-based methods are feasible, the decomposition of the space takes valuable time that could be avoided with sampling-based planners.

Cons:

• Suboptimality of the solution — The above-explained pros come at a cost, the smaller your set of sampled configurations, the less optimal your path will be, or you might fail at finding a path even though one could exist. Consider the PRM example I showed above, and look at the quality of the final path generated, it doesn’t look very optimal right! This is the catch, if you want a solution fast or if your configuration space is high in dimensionality, you’ll often end up sparsely sampling the configuration space, which translates into a suboptimal solution, or you might fail at finding a path in the first place, even though a feasible one exists. This is the tradeoff you’ll often have to make, either spend a whole lot of time to densely sample the configuration space or just sparsely sample the space and contend with a suboptimal solution.
• Repeatability of the solution — Another problem is the repeatability of finding paths since there is inherent randomness in sampling-based planners, so for the same start/goal/environment, your solution will vary every time you run the planner. There are ways to get around this issue by caching previous successful paths, for reuse later to avoid having to run the planner a second time.
• Navigating in tight gaps — Sampling-based planners often fail at finding solutions that require navigating through narrow gaps or passages in the configuration space, that’s because the likelihood of sampling a configuration that’ll get you through a tight gap diminishes the tighter the gap becomes. You can think of random sampling as randomly shooting darts in the dark, imagine how unlikely it is for you to land a bullseye, the same idea applies to navigating into narrow passages, the chances of randomly sampling a configuration that’ll navigate you through a tight area can be very small.

It’s worth mentioning that even though the above cons might not seem very good, sampling-based planning has found a lot of success in practice as it provided a new approach to solving problems that were unsolvable with traditional approaches.

Conclusion

Sampling-based motion planning is a powerful technique that can be both fast and efficient since it doesn’t require fully exploring the configuration space of the problem. Instead, random configurations are sampled, checked for validity, and then added to a tree or graph structure that can be queried for a solution. Since the amount of sampling done is controlled by the user, sampling-based planners can usually arrive at a solution very fast but that usually comes at a reduction of the optimality in the found path.