TY - GEN
T1 - Efficient sampling-based approaches to optimal path planning in complex cost spaces
AU - Devaurs, Didier
AU - Siméon, Thierry
AU - Cortés, Juan
PY - 2015/1/1
Y1 - 2015/1/1
N2 - Sampling-based algorithms for path planning have achieved great success during the last 15 years, thanks to their ability to efficiently solve complex highdimensional 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.
AB - Sampling-based algorithms for path planning have achieved great success during the last 15 years, thanks to their ability to efficiently solve complex highdimensional 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.
KW - anytime path planning
KW - cost space path planning
KW - optimal path planning
KW - sampling-based path planning
U2 - 10.1007/978-3-319-16595-0_9
DO - 10.1007/978-3-319-16595-0_9
M3 - Conference contribution book
AN - SCOPUS:84946038481
SN - 9783319165943
SN - 9783319366074
T3 - Springer Tracts in Advanced Robotics
SP - 143
EP - 159
BT - Algorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
A2 - Levent Akin, H.
A2 - Amato, Nancy M.
A2 - Isler, Volkan
A2 - Stappen, A. Frank
PB - Springer
CY - Cham, Switzerland
T2 - 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
Y2 - 3 August 2014 through 5 August 2014
ER -