# Obstacle Aware Sampling for Path Planning

arXiv: https://arxiv.org/abs/2203.04075 · HTML: https://mlsanity.com/paper/2203.04075/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 61 references that are in the map.
- First posted on arXiv 8 Mar 2022.

## Builds on (most cited first, 19 of 19)

- [Provable Filter Pruning for Efficient Neural Networks](https://mlsanity.com/paper/1911.07412/) (2019)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic](https://mlsanity.com/paper/1404.2334/) (2014)
- [Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds](https://mlsanity.com/paper/1804.05345/) (2018)
- [Small-GAN: Speeding Up GAN Training Using Core-sets](https://mlsanity.com/paper/1910.13540/) (2019)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Discrepancy, Coresets, and Sketches in Machine Learning](https://mlsanity.com/paper/1906.04845/) (2019)
- [Coresets for Robust Training of Neural Networks against Noisy Labels](https://mlsanity.com/paper/2011.07451/) (2020)
- [On Coresets for Support Vector Machines](https://mlsanity.com/paper/2002.06469/) (2020)
- [Sets Clustering](https://mlsanity.com/paper/2003.04135/) (2020)
- [Introduction to Coresets: Accurate Coresets](https://mlsanity.com/paper/1910.08707/) (2019)
- [Data-Independent Structured Pruning of Neural Networks via Coresets](https://mlsanity.com/paper/2008.08316/) (2020)
- [One-Shot Coresets: The Case of k-Clustering](https://mlsanity.com/paper/1711.09649/) (2017)
- [Strong Coresets for Hard and Soft Bregman Clustering with Applications to Exponential Family Mixtures](https://mlsanity.com/paper/1508.05243/) (2015)
- [Coresets for Decision Trees of Signals](https://mlsanity.com/paper/2110.03195/) (2021)
- [Balancing Global Exploration and Local-connectivity Exploitation with Rapidly-exploring Random disjointed-Trees](https://mlsanity.com/paper/1810.03749/) (2018)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)

## Built on by (most cited first, 6 of 6)

- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [Dataset Distillation Meets Provable Subset Selection](https://mlsanity.com/paper/2307.08086/) (2023)
- [An Efficient Drifters Deployment Strategy to Evaluate Water Current Velocity Fields](https://mlsanity.com/paper/2301.04216/) (2023)
- [ORBSLAM3-Enhanced Autonomous Toy Drones: Pioneering Indoor Exploration](https://mlsanity.com/paper/2312.13385/) (2023)
- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)

## Abstract (arXiv)

Many path planning algorithms are based on sampling the state space. While this approach is very simple, it can become costly when the obstacles are unknown, since samples hitting these obstacles are wasted. The goal of this paper is to efficiently identify obstacles in a map and remove them from the sampling space. To this end, we propose a pre-processing algorithm for space exploration that enables more efficient sampling. We show that it can boost the performance of other space sampling methods and path planners. Our approach is based on the fact that a convex obstacle can be approximated provably well by its minimum volume enclosing ellipsoid (MVEE), and a non-convex obstacle may be partitioned into convex shapes. Our main contribution is an algorithm that strategically finds a small sample, called the active-coreset, that adaptively samples the space via membership-oracle such that the MVEE of the coreset approximates the MVEE of the obstacle. Experimental results confirm the effectiveness of our approach across multiple planners based on Rapidly-exploring random trees, showing significant improvement in terms of time and path length.