In earlier chapters, you have seen configuration spaces \( \mathcal{C} \), free space \( \mathcal{C}_{\text{free}} \subset \mathcal{C} \) (collision-free configurations), and graph-search-based planners on discretized spaces. For high-degree-of-freedom (DOF) manipulators, regular grids in \( \mathbb{R}^d \) suffer from the curse of dimensionality:

\[ \text{ #grid points } \approx \prod_{i=1}^d \frac{\text{range}_i}{\Delta_i} \]

Even moderate dimension \( d \) and resolution \( \Delta_i \) make exhaustive search impractical. Sampling-based methods instead probe \( \mathcal{C}_{\text{free}} \) with random samples and build a graph or tree \( G_n \) incrementally from \( q_{\text{start}} \) toward \( q_{\text{goal}} \).

A generic sampling-based planner iterates:

• Draw a random configuration \( q_{\text{rand}} \) in \( \mathcal{C} \).
• If \( q_{\text{rand}} \in \mathcal{C}_{\text{free}} \), connect it to nearby samples.
• Search the resulting graph for a path from start to goal.

The central question for this lesson is: if a collision-free path exists, does this randomized procedure find it with probability tending to one as the number of samples grows? This property is what we call probabilistic completeness.

flowchart TD
  A["Query: q_start, q_goal, C_free"] --> B["Initialize graph with q_start"]
  B --> C["Loop: sample random config q_rand"]
  C --> D{"q_rand in free space?"}
  D -->|no| C
  D -->|yes| E["Add q_rand to graph, connect to neighbors"]
  E --> F{"Path from start \nto goal in graph?"}
  F -->|yes| G["Return collision-free path"]
  F -->|no| C
        

This flow is intentionally abstract: specific planners (PRM, RRT, etc.) modify details of the sampling and connection steps, but they share the same conceptual structure.

Let \( \mathcal{C} \) be a configuration space equipped with a probability measure \( \mu \) (often normalized Lebesgue measure on a bounded region). A random sample \( Q \) in \( \mathcal{C} \) is drawn according to a distribution with density strictly positive on \( \mathcal{C}_{\text{free}} \).

Consider a sampling-based planner that after \( n \) samples returns either: \( \texttt{SUCCESS} \) with a path \( \sigma_n \) from \( q_{\text{start}} \) to \( q_{\text{goal}} \), or \( \texttt{FAILURE} \). Let \( F_n \) denote the event “planner fails to find a path after \( n \) samples”.

\[ \text{Planner is probabilistically complete} \quad \Longleftrightarrow \quad \forall\ \text{feasible queries}:\ \lim_{n \to \infty} \mathbb{P}(F_n) = 0. \]

Here “feasible query” means that there exists at least one collision-free path in \( \mathcal{C}_{\text{free}} \) connecting \( q_{\text{start}} \) and \( q_{\text{goal}} \). In practice, we also require some robustness of the solution, captured next.

A continuous path \( \sigma:[0,1]\to \mathcal{C}_{\text{free}} \) has \( \delta \)-clearance if every point on the path can be thickened by a ball of radius \( \delta > 0 \) fully contained in \( \mathcal{C}_{\text{free}} \):

\[ \text{clearance}(\sigma) \ge \delta \quad \Longleftrightarrow \quad \forall t \in [0,1]:\ B(\sigma(t), \delta) \subset \mathcal{C}_{\text{free}}. \]

Probabilistic completeness is typically stated for all queries admitting at least one path with positive clearance. This excludes extremely “needle-like” solutions of zero measure, where random sampling almost surely never hits the feasible set.

The intuitive proof idea behind probabilistic completeness is geometric: a robust path can be covered by a finite number of small balls of positive measure inside \( \mathcal{C}_{\text{free}} \). Independent random samples eventually land in each ball with probability one.

Assume there exists a path \( \sigma:[0,1]\to \mathcal{C}_{\text{free}} \) with clearance \( \delta > 0 \). For any \( 0 < r \le \delta/2 \), we can choose a finite set of parameters \( 0 = t_0 < t_1 < \cdots < t_k = 1 \) so that the balls \( B_i = B(\sigma(t_i), r) \) overlap and form a “thickened tube” along the path. Each ball is fully contained in \( \mathcal{C}_{\text{free}} \).

\[ \mu(B_i) > 0,\quad \mu(\mathcal{C}_{\text{free}}) > 0,\quad i = 0,\dots,k, \]

where \( \mu \) is the volume measure. A planner that:

1. draws i.i.d. samples in \( \mathcal{C} \) with density positive on \( \mathcal{C}_{\text{free}} \), and
2. connects “nearby” samples in a way that respects local collision avoidance,

will succeed once it has at least one sample in each ball \( B_i \), because local connections inside and between neighboring balls lie entirely in free space and can be chained to form a global path.

Let \( p_i = \mu(B_i) / \mu(\mathcal{C}_{\text{free}}) \) be the probability that a single random free configuration lands in ball \( B_i \). The probability that we miss ball \( B_i \) with \( n \) independent samples is:

\[ \mathbb{P}(\text{miss } B_i \text{ after } n \text{ samples}) = (1 - p_i)^n. \]

Using the union bound for the event of missing any ball, we obtain:

\[ \mathbb{P}(\text{some } B_i \text{ missed after } n \text{ samples}) \le \sum_{i=0}^k (1 - p_i)^n \le (k+1)\, (1 - p_{\min})^n, \]

where \( p_{\min} = \min_i p_i > 0 \). Since \( 0 < 1 - p_{\min} < 1 \), we have

\[ \lim_{n \to \infty} (1 - p_{\min})^n = 0 \quad \Longrightarrow \quad \lim_{n \to \infty} \mathbb{P}(\text{some } B_i \text{ missed}) = 0. \]

Therefore, the probability that every ball has been hit tends to one as \( n \to \infty \). Under mild conditions on the local connection strategy (no “shortcuts” through obstacles, bounded step size), this implies probabilistic completeness.

In discrete graph search (e.g., A* on a finite graph), we often demand resolution completeness or algorithmic completeness: for any feasible query, the planner must always eventually find a solution in a finite number of steps.

Probabilistic completeness is weaker but more realistic for high-dimensional spaces:

• A probabilistically complete planner is allowed to fail for a particular finite budget \( n \) of samples, but the failure probability vanishes as \( n \to \infty \).
• Deterministic completeness is impossible for certain configuration spaces under practical constraints, since any finite-resolution grid discretization might “miss” a narrow passage entirely.

PC guarantees are thus asymptotic. In practice, we care about rates such as:

\[ \mathbb{P}(F_n) \le C\, (1 - p_{\min})^n \approx C\, e^{-n p_{\min}}, \]

for some constant \( C \) depending on the covering. The exponent \( p_{\min} \) effectively encodes how “narrow” the most difficult part of the path is: narrow passages lead to very small \( p_{\min} \) and hence slow practical convergence, even though the algorithm is still probabilistically complete.

To make the above argument more concrete, consider the following generic roadmap construction:

1. Draw \( n \) i.i.d. samples in \( \mathcal{C} \).
2. Discard colliding samples; keep only those in \( \mathcal{C}_{\text{free}} \).
3. For each pair of free samples within some fixed radius \( r \), attempt a local collision-free connection (e.g., interpolate linearly in joint space and check for collisions).
4. Add edges for successful local connections to obtain a graph \( G_n \) and run a graph search between \( q_{\text{start}} \) and \( q_{\text{goal}} \).

Suppose the radius \( r \) is chosen small enough that:

• if two vertices lie in the same ball of radius \( r \) inside the path tube, then the straight-line interpolation between them remains in \( \mathcal{C}_{\text{free}} \);
• every pair of consecutive balls \( B_i, B_{i+1} \) intersects, so that a sample in each yields at least one nearby pair to connect.

Once we have at least one sample in every covering ball, the roadmap contains a chain of collision-free edges forming a discrete path. Thus, the event “planner fails after \( n \) samples” is contained in the event “some covering ball is empty after \( n \) samples”, whose probability we have already shown tends to zero. This recovers probabilistic completeness.

In later lessons (e.g., on PRM and RRT), we will see how this abstract argument is specialized and refined, including dimension-dependent connection radii and more sophisticated local planners.

To build intuition, we consider an extremely simplified model: a unit hypercube \( [0,1]^d \) with a “goal tube” of volume \( v_{\text{goal}} \). A trial is successful if at least one sample falls inside the goal region. For each language, we estimate \( \mathbb{P}(\text{success}) \) for different numbers of samples \( n \) by Monte Carlo.

6.1 Python (with NumPy, for OMPL-style intuition)

import numpy as np

def success_probability(num_samples, num_trials=1000, dim=4, goal_radius=0.1):
    """
    Approximate P(success) that at least one of num_samples
    falls inside a d-dimensional ball of radius goal_radius
    centered at 0.5 (approx. 'goal tube' in C-space).
    """
    center = 0.5 * np.ones(dim)
    successes = 0

    for _ in range(num_trials):
        q = np.random.rand(num_samples, dim)  # uniform in [0,1]^dim
        # Euclidean distance to center
        dist = np.linalg.norm(q - center, axis=1)
        if np.any(dist <= goal_radius):
            successes += 1

    return successes / num_trials

for n in [10, 50, 100, 200, 500, 1000]:
    print(f"n = {n}, approx P(success) = {success_probability(n):.3f}")
      

In practice, libraries such as ompl (Open Motion Planning Library) provide Python bindings where the underlying sampling and connection strategies are implemented in C++. The probabilistic completeness intuition above still applies: as num_samples grows, the success probability approaches 1 for any goal tube of positive volume.

6.2 C++ (roadmap-like Monte Carlo)

#include <iostream>
#include <random>
#include <cmath>

bool trial_success(int numSamples, int dim, double radius) {
    static thread_local std::mt19937 gen(std::random_device{}());
    std::uniform_real_distribution<double> unif(0.0, 1.0);

    // center at 0.5 in each coordinate
    std::vector<double> center(dim, 0.5);

    for (int i = 0; i < numSamples; ++i) {
        double dist2 = 0.0;
        for (int d = 0; d < dim; ++d) {
            double x = unif(gen);
            double diff = x - center[d];
            dist2 += diff * diff;
        }
        if (std::sqrt(dist2) <= radius) {
            return true; // at least one sample hits the goal tube
        }
    }
    return false;
}

double estimate_success_prob(int numSamples, int dim = 4,
                             double radius = 0.1, int trials = 1000) {
    int successCount = 0;
    for (int t = 0; t < trials; ++t) {
        if (trial_success(numSamples, dim, radius)) {
            ++successCount;
        }
    }
    return static_cast<double>(successCount) / trials;
}

int main() {
    for (int n : {10, 50, 100, 200, 500, 1000}) {
        double p = estimate_success_prob(n);
        std::cout << "n = " << n
                  << ", approx P(success) = " << p << std::endl;
    }
    return 0;
}
      

In a full robotics application, this logic is wrapped by C++ libraries like OMPL or integrated into frameworks such as MoveIt. The intuitive trend of increasing \( \mathbb{P}(\text{success}) \) with \( n \) is exactly what probabilistic completeness formalizes.

6.3 Java (for Java-based robotics stacks)

import java.util.Random;

public class PCMonteCarlo {
    private static final Random rng = new Random();

    public static boolean trialSuccess(int numSamples, int dim, double radius) {
        double[] center = new double[dim];
        for (int i = 0; i < dim; ++i) {
            center[i] = 0.5;
        }
        for (int i = 0; i < numSamples; ++i) {
            double dist2 = 0.0;
            for (int d = 0; d < dim; ++d) {
                double x = rng.nextDouble();
                double diff = x - center[d];
                dist2 += diff * diff;
            }
            if (Math.sqrt(dist2) <= radius) {
                return true;
            }
        }
        return false;
    }

    public static double estimateSuccessProb(int numSamples,
                                             int dim,
                                             double radius,
                                             int trials) {
        int successes = 0;
        for (int t = 0; t < trials; ++t) {
            if (trialSuccess(numSamples, dim, radius)) {
                successes++;
            }
        }
        return ((double) successes) / trials;
    }

    public static void main(String[] args) {
        int[] ns = {10, 50, 100, 200, 500, 1000};
        for (int n : ns) {
            double p = estimateSuccessProb(n, 4, 0.1, 1000);
            System.out.println("n = " + n +
                               ", approx P(success) = " + p);
        }
    }
}
      

6.4 MATLAB / Simulink

function p = estimate_success_prob(numSamples, numTrials, dim, radius)
%ESTIMATE_SUCCESS_PROB Monte Carlo estimate of P(success)
%   numSamples : number of samples per trial
%   numTrials  : number of trials
%   dim        : configuration-space dimension
%   radius     : goal-tube radius

if nargin < 4
    radius = 0.1;
end
if nargin < 3
    dim = 4;
end
if nargin < 2
    numTrials = 1000;
end

center = 0.5 * ones(1, dim);
successCount = 0;

for t = 1:numTrials
    Q = rand(numSamples, dim);    % samples in [0,1]^dim
    diffs = Q - center;
    dists = sqrt(sum(diffs.^2, 2));
    if any(dists <= radius)
        successCount = successCount + 1;
    end
end

p = successCount / numTrials;
end

% Example usage:
for n = [10, 50, 100, 200, 500, 1000]
    p = estimate_success_prob(n, 1000, 4, 0.1);
    fprintf('n = %d, approx P(success) = %.3f\n', n, p);
end
      

In Simulink, one can encapsulate this logic in a MATLAB Function block that takes numSamples and radius as inputs and outputs the estimated success probability. The block can be placed in a larger simulation that also models robot dynamics and collision checking.

6.5 Wolfram Mathematica

ClearAll[TrialSuccess, EstimateSuccessProb];

TrialSuccess[numSamples_Integer, dim_Integer, radius_?NumericQ] := Module[
  {center, q, dist},
  center = ConstantArray[0.5, dim];
  Do[
    q = RandomReal[{0, 1}, dim];
    dist = Norm[q - center];
    If[dist <= radius, Return[True]],
    {numSamples}
  ];
  False
];

EstimateSuccessProb[numSamples_Integer, dim_Integer : 4, radius_?NumericQ : 0.1,
                    numTrials_Integer : 1000] := Module[
  {successes = 0},
  Do[
    If[TrialSuccess[numSamples, dim, radius], successes++],
    {numTrials}
  ];
  N[successes/numTrials]
];

Table[
  {n, EstimateSuccessProb[n]},
  {n, {10, 50, 100, 200, 500, 1000}}
]
      

In all languages, as we increase numSamples, the estimated success probability monotonically approaches 1 for any fixed goal region of positive volume, illustrating the core intuition of probabilistic completeness.

It is often useful to think of the planner's failure event in terms of simpler sub-events. For a path covered by balls \( B_0,\dots,B_k \), define \( E_i \) as “ball \( B_i \) has at least one sample after \( n \) draws”. Then:

\[ \text{success after } n \text{ samples} \quad \Longrightarrow \quad \bigcap_{i=0}^k E_i, \]

and conversely, under suitable local-connection assumptions:

\[ \bigcap_{i=0}^k E_i \quad \Longrightarrow \quad \text{planner can construct a discrete path}. \]

The failure event is thus contained in a union of “missing-ball” events. This decomposition directly leads to the union bound estimates and the exponential convergence of the failure probability.

flowchart TD
  S["Robust path exists"] --> C["Cover path by balls B_0,...,B_k"]
  C --> E["For each i, event E_i: ball i hit by some sample"]
  E --> U["Failure subset of union of complements of E_i"]
  U --> P["Union bound gives exponential decay of P(failure)"]
        

Problem 1 (Hitting a Ball in a Hypercube): Let random samples be drawn i.i.d. uniformly from the unit hypercube \( [0,1]^d \). Let \( B \) be a ball of radius \( r > 0 \) entirely contained in the hypercube. Show that the probability of missing \( B \) after \( n \) samples is \( (1 - v)^n \), where \( v \) is the volume of \( B \) divided by the volume of the hypercube.

Solution:

Each sample is uniformly distributed over the hypercube, whose volume is 1. Let \( V_B \) be the volume of \( B \). Then the probability that a single sample lies inside \( B \) is \( v = V_B / 1 = V_B \). The complementary event “sample lies outside \( B \)” has probability \( 1 - v \). Independence of the \( n \) samples implies that the probability that all of them lie outside \( B \) is

\[ \mathbb{P}(\text{miss } B \text{ after } n \text{ samples}) = (1 - v)^n. \]

This is exactly the form used in the union-bound proof of probabilistic completeness.

Problem 2 (Union Bound for a Path Cover): Suppose a robust path is covered by \( k+1 \) balls \( B_0,\dots,B_k \), each with volume fraction at least \( v_{\min} > 0 \) (i.e., each ball has volume at least \( v_{\min} \) times the volume of \( \mathcal{C}_{\text{free}} \)). Show that the probability that at least one ball is empty after \( n \) i.i.d. uniform samples in \( \mathcal{C}_{\text{free}} \) is at most \( (k+1)\, (1 - v_{\min})^n \).

Solution:

Let \( E_i \) be the event “ball \( B_i \) is empty after \( n \) samples”. From Problem 1, each ball has volume fraction at least \( v_{\min} \), so the probability of missing ball \( B_i \) is:

\[ \mathbb{P}(E_i) \le (1 - v_{\min})^n. \]

The event that at least one ball is empty is the union \( E_0 \cup \cdots \cup E_k \). By the union bound:

\[ \mathbb{P}\left(\bigcup_{i=0}^k E_i\right) \le \sum_{i=0}^k \mathbb{P}(E_i) \le \sum_{i=0}^k (1 - v_{\min})^n = (k+1)\, (1 - v_{\min})^n. \]

This provides an explicit exponential upper bound on the failure probability of any roadmap-like planner that needs at least one sample in each covering ball.

Problem 3 (Narrow Passage Intuition): In a 2D configuration space, consider two large square regions of free space connected by a narrow rectangular passage of width \( w \) and length 1. The total area of \( \mathcal{C}_{\text{free}} \) is approximately \( A_{\text{free}} \approx 2 + w \). Give a rough expression (up to constants) for the probability that a single uniform sample lies in the passage, and discuss what happens to the rate of convergence of a probabilistically complete planner as \( w \) becomes small.

Solution:

The area of the passage is approximately \( A_{\text{pass}} = w \). A single uniform sample in \( \mathcal{C}_{\text{free}} \) lands in the passage with probability:

\[ p_{\text{pass}} \approx \frac{A_{\text{pass}}}{A_{\text{free}}} \approx \frac{w}{2 + w}. \]

For small \( w \), \( p_{\text{pass}} \approx w/2 \), which becomes very small as \( w \to 0 \). A probabilistically complete planner still satisfies \( \lim_{n \to \infty} \mathbb{P}(\text{failure}) = 0 \), but the convergence rate is roughly controlled by \( p_{\text{pass}} \). In practice, this means that the number of required samples to obtain a reasonable success probability grows like \( 1 / w \) or worse, making narrow passages challenging despite asymptotic guarantees.

Problem 4 (Probabilistic vs Deterministic Completeness): Explain why a grid-based planner with a fixed resolution may fail to be (deterministically) complete on a configuration space with arbitrarily thin obstacles, while a sampling-based planner with probabilistic completeness can still guarantee asymptotic success.

Solution:

A fixed-resolution grid planner divides the space into cells of size \( \Delta \). If an obstacle is narrower than \( \Delta \), some cells may be partially occupied but entirely classified as free or occupied depending on the collision checker's policy. Thus, for any fixed resolution, one can construct a configuration space where a feasible path passes through regions that the grid discretization misclassifies, leading to permanent failure of the planner. No matter how long we run the search, the discretization error persists.

In contrast, a sampling-based planner uses continuous random samples in the geometric space. For any robust path with positive clearance, there exists a tube of positive measure around it. Independent samples eventually land inside this tube with probability 1, regardless of how “thin” the obstacles are, as long as they do not shrink the clearance to zero. Hence, the planner is probabilistically complete even when any fixed discretization might fail.

Problem 5 (Asymptotic Behavior of Failure Probability): Suppose a planner's failure probability after \( n \) samples is bounded by \( C e^{-a n} \) for some constants \( C > 0 \) and \( a > 0 \). Show that the expected number of samples needed until success is finite.

Solution:

Let \( N \) be the (random) number of samples at success. We are given \( \mathbb{P}(F_n) \le C e^{-a n} \), where \( F_n \) is “failure after \( n \) samples”. Note that:

\[ \mathbb{P}(N > n) = \mathbb{P}(\text{failure after } n \text{ samples}) = \mathbb{P}(F_n) \le C e^{-a n}. \]

Using the tail-sum formula for nonnegative integer-valued random variables:

\[ \mathbb{E}[N] = \sum_{n=0}^{\infty} \mathbb{P}(N > n) \le \sum_{n=0}^{\infty} C e^{-a n} = C \sum_{n=0}^{\infty} (e^{-a})^n = \frac{C}{1 - e^{-a}} < \infty. \]

Thus, exponential decay of the failure probability implies a finite expected sample complexity, reinforcing the practical significance of probabilistic completeness with a good convergence rate.

In this lesson, we developed an intuition for probabilistic completeness in sampling-based motion planning. Starting from configuration-space geometry and robust paths with positive clearance, we showed how finite coverings by balls of positive volume lead naturally to exponential bounds on the probability that random sampling misses all points on a feasible path. Unlike deterministic grid methods, probabilistically complete planners are robust to certain geometric pathologies, although the convergence rate can be severely impacted by narrow passages.

Through Monte Carlo simulations in Python, C++, Java, MATLAB/Simulink, and Mathematica, we saw how the probability of discovering a goal region of positive measure tends to 1 as the number of samples grows. In later lessons, we will apply these ideas concretely to specific algorithms such as PRM, RRT, and asymptotically optimal variants, and study how their design choices influence both probabilistic completeness and empirical performance.