Robotic Path Planning: PRM and PRM*

Building a infrastructure for path planning

In my previous article, I discussed two path planning algorithms often used in robotics. The algorithms aimed to solve the problem that I mentioned last week:

The robotic path planning problem is a classic. A robot, with certain dimensions, is attempting to navigate between point A and point B while avoiding the set of all obstacles, Cobs. The robot is able to move through the open area, Cfree, which is not necessarily discretized.

The Rapidly-exploring random tree (RRT) family of algorithms solved this problems by building a graph from a starting position and aiming to land a randomly generated point in the goal region. Various methods were used to connect points and optimize the path.

A robot using PRM to generate a circle

The RRT algorithm was advantageous to find possible paths from a given point. Yet, each time a new location was given, an entirely new graph had to be generated. Repeatedly generating a new graph to find a single path is arguably inefficient, especially if a relatively large area is being explored. An alternative approach that addresses this deficiency is the Probabilistic Roadmap (PRM) algorithm.

Instead of generating a fresh graph with each desired path, PRM builds a single roadmap that aims to cover a good portion of the…