CIT: Context-Based Biased Batch-Sampling for Almost-Surely Asymptotically Optimal Motion Planning

Abstract

This paper introduces Context Informed Trees (CIT*), a sampling-based motion planning algorithm that enhances exploration efficiency by biasing sampling based on uncertainty estimation from local samples and connectivity information obtained during the search process. CIT* is based on Flexible Informed Trees (FIT*) and incorporates three key components: region-based sampling, uncertainty-driven weighting, and connection-greedy prioritization (CGP). It generates regions from sampled states based on local obstacle proximity, assigning weights to these regions using probability uncertainty estimation via kernel density estimation (KDE) classification. To further refine the sampling focus, CGP prioritizes regions that exhibit strong connectivity in previous searches, ensuring that exploration is directed toward unknown and critical areas that have a higher likelihood of contributing to feasible and efficient paths. The sampling process is then guided by a mixture of Gaussian distributions centered on weighted regions, where the weighting biases sampling toward more critical regions, thereby improving search efficiency and accelerating convergence. Benchmark evaluations demonstrate that CIT* improves efficiency by reducing reliance on random sampling, which often leads to slower solution discovery and higher path costs. With biased sampling, CIT* maintains strong performance in solving complex motion planning problems in ${\mathbb{R}^4}$ to ${\mathbb{R}^{16}}$ and has been demonstrated on a real-world manipulation task. A video showcasing our method and experimental results is available at: https://youtu.be/SG2cy9WmjD0.