Path planning of an autonomous vehicle using the optimized RRT* algorithm

• Grant number: 12/20824-5
• Support type: Scholarships in Brazil - Master
• Effective date (Start): February 01, 2013
• Effective date (End): February 28, 2014
• Field of knowledge: Engineering - Electrical Engineering
• Principal Investigator: Valdir Grassi Junior
• Grantee: Hiparco Lins Vieira
• Home Institution: Escola de Engenharia de São Carlos (EESC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

The application of sample-based techniques in path planning algorithms has become year-by-year more widespread. In this group, one of the most employed algorithms is denominated Rapidly-exploring Random Tree (RRT), which is based on a incremental sampling of configurations to quickly and efficiently compute the robot's path plans while avoiding collision with obstacles. However, the solutions obtained by the RRT are usually far away from the optimal solution. To overcome this problem, a sample-based method, named RRT*, was proposed. One of the advantages of the RRT* is its almost-sure convergence to an optimal solution without provoking substantial computational overhead. Furthermore, RRT* can improve solution before plan execution is complete. One extension of the RRT*, combines the RRT* algorithm with branch-and-bound and committed trajectories algorithms, to enhance its efficiency in real-time applications. In this project, the main purpose is to implement this variation of the RRT* algorithm and apply it in dynamic environments. To develop the robot's software and perform simulations, the Robot Operating System (ROS) will be used as tool, and, as robot platform, the CaRINA (Autonomous Intelligent Vehicle for Autonomous Navigation), project in progress in the Instituto de Ciências Matemáticas e de Computação (ICMC-USP), in an association with the Escola de Engenharia de São Carlos (EESC-USP). (AU)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

VIEIRA, Hiparco Lins. Reduction in the computational cost of the RRT algorithm through optimization by elimination. 2014. Master's Dissertation - Universidade de São Paulo (USP). Escola de Engenharia de São Carlos São Carlos.