Reduction in the computational cost of the RRT algorithm through optimization by elimination

Author(s)

Hiparco Lins Vieira

• Document type: Master's Dissertation
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Escola de Engenharia de São Carlos (EESC/SBD)
• Defense date: 2014-07-15

Examining board members

Valdir Grassi Júnior; Luiz Chaimowicz; Denis Fernando Wolf

• Advisor: Valdir Grassi Júnior

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 widely used algorithms is the Rapidly-exploring Random Tree (RRT), which is based on an incremental sampling of configurations to efficiently compute the robot\'s path while avoiding obstacles. Many efforts have been made to reduce RRT computational costs, targeting, in particular, applications in which quick responses are required, e.g., in dynamic environments. One of the dilemmas posed by the RRT arises from its motion primitives generation. If many primitives are generated to enable the robot to perform a broad range of basic movements, a signicant computational cost is required. On the other hand, when only a few primitives are generated, thus, enabling a limited number of basic movements, the robot may be unable to find a solution to the problem, even if one exists. To address this quandary, an optimized method for primitive generation is proposed. This method is compared with the traditional and random primitive generation methods, considering not only computational cost, but also the quality of local and global solutions that may be attained. The optimized method is applied to the RRT algorithm, which is then used in a case study in dynamic environments. In the study, the modied RRT is evaluated in terms of the computational costs of its planning and replanning. The simulations were developed to access the effectiveness and efficiency of the proposed algorithm. (AU)

• FAPESP's process: 12/20824-5 - Path planning of an autonomous vehicle using the optimized RRT* algorithm
• Grantee: Hiparco Lins Vieira
• Support Opportunities: Scholarships in Brazil - Master