RRT_PathPlanning

Rapidly-exploring Random Trees (RRT) is an algorithm for path planning and exploration. It is useful for navigating spaces in complex environment. Bidirectional RRT & RRT* are variation/extended versions of regular RRT. The nodes sampled by RRT can be used by other searched-based path planning algorithm e.g. Astar, to obtain paths for other start-goal pairs

🌳 RRT

RRT repeatly perform the steps below until a path is found from the start to goal or a specified number of iterations is reached.

1. Randomly samples point in the space
2. Extends tree towards it
3. Checks for collisions

↔️ Bidirectional RRT

Bidirectional RRT grows two tree, one from start and one from goal, simultaneosly.

⭐ RRT*

RRT* optimizes the path by performing rewiring during node sampling. Rewiring of sampled node ensure it is connected to a parent of lowest cost and it will be the best parent to other nodes. RRT* can improve the path with more nodes sampled.

🔍 Astar

Process other path query by searching up the map generated by RRT.

📂 Scripts

1. rrt_simulate.py run rrt on a random simulated environment returning the path & path cost, pylab plot visualization allowed, you can specify the arguments in command line as shown below.

usage: rrt_simulate.py [-h] [-x X] [-y Y] [-o O] [--seed SEED] [--len LEN] [--bias BIAS] [--iter ITER] [--bidir] [--star] [--max] [--ani]

RRT Path Planning Simulation Arguments

options:
  -h, --help   show this help message and exit
  -x X         Environment X size
  -y Y         Environment Y size
  -o O         Number of obstacles
  --seed SEED  Random seed
  --len LEN    Max distance allowed for node expansion
  --bias BIAS  Percentage of biased-sampled goal
  --iter ITER  Max sampling iteration
  --bidir      Use bidirectional RRT
  --star       Use RRT*
  --max        Sampling for max iteration
  --ani        Disable animated visualization

2. interactive.py run rrt first, like rrt_simulate.py. After rrt finish planning the first path query, you can press spacebar key to change a random path query, the program use astar to find the path solution, the process are visualized on the pylab plot. Exit by pressing Ctrl+C or cross out the plot window.

🚀 Installation

cd /path/to/your/directory
git clone https://github.com/bk1021/RRT_PathPlanning.git
pip install -r requirements.txt

🙏 Acknowledgement

1. utils/environment_2d.py is from open source robotics course: https://www.osrobotics.org/osr/
2. The visualization method for RRT path planning is inspired by this video https://www.youtube.com/watch?v=QR3U1dgc5RE