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

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.

Authors

• Liding Zhang
• Yankun Wei
• Kuanqi Cai
• Zhenshan Bing
• Yuan Meng
• Fan Wu 0015
• Sami Haddadin
• Alois C. Knoll

Keywords

• Uncertainty
• Costs
• Trees (botanical)
• Estimation
• Gaussian distribution
• Planning
• Kernel
• Intelligent robots
• Videos
• Convergence
• Path Planning
• Asymptotic Optimality
• Sampling Bias
• Critical Region
• Critical Areas
• Planning Problem
• Gaussian Mixture Distribution
• Cost Path
• Feasible Path
• Gaussian Kernel
• Active Learning
• State Space
• Convergence Rate
• Morphine
• High Uncertainty
• Kullback-Leibler
• Batch Of Samples
• Shannon Entropy
• Optimal Path
• Fewer Samples
• Rapidly-exploring Random Tree
• Reverse Search
• Free Samples
• Unexplored Area
• Valid Path
• Gaussian Sampling
• Shell Radius
• Forward Search
• Tree Search
• Free Space