realkushagrakhare / 3d_path_planning

AI project for 3D Path Planning. Other details and running instructions can be found on the Readme.md file

3D_Path_Planning

is an AI project for 3D Path Planning which involves pruning with constant satisfaction.

3D path planning is required in various applications such as robotics, self-driving cars, protein folding, games etc. It ensures to and a trajectory from the initial point to the destination, subject to rules of motion and any other constraints, such as collision avoid- ance, balance and joint limits.
Algorithms like Dijkstra, A* can be used but they are quite expensive to compute for large clustered space Random sampling based planning algorithm like RRT can solve motion planning problem while also taking the differential constraint into consideration. But the paths so produced are jagged, with several unnecessary branches. They need to be pruned and smoothed. An approach could be to fit a spline over the points which would produce a smooth path.

Developers: Kushagra Khare, Rachit Jain
Mentor: Prof. Srisha Rao, IIIT-B
Project Duration: Aug '18 - Nov '18

Goal

In this project, we aim to provide an algorithm for 3D Path Planning. We will implement a RRT-A* based 3D Path Planning algorithm. The algorithm would include path pruning with constraint satisfaction and account for non-holonomic constraints. We will go ahead with Manhattan based RRT-A* in the initial stages but will also try to find an optimized distance metric function using Voronoi bias property for the algorithm.

Technologies used:

• PyGame & POGL
• Scikit, NumPy, Scipy

Running Requirements

• Python 3.7
• Pygame and Scipy

Milestones

Week 1

• Implemented a basic Random-exploring Random Tree algorithm using PyGame.
• Read about various types of RRTs and implemented RRT-A* vartion. Compared its pros and cons with the basic algorithm

Week 2

• Implemented RRT* which results into asymptotically optimum solution.

Week 4

• Added Node Pruning and Spline Fitting in RRT* pipeline.
• Later we realized that node pruning is not needed for RRT* as probability of pruning a path of RRT* is nearly 0.04.

Week 5

• Implemented 2-Phase Sampling making the algorithm faster.

Week 7

• Combined Dubins and Reeds-Shepp Path Planning algorithms with RRT* for non-holonomic constraints.

Future works:

• Obstacle collision detection can be parallelized by using CUDA which will make computation a lot faster and applicable in real life scenarios.
• Including various other non-holonomic constraints like velocity, size of robot(or car).