About The Project

rrt_2d

Rapidly-exploring random trees (RRT) is a common option that both creates a graph and finds a path which may not necessarily be optimal. Points are randomly generated and connected to the closest available node. Each time a vertex is created, a check must be made that the vertex lies outside of an obstacle. Furthermore, chaining the vertex to its closest neighbor must also avoid obstacles. The algorithm ends when a node is generated within the goal region, or a limit is hit.

Built With

Python3

Getting Started

Prerequisites

Installation

Clone the repo

git clone https://github.com/vishalgattani/Path-Planning.git

Change to PRM
```
cd sampling-based/
```

Usage

Run the python file:
```
python3 rrt_2d.py
```

RRT Algorithm(in progress)

Qgoal //region that identifies success
Counter = 0 //keeps track of iterations
lim = n //number of iterations algorithm should run for
G(V,E) //Graph containing edges and vertices, initialized as empty
While counter < lim:
    Xnew  = RandomPosition()
    if IsInObstacle(Xnew) == True:
        continue
    Xnearest = Nearest(G(V,E),Xnew) //find nearest vertex
    Link = Chain(Xnew,Xnearest)
    G.append(Link)
    if Xnew in Qgoal:
        Return G
Return G

Output(in progress)

License

Distributed under the MIT License. See LICENSE for more information.

Contact

Project Link: https://github.com/vishalgattani/Path-Planning

References

https://theclassytim.medium.com/robotic-path-planning-rrt-and-rrt-212319121378

2D RRT

Table of contents