Effectiveness Evaluation of Precomputation Search Using Steering Sets

We present a new pruning method for compact precomputed search trees and evaluate the effectiveness and efficiency of our precomputation planning with steering sets. Precomputed search trees are one method for reducing planning time; however, there is a time-memory trade-off. Our PreComputed Search tree (PCS) is built with pruning based on a rule of constant memory, i.e., Maximum Size Pruning method (MSP), which is the preset pruning ratio. UsingMSP, we get a large, reasonably sized precomputed search tree. Applying a Node Selection Strategy (NSS) to MSP, extends the tree’s outer edges and enhances the path reachability. We also checked the dispersion in real 5150m 2 indoor environments, we found the obstacle rate to be 5%. On the uniformed scattered obstacle map with a less than 13% obstacle rate, precomputation planning runtime with steering sets is more than two orders of magnitude faster than the planning without precomputed search trees. With steering sets, our precomputed search tree finds an optimal path at obstacle rate of 12%. Precomputation planning also produces a smooth optimal path speedily in an indoor environment.