Our paper on cost-aware path planning is accepted to IEEE Transactions on Robotics (T-RO)

[2017.07.10]

The following paper is accepted to the IEEE Transactions on Robotics (T-RO):

  • Fast Sampling-Based Cost-Aware Path Planning with Nonmyopic Extensions Using Cross Entropy by Junghun Suh, Joonsig Gong, and Songhwai Oh
    • 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 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* and a stochastic optimization method, called cross entropy. The proposed method constructs two RRT trees: the first tree is a standard RRT* 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 non-myopically to improve the efficiency of the algorithm while ensuring the asymptotic optimality of RRT*. 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 existing algorithms.
    • Video