View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        An Overview of the Class of Rapidly-Exploring Random Trees.

        Thumbnail
        View/Open
        ICML.pdf (6.059Mb)
        Publication date
        2018
        Author
        Cardenas Guevara, B.
        Metadata
        Show full item record
        Summary
        In motion planning the objective is to move a robot from one place to another in a possibly constrained environment. There exist exact methods to solve this problem but exact solutions in constrained higher dimensional spaces are in general unfeasible. It has been shown that sampling-based algorithms, such as the Rapidly-Exploring Random Trees (RRT), perform well when solving motion planning problems under certain constraints. A tree is constructed incrementally to search for the goal by taking samples from the state space. The class of RRTs has been shown to be probabilistically complete; it will eventually find a solution as the tree grows. The basic RRT algorithm has been shown to be asymptotically suboptimal, it will almost surely converge to a path of suboptimal cost. RRT* was proposed to overcome this problem and was in turn shown to be asymptotically optimal. Informed RRT* exploited this property by introducing a heuristic that focused the algorithm between the start and the goal. In this paper the theory behind these baseline algorithms, as well as some of their variants, is explained along with their behaviour and properties. Extensive research has been done in the field of RRTs but no updated account exists on the class of RRTs. This paper organises an overarching review of the class of RRTs. Additionally, the three baseline algorithms are compared to each other. From the analysis of this comparison it follows that Informed RRT* converges significantly faster to optimal paths, as opposed to RRT* and RRT. Finally, current issues and assumptions for future research are discussed.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/30507
        Collections
        • Theses
        Utrecht university logo