On Probabilistic Completeness of the Generalized Shape Expansion-Based Motion Planning Algorithm

A major aspect of motion planning is the use of sampling-based algorithms. Sampling-based methods are primarily used to generate a feasible collision-free path for agents in an environment known a-priori. A recently proposed motion planning algorithm, termed as 'Generalized Shape Expansion' (GSE) algorithm, is a promising option in this class of algorithm. Extensive numerical studies have suggested that the GSE outperforms several seminal algorithms in literature in terms of computational time. However, so far no guarantee of probabilistic completeness of the GSE has been presented in literature. To this end, this paper elaborates a detailed mathematical analysis of GSE, providing upper bounds on the probability of failure of the GSE algorithm. A numerical example is presented to illustrate the proof. Simulation studies are presented to compare it with prominent algorithms in the literature, particularly in terms of number of iterations to reach a feasible path.