When using sampling-based motion planners such as PRMs, it is difficult to determine how many samples are required for the PRM to find a solution consistently. This is particularly relevant in Task and Motion Planning (TAMP), where many motion planning problems must be solved sequentially. We attempt to address this problem by proving an upper bound on the number of samples that are sufficient, with high probability, for a radius PRM to find a feasible solution, drawing on prior work in deterministic sampling and sample complexity theory. We also introduce a numerical algorithm that refines the bound based on the proofs of the sample complexity results we leverage. Our experiments show that our numerical algorithm is tight up to two to three orders of magnitude on planar problems for radius PRMs but becomes looser as the problem’s dimensionality increases. The numerical algorithm is empirically more useful as a heuristic for estimating the number of samples needed for a KNN PRM in low dimensions. When deployed to schedule samples for a KNN PRM in a TAMP planner, we also observe improvements in planning time in planar problems. While our experiments show that much work remains to tighten our bounds, the ideas presented in this paper are a step towards a practical sample bound.