From Configuration-Space Clearance to Feature-Space Margin: Sample Complexity in Learning-Based Collision Detection

Aviv Tamar; Kiril Solovey; Oren Salzman; Sapir Tubul

REVIEW 3 major objections 4 minor 37 references

From Configuration-Space Clearance to Feature-Space Margin: Sample Complexity in Learning-Based Collision Detection

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that learned collision detection can carry a statistical guarantee: a bounded number of labeled configurations suffices to certify a misclassification rate below any target ε.

desk verdict A genuinely new clearance-to-margin construction, but the paper's central guarantee rests on a monotonicity claim that its own sample-complexity formula contradicts. read the letter →

arxiv 2502.04170 v1 pith:Z64WN3RZ submitted 2025-02-06 cs.RO

Sapir Tubul , Aviv Tamar , Kiril Solovey , Oren Salzman This is my paper · ORCID

classification cs.RO

keywords samplecomplexitysupportvectormachinescollisiondetectionmotionplanningclearancemarginconfigurationspacestatisticalguarantees

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Motion planning relies on fast collision checks, and learned collision detectors trained with SVMs promise to speed them up, but until now there has been no theory saying how much data is enough or how often the learned classifier will be wrong. This paper tries to close that gap by proving a sample-complexity bound for a hard-margin SVM whose feature vectors are derived from the robot's configuration-space clearance. The main claim is that for any desired error $\varepsilon$ and confidence $1-\xi$, there is a labeled sample size, explicitly bounded in Eq. (2), that yields an LCD whose 0-1 error on the $\delta$-interior of the configuration space is at most $\varepsilon$. The paper then builds an adaptive algorithm that claims to extend this guarantee from the $\delta$-interior to the whole configuration space, so a user receives a collision detector with a statistical contract: misclassification probability at most $\varepsilon$, with confidence at least $1-\xi$.

What carries the argument

The load-bearing construction is the feature map $\phi^\sigma$ (Eq. 1): overlay a grid of $n^d$ cells on the unit cube $[0,1]^d$, and for each cell center $c_i$ define $h_i(x) = \exp(-\|c_i-x\|^2/\sigma^2)$, so $\phi(x)$ is the vector of a configuration's influence on every cell. Theorem 1 labels each cell free, forbidden, or boundary, and builds a separating direction $\alpha$ from those labels; the margin bound follows because a point in the $\delta$-interior is dominated by its own cell's feature and the neighboring opposite-class cells are at least roughly $1.5\delta$ away. This clearance-to-margin transfer is what lets the authors recycle SVM margin theory to obtain Eq. (2). Algorithm 1 then combines that sample-complexity check (condition C2) with a binomial-proportion estimate of the $\delta$-interior's size (condition C1), and Algorithm 2's loop is the mechanism intended to turn the interior guarantee into an all-of-configuration-space guarantee.

What would settle it

Take a C-space with a known obstacle ball, choose $\varepsilon$ and $\xi$, and instrument Algorithm 2 to record at each iteration whether conditions (C1) and (C2) hold. If there is an iteration where a pair $(\delta,m)$ succeeds but the next pair $(\delta/2,2m)$ fails condition (C2), the monotonicity assumption behind Lemma 2 is false and the algorithm is not guaranteed to terminate; this is a direct calculation from Eq. (2) and the environment's volume function.

Watch

Extended reading notes

Core claim

The paper's central discovery is a bridge between two notions of separation: clearance, the Euclidean distance from a configuration to the boundary between free and forbidden space, and margin, the distance between classes in the SVM's feature space. Theorem 1 constructs a feature map $\phi^\sigma$ whose coordinates are Gaussian bumps centered on a grid over the configuration space, and proves that configurations with clearance at least $\delta$ are linearly separable in that feature space with margin $\gamma^* \ge 8/(9^{9/8} n^{5d/8})$ when $n = \sqrt{d}/\delta$. Feeding this margin into a standard SVM sample-complexity theorem yields Eq. (2), which bounds the number of labeled samples needed to learn the $\delta$-interior to accuracy $\varepsilon$ at confidence $1-\xi$. Algorithm 1 uses this bound, plus an estimate of how much of the configuration space lies in the $\delta$-interior, to filter training samples; Lemma 1 states that good parameters always exist; and Lemma 2 states that Algorithm 2, which repeatedly halves $\delta$ and doubles $m$, terminates and returns an LCD with the requested global error guarantee.

Load-bearing premise

Algorithm 2 is promised to terminate because the paper assumes that 'smaller clearance plus more samples' is always at least as good as a working pair; if that monotonicity fails, the loop may never find a feasible pair.

Editorial extensions

If this is right

For any clear obstacle geometry and any requested $(\varepsilon, \xi)$, the theory identifies a finite dataset size that is sufficient in the worst case for a hard-margin SVM collision classifier to meet the error bound on the $\delta$-interior.
The explicit bound $m_{X_\delta}(\varepsilon,\xi) \le \frac{1}{\varepsilon^2}\left[\frac{9^9}{4^4}\left(\frac{\sqrt{d}}{\delta}\right)^{9d/4} + 8\ln\frac{2}{\xi}\right]$ tells practitioners how data requirements scale with dimension, clearance, and confidence: exponentially in $d$ and in inverse clearance, but only logarithmically in $1/\xi$.
If Lemma 2's guarantee holds, a planner can replace exact collision checks with the returned LCD and know that a random query from the same distribution is misclassified with probability at most $\varepsilon$, at confidence level $1-\xi$.
The framework opens a path to end-to-end probabilistic path guarantees: a planner could aggregate per-configuration error probabilities over a planned sequence and certify collision-freeness with high probability.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The monotonicity premise in Lemma 2 is the point to attack first: the bound in Eq. (2) suggests the required sample count grows like $\delta^{-9d/4}$, while Algorithm 2 only doubles $m$ each time $\delta$ is halved, so a direct verification on a simple environment would either confirm termination or reveal an infinite loop.
The feature vector's dimension is $n^d = (\sqrt{d}/\delta)^d$, so the same geometry that gives the margin also drives the sample bound's exponential cost; a practical route to usable guarantees will need a lower-dimensional or kernel-based feature map that preserves the clearance-to-margin link.
The guarantee is distribution-dependent: the paper notes that training and testing must draw from the same distribution over configurations, so applying the LCD inside a planner that samples non-uniformly, such as near obstacles or along edges, requires reweighting or a new analysis.
A concrete falsifiable test is to instantiate Algorithm 2 on a 2D or 3D disk-in-box environment and check whether halving $\delta$ and doubling $m$ always keeps condition (C2) satisfied; if not, Lemma 2's claim of finite termination does not follow from the stated bounds.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my read. The core idea is new and worth taking seriously: encode the configuration space with a Gaussian grid feature map, turn clearance into feature-space margin, and then apply standard SVM sample-complexity theory. I believe this is the first formal sample-complexity analysis for learned collision detection, and Eq. (2) is a concrete, unfitted bound. The authors are also honest about its exponential dependence on dimension and inverse clearance.

But two proof gaps break the advertised guarantee, and I agree with the stress-test note that the second one is decisive.

First, Theorem 1's cell-labeling function g in Appendix B is not well-defined. With n = sqrt(d)/delta, each grid cell has diameter delta, so a cell can contain a point with clearance exactly delta and, on the other side of the boundary, a forbidden point. The definition of g then assigns both +1 and -1 to that cell. The claim that every cell is homogeneous is false for cells straddling the boundary. This might be fixable—label straddling cells 0 and rework the constants—but the proof as written does not go through.

Second, and more seriously, Lemma 2's convergence proof assumes monotonicity: if (delta', m') satisfies Lemma 1, then any delta <= delta' and m >= m' also works. That is contradicted by the paper's own Eq. (2), where the required sample count grows like delta^{-9d/4}. Algorithm 2 keeps m * delta constant along its search, so as delta shrinks, the available sample size grows only linearly in 1/delta while the requirement grows faster. The search can walk out of the feasible region and never terminate. The proof gives no argument that the specific curve m = m0 * delta0 / delta intersects the feasible set, and in general it need not. So the statistical guarantee for Algorithm 2 is not established.

The experiments are illustrative only and do not test the convergence claim, so they do not rescue this.

Who is this for? A theory-minded robotics or ML reader curious about what guarantees are possible for learned collision detection. I would send this to a serious referee rather than desk-reject it: the construction is novel, the flaws are pinpointable, and a corrected cell labeling plus a different search schedule could plausibly salvage the framework. But as it stands, the paper's central promise—an algorithm that always terminates with a guaranteed LCD—is unsupported. I would not accept the current version.

Referee Report

3 major / 4 minor

Summary. The paper studies learned collision detection (LCD) in robot motion planning. The authors define a Gaussian feature map over a grid discretization of the configuration space, prove (Theorem 1) that clearance in configuration space implies a margin in feature space, and use a standard hard-SVM generalization bound to derive an explicit sample-complexity estimate (Theorem 2, Eq. (2)) for classification over the δ-interior. They then propose Algorithm 1, which trains an SVM on samples with clearance exceeding δ and fails when the tolerable interior error or sample count is insufficient, and Algorithm 2, which iteratively halves δ and doubles m until Algorithm 1 succeeds. The headline claim (Lemma 2) is that for every ε>0 and confidence 1−ξ, Algorithm 2 terminates and returns an LCD whose 0-1 error on a random configuration from X is at most ε with confidence at least 1−ξ.

Significance. If the proof gaps could be closed, the paper would supply a rare formal connection between geometric clearance and feature-space margin for a practical collision-detection surrogate, with an explicit sample-complexity formula rather than an order-of-magnitude statement. The analysis is not circular: Theorem 2 is derived from an external SVM generalization theorem together with the new margin construction, no constants are fit to data, and the feature-map parameters are set analytically from δ. The paper also candidly acknowledges the exponential dependence on d and 1/δ as a limitation. These strengths make the contribution potentially valuable. However, the central termination guarantee is currently unsupported because of the failure of the monotonicity assertion in Lemma 2, and Theorem 1's proof contains a false cell-homogeneity claim; both must be repaired before the advertised guarantees can be relied upon.

major comments (3)

[Sec. V-B, Lemma 2] The proof of Lemma 2 rests on the assertion that if (δ′,m′) satisfies Lemma 1 then 'the same guarantees hold for any δ ≤ δ′ and m ≥ m′'. This monotonicity is false under the paper's own Eq. (2). For fixed ε and ξ, the value of m_{Xδ}(εXδ,ξ) used in condition (C2) diverges like δ^{-9d/4} as δ→0 (εXδ tends to ε as the empirical interior probability p̂ tends to 1). Algorithm 2 updates m←2m and δ←δ/2, so mδ is invariant. Thus after enough halvings the available number of interior samples, O(m) = O(1/δ), is smaller than the threshold m_{Xδ} that Algorithm 1 itself tests, and condition (C2) fails permanently; the loop never terminates. Even if some feasible pair exists (Lemma 1), the proof does not show that the particular curve m = m0δ0/δ intersects the feasible region. The termination and correctness guarantee for Algorithm 2 is therefore not established, and this is the main advertised contribution of the paper.
[Appendix B, Eq. (5), proof of Theorem 1] The definition g(i)=+1 if there exists x∈CELL_i with f(x)=+1 and g(i)=-1 if there exists x∈CELL_i with f(x)=-1 is claimed to be well defined because no cell can contain both a free and a forbidden configuration. This is not correct for cells crossing the free/forbidden boundary: such a cell may contain both classes, and the two configurations can have clearance exactly δ and lie at opposite corners at distance equal to the cell diameter δ=√d/n. The proof needs a repair, for example by defining labels only for cells that intersect Xδ and by choosing n strictly larger than √d/δ (or using a strict-clearance convention) to guarantee a positive separation between opposite-class points in a cell.
[Sec. V-A, Lemma 1 and Eq. (3)] Lemma 1 establishes existence of some feasible pair (δ*, m*), but it does not provide the monotonicity needed by Lemma 2; in fact, the proof's choice m* := max(κ1, κ2) is tailored to the single clearance value δ* and does not imply that the same m* works for smaller δ. The divergence of Eq. (2) as δ→0 is precisely what makes the transition from Lemma 1 to Lemma 2 fail. A revised argument should either choose m as a function of δ according to Eq. (2) or prove that the feasible region is visited by the search schedule; neither is currently supplied.

minor comments (4)

[References] References [17] and [24] are the same paper (Das and Yip, 'Forward kinematics kernel for improved proxy collision checking') and should be merged or one removed.
[Acknowledgments] The acknowledgments spell the first author's name as 'S. Tubbul'; this appears to be a typo for 'S. Tubul' and should be corrected.
[Fig. 2(c) caption] The caption says 'the boundary between Xforb and Xforb dashed', which appears to be a typo; presumably it should refer to the boundary between Xfree and Xforb.
[Eq. (2) and Sec. IV-C] The constant 9^9/4^4 in Eq. (2) is not derived in the main text; adding a pointer to the appendix computation would help readers verify the algebra.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sample-complexity bound follows from an explicit margin construction and an external SVM generalization theorem.

full rationale

The paper's derivation chain is not circular. Theorem 1 constructs a unit vector alpha from the cell labeling g and proves an explicit margin lower bound by direct algebraic estimates on the Gaussian feature map; the bound follows from the chosen n and sigma and does not assume the target sample-complexity result. Theorem 2 combines this margin with the external SVM generalization bound from Shalev-Shwartz and Ben-David [21, Thm. 15.4], an independent textbook result; no constants are fitted to data and no target error bound is inserted as an input. Lemma 1 chooses delta* and m* to satisfy conditions (C1) and (C2) in Algorithm 1; its proof explicitly sets m* >= kappa2 = 4 m_{X_delta*}(epsilon_X_delta*, xi)/(4(1-epsilon)+3Delta*), which is a constructive existence argument rather than an assumption of the conclusion, and kappa2 is finite because Eq. (2) is finite. Lemma 2's claimed monotonicity for delta and m may be mathematically questionable, and the concern that the invariant m*delta can outrun the delta^{-9d/4} growth in Eq. (2) is a possible correctness gap if valid, but it is not a circularity: it does not reduce the statistical guarantee to a fitted value or to a self-citation. Self-citations in the references ([8], [31], [32]) are related-work citations and are not load-bearing for the sample-complexity bound. The paper itself flags the exponential dependence of Eq. (2) in Sec. VII as a performance limitation, which is an honest acknowledgment rather than a circular step. Therefore no pattern of self-definition, fitted-input prediction, or imported uniqueness is present; score 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No fitted parameters are used in the theory; n and sigma are set analytically from delta. The Gaussian-grid feature map is a mathematical construction, not a postulated physical entity. The axioms listed include external learning-theory results, the hypercube C-space assumption, the availability of a clearance oracle, the validity of the normal approximation, and the homogeneity of grid cells.

assumptions (5)

standard math Hard-SVM generalization bound of Shalev-Shwartz and Ben-David Thm. 15.4 applies to the constructed feature space with margin gamma and radius rho.
Invoked in Appendix C, Eq. (6), as the foundation of the sample-complexity bound. The bound is external and assumed correct.
domain assumption The configuration space is an axis-aligned unit hypercube X = [0,1]^d with Euclidean distance.
Assumed in Section IV-A to define grid cells and clearance; restricts generality.
domain assumption An exact collision detector can also compute clearance cl(s) for any sampled configuration.
Algorithm 1 Line 2 uses CD.cl(s) to filter the delta-interior; many collision checkers only return a boolean and do not provide clearance.
standard math The normal approximation to the binomial proportion is valid for the sample sizes used in Algorithm 1.
Lemma 3 in Appendix A relies on the central limit theorem; the condition m * min(p, 1-p) >= 5 is not checked in Algorithm 1 or Lemma 1.
ad hoc to paper For any grid cell, defining g(i) by the existence of any free or forbidden point yields a unique label.
Appendix B Eq. (5) needs every cell to be homogeneous, but cells straddling the free/forbidden boundary can contain both labels if none of their points have clearance at least delta.

how reviews work

0 comments

Cite this review

Pith. "Pith review of From Configuration-Space Clearance to Feature-Space Margin: Sample Complexity in Learning-Based Collision Detection." pith.science (2026). https://pith.science/paper/Z64WN3RZ

@misc{pith2026250204170,
  author       = {Pith},
  title        = {Pith review of: From Configuration-Space Clearance to Feature-Space Margin: Sample Complexity in Learning-Based Collision Detection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z64WN3RZ}},
  note         = {Machine review of arXiv:2502.04170}
}

read the original abstract

Motion planning is a central challenge in robotics, with learning-based approaches gaining significant attention in recent years. Our work 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 theory 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. Our work bridges this gap by analyzing the sample complexity of an SVM classifier for learning-based collision detection in motion planning. We bound 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 also provide statistical guarantees on the algorithm's error in classifying robot configurations as collision-free or not.

Figures

Figures reproduced from arXiv: 2502.04170 by the authors.

**Figure 2.** Illustration of the learning process for the C-space visualized [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** Trends between key parameters in our framework. (a) The δ [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 32 canonical work pages

[1]

S. M. LaValle, Planning algorithms . Cambridge university press, 2006

2006
[2]

Algorithmic motion plan- ning,

D. Halperin, O. Salzman, and M. Sharir, “Algorithmic motion plan- ning,” in Handbook of Discrete and Computational Geometry, 3rd ed., J. E. G. Csaba D. Toth, Joseph O’Rourke, Ed. CRC Press, Inc., 2017, ch. 50, pp. 1307–1338

work page 2017
[3]

Latombe, Robot motion planning

J.-C. Latombe, Robot motion planning. Springer Science & Business Media, 2012, vol. 124

work page 2012
[4]

Sampling-based algorithms for optimal motion planning,

S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” Int. J. Robotics Research (IJRR) , vol. 30, no. 7, pp. 846–894, 2011

work page 2011
[5]

Sampling-based robot motion planning: A review,

M. Elbanhawi and M. Simic, “Sampling-based robot motion planning: A review,” IEEE Access, vol. 2, pp. 56–77, 2014

2014
[6]

CHOMP: co- variant hamiltonian optimization for motion planning,

M. Zucker, N. D. Ratliff, A. D. Dragan, M. Pivtoraiko, M. Klingen- smith, C. M. Dellin, J. A. Bagnell, and S. S. Srinivasa, “CHOMP: co- variant hamiltonian optimization for motion planning,” Int. J. Robotics Research (IJRR), vol. 32, no. 9-10, pp. 1164–1193, 2013

work page 2013
[7]

Single- and dual-arm motion planning with heuristic search,

B. J. Cohen, S. Chitta, and M. Likhachev, “Single- and dual-arm motion planning with heuristic search,” Int. J. Robotics Research (IJRR), vol. 33, no. 2, pp. 305–320, 2014

work page 2014
[8]

Sampling-based robot motion planning,

O. Salzman, “Sampling-based robot motion planning,” Commun. ACM, vol. 62, no. 10, pp. 54–63, 2019

work page 2019

Show all 37 references

[9]

Lazy collision checking in asymptotically-optimal motion planning,

K. Hauser, “Lazy collision checking in asymptotically-optimal motion planning,” in IEEE Int. Conf. Robotics and Automation (ICRA) , 2015, pp. 2951–2957

2015
[10]

Proba- bilistic roadmaps for path planning in high-dimensional configuration spaces,

L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Proba- bilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robotics (TRO) , vol. 12, no. 4, pp. 566–580, 1996

1996
[11]

Randomized kinodynamic plan- ning,

S. M. LaValle and J. J. Kuffner Jr, “Randomized kinodynamic plan- ning,” Int. J. Robotics Research (IJRR) , vol. 20, no. 5, pp. 378–400, 2001

2001
[12]

A unifying formalism for shortest path problems with expensive edge evaluations via lazy best-first search over paths with edge selectors,

C. M. Dellin and S. S. Srinivasa, “A unifying formalism for shortest path problems with expensive edge evaluations via lazy best-first search over paths with edge selectors,” in Int. Conf. on Automated Planning and Scheduling (ICAPS) , 2016, pp. 459–467

2016
[13]

Gen- eralized lazy search for robot motion planning: Interleaving search and edge evaluation via event-based toggles,

A. Mandalika, S. Choudhury, O. Salzman, and S. S. Srinivasa, “Gen- eralized lazy search for robot motion planning: Interleaving search and edge evaluation via event-based toggles,” in Int. Conf. on Automated Planning and Scheduling (ICAPS) , 2019, pp. 745–753

2019
[14]

Learning-based proxy collision detection for robot motion planning applications,

N. Das and M. Yip, “Learning-based proxy collision detection for robot motion planning applications,” IEEE Trans. Robotics (TRO) , 2020

2020
[15]

DiffCo: Autodifferentiable proxy collision detection with multiclass labels for safety-aware trajectory optimization,

Y . Zhi, N. Das, and M. C. Yip, “DiffCo: Autodifferentiable proxy collision detection with multiclass labels for safety-aware trajectory optimization,” IEEE Trans. Robotics (TRO) , vol. 38, no. 5, pp. 2668– 2685, 2022

2022
[16]

Collisiongp: Gaussian process-based collision checking for robot motion planning,

J. Mu ˜noz, P. Lehner, L. E. Moreno, A. Albu-Sch ¨affer, and M. A. Roa, “Collisiongp: Gaussian process-based collision checking for robot motion planning,” IEEE Robotics and Automation Letters (RAL), vol. 8, no. 7, pp. 4036–4043, 2023

2023
[18]

Neural collision clearance estimator for batched motion planning,

J. Chase Kew, B. Ichter, M. Bandari, T.-W. E. Lee, and A. Faust, “Neural collision clearance estimator for batched motion planning,” in Workshop on the Algorithmic Foundations of Robotics (WAFR) . Springer, 2020, pp. 73–89

2020
[19]

A survey of learning-based robot motion planning,

J. Wang, T. Zhang, N. Ma, Z. Li, H. Ma, F. Meng, and M. Q.-H. Meng, “A survey of learning-based robot motion planning,”IET Cyber- Systems and Robotics , vol. 3, no. 4, pp. 302–314, 2021

2021
[20]

A survey on the integration of machine learning with sampling-based motion planning,

T. McMahon, A. Sivaramakrishnan, E. Granados, K. E. Bekris et al., “A survey on the integration of machine learning with sampling-based motion planning,” Foundations and Trends® in Robotics, vol. 9, no. 4, pp. 266–327, 2022

2022
[21]

Shalev-Shwartz and S

S. Shalev-Shwartz and S. Ben-David, Understanding machine learn- ing: From theory to algorithms . Cambridge university press, 2014

2014
[22]

Cristianini, An Introduction to Support Vector Machines and other kernel-based learning methods

N. Cristianini, An Introduction to Support Vector Machines and other kernel-based learning methods . Cambridge University Press, 2000

2000
[23]

Active learning literature survey,

B. Settles, “Active learning literature survey,” 2009

2009
[24]

Forward kinematics kernel for improved proxy collision checking,

N. Das and M. C. Yip, “Forward kinematics kernel for improved proxy collision checking,” IEEE Robotics and Automation Letters (RAL) , vol. 5, no. 2, pp. 2349–2356, 2020

2020
[25]

Reducing collision checking for sampling-based motion planning using graph neural networks,

C. Yu and S. Gao, “Reducing collision checking for sampling-based motion planning using graph neural networks,” in Neural Information Processing Systems (NEURIPS) , vol. 34, 2021, pp. 4274–4289

2021
[26]

Graph neural networks: A review of methods and applications,

J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun, “Graph neural networks: A review of methods and applications,” AI open, vol. 1, pp. 57–81, 2020

2020
[27]

Learning-based motion planning in dynamic environments using GNNs and temporal encoding,

R. Zhang, C. Yu, J. Chen, C. Fan, and S. Gao, “Learning-based motion planning in dynamic environments using GNNs and temporal encoding,” in Advances in Neural Information Processing Systems , S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, Eds., vol. 35. Cur...

2022
[28]

Configuration space distance fields for manipulation planning,

Y . Li et al. , “Configuration space distance fields for manipulation planning,” in Proceedings of the Robotics: Science and Systems Conference (RSS), 2024

2024
[29]

Neural joint space implicit signed distance functions for reactive robot manipulator control,

M. Koptev, N. Figueroa, and A. Billard, “Neural joint space implicit signed distance functions for reactive robot manipulator control,”IEEE Robotics and Automation Letters , vol. 8, no. 2, pp. 480–487, 2022

2022
[30]

V . N. Vapnik, Uniform convergence of relative frequencies of events to their probabilities . Springer, Cham, 2015

2015
[31]

Sample complexity of prob- abilistic roadmaps via ϵ-nets,

M. Tsao, K. Solovey, and M. Pavone, “Sample complexity of prob- abilistic roadmaps via ϵ-nets,” in IEEE International Conference on Robotics and Automation . IEEE, 2020, pp. 2196–2202

2020
[32]

Near-optimal multi-robot motion planning with finite sampling,

D. Dayan, K. Solovey, M. Pavone, and D. Halperin, “Near-optimal multi-robot motion planning with finite sampling,” IEEE Trans. Robotics, vol. 39, no. 5, pp. 3422–3436, 2023

2023
[33]

Towards practical finite sample bounds for motion planning in TAMP,

S. Shaw, A. Curtis, L. P. Kaelbling, T. Lozano-P ´erez, and N. Roy, “Towards practical finite sample bounds for motion planning in TAMP,” CoRR, vol. abs/2407.17394, 2024

2024 arXiv
[34]

Integrated task and motion plan- ning,

C. R. Garrett, R. Chitnis, R. M. Holladay, B. Kim, T. Silver, L. P. Kaelbling, and T. Lozano-P ´erez, “Integrated task and motion plan- ning,” Annual Review of Control, Robotics, and Autonomous Systems , vol. 4, pp. 265–293, 2021

2021
[35]

Wackerly, W

D. Wackerly, W. Mendenhall, and R. L. Scheaffer, Mathematical Statistics with Applications, 7th ed. Belmont, CA: Cengage Learning, 2008

2008
[36]

Approximate is better than “exact

A. Agresti and B. A. Coull, “Approximate is better than “exact” for in- terval estimation of binomial proportions,” The American Statistician , vol. 52, no. 2, pp. 119–126, 1998

1998
[37]

Confidence intervals for a binomial proportion and asymptotic expansions,

L. D. Brown, T. T. Cai, and A. Dasgupta, “Confidence intervals for a binomial proportion and asymptotic expansions,” The Annals of Statistics, vol. 30, no. 1, pp. 160–201, 2002

2002
[38]

Interval estimation for a binomial proportion,

——, “Interval estimation for a binomial proportion,” Statistical Science, vol. 16, no. 2, pp. 101–133, 2001. APPENDIX A. Statistics We present a fundamental result in statistics that will be important in our analysis which is based on a normal approximation of the binomial dis...

2001

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

S. M. LaValle, Planning algorithms . Cambridge university press, 2006

2006

[2] [2]

Algorithmic motion plan- ning,

D. Halperin, O. Salzman, and M. Sharir, “Algorithmic motion plan- ning,” in Handbook of Discrete and Computational Geometry, 3rd ed., J. E. G. Csaba D. Toth, Joseph O’Rourke, Ed. CRC Press, Inc., 2017, ch. 50, pp. 1307–1338

work page 2017

[3] [3]

Latombe, Robot motion planning

J.-C. Latombe, Robot motion planning. Springer Science & Business Media, 2012, vol. 124

work page 2012

[4] [4]

Sampling-based algorithms for optimal motion planning,

S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” Int. J. Robotics Research (IJRR) , vol. 30, no. 7, pp. 846–894, 2011

work page 2011

[5] [5]

Sampling-based robot motion planning: A review,

M. Elbanhawi and M. Simic, “Sampling-based robot motion planning: A review,” IEEE Access, vol. 2, pp. 56–77, 2014

2014

[6] [6]

CHOMP: co- variant hamiltonian optimization for motion planning,

M. Zucker, N. D. Ratliff, A. D. Dragan, M. Pivtoraiko, M. Klingen- smith, C. M. Dellin, J. A. Bagnell, and S. S. Srinivasa, “CHOMP: co- variant hamiltonian optimization for motion planning,” Int. J. Robotics Research (IJRR), vol. 32, no. 9-10, pp. 1164–1193, 2013

work page 2013

[7] [7]

Single- and dual-arm motion planning with heuristic search,

B. J. Cohen, S. Chitta, and M. Likhachev, “Single- and dual-arm motion planning with heuristic search,” Int. J. Robotics Research (IJRR), vol. 33, no. 2, pp. 305–320, 2014

work page 2014

[8] [8]

Sampling-based robot motion planning,

O. Salzman, “Sampling-based robot motion planning,” Commun. ACM, vol. 62, no. 10, pp. 54–63, 2019

work page 2019