Improved Connected-Component Expansion Strategies for Sampling-Based Motion Planning

Motion planning is the problem of computing valid paths through an environment. Since computing exact solutions is intractable, sampling-based algorithms, such as Probabilistic RoadMaps (PRMs), have gained popularity. PRMs compute an approximate mapping of the planning space by sacrificing completeness in favor of efficiency. However, these algorithms have certain bottlenecks that hinder performance, causing difficulty mapping narrow or crowded regions, with the asymptotic bottleneck of these algorithms being the nearest-neighbor queries required to connect the roadmap. Thus, roadmaps may fail to efficiently capture the connectivity of the planning space. In this thesis, we present a set of connected component (CC) expansion algorithms, each with different biases (random expand, expand to the nearest CC, expand away from the host CC, and expand along the medial-axis) and expansion node selection policies (random, farthest from CC's centroid, and difficult nodes), that create a linked-chain of configurations designed to enable efficient connection of CCs. Given an a priori roadmap quality requirement in terms of roadmap connectivity, we show that when our expansion methods augment PRMs, we reach the required roadmap connectivity in less time