Optimal path planning in complex cost spaces with sampling-based algorithms
Devaurs, Didier and Siméon, Thierry and Cortés, Juan (2016) Optimal path planning in complex cost spaces with sampling-based algorithms. IEEE Transactions on Automation Science and Engineering, 13 (2). pp. 415-424. ISSN 1545-5955 (https://doi.org/10.1109/TASE.2015.2487881)
Preview |
Text.
Filename: Devaurs-etal-IEEE-TASE-2016-Optimal-path-planning-in-complex-cost-spaces.pdf
Accepted Author Manuscript Download (1MB)| Preview |
Abstract
Sampling-based algorithms for path planning, such as the Rapidly-exploring Random Tree (RRT), have achieved great success, 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, such as T-RRT, have been proposed to deal with cost spaces: by taking configuration-cost functions into account during the exploration process, they can produce high-quality (i.e., low-cost) paths. Other novel variants, such as RRT, can deal with optimal path planning: they ensure convergence toward the optimal path, with respect to a given path-quality criterion. In this paper, we propose to solve a complex problem encompassing this two paradigms: optimal path planning in a cost space. For that, we develop two efficient sampling-based approaches that combine the underlying principles of RRT∗ and T-RRT. These algorithms, called T-RRT∗ and AT-RRT, offer the same asymptotic optimality guarantees as RRT. 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.
ORCID iDs
Devaurs, Didier ORCID: https://orcid.org/0000-0002-3415-9816, Siméon, Thierry and Cortés, Juan;-
-
Item type: Article ID code: 90242 Dates: DateEvent1 April 2016Published26 October 2015Published Online18 September 2015AcceptedNotes: © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Subjects: Technology > Electrical engineering. Electronics Nuclear engineering Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 14 Aug 2024 09:37 Last modified: 08 Oct 2024 17:15 URI: https://strathprints.strath.ac.uk/id/eprint/90242