Estimated Informed Anytime Search for Sampling-Based Planning via Adaptive Sampler

摘要

Path planning in robotics often involves solving continuously valued, high-dimensional problems. Popular informed approaches include graph-based searches, such as A*, and sampling-based methods, such as Informed RRT*, which utilize informed set and anytime strategies to expedite path optimization incrementally. Informed sampling-based planners define informed sets as subsets of the problem domain based on the current best solution cost. However, when no solution is found, these planners re-sample and explore the entire configuration space, which is time-consuming and computationally expensive. This article introduces Multi-Informed Trees (MIT*), a novel planner that constructs estimated informed sets based on prior admissible solution costs before finding the initial solution, thereby accelerating the initial convergence rate. Moreover, MIT* employs an adaptive sampler that dynamically adjusts the sampling strategy based on the exploration process. Furthermore, MIT* utilizes length-related adaptive sparse collision checks to guide lazy reverse search. These features enhance path cost efficiency and computation times while ensuring high success rates in confined scenarios. Through a series of simulations and real-world experiments, it is confirmed that MIT* outperforms existing single-query, sampling-based planners for problems in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {R}^{4}$ </tex-math></inline-formula> to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {R}^{16}$ </tex-math></inline-formula> and has been successfully applied to real-world robot manipulation tasks. A video showcasing our experimental results is available at: <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://youtu.be/30RsBIdexTU</uri> Note to Practitioners—The motivation for this work stems from the challenges faced by existing informed path planners in high-dimensional, continuously valued environments, particularly when an initial feasible solution is difficult to find. Traditional asymmetric bidirectional planners rely on the best current solution to define problem subsets. When a lazy path has been found through lazy reverse search, these planners tend to re-sample and explore the entire problem space, which could hinder the path planning process. Our proposed MIT* algorithm addresses this issue by constructing an estimated informed set based on prior admissible solution costs before finding the initial solution. This estimated set helps to narrow the search area, thereby accelerating the initial convergence rate. MIT* also integrates an adaptive sampling strategy that dynamically adjusts based on the ongoing exploration process, enhancing the planner’s ability to efficiently navigate through challenging spaces. Furthermore, MIT* employs adaptive sparse collision checks, which guide the lazy reverse search that balances computational efficiency with accuracy in pathfinding. The proposed algorithm can be applied to industrial robots, humanoid robots, or service robots to achieve efficient path planning.