Optimal Path Planning in Complex Cost Spaces With Sampling-Based Algorithms

Didier Devaurs (1) , Thierry Simeon (1) , Juan Cortés (1)

1 LAAS-RIS - Équipe Robotique et InteractionS

Sampling-based algorithms for path planning, such as 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. Note to Practitioners—Despite their conceptual simplicity, sampling-based algorithms are very successful at solving complex, high-dimensional path-planning problems. Their underlying principle is to explore the configuration space of a mobile system by sampling it, and to build a graph representing the topology of this space. Sampling-based path planning has traditionally focused on finding feasible (i.e. collision-free) paths, without considering their quality. However, in many applications, it is important to compute high-quality (i.e. low-cost) paths with respect to a cost function defined on the configuration space, which is referred to as cost-space path planning. In recent years, variants of classical sampling-based planners have been developed to explore cost spaces. On another front, other approaches have aimed at finding the optimal (i.e. highest-quality) path with respect to a path-quality criterion, which is referred to as optimal path planning. In this paper, we study a problem to which little work has been devoted, and that encompasses these two paradigms: optimal path planning in a cost space. In this context, the definition of the path-quality criterion is based on the configuration-cost function. To efficiently solve this challenging problem, we propose two new sampling-based algorithms that combine the principles underlying current approaches targeting cost-space and optimal path planning. These two novel algorithms provide the same completeness and optimality guarantees as existing ones, but converge faster toward the optimal path, especially on complex). planning problems. These methods have been evaluated only in simulated environments and many applications (in robotics, automation and other domains) remain to be investigated. Keywords—Optimal path planning, cost space path planning, anytime path planning, sampling-based path planning.

Domaines: Robotique [cs.RO]; Automatique / Robotique

Didier Devaurs, Thierry Simeon, Juan Cortés. Optimal Path Planning in Complex Cost Spaces With Sampling-Based Algorithms. IEEE Transactions on Automation Science and Engineering, 2016, 13 (2), pp.415-424. ⟨10.1109/TASE.2015.2487881⟩. ⟨hal-01231482⟩