Giter VIP home page Giter VIP logo

python-rrt's Introduction

logo


Software License Build Status Stars Contributions Lines Of Code Total alerts Code

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

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*

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 star FN

RRT with B-spline and node pruning

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

    RRT-Bspline and Pruning

    RRT-Bspline and Pruning

    RRT-Bspline and 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

      RRT-bidirectional with Manhattan distance

      • The manhattan distance concept is based on the Taxicab geometry
      • RRT-bidirectional

        RRT-bidirectional

        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.

        Astar

        ROS exercises

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

          creating objects in rviz

          creating objects in rviz

          creating objects in rviz

          creating objects in rviz

          creating objects in rviz

        Robotic arm trajectory and inverse kinematics

        UR5

        UR5

        UR5

      Quadtree

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

        Quadtree

        Quadtree

        Quadtree

        Quadtree

        Quadtree

        Quadtree

python-rrt's People

Contributors

addy1997 avatar pyup-bot avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.