Probabilistic Roadmap (PRM) for Path Planning in Robotics

What is Path Planning?

As the term itself suggests, path planning is a computational problem that lets an autonomous mobile robot find the optimal path between two points. In other words, this problem deals with finding the shortest path between point A and point B such that there is no intersection with any configuration space obstacle.

At this point, the reader should know about the following important terms in robotics:
1. Configuration Space
2. Configuration Space Obstacle

Configuration Space

The set of all configurations or positions that a robot can attain is known as its configuration space. We also refer to it as c-space. We use cartesian coordinates to define a robot’s configuration.

Configuration Space

It is the region in which either the robot collides with the physical obstacles or some specified links of the robot to collide with each other.

Moving back to the main topic, Probabilistic Roadmap planning is used to determine the shortest (and/or optimal) path between two specified points, let’s refer to these points as nodes now.

A probabilistic roadmap (PRM) is a network graph of possible paths in a given map based on free and occupied spaces. Click

Let’s look at the steps involved in forming such a network graph

1. A random node is generated in the configuration space.
2. The system checks whether this node lies in free space or not i.e, whether this configuration intersects with an obstacle or not.
3. If the node is in free space, it is added to the graph.
4. This newly generated node is then connected to the closest nodes through a straight line.
5. The system then checks if the connection between two nodes lies in free space or not.
6. If it lies in free space, the connection is added to the graph. Let’s refer to theses connection as edges now.

Explanation

The process of generating random nodes and then making edges is repeated n times. Let’s say the system generates a random node x. Now, a function is called to check whether the x lies in free space. Let’s call this function collision_check. If collision_check() returns TRUE, the system will call another function to find the m (m can be any number) nearest points to this new node x . Here, this function will be called distance. It will return the coordinates of m nearest nodes Then another function, check_edge, is called to check if it is possible to construct an edge between the nodes that the distance function returns.

A visual representation of two consecutive iterations of this algorithm is given below (The blue shapes are obstacles)

Now that we have a graph of nodes and edges, we can augment the start and end points in it to arrive at a solution to our path planning problem.

After getting a complete graph, the shortest path can be found using algorithms like Dijkstra’s algorithm or the A* search algorithm which would yield a path as shown:

Here’s a visualisation of the PRM algorithm from Matlab

Disadvantages of PRM

This algorithm is very useful but, it does not give the optimal solution every time. Consider a configuration space with a large number of obstacles situated very close to each other. Assume the gap between two obstacles is very narrow. Recall, that our system generates nodes randomly. Due to this, the probability of generating nodes between those gaps is very small. The system might generate nodes in that region if we increase the number of iterations. You might think that increasing the number of iterations solves the problem, but it is not the case. When the system fails to generate a path for such configurations of the space, we wouldn’t know whether it is because the path does not exist or the number of iterations is less for that environment. This is the only drawback of this algorithm. It does not paint a clear picture for us in event of failure.

I would highly recommend you to read a little about the Rapidly Exploring Random Tree (RRT) Method which overcomes this drawback.

Also, I’ll be introducing more such topics in the upcoming blogs. Stay tuned!