RRT Path Planning (Rapidly-exploring Random Trees)

Path planning is a fundamental problem in robotics: finding a collision-free path for a robot from a start configuration to a goal configuration in the presence of obstacles.

Unlike grid search algorithms (like A* or Dijkstra) which suffer from the curse of dimensionality, sampling-based path planners build a roadmap of the environment by randomly sampling configurations.

RRT is specifically designed to handle non-holonomic and kinodynamic constraints:

1. Initialize: Start with a tree containing only the start node q_start.
2. Sample: Sample a random configuration q_rand in the configuration space.
3. Extend: Find the nearest node q_near in the tree to q_rand. Extend the tree from q_near towards q_rand by a step size delta to get q_new.
4. Obstacle Check: If the path from q_near to q_new is collision-free, add q_new to the tree.
5. Loop: Repeat until a node is within threshold of q_goal.

RRT* extends RRT by rewiring the tree to minimize path cost. After finding q_new, RRT* searches the neighborhood of q_new for a nearby node q_min that yields the lowest cost to reach q_new. It then re-evaluates nearby nodes to see if routing through q_new reduces their current path cost (rewiring).

Interactive goals: Launch the RRT planner lab. Add obstacles, set the start/goal points, and watch the random tree populate the search space. Compare standard RRT with RRT* optimization to see how path cost decreases over iterations.

CBSE/ICSE CS focus: Analysis of algorithmic time complexity, space complexity of trees, collision check helper routines, and randomized algorithms.