Efficient Sampling-Based Approaches to Optimal Path Planning in Complex Cost Spaces

Didier Devaurs, Thierry Siméon, Juan Cortés

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Abstract / Description of output

Sampling-based algorithms for path planning have achieved great success during the last 15 years, thanks to their ability to efficiently solve complex high-dimensional problems. However, standard versions of these algorithms cannot guarantee optimality or even high-quality for the produced paths. In recent years, variants of these methods, taking cost criteria into account during the exploration process, have been proposed to compute high-quality paths (such as T-RRT), some even guaranteeing asymptotic optimality (such as RRT*). In this paper, we propose two new sampling-based approaches that combine the underlying principles of RRT* and T-RRT. These algorithms, called T-RRT* and AT-RRT, offer probabilistic completeness and asymptotic optimality guarantees. Results presented on several classes of problems show that they converge faster than RRT* toward the optimal path, especially when the topology of the search space is complex and/or when its dimensionality is high.
Original languageEnglish
Title of host publication Algorithmic Foundations of Robotics XI
Subtitle of host publicationSelected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics
EditorsH. Levent Akin, Nancy M. Amato, Volkan Isler, A. Frank Stappen
Place of PublicationCham, Switzerland
ISBN (Electronic)9783319165950
ISBN (Print)9783319165943, 9783319366074
Publication statusPublished - 1 Jan 2015

Publication series

Name Springer Tracts in Advanced Robotics
ISSN (Electronic)1610-742X


Dive into the research topics of 'Efficient Sampling-Based Approaches to Optimal Path Planning in Complex Cost Spaces'. Together they form a unique fingerprint.

Cite this