Data

Tools

Indexes

Applications

Experiments

Open Source Science

rrt-algorithm

Rapidly-Exploring Random Tree Implementation

https://github.com/khachdavid/rrt-algorithm

Science Score: 31.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ○
    .zenodo.json file
  • ○
    DOI references
  • ○
    Academic publication links
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (6.1%) to scientific vocabulary
Last synced: 10 months ago · JSON representation ·

Repository

Rapidly-Exploring Random Tree Implementation

Basic Info
  • Host: GitHub
  • Owner: KhachDavid
  • License: mit
  • Language: Python
  • Default Branch: main
  • Size: 7.81 KB
Statistics
  • Stars: 0
  • Watchers: 1
  • Forks: 0
  • Open Issues: 0
  • Releases: 0
Created almost 2 years ago · Last pushed almost 2 years ago
Metadata Files
License Citation

https://github.com/KhachDavid/rrt-algorithm/blob/main/ 

# RRT-Algorithm

This repository is my implementation of the RRT algorithm.

## How does it work?
1. Initialization

    The algorithm starts by defining a starting position (root of the tree) and a goal position. It also defines the environment, including obstacles that must be avoided.

2. Random Sampling

    At each iteration, the algorithm samples a random configuration (a point in the space), which could be anywhere in the defined search space.

3. Nearest Vertex

    The algorithm finds the vertex (node) in the current tree that is closest to the random sample.

4. New Configuration

    A new node is generated by extending from the nearest vertex in the direction of the random sample. The new node is created at a predefined step size to avoid overshooting obstacles or the goal.

5. Collision Check

    The algorithm checks whether the new node is in collision with any obstacles. If a collision is detected, the node is discarded.

6. Expand Tree

    If the new node is collision-free, it is added to the tree, and an edge is created from the nearest vertex to the new node.

7. Goal Check

    The algorithm if a direct, collision-free path to the goal is possible, the algorithm terminates.

8. Iterate

    The process is repeated until a valid path to the goal is found or a maximum number of iterations is reached.

## Example Output
![demo](demo.png)

The implementation was completed in September 2024 during the MSR program kick-off hackathon at Northwestern University

Owner

  • Name: David Khachatryan
  • Login: KhachDavid
  • Kind: user
  • Location: Chicago, Illinois
  • Company: Sunrise Futures

📚 UW Madison, Class of 2022

Citation (citations.txt) 

[1] https://stackoverflow.com/a/25421861 Accessed on 9/17/24
[2] https://stackoverflow.com/a/74932533 Accessed on 9/17/24
[3] ChatGpt. OpenAIUsed on 9/17/2024. Transcript is in ./chatgpt/transcript1.txt

GitHub Events

Total
Last Year

Dependencies

requirements.txt pypi
  • contourpy ==1.3.0
  • cycler ==0.12.1
  • fonttools ==4.53.1
  • imageio ==2.35.1
  • kiwisolver ==1.4.7
  • matplotlib ==3.9.2
  • numpy ==2.1.1
  • packaging ==24.1
  • pillow ==10.4.0
  • pyparsing ==3.1.4
  • python-dateutil ==2.9.0.post0
  • six ==1.16.0