Multi-Sets Trees (MST*): Accelerated Asymptotically Optimal Motion Planning Optimization Informed by Multiple Domain Subsets

Abstract

Robotic motion planning faces formidable challenges in constrained environments, particularly in rapidly searching for feasible solutions and converging towards optimal. This study introduces Multi-Sets Tree (MST*), a sampling-based planner designed to accelerate path searching and solution optimization. MST* integrates estimated guided incremental local densification (GuILD) sets that are based on prior estimated solution costs before finding the initial solution. For path optimization, MST* integrates novel beacon selectors to define problem subsets, thereby guiding exploration and effectively exploiting high-potential areas. This multi-set strategy ensures balanced exploration and exploitation, enabling MST* to handle sparse free space. Moreover, MST* utilizes adaptive sampling techniques via Lebesgue’s measure of domain subsets for rapid search. MST* improves search efficiency and path optimality, particularly in constrained high-dimensional environments. It extends the informed sampling concept by refining the search region and batch sampling. Experimental results demonstrate that MST* outperforms single-query planners across ℝ<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> to ℝ<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">16</sup> benchmarks and in real-world robotic navigation tasks. A video showcasing our experimental results is available at: https://youtu.be/obftvS0a41M.