Bidirectional Lazy Informed Trees (BLIT*)

This paper introduces Bidirectional Lazy Informed Trees (BLIT), the first algorithm to incorporate anytime incremental lazy bidirectional heuristic search (Bi-HS) into batch-wise sampling-based motion planning (Bw-SBMP). BLIT operates on batches of informed states (states that can potentially improve the cost of the incumbent solution) structured as an implicit random geometric graph (RGG). The computational cost of collision detection is mitigated via {\em a new lazy edge-evaluation strategy} by focusing on states near obstacles. Experimental results, especially in high dimensions, show that BLIT* outperforms existing Bw-SBMP planners by efficiently finding an initial solution and effectively improving the quality as more computational resources are available.

Recommended citation: Yi Wang, Bingxian Mu, Oren Salzman