Motion Planning (RRT and EST)

2024-03-01T00:00:00Z

This project involved an in-depth exploration of motion planning algorithms, focusing on Rapidly-exploring Random Trees (RRT) and Expansive Space Trees (EST). Through simulations and implementation, I gained a deep understanding of how these algorithms solve complex pathfinding problems in high-dimensional spaces.

Rapidly-exploring Random Trees

In the first part of this project, I developed a rapidly exploring random Trees (RRT) algorithm using Python with Matplotlib and Shapley libraries. To simplify the problem, the algorithm was implemented in a 2D space. I ran experiments to analyze the effects of uniform and goal-directed sampling, comparing the behaviors of each. I did this by adjusting the step size to evaluate its impact on the nodes' density, increasing and decreasing their number. Lastly, I explored the algorithm's behavior when orienting toward the goal only a certain percentage of the time, providing insights into its flexibility and adaptability in different scenarios.

Expansive Space Trees

In this part of the project, I developed an Expansive Spaces Tree Planner (EST) algorithm using Python with Matplotlib and Shapley libraries. This algorithm prioritizes exploring less-visited areas of the configuration space and samples based on the density of nodes. This characteristic enables the EST to cover more of the map and increases the chance of discovering the most optimal path. Additionally, I experimented with adjusting the standard deviation of the sampling distribution, which influenced the path heading and resulted in many behavioral patterns during exploration.