RRT Path Planning for Robot Navigation

This project implements Rapidly-exploring Random Tree (RRT) and its optimized variant RRT* algorithms for robot path planning in complex environments. The system enables a mobile robot to autonomously navigate from a starting position to a goal while avoiding obstacles in maps of varying complexity.

Section 1: Path Planning with RRT

The standard RRT algorithm was implemented to find feasible paths through complex environments:

• Random Sampling: The algorithm randomly samples points in the configuration space to explore the environment efficiently.
• Tree Expansion: From the nearest node in the tree, the algorithm attempts to expand toward the sampled point.
• Collision Detection: Implemented an efficient collision checking system using precomputed collision maps to speed up the planning process.

The standard RRT algorithm provides rapid exploration of the configuration space and finds feasible paths quickly, but these paths are typically not optimal in terms of distance or smoothness.

Section 2: Optimal Path Planning with RRT*

The RRT* algorithm improves upon standard RRT by continuously optimizing the tree structure:

• Near-Optimal Paths: RRT* converges to the optimal path as the number of iterations increases.
• Tree Rewiring: After adding a new node, nearby nodes are checked to see if connecting through the new node would reduce their cost.
• Dynamic Ball Radius: The algorithm dynamically adjusts the search radius based on the number of nodes in the tree.

The implementation includes:

• Efficient neighbor searching within a dynamically calculated radius
• Path cost optimization through tree rewiring
• Smooth trajectory generation between nodes

Results and Performance

The implementation was tested on multiple environments:

• Willow Garage Map: A complex office environment with narrow corridors and multiple rooms.
• MyHal Map: A simple environment with various obstacles and open spaces.

Performance metrics:

• RRT* consistently produced shorter, smoother paths compared to standard RRT
• Collision checking optimization resulted in significant performance improvements
• The system successfully navigated through complex environments with narrow passages

Implementation Details

The system was implemented in Python with the following key components:

• Map Processing: Tools for loading and processing occupancy grid maps
• Collision Detection: Efficient collision checking using precomputed maps
• Visualization: Real-time visualization of the planning process using Pygame
• Path Recovery: Extraction of the final path from the constructed tree

This project demonstrates expertise in:

• Sampling-based planning algorithms
• Robot motion planning and control
• Collision detection and avoidance
• Path optimization techniques