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)

[thumbnail of Devaurs-etal-IEEE-TASE-2016-Optimal-path-planning-in-complex-cost-spaces]
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 logoORCID: https://orcid.org/0000-0002-3415-9816, Siméon, Thierry and Cortés, Juan;
  • Item type:Article
    ID code:90242
    Dates:
    Date
    Event
    1 April 2016
    Published
    26 October 2015
    Published Online
    18 September 2015
    Accepted
    Notes:© 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:01 Sep 2024 01:49
    URI:https://strathprints.strath.ac.uk/id/eprint/90242
CORE (COnnecting REpositories)