A 2D Rapidly-Exploring Random Tree (RRT) algorithm built from scratch with a custom steering function and parameter optimization. RRT is applied frequently in high-dimensional spaces and is widely used in robotics to generate an initial high-level path for motion planning tasks.
Implementation Details:
- Node Steering: Allows for a percentage of samples to be directed at the goal rather than at random. Furthermore, this also includes a steering contraint to limit the angle at which a node is sampled w.r.t the angle created by the node parent, the goal node, and the sampled node. This allows results in less time to search for a valid path.
- Parameter Optimization: Finds the set of parameters that will minimize the number samples to find a path to the goal in the given search space.
More about the parameter optimization
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
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