Alternative Connection Radius for Asymptotic Optimality in RRT∗

Abstract

Connection radius in asymptotically optimal motion planning algorithms is of interest to both understand the theoretical properties of these algorithms, as well as to ensure practical performance by estimating lower bounds. The smaller the connection radius, the sparser the data structures constructed using them, which makes the associated algorithms computationally more efficient. The original radii for both roadmap and tree variants were reported to be asymptotically shrinking functions of n. A recent amendment to the original arguments for trees demonstrated that the radius has to be larger for tree-based variants (RRT*). A practical problem in the newly proposed radius is the persistence of hard-to-estimate or large-valued parameters (like optimal path cost) within the connection radius function. In this short paper, a new perspective is presented of approaching the proof of asymptotic optimality of RRT∗ from a minimal variant of RRT∗ that only includes tree additions within connection neighborhoods. The work provides an alternative connection radius that gets rid of unwieldy parameters, presents insights that holds promise in studying the problem and using the result. Show more