Performance Comparison of Classical and Neural Sampling Algorithms for Robotic Navigation

Technical Summary: Performance Comparison of Classical and Neural Sampling Algorithms for Robotic Navigation

Problem Statement
Sampling-based motion planning is fundamental to autonomous systems, including ground robots, UAVs, and self-driving vehicles. While the Rapidly-Exploring Random Tree (RRT) and its optimal variant, RRT*, are widely used for their efficiency in high-dimensional spaces, they suffer from inefficient random sampling. This leads to high computational costs, slow convergence, and suboptimal, jagged paths, particularly in cluttered environments with varying obstacle densities. Although variants like Informed RRT* utilize hand-crafted heuristics (e.g., ellipsoidal sampling) to accelerate convergence, they lack the adaptability to diverse environment structures. Recent machine learning advances suggest that neural networks could bias sampling toward promising regions, yet a unified, controlled evaluation comparing these neural-guided approaches against classical baselines under consistent conditions remains limited.

Methodology
This study implements and compares three algorithms within a unified framework across environments with sparse, medium, and dense obstacle distributions:

1. RRT:* The classical baseline utilizing uniform random sampling and asymptotic optimality via node rewiring.
2. Neural RRT:* An enhancement where the sampling step is guided by a probability map $P(x, y)$ predicted by a trained neural network. Sampling is a weighted mix of the learned distribution and uniform sampling ($x_{rand} \sim \alpha P(x, y) + (1-\alpha)U(X_{free})$).
3. Neural Informed RRT:* A hybrid approach that combines the learned sampling distribution with the geometric constraints of Informed RRT*. After finding an initial feasible path with cost $c_{best}$, sampling is restricted to the intersection of the learned probability map and an ellipsoidal region defined by the start, goal, and $c_{best}$.

Neural Network Architecture and Training
Both neural planners utilize a U-Net-based model with a ResNet-50 encoder-decoder structure. The input is a 224×224 three-channel image encoding the obstacle map, start position, and goal position. The network outputs a dense probability map guiding the sampling process. The model is trained in a supervised manner using a dataset generated by the A* algorithm on random grid maps. The training objective minimizes Dice loss between the predicted probability map and the ground-truth path mask (dilated for robustness). Data augmentation techniques, including random obstacle variations and start-goal repositioning, are employed to ensure generalization.

Key Contributions

• Unified Comparison: The paper provides a controlled, side-by-side evaluation of classical RRT*, Neural RRT*, and Neural Informed RRT* across maps of varying complexity, addressing the lack of consistent benchmarks in existing literature.
• Quantitative Evaluation: Performance is rigorously assessed using four metrics: path length, planning time, path smoothness, and success rate.
• Trade-off Analysis: The study explicitly analyzes the trade-offs between the computational overhead of neural inference and the gains in trajectory quality and convergence efficiency.

Results
Experiments conducted on 50 runs per map type (sparse, medium, dense) yielded the following findings:

• Path Quality: Neural Informed RRT* consistently achieved the shortest path lengths and smoothest trajectories. In dense environments, it demonstrated up to a 14% reduction in path length and 55–75% improvement in smoothness compared to classical RRT*. Neural RRT* also improved path quality over the baseline but to a lesser extent.
• Planning Time: Classical RRT* generally exhibited the fastest planning times, particularly in sparse maps. Neural-guided planners incurred a marginal increase in computation time due to network inference. However, the study notes that this time cost is outweighed by the significant improvements in path optimality and smoothness in complex environments.
• Success Rate: All algorithms maintained a 100% success rate in sparse and medium-density maps. In dense maps, Neural Informed RRT* occasionally dropped to a 90% success rate (attributed to aggressive search space pruning) but still outperformed others in efficiency metrics.

Significance and Claims
The paper claims that integrating AI-based guidance into sampling-based planners significantly enhances the reliability and trajectory efficiency of robotic navigation. The results demonstrate that Neural Informed RRT* offers the best balance between path quality and computation time, making it the most suitable choice for navigation in complex, cluttered environments. While the approach introduces a slight computational overhead, the study concludes that the resulting improvements in path optimality and smoothness justify this cost for real-time applications. The authors position this work as a step toward advancing real-time robotic path planning through the effective integration of learned heuristics with classical optimality guarantees. Future work is proposed to extend these methods to dynamic, three-dimensional environments and real-world robotic applications.