Abstract
Connection radius in asymptotically optimal mo- tion 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. I. MOTIVATION AND KEY FINDINGS Asymptotic optimality [1], [2] in motion planning [3] demonstrated that in kinematic motion planning, careful selection of connection rules in roadmaps [4] and trees [5] can ensure that the cost of the solution path asymptotically approaches the optimal solution cost. The connection radius lower bound for roadmaps was subsequently improved [6]. The initial key results [3], [6] leverage theories [7] developed in random geometric graphs [8]. These theories describe probabilistic and asymptotic properties of graphs with sam- pled vertices that include edges for vertices lying within neighborhoods defined by a connection radius function. Careful choice of connection radius functions can guarantee asymptotic optimality of motion plans discovered over the graphs or trees. It is of significance to identify accurate lower bound estimates of these connection radii. Smaller connection radii are more desirable as they express sparser data structures and are incur lower computation and memory overheads. It is of practical interest to identify estimates for connection radii in such asymptotically motion planners. This work provides a new connection radius lower bound for RRT∗that is smaller and only involves known constants (Fig 1 bottom). The arguments applicable to PRM∗[3], [6] defined a con- nection radius as an asymptotically diminishing function rn of the number of samples n. The lower bound was reported for both PRM∗and RRT∗(i.e., both roadmap and tree-based *The author is affiliated to the School of Computing, the Australian National University. Corresponding contact rahul.shome@anu.edu.au roadmap radius r tree radius r tree radius r > r r > 2 1 d + 1 ! 1 d vol(free C-Space) vol(unit hyperball) ! 1 d (log N) 1 d N 1 d+1 Fig. 1. (Top row:) Five states x1 · · · x5 sampled in sequence. x2 will be added to a roadmap (left) but is not part of the tree (middle), unless a larger radius is used (right). (Middle row:) 10000 samples connected in an 2D unit square. Using roadmap connectivity with radius proportional to (log n/n)1/d (left), a radius proportional to (log n/n)1/d used to grow a tree from the center (middle), and tree using a larger radius (right). The middle does not resemble an optimal tree while the right does (as has been theorized in earlier work [9]). (Bottom Row:) In this work we build on roadmap arguments to come up with an estimate for connection radius that emulates the behavior like the middle right. A sketch of the relationship between roadmap arguments of sampling M balls along an optimal path compared to tree arguments that need to guarantee the M balls in sequence using the connection radius outlined by the connection radius estimate. versions of the approach) as proportional to (log n/n) 1 d , where d is the dimensionality of the configuration space. Recently [9], it has been shown that this radius is not sufficient to address tree-based methods like RRT∗. Instead, the lower bound is shown to be larger and proportional to (log n/n) 1 d+1 , which is larger than what is necessary for roadmaps. It is important to provide an sketch of the reasoning behind this incongruence. In roadmaps, a new vertex is connected to another roadmap vertex as long as it is within the connection radius. In trees, connecting a new vertex to a tree vertex when it is within the connection radius 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) October 14-18, 2024. Abu Dhabi, UAE 979-8-3503-7769-9/24/$31.00 ©2024 IEEE 5327