RRT, RRT* and Informed RRT* path planner with tree-growth animation

[darshit-desai]

Summary

I’d like to add a sampling-based planner: RRT (Rapidly-exploring Random Tree) for 2D path planning. This would complement the existing grid planners (A*, Dijkstra) with a continuous-space method and a tree-growth animation.

Why this fits the repo

• Beginner-friendly algorithm with visual intuition (tree expansion).
• Uses only Python + NumPy + Matplotlib (and optionally SciPy, but not required).
• Adds a new planning approach without changing existing code.

Proposed plan

1. Add a planner component:

   • New module: src/components/plan/rrt/rrt_path_planner.py
   • Inputs similar to A*: start, goal, map_file, x_lim, y_lim
   • Parameters: step_size, goal_radius, max_iters, seed
   • Collision checking on the occupancy grid by sampling along each edge.
   • Treat any grid cell > 0 as blocked (same semantics as A*).

2. Add a simulation:

   • New folder: src/simulations/path_planning/rrt_path_planning/
   • Script: rrt_path_planning.py
   • Build the same obstacle map as A* using BinaryOccupancyGrid
   • Run RRT, save path to path.json
   • Generate rrt_search.gif showing tree growth and final path
   • (Optional) Use CubicSplineCourse + PurePursuitController to create rrt_navigate.gif

3. Add unit tests:

   • test/test_rrt_path_planning.py
   • Disable animation via a show_plot flag
   • Use a fixed RNG seed
   • Assert: path starts near start, ends near goal, and edges are collision-free.

4. Update README:

   • Add RRT under Path Planning with GIF(s)

Testing

• python -m pytest test/test_rrt_path_planning.py -v
• run_test_suites.sh / run_test_suites.bat

Question

Does this plan look OK? Any preferences on parameters, file layout, or the animation style?

[ShisatoYano]

Hi @darshit-desai,

Thank you for opening this issue!

Your proposal looks so great. So you can create the PR and I will start reviewing later.

I’m looking forward to your Pull Request!

Additionally, I have a question your plan. Does this plan mean both of RRT and RRT* are implemented or only RRT is implemented as scope?

[darshit-desai]

I will implement 3 of them:

RRT
RRT*
Informed RRT*

[ShisatoYano]

I understood your plan. It sounds great! In that case, could you separate Your PR into three ones, for RRT, RRT* and informed RRT*? If so, it will be easier for me to review your PRs.