---

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

1. have a smooth trajectory
2. accurate obstacle avoidance and
3. 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.
RRT* is also asymptotically optimal like 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.



ROS exercises

Please note that these are random exercises to which the source code can be found at Ros-codes











Robotic arm trajectory and inverse kinematics







Quadtree

Quadtree using matplotlib
• Quadtree is a data structure used to divide the configuration space recursively into smaller segments.