Path Planning with A* and RRT

Objective

This assignment is focused on comparing different path planning algorithms, specifically A* and RRT (Rapidly-exploring Random Tree), within the context of the map created in Assignment 5 ( Robot Sensing ). You will analyze the performance of these algorithms, improve the RRT implementation to RRT*, and write detailed unit tests for the improved algorithm.

Tasks

Task 1: Compare A* and RRT Path Planning

Objective: Compare the performance of A* and RRT path planning algorithms in terms of their effectiveness and computational cost using the maze map created in Assignment 5 ( Robot Sensing ).

1. Create the Map of Maze
2. Implement Path Planning:
3. Use the A* algorithm to find a path through the maze
4. Use the RRT algorithm to find a path through the same maze.
5. Compare Performance:
6. Measure and document the computation time and success rate for both algorithms.
7. Analyze the paths generated by A* and RRT in terms of length, smoothness, and efficiency.
8. Document Your Findings:
9. Provide a detailed comparison of A* and RRT, explaining which algorithm works best for the given maze and why.
10. Discuss the computational cost associated with each algorithm and the scenarios where one may be preferred over the other.

Task 2: Improve RRT to RRT* (Star) for Enhanced Performance

Objective: Enhance the RRT algorithm by implementing RRT* (RRT Star)

1. Implement RRT*
2. Modify the existing RRT implementation to RRT*, which includes an optimization step to improve path quality.
3. Test and Compare with A:*
4. Run the RRT* algorithm on the maze created in Module 5 assignment of Maze and compare its performance with both the original RRT and A*.
5. Document any improvements in path optimality, computation time, and overall performance.
6. Document the Implementation:
7. Provide detailed documentation on how RRT* was implemented, including key differences from the original RRT algorithm.
8. Explain why these improvements make RRT* more competitive with A*.

Task 3: Explain and Write Unit Tests for RRT*

Objective: Deepen your understanding of the RRT* algorithm by explaining its workings in detail and writing comprehensive unit tests to ensure its correctness.

1. Detailed Explanation of RRT:*
2. Write a detailed explanation of the RRT* algorithm, focusing on its key concepts such as node re-wiring, cost function optimization, and convergence properties.
3. Develop Unit Tests:
4. Write unit tests for the RRT* implementation to validate its functionality.
5. Ensure the tests cover edge cases such as narrow corridors, dead-ends, and open spaces.
6. Run and Document Test Results:
7. Run the unit tests and document the results, highlighting any issues found and how they were addressed.
8. Discuss the robustness of the RRT* implementation based on the test outcomes.

Submission Process

1. Create Files:
2. Navigate to the module_8_assignment package.
3. Create the required files for the path planning implementations, RRT* improvements, and unit tests.
4. Document Your Work:
5. Create a README.md file in the module_8_assignment package.
6. Provide details about the files you created, including explanations of the code and the commands needed to run your path planning algorithms and tests.
7. Submit Your Assignment:
8. Push your changes to your forked repository.
9. Provide your repository link in the assignment submission text area.
10. Note: Ensure you press the “Start Assignment” button when you see the page (as it takes time to generate the pages).
11. Wait for Review:
12. Wait for the instructors to review your submission.

Learning Outcome

By completing this assignment, you will:

1. Gain a deeper understanding of path planning algorithms and their practical applications in robotics.
2. Learn how to enhance the performance of path planning algorithms by implementing RRT*.
3. Develop skills in writing and running unit tests to ensure the correctness and reliability of your algorithms.