Fast Sampling-Based Cost-Aware Path Planning With Nonmyopic Extensions Using Cross Entropy

Abstract

This paper presents a cost-effective motion-planning method for robots operating in complex and realistic environments. While sampling-based path-planning algorithms, such as a rapidly exploring random tree (RRT) and its variants, have been highly effective for general path-planning problems, it is still difficult to find the minimum cost path in a complex space efficiently since RRT-based algorithms extend a search tree locally, requiring a large number of samples before finding a good solution. This paper presents an efficient nonmyopic path-planning algorithm by combining RRT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> and a stochastic optimization method, called cross entropy. The proposed method constructs two RRT trees: The first tree is a standard RRT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> tree, which is used to determine the nearest node in the tree to be extended to a randomly chosen point, and the second tree contains the first tree with additional long extensions. By maintaining two separate trees, we can grow the search tree nonmyopically to improve the efficiency of the algorithm while ensuring the asymptotic optimality of RRT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> . From an extensive set of simulations and experiments using mobile and humanoid robots, we demonstrate that the proposed method consistently finds low-cost paths faster than the existing algorithms.