This repository contains the sampling based motion planning algorithms like RRT(Rapidly exploring Random Tree) and PRM(Probabilistic Roadmap) in 2D configuration space with pygame.

These algorithms are part of my project at HTIC, IIT-Madras during my research internship.

We tried a variety of algorithms like RRT, A-star, Dijkstra's, PRM etc in 2D space. RRT among them proves to be the most promising candidate for efficient motion planning in 2D as well as 3D space.

These algorithms have a variety of applications ranging from protein folding to collision avoidance of mars rover.

Developers: Adwait P Naik
Guide: Mr. Manojkumar L @ HTIC, IIT-Madras
Project: Motion Planning for UR5 robotic Arm
Duration: November 2019 - February 2020

Problem Statement

To determine a collision free path in Kinodynamic environment provided the obstacles are static.

Goal

During accuracy testing & TCP calibration we observed that the our UR5 robot after collision with the table or the mount stopped with a backslash. The trajectories were not smooth at all which affected the accuracy. So we tested a few algorithms to

have a smooth trajectory
accurate obstacle avoidance and
be memory efficient and computationally cheap.

Libraries used

for animation - Pygame
for calculations - numpy, itertools etc

Running requirements

Python 3.7
Pygame and Tkinter

Results

RRT

Rapidly-exploring Random Tree

Implemented a basic RRT algorithm using the pygame library in python
Observations - RRT is an asymptotically optimal algorithm. In other words, it obtains a solution path when the number of iterations tend to infinity. It's probabilistically complete which means that if the path exists it will return it.
disadvantages - In RRT, each time the graph is constructed from scratch which makes it inefficient for finding paths in larger space.
Space complexity of RRT is O(n). In other words it has a linear space complexity which means that if the search space increases the iterations to find an optimal path will also increase subsequently.

RRT-star

Rapidly-exploring Random Tree star

Implemented RRT-star algorithm using pygame.
RRT* unlike RRT has a slightly different strategy for finding the nearest node which makes it computationally more efficient than RRT.
RRT* takes less iterations to find the optimal path as compares to RRT.
disadvantages - In RRT-star, each time the graph is constructed from scratch which makes it inefficient for finding paths in larger space like RRT.
Space and Time complexity of RRT is O(logn) and O(nlogn). In other words it has a linear space complexity which means that if the search space increases the iterations to find an optimal path will also increase subsequently.
Link to the research paper Research paper

RRT-star FN

Rapidly-exploring Random Tree star Fixed Nodes

Implemented RRT-star algorithm using pygame.
Here we have created circular obstacles to test for the collision free path.
This is the modified version of RRT star probabilistically complete in nature.
It grows the tree till the count reaches fixed amount of nodes and then optimizes the tree further by removing the weaker node by adding a node with high probability to converge an efficient path.
Link to the research paper Research paper

RRT with B-spline and node pruning

Rapidly-exploring Random Tree with B-spline and Node pruning

RRT-bidirectional

Rapidly-exploring Random Tree bidirectional

In this variant the tree is made to grow from the start node and the goal node as well until it meets at a particular point

RRT-bidirectional with Manhattan distance

The manhattan distance concept is based on the Taxicab geometry

Astar Algorithm

Astar Algorithm

Astar is an algorithm based on graph traversal and path search used in travel-routing systems and path finding
It is based o heuristic approach governed by equation f(n) = g(n) + h(n). The estimation is done on the basis of cost of the path and cost to expand the nodes in particular direction.