In this programming assignment, I implemented four different sampling-based planners for a 5-DoF planar arm to move from its start joint angles to the goal joint angles. I coded the planners in C++ and followed an object-oriented programming approach to write & maintain clean code.

The four algorithms are:

1. Rapidly-exploring Random Tree (RRT)
2. RRT-Connect
3. RRT-Star
4. Probabilistic Roadmap (PRM)

I then compared the average planning times, average number of vertices sampled, average length of plan generated, and the average path qualities of these planners. There were a number of paramaters I tuned to ensure all four planners were able to find a path to the goal. The most notable is the maximum number of configurations each planner is allowed to sample before we declare that a path cannot be generated- I capped this at 20000.

The start joint angle configuration that was fed to each of these four planners is shown below:

Rapidly-exploring Random Tree (RRT)

The path generated by the planner from start to goal configuration is:

Average planning time:

17 seconds

Average number of vertices sampled:

12000

Average length of plan generated:

56

Average path quality:

As is seen in the output, the RRT algorithm generates a plan that has nodes “all over the place”. The algorithm randomly samples points in the configuration space and adds it to the tree if it is a valid configuration. This repeats until a newly sampled node is close to the goal configuration within a small margin of error. However, there is no heuristic to help determine how to grow the tree and generate a straightforward path to the goal.

RRT-Connect

The path generated by the planner from start to goal configuration is:

Average planning time:

3 seconds

Average number of vertices generated:

90

Average length of plan generated:

24

Average path quality:

RRT-Connect grows two trees: one starting at the initial config and another stemming from the goal config. The two trees take turns sampling a node and incrementally grow towards each other. The generated path is not as random as the RRT’s and demonstrates some structure in moving towards the goal.

RRT-Star

The path generated by the planner from start to goal configuration is:

Average planning time:

24 seconds

Average number of vertices generated:

10000

Average length of plan generated:

9

Average path quality:

RRT* takes the longest time to generate a plan because it rewires nodes within a neighborhood of region to ensure each node has the shortest possible path back to the start. This induces extra time complexity, slowing the planner down. However, the plan it generates is incredibly intuitive and is almost always the shortest of the plans generated by the other three algorithms.

Probabilistic Roadmap (PRM)

The path generated by the planner from start to goal configuration is:

Average planning time:

2 seconds

Average number of vertices generated:

20000 (samples as many nodes as is the threshold)

Average length of plan generated:

15

Average path quality:

The PRM planner succeeds in generating a plan under 5 seconds 100% of the time. The algorithm samples the entire configuration space, and then uses Dijkstra’s algorithm to traverse the graph and find the shortest path from the start to the goal configuration. Just like the RRT* planner, PRM generates instinctual paths to the goal.