Motion planning is a central challenge in robotics, with learning-based approaches gaining significant attention in recent years. This thesis focuses on a specific aspect of these approaches: using machine-learning techniques, particularly Support Vector Machines (SVM), to evaluate whether robot configurations are collision-free, an operation termed "collision detection". Despite the growing popularity of these methods, there is a lack of theoretical guarantees supporting their efficiency and prediction accuracy. This is in stark contrast to the rich theoretical results of machine-learning methods in general and of SVMs in particular.
This work bridges this gap by analyzing the sample complexity of an SVM classifier for learning-based collision detection in motion planning. We provide a comprehensive theoretical framework that bounds the number of samples needed to achieve a specified accuracy at a given confidence level. This result is stated in terms relevant to robot motion-planning such as the system's clearance.
Building on these theoretical results, we propose a collision-detection algorithm that can provide statistical guarantees on the algorithm's error in classifying robot configurations as collision-free or not. We rigorously prove the correctness of our approach and demonstrate its practical implications through extensive experimental evaluations.
Our findings contribute to the theoretical understanding of learning-based collision detection and provide a foundation for developing more reliable and efficient motion planning algorithms. This work opens up new avenues for integrating machine learning techniques into robotics while maintaining provable performance guarantees.
