Table of Contents
This project implements the Rapidly-Exploring Random Tree (RRT) algorithm for efficiently charting a path to goal in an environment with obstacles. RRT is applied frequently in high-dimensional spaces and is widely used in robotics for motion planning tasks. So far, this project features 2D planning around obstacles and an optimizer to find the optimal RRT parameters.
Key features of this implementation include:
- Obstacle Creation: Randomly generates rectangular obstacles defined within the search space.
- Biased Node Steering: Connects a node to the tree in the direction of the goal a set percent of the time to more quickly find a valid path to the goal.
- Angular Node Steering Constraint: Limits the angle at which a node can be randomly placed with respect to its corresponding parent node and the goal position a set percent of the time to speed up path finding.
- Live Visual: Provides live plotting of the tree expansion and final path.
- Parameter Optimization: Finds the set of parameters that will minimize the number samples to find a path to the goal in a given search space.
This project implements Bayesian Optimization to find the optimal parameters for the constraints of the search space.
More about the implementation
The optimization aims to minimize the number of samples required to find a path in a given search space. The parameters optimized include step_size, theta, turn_percent, and bias_percent. Furthermore, it features cumulative logging to persist optimization progress across multiple sessions, ensuring that the optimizer leverages previously gathered data.
The optimization process is divided into multiple "sessions," where each session continues to refine the search based on the cumulative history of the past sessions. Each session consists of many RRT searches, or iterations, being executed under the same conditions (i.e. same obstacles). Upon completion, the optimizer outputs the overall best parameters found and also examines nearby good points to provide insights into the general optimal region, rather than just a single "lucky" parameter set.
To learn more about how the optimizer works, visit this repository.
--- Bayesian Optimization Session 2/2 ---
Optimizer space has 25 points. Using 0 new initial random points, relying on history.
Starting optimizer.maximize() with init_points=0 and n_iter=20.
--- End of Session 2 ---
Best parameters found by this optimizer instance (current overall best):
Target: -117.00
Parameters (rounded to 4 decimal places):
- bias_percent: 15.2956
- step_size: 5.4456
- theta: 198.4974
- turn_percent: 31.5858
Total unique points known to this optimizer instance: 45
--- Examining Optimization Results ---
### Fixed RRT Space Parameters
Dimensions: [100 100]
Start Position: [1 1]
Goal Position: [99 99]
Goal Radius: 3
Max RRT Samples per iteration (n_samples): 1000
Number of Rectangle Obstacles (n_rectangles): 75
Rectangle Sizes( [[min_width, max_width] [min_height, max_height]]): [[ 5 15] [ 5 15]]
----------------------------------------
### Overall Best Point
Target: -117.00
Parameters (rounded to 4 decimal places):
- bias_percent: 15.2956
- step_size: 5.4456
- theta: 198.4974
- turn_percent: 31.5858
### Top 0 Nearby Good Points (within 30.00 of best)
No other points found within the specified tolerance.
Total time taken to run: 0h 8m 25.82s
To get a local copy up and running, follow the steps below.
Python is installed and added to path.
- Clone the repository
git clone https://github.com/hongb007/RTT-Algorithms.git
- Install the packages
pip install treelib numpy plotly matplotlib bayesian-optimization
-
CD to the project directory
cd .../RRT-Algorithms -
Run the algorithm via terminal. To exit the program, close the plot.
python rrt_2d.py
If you don't want to plot the algorithm live or the end result, run
python rrt_2d.py --live False --plot_result False
-
Run optimizer on set paremeters
python bayesian_optimization.py
To change the number of sessions and iterations per session, change these values
# ... (bayesian_optimization.py) ... n_bo_sessions = 5 # Number of Bayesian Optimization meta-iterations (sessions) n_bo_iterations_per_session = 50 # Adjust as needed (e.g., to 50-100 for real runs)
After running the optimizer, copy and paste the optimized parameters from the terminal into rrt_2d.py and run the algorithm!
# ... (rrt_2d.py) ... # Set the maximum distance the tree can extend in one iteration step_size = 7.04 # Define the maximum turning angle in degrees theta = 180.0 # Set the chance to turn a sample into the theta range from goal to parent node turn_percent = 65.0 # Set the percentage bias towards sampling the goal directly bias_percent = 20.8
python rrt_2d.py --live True --plot_result True
Plots from Baseyian optimized parameters:
Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.
If you have a suggestion that would make this better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Don't forget to give the project a star! Thanks again!
- Fork the Project
- Create your Feature Branch (
git checkout -b feature/AmazingFeature) - Commit your Changes (
git commit -m 'Add some AmazingFeature') - Push to the Branch (
git push origin feature/AmazingFeature) - Open a Pull Request