PaperlayerView exact revision on arXiv

Source-linked AI summary

Sampling-based Algorithms for Optimal Motion Planning

Sertac Karaman, Emilio Frazzoli

arXiv:1105.1186v1cs.RO

TL;DR

Sampling-based planners lacked systematic analysis of whether solution quality converges to the optimum. This paper analyzes that asymptotic behavior and introduces planners that achieve asymptotic optimality with only a constant-factor complexity increase.

  • Problem

    Optimality properties of sampling-based motion-planning algorithms had not been systematically investigated, with much prior work relying on heuristics.

  • Method

    The paper analyzes sampling-based planners through random-geometric-graph theory and introduces PRM*, RRG, and RRT* with sample-dependent connection rules.

  • Results

    PRM and RRT are not asymptotically optimal, whereas the proposed algorithms are asymptotically optimal and computationally efficient relative to probabilistically complete counterparts.

  • Takeaways & Limitations

    Asymptotic optimality can be obtained with only a constant-factor increase in complexity over probabilistic completeness.

  • Takeaways & Limitations

    The analysis does not address motion-planning problems with differential, temporal, or logic constraints.

Abstract

from arXiv · show

During the last decade, sampling-based path planning algorithms, such as Probabilistic RoadMaps (PRM) and Rapidly-exploring Random Trees (RRT), have been shown to work well in practice and possess theoretical guarantees such as probabilistic completeness. However, little effort has been devoted to the formal analysis of the quality of the solution returned by such algorithms, e.g., as a function of the number of samples. The purpose of this paper is to fill this gap, by rigorously analyzing the asymptotic behavior of the cost of the solution returned by stochastic sampling-based algorithms as the number of samples increases. A number of negative results are provided, characterizing existing algorithms, e.g., showing that, under mild technical conditions, the cost of the solution returned by broadly used sampling-based algorithms converges almost surely to a non-optimal value. The main contribution of the paper is the introduction of new algorithms, namely, PRM* and RRT*, which are provably asymptotically optimal, i.e., such that the cost of the returned solution converges almost surely to the optimum. Moreover, it is shown that the computational complexity of the new algorithms is within a constant factor of that of their probabilistically complete (but not asymptotically optimal) counterparts. The analysis in this paper hinges on novel connections between stochastic sampling-based path planning algorithms and the theory of random geometric graphs.

1 Introduction

Sampling-based planning avoids explicit obstacle representations and offers probabilistic completeness, but the optimality of its returned solutions had not been systematically analyzed. This paper establishes negative results for existing methods and introduces computationally efficient algorithms with probabilistic completeness and asymptotic optimality.

  • Motivation: Sampling-based algorithms reduce computational burden by avoiding explicit obstacle construction, while failure probability decays to zero as samples approach infinity.These guarantees are probabilistic rather than full completeness guarantees.
  • Motivation: The quality of returned paths matters because applications may require minimum-cost solutions, such as shortest paths or paths minimizing execution time.Computing optimal motion plans is challenging even in basic cases.
  • Gap: Prior work had not systematically investigated optimality properties of sampling-based planners, with much relevant practice relying on heuristics.Examples include biasing RRT growth toward low-cost regions and repeatedly running RRT to improve path cost.
  • Results: Standard PRM and RRT are not asymptotically optimal, while simplified PRM is asymptotically optimal but computationally expensive.The k-nearest simplified PRM is not necessarily probabilistically complete, including for k = 1, and is not asymptotically optimal for any fixed k.
  • Contributions: PRM*, RRG, and RRT* are proven probabilistically complete, asymptotically optimal, and computationally efficient.The analysis establishes novel connections between sampling-based planning and random geometric graph theory.

2 Preliminary Material

This section formalizes feasible and optimal path-planning problems and introduces the random-geometric-graph results used later to analyze sampling-based algorithms. It defines the configuration-space model, path costs, finite random geometric graphs, and their percolation framework.

  • Path-planning formulation: A path-planning problem is the triplet (Xfree, xinit, Xgoal), with Xfree the closed obstacle-free space, xinit ∈ Xfree, and Xgoal an open subset of Xfree.The configuration space is X = (0, 1)^d with d ∈ N and d ≥ 2.
  • Path-planning formulation: A feasible path is continuous, collision-free, starts at xinit, and ends in cl(Xgoal); feasible planning finds one or reports failure if none exists.Collision freedom requires σ(τ) ∈ Xfree for every τ ∈ [0, 1].
  • Path-planning formulation: Optimal path planning seeks a feasible path σ* minimizing a nonnegative cost function c over all feasible paths, or reports failure when no such path exists.The cost function assigns strictly positive cost to every non-trivial collision-free path.
  • Random geometric graphs: Random geometric graphs connect stochastic points in a metric space when pairwise conditions such as distance thresholds hold, linking graph theory to probabilistic completeness and asymptotic optimality.The paper uses these connections as analytical tools for sampling-based path-planning algorithms.
  • Random geometric graphs: Finite random r-disc graphs use n independent uniformly distributed vertices in (0, 1)^d and connect pairs whose distance is less than r; their asymptotic properties include percolation and connectivity transitions.Percolation is characterized through the largest connected component, while the continuum threshold λc separates subcritical and supercritical regimes.

3 Algorithms

Section 3 defines the primitive procedures used by sampling-based planners, outlines PRM and related roadmap variants, and introduces PRM*, RRT*, and RRG as new or efficient algorithmic counterparts. These procedures rely on independent sampling, nearest-neighbor queries, steering, local collision tests, and radius- or neighbor-based connection rules.

  • Algorithm overview: The section introduces PRM and RRT as representative sampling-based planning paradigms before presenting PRM* and RRT* as asymptotically optimal, computationally efficient counterparts.The new algorithms are analyzed in the next section.
  • Primitive procedures: Sampling draws points independently and identically distributed, typically uniformly, with results extending to absolutely continuous densities bounded away from zero on X.A separate SampleFree procedure returns samples in Xfree.
  • Primitive procedures: Nearest and k-nearest procedures select the closest vertex or the k closest vertices using Euclidean distance, while Near selects vertices inside a radius-r ball.If fewer than k vertices exist, kNearest returns all available vertices.
  • Primitive procedures: Steer moves toward a target while limiting the displacement from the starting point to a prespecified η, and CollisionFree accepts exactly when the connecting segment lies in Xfree.The steering point minimizes distance to the target subject to the η bound.
  • PRM variants: PRM constructs a roadmap from randomly sampled free-space points by attempting collision-free local connections to nearby vertices, while k-nearest and bounded-degree variants limit connection candidates.Typical reported neighbor limits are k = 15 for k-nearest PRM and k = 20 for bounded-degree PRM.
  • RRG: RRG incrementally builds a connected roadmap by adding successful connections from the nearest node and additional nearby vertices, making the RRT graph a subgraph of RRG for the same samples.RRT is directed and tree-structured, whereas RRG is undirected and may contain cycles.

4 Analysis

The analysis establishes that several standard sampling-based planners are not asymptotically optimal, while PRM*, RRG, RRT*, and their k-nearest variants achieve almost-sure convergence to optimal solutions under stated connection conditions. It also characterizes probabilistic completeness failures and confirms completeness for the new algorithms.

  • Probabilistic completeness: The 1-nearest sPRM is not probabilistically complete, and variable-radius sPRM with r(n) = γn−1/d is not probabilistically complete for some γ > 0.RRT is described as an incremental version of the 1-nearest sPRM, which connects each sample to its nearest neighbor while enforcing graph connectivity.
  • Probabilistic completeness: PRM*, RRG, and RRT* are probabilistically complete, with completeness of PRM* implied by its asymptotic optimality.For robustly feasible problems, the analysis also states theorem-based constants governing completeness probabilities.
  • Asymptotic optimality: Probabilistic completeness is necessary for asymptotic optimality, and convergence to an optimal solution occurs with probability either zero or one.The analysis defines asymptotic optimality through almost-sure convergence to optimal paths.
  • Asymptotic optimality: PRM, k-nearest sPRM, variable-radius sPRM, and RRT are not asymptotically optimal, whereas sPRM is asymptotically optimal.RRT’s best-solution cost converges almost surely to a suboptimal value; PRM’s failure is attributed to its incremental construction and edge-elimination constraint.
  • Asymptotic optimality: PRM*, k-nearest PRM*, RRG, k-nearest RRG, RRT*, and k-nearest RRT* are asymptotically optimal when their connection parameters exceed the theorem-specific thresholds.The theorems give separate threshold conditions for radius-based and k-nearest implementations.

5 Numerical Experiments

The numerical experiments compare PRM* with k-nearest PRM and RRT* with RRT across several environments, dimensions, and cost functions. They show PRM* and RRT* converging toward optimal solutions, while RRT does not, with RRT* runtime ratios approaching a constant.

  • PRM versus PRM*: PRM* converges to optimal solutions in two-dimensional experiments, unlike k-nearest PRM, and is also evaluated in configuration spaces up to five dimensions.The comparison plots best-path cost against iterations for both algorithms.
  • RRT versus RRT*: In the obstacle-free scenario, RRT does not improve its feasible solution toward an optimum, whereas RRT* continues lowering tree-path costs.The experiments use Euclidean path length as the cost function.
  • RRT versus RRT*: RRT-run variance approaches 2.5, while RRT* variance approaches zero, indicating that almost all RRT* runs converge to an optimal solution.This result is reported for the obstacle-free scenario across Monte-Carlo runs.
  • RRT versus RRT*: With obstacles, RRT* initially explores rapidly like RRT and then improves its tree as the number of samples increases, discovering lower-cost paths.The tree behavior is illustrated after 20,000 iterations and at multiple stages.
  • Running-time comparison: The ratio of RRT* to RRT running times converges to a constant value, based on experiments of up to one million iterations averaged over 50 runs.A similar running-time comparison is also reported for the obstacle scenario.

6 Conclusion · Appendix · A Notation

The paper concludes that PRM* and RRT* achieve asymptotic optimality with only constant-factor complexity increases, while identifying random geometric graphs and constrained planning as directions for further work. The appendix defines notation for sets, probability, asymptotic growth, and directed graphs.

  • 6 Conclusion: Existing sampling-based algorithms can be probabilistically complete yet fail to converge to the optimal solution cost as sample counts increase.This conclusion distinguishes probabilistic completeness from asymptotic optimality.
  • 6 Conclusion: PRM* and related algorithms are asymptotically optimal and computationally efficient, with asymptotic optimality requiring only a constant-factor complexity increase.PRM* uses a variable connection radius scaling as log(n)/n.
  • 6 Conclusion: Connections within balls whose radius scales as log(n)/n balance asymptotic optimality and computational efficiency.Faster shrinking can lose asymptotic optimality, while slower shrinking increases complexity.
  • 6 Conclusion: Connecting to k log(n) neighbors preserves asymptotic optimality and computational efficiency when k is at least a constant k∗.The threshold constant depends only on the dimension, not the problem instance.
  • 6 Conclusion: The analysis connects sampling-based planning graphs to random geometric graphs, whose percolation and connectivity phase transitions match planning thresholds.These connections support the paper’s analysis of probabilistic completeness and asymptotic optimality.
  • 6 Conclusion: Future work includes broader random-geometric-graph connections and applying similar analysis to additional sampling-based planning algorithms.The paper also identifies extensions to differential constraints, temporal or logic constraints, and dynamic-obstacle planning.
  • 6 Conclusion: The proposed sampling-based algorithms may also extend beyond robotics to partial differential equations, including the eikonal and Hamilton-Jacobi-Bellman equations.This is presented as an application outside the robotic motion-planning domain.
  • A Notation: The notation appendix defines sets and intervals, Euclidean norms and closures, probability events and convergence, asymptotic function classes, and directed graphs and paths.It introduces N, R, probability-space terminology, O, Ω, Θ, and graph neighbor definitions.

B Proof of Theorem 33 (Non-optimality of RRT)

The proof establishes RRT’s non-asymptotic optimality in an obstacle-free unit hypercube with sufficiently large steering range. It begins by identifying a necessary condition involving infinitely many branches extending beyond a small neighborhood of the initial state.

  • Proof assumptions: The proof assumes Xfree = [0, 1]d and η ≥ diam (Xfree), making the steering range sufficiently large.These assumptions simplify the argument by removing obstacles and allowing broad steering connections.
  • Proof assumptions: This simplified case suffices to show RRT fails to converge to an optimal solution despite the instance being robustly optimal.The authors state that the assumptions are not essential, although extending the proof requires considerably more technical detail.
  • Proof outline: The proof orders RRT vertices by insertion time and defines each branch as a root child together with all its descendants.The k-th branch contains the k-th child of the root and every descendant in that subtree.
  • Proof outline: A necessary condition for RRT asymptotic optimality is that infinitely many branches contain vertices outside a small ball centered at the initial condition.This condition is the first step in the proof outline.

B.1 A necessary condition

The section establishes a necessary condition for RRT asymptotic optimality: infinitely many tree branches must contain vertices outside every sufficiently small R-ball around xinit. Under the stated zero-measure assumption for optimal-path points, failure of this condition implies the limiting cost exceeds c∗.

  • B.1 A necessary condition: RRT can be asymptotically optimal only if the k-th branch contains vertices outside the R-ball centered at xinit for infinitely many k.This condition is stated for 0 < R < inf_{y∈Xgoal} ∥y − xinit∥.
  • B.1 A necessary condition: The proof relies on the assumption that the set of points lying on an optimal path has measure zero, making Γ(xk) = c∗ have probability zero for every k.Here Γ(xk) is the optimal cost of a path through child xk that reaches the goal region.
  • B.1 A necessary condition: If vertices leave that R-ball in only finitely many branches, then the best-path cost remains strictly above c∗.The argument selects the largest branch index K with this property and uses Γ(xk) > c∗ for every root child.
  • B.1 A necessary condition: The probability bound is completed by taking complements, applying monotonicity of probability measures, and using a union bound whose final term is zero.This establishes the lemma’s necessary-condition result.

B.2 Length of the first path in a branch

The RRT’s nearest-neighbor structure gives each sampled point equal chance of being selected and yields expected nearest-neighbor distance n^-1/d. For branch paths indexed by k, expected length is finite, decreases with k, and converges to zero.

  • Nearest-neighbor structure: For n uniformly sampled points, each point has probability 1/n of being the nearest neighbor of an independent query, with expected nearest-neighbor distance n^-1/d.This characterizes the nearest-neighbor selection underlying the RRT structure.
  • Nearest-neighbor structure: Each RRT vertex has unbounded degree almost surely as the number of samples approaches infinity.
  • Branch-path lengths: For every k ∈ N, the branch-path length Lk has finite, non-negative expectation, and E[Lk+1] ≤ E[Lk].The finite-expectation result follows from the nearest-neighbor analysis and the finiteness of the Riemann zeta function for positive arguments greater than one.
  • Branch-path lengths: The expected branch-path length converges to zero as k approaches infinity: limk→∞ E[Lk] = 0.This follows because the first sample contributing to Lk is generated no earlier than iteration k.

B.3 Length of the longest path in a branch · B.4 Violation of the necessary condition

The analysis bounds the expected length of paths in later RRT branches and shows that exceptionally long branches become increasingly unlikely. Consequently, the RRT violates a necessary condition for asymptotic optimality.

  • B.3 Length of the longest path in a branch: The quantity sup α≥k L_α upper-bounds the length of every path in the k-th RRT branch and all following branches.This quantity is therefore sufficient for controlling long paths across the tail of the tree.
  • B.3 Length of the longest path in a branch: E[L_α] ≤ E[L_k] for every α ≥ k, so expected path length does not increase along later branches.The proof uses induction and compares successive finite-path descendants.
  • B.3 Length of the longest path in a branch: The bound follows by selecting the first branch index whose path length exceeds ϵ and applying the expectation inequality from Lemma 48.On the relevant event, the selected path length is at least ϵ.
  • B.3 Length of the longest path in a branch: For any ϵ > 0, lim k→∞ P({sup α≥k L_α > ϵ}) = 0.Thus, the probability that any path in branch k or subsequent branches exceeds ϵ vanishes as k grows.
  • B.4 Violation of the necessary condition: A necessary condition for asymptotic optimality is that infinitely many RRT branches contain vertices outside the R-ball centered at x_init.Here 0 < R < inf y∈X_goal ∥y − x_init∥.
  • B.4 Violation of the necessary condition: Because reaching outside that ball requires branch length greater than R infinitely often, Corollary 49 makes this necessary event have probability zero.The events are monotonic, so their limiting probability equals the limit of P({sup α≥k L_α > R}), which is 0.

C Proof of Theorem 34 (Asymptotic optimality of PRM∗)

This section first presents an outline of the proof before giving the detailed argument.

  • Proof outline: The proof is organized by presenting an outline before the details.The passage explicitly introduces an outline followed by detailed proof steps.

C.1 Outline of the proof

The proof approximates a robustly optimal path with strongly clearance-controlled paths covered by overlapping balls. It then shows that PRM* eventually samples every ball almost surely, yielding collision-free paths whose best cost converges to the optimum.

  • C.1 Outline of the proof: A robustly optimal path σ∗ is approximated by paths σn with strong δn-clearance, where δn > 0 and δn approaches zero.The paths σn converge to σ∗ as n approaches infinity.
  • C.1 Outline of the proof: Each σn is covered by overlapping radius-qn balls arranged so consecutive sampled points can connect within r(n) through obstacle-free space.The construction requires consecutive points to be no more than the connection radius apart, with their straight-line path entirely collision-free.
  • C.1 Outline of the proof: The event that every covering ball contains a PRM* vertex occurs for all sufficiently large n with probability one.Under this event, PRM* connects vertices in consecutive balls with edges, producing collision-free paths.
  • C.1 Outline of the proof: Any resulting path sequence converges to σ∗, and the best graph-path cost converges almost surely to c(σ∗).The final convergence argument uses the robustness of σ∗.

C.2 Construction of the sequence {σn}n∈N of paths … C.5 Connecting the vertices in subsequent balls in Bn

The proof constructs paths with vanishing clearance, covers each path by overlapping balls, and shows that PRM* eventually samples every ball almost surely. Vertices in consecutive balls lie within the connection radius, and their connecting segments are collision-free.

  • C.2 Construction of the sequence {σn}n∈N of paths: C.2 constructs paths σn that converge to σ∗ while retaining strong δn-clearance, where δn → 0 and 0 ≤ δn ≤ δ.This follows from Lemma 50 and the chosen sequence δn based on the PRM* connection radius.
  • C.2 Construction of the sequence {σn}n∈N of paths: The construction uses weak δ-clearance of σ∗ to select σn from a homotopy, with σn → σ∗ as n increases.The sets Xn expand to Xfree as δn → 0, forcing the selected homotopy parameters αn toward zero.
  • C.3 Construction of the sequence {Bn}n∈N of sets of balls: C.3 covers each σn with balls of radius qn whose consecutive centers are θ1qn apart.The balls are generated by CoveringBalls and collectively cover the path.
  • C.4 The probability that each ball in Bn contains at least one vertex: C.4 proves that every ball in Bn contains at least one PRM* vertex for all sufficiently large n with probability one.The argument uses a Borel-Cantelli bound after showing that the relevant failure probabilities are summable.
  • C.5 Connecting the vertices in subsequent balls in Bn: Together, the covering-ball construction and connection lemmas provide a chain of PRM* vertices that follows σn through obstacle-free connections.This combines eventual vertex coverage with guaranteed connection attempts and successful collision-free segments.
  • C.4 The probability that each ball in Bn contains at least one vertex: The probability result is obtained by bounding the number and volume of covering balls and applying a union bound to the probability that any ball is empty.The proof selects θ1 so the resulting bound satisfies the required summability condition.
  • C.5 Connecting the vertices in subsequent balls in Bn: C.5 shows that any points selected from consecutive balls satisfy ∥xn,m+1 − xn,m∥ ≤ rn, so PRM* attempts to connect them.The bound follows from the ball radius qn, center spacing θ1qn, and the triangle inequality.
  • C.5 Connecting the vertices in subsequent balls in Bn: The connection between points in consecutive balls is collision-free because every segment point remains within the clearance margin around the path.Strong δn-clearance and qn = δn (1 + θ1) ensure the segment stays away from obstacles.

C.6 Convergence to the optimal path · D Proof of Theorem 35 (Asymptotic Optimality of k-nearest PRM∗)

The PRM* proof shows that a graph path approaches a robust optimal path almost surely, and consequently its minimum cost converges to c∗ as samples increase. The proof uses bounded-variation convergence, Borel-Cantelli, Poissonization, and de-Poissonization, while the k-nearest PRM* theorem follows by a similar argument.

  • C.6 Convergence to the optimal path: The bounded variation distance between the selected graph path σ′_n and reference path σ_n approaches zero with probability one.The proof establishes this through a Borel-Cantelli argument showing the relevant failure probabilities are summable.
  • C.6 Convergence to the optimal path: The proof uses Poissonization to analyze independent samples and then de-Poissonization to transfer the result to the original sampling process.The Poisson process has intensity ν n/µ(Xfree) and expected sample count ν n.
  • C.6 Convergence to the optimal path: If at most an α fraction of covering balls lack a nearby vertex, the bounded variation difference is bounded by 2(α + β)L.Here L is a finite bound on the lengths of the paths in {σ_n}n∈N.
  • C.6 Convergence to the optimal path: The resulting probability bound is summable for all ϵ > 0, implying that σ′_n − σ_n converges to zero almost surely.The argument combines bounds for the original sampling process with the Poisson-process analysis.
  • C.6 Convergence to the optimal path: The minimum-cost path in the PRM* graph converges to the optimal cost c∗ as the number of samples approaches infinity, with probability one.This follows from convergence of σ_n to the optimal path, bounded-variation convergence of σ′_n to σ_n, and robustness of the optimal path.
  • D Proof of Theorem 35 (Asymptotic Optimality of k-nearest PRM∗): The proof of asymptotic optimality for k-nearest PRM* is similar to the proof of Theorem 34.A complete proof is provided while repeating some of the earlier arguments.

D.1 Outline of the proof … E.2 Definitions of {σn}n∈N and {Bn}n∈N

The proof constructs paths converging to a robust optimal path, covers them with overlapping balls, and shows that PRM* eventually connects vertices through these balls almost surely. The same construction is reused for RRG, with exploration events replacing the PRM* vertex-count argument.

  • D.4 The probability that each ball in Bn contains at least one vertex: The proof shows that every ball in Bn eventually contains a PRM* vertex almost surely, while each corresponding larger ball contains at most k(n) vertices.These events are combined to establish connectivity between vertices in subsequent covering balls.
  • D.8 Convergence to the optimal path: The best path in the k-nearest PRM* graph converges almost surely to c(σ∗), using paths formed through consecutive balls and the robustness of σ∗.The proof selects the graph path closest to σn in bounded variation norm and invokes robustness of the optimal solution.
  • D.2 Construction of the sequence {σn}n∈N of paths: A sequence of strongly δn-clear paths σn is constructed so that σn converges to the robust optimal path σ∗.The construction uses limn→∞δn = 0 and 0 ≤ δn ≤ δ.
  • D.3 Construction of the sequence {Bn}n∈N of sets of balls: Each σn is covered by overlapping balls Bn with radius qn := δn 1 + θ1 and spacing θ1qn.The covering is defined as Bn := CoveringBalls(σn, qn, θ1qn).
  • D.5 Construction of the sequence {B′ n}n∈N of sets of balls: The auxiliary balls B′n share centers with Bn, have radius δn, and are larger than the balls in Bn.Their geometry ensures that consecutive balls in Bn lie inside the same corresponding B′n ball.
  • D.6 The probability that each ball in B′ n contains at most k(n) vertices: If kPRM > e (1 + 1/d)1/d, suitable θ1, θ2 > 0 make the required occupancy event occur for all large n with probability one.The event combines at-least-one-vertex occupancy in Bn with at-most-k(n)-vertex occupancy in B′n.
  • D.7 Connecting the vertices in the subsequent balls in Bn: Because consecutive Bn balls lie inside a common B′n ball, k-nearest PRM* attempts their connections, and every resulting line segment is collision-free.The collision-free property holds for any points chosen from consecutive balls.
  • E.1 Outline of the proof: For RRG, the proof reuses σn and Bn, but conditions on exploration events Ci over iterations ⌊θ3n⌋ through n to show eventual ball occupancy almost surely.The RRG event Cn requires that every obstacle-free point can connect to a maintained graph vertex.

E.3 Probability that each ball in Bn contains at least one vertex · E.4 Convergence to the optimal path · F Proof of Theorem 37 (asymptotic optimality of k-nearest RRG)

The proof establishes that, with probability one, every ball in the covering B_n eventually contains an RRG vertex. Using this result and robustness of the optimal solution, it concludes convergence to the optimal path.

  • E.3 Probability that each ball in Bn contains at least one vertex: A_n denotes the event that every ball in B_n contains at least one RRG vertex after n iterations.The event is defined as the intersection of the corresponding per-ball events A_n,m.
  • E.3 Probability that each ball in Bn contains at least one vertex: The probability that a ball or partition element contains no RRG vertex decays to zero at an exponential rate.The partition argument and a union bound extend the exponential decay from individual sets to the event that at least one partition fails.
  • E.3 Probability that each ball in Bn contains at least one vertex: Borel-Cantelli implies that the failure event A_n^c occurs infinitely often with probability zero.The proof uses finiteness of the relevant infinite sum to obtain P(lim sup_n→∞ A_n^c) = 0.
  • E.3 Probability that each ball in Bn contains at least one vertex: The proof bounds the number and volume of balls in B_n and conditions on continued successful local coverage to analyze vertex insertion.It uses the connection-radius constant γ_RRG, the Steer parameter η, and a threshold θ_3 n for the conditioning event.
  • E.3 Probability that each ball in Bn contains at least one vertex: Therefore, A_n occurs for all sufficiently large n with probability one.The conclusion is obtained by combining the summability argument with the complement event.
  • E.4 Convergence to the optimal path: Letting P_n be the graph’s paths, the path σ′_n closest to σ_n in bounded variation satisfies σ′_n = σ* with probability one, yielding the result by robustness of the optimal solution.This establishes the convergence step for the optimal path.

F.1 Outline of the proof … G.2 Definitions of {σn}n∈N and {Bn}n∈N

The paper combines earlier proof strategies with probabilistic bounds on covering balls to establish eventual connectivity and convergence toward an optimal path. For RRT*, it reformulates the algorithm through a marked point process and constructs disjoint ball covers along a sequence of paths.

  • F.1 Outline of the proof: The proof combines the arguments of Theorems 35 and 36, conditioning on C_i to show A_n and A′_n hold together for all sufficiently large n almost surely.A_n requires every ball in B_n to contain a vertex, while A′_n bounds vertices in each ball of B′_n.
  • F.2 Definitions of {σ_n}n∈N, {B_n}n∈N, and {B′: The sequences δ_n, σ_n, q_n, B_n, and B′_n are defined using the constructions from Theorem 35’s proof.The section introduces θ_1 and θ_2 as positive constants before defining these sequences and ball collections.
  • F.3 The probability that each ball in B_n contains at least one vertex: The analysis defines A_n as the event that every covering ball contains a vertex and uses C_n to express η-neighborhood coverage by the k-nearest RRG algorithm.The ball-level events A_n,m are combined across all balls, while s_n denotes the length of σ_n.
  • F.4 The probability that each ball in B′ n contains at most k(n) vertices: If k_PRM > e(1 + 1/d), suitable θ_1, θ_2, and θ_3 make the probability bounds for excessive occupancy summable.The proof applies a Chernoff bound to vertex counts in B′_n and then a union bound over balls.
  • F.5 Connecting the vertices in subsequent balls in B_n: If k_PRM > e(1 + 1/d)^(1/d), every B_n ball eventually contains a vertex while every B′_n ball contains at most k(n) vertices almost surely.The conclusion follows by combining Lemmas 66, 67, and 69 through union bounds.
  • F.6 Convergence to the optimal path: The convergence proof selects, from paths returned by k-RRG, a path closest to σ_n in bounded variation and invokes robustness of the optimal solution.The cited result states σ′_n = σ* with probability one.
  • G Proof of Theorem 38 (Asymptotic optimality of RRT∗): For RRT*, the proof models uniformly sampled points with independent uniform marks and connects earlier-marked points within radius r_n, producing an acyclic graph equivalent to the algorithm under sufficiently large η.The graph’s best-path costs are compared with those of a single-parent graph to derive the asymptotic result.
  • G.2 Definitions of {σ_n}n∈N and {B_n}n∈N: The RRT* construction uses paths σ_n and openly disjoint covering balls B_n = CoveringBalls(σ_n, r_n, 2r_n), spaced 2r_n apart.The sequence σ_n is guaranteed by Lemma 50, and the balls cover each corresponding path.

G.3 Connecting the vertices in subsequent balls in Bn · G.4 Convergence to the optimal path

The analysis establishes that RRT* connects vertices in every pair of consecutive balls B_n,m and B_n,m+1 eventually almost surely. It then uses this connectivity and robustness of the optimal solution to conclude convergence to the optimal path.

  • G.3 Connecting the vertices in subsequent balls in B_n: RRT* connects vertices in each consecutive pair of balls B_n,m and B_n,m+1 whenever a suitable mark ordering holds.The event A_n,m requires vertices X_i ∈ B_n,m and X_i′ ∈ B_n,m+1 with Y_i′ ≤ Y_i, ensuring an edge in G_n.
  • G.3 Connecting the vertices in subsequent balls in B_n: The connectivity result provides the eventual graph structure needed to construct paths through successive balls along the reference path.The section defines A_n as the event that every A_n,m holds across the balls.
  • G.3 Connecting the vertices in subsequent balls in B_n: The proof Poissonizes the sampling process by running RRT* for Poisson(θ n) iterations, producing a Poisson point process with intensity θ n / µ(X_free).Here θ ∈ (0, 1) is independent of n.
  • G.3 Connecting the vertices in subsequent balls in B_n: Since θ < 1, the probability that Poisson(θ n) exceeds n is at most e^−a n for a constant a > 0 independent of n.This exponential bound supports the comparison between Poissonized and fixed-sample events.
  • G.3 Connecting the vertices in subsequent balls in B_n: For α > 2(1 + 1/d), the resulting failure-probability bound is summable, so Borel-Cantelli implies that A_n occurs for all sufficiently large n almost surely.Equivalently, P(lim inf_n→∞ A_n) = 1.
  • G.4 Convergence to the optimal path: In the returned RRT* graph, the path σ′_n closest to σ_n in bounded variation norm converges to the optimal path under robustness of the optimal solution.The cited conclusion states σ′_n = σ* with probability one.
Loading 1105.1186v1…