Rapidly exploring random trees (RRT) - Path planning
This page demonstrates the rapidly exploring random trees (RRTs). In a 2D configuration space (C-space) with obstacles, a path is to be searched between the start and the goal points. For the problems below, C-space is a rectangle of size 100x100 containing three obstacles of different shapes.
The videos below are at 120 fps, and can be downloaded from links below. In VLC player, they can be viewed frame by frame, by pressing 'e' on the keyboard.
Start (24,13), Goal (63,47) (3.2 MB)
Start (80,60), Goal (80,50) (0.5 MB)
Start (93,04), Goal (54,19) (1.7 MB)
Start (24,13), Goal (63,47) (3.2 MB)
Start (80,60), Goal (80,50) (0.5 MB)
Start (93,04), Goal (54,19) (1.7 MB)
Notations:
References: ●
target point ○
nearest RRT vertex ●
new vertices in the RRT.
1. LaValle, Steven M. Planning algorithms . Pages - 228-236 Cambridge university press, 2006.
2. LaValle, Steven M. Rapidly-exploring random trees: A new tool for path planning. (1998).
3. Kuffner, James J., and Steven M. LaValle. RRT-connect: An efficient approach to single-query path planning. International Conference on Robotics and Automation, Vol. 2. IEEE, 2000.