Satadal Ghosh

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.

We present an online motion planning algorithm (3D-OGSSE) for generating smooth, collision-free trajectories over multiple planning iterations for a 3-D agent operating in an unknown, obstacle-cluttered, 3-D environment. In each planning iteration, 3D-OGSSE constructs an obstacle-free region termed 'generalized sensed shape' based on the locally-sensed environment information and the notion of generalized shape. A collision-free path is computed by sampling points in the generalized sensed shape and is used to generate a smooth, time-parametrized trajectory by minimizing snap. The generated trajectory at every planning iteration is constrained to lie within generalized sensed shape, which ensures the agent maneuvers in locally obstacle-free space. As the agent reaches the boundary of the generalized sensed shape in a planning iteration, a re-plan is triggered by a receding horizon planning mechanism that also enables the initialization of the next planning iteration. We also present a theoretical guarantee for probabilistic completeness of the developed algorithm over the entire environment and for completely collision-free trajectory generation. We evaluate the proposed method in simulation on complex 3-D environments with varied obstacle-densities. Further, we also evaluate it in scenarios with sensor noise and constraints on the on-board sensor's field-of-view (FOV). We observe that each planning iteration computation takes $\sim 14$ milliseconds on a single thread of an Intel Core i5-8500 3.0 GHz CPU, which is significantly faster than several existing algorithms. In addition, we also observe 3D-OGSSE to be less conservative in complex scenarios such as narrow passages.

Motion planning is a fundamental area of research in robotics and aerospace applications. Sampling-based methods provide an efficient solution to an otherwise challenging problem in motion planning. Recently, a sampling-based motion planner was presented based on the notion of novel 3D generalized shape to plan for an optimal collision-free path in 3D workspace and was termed as 3D-Generalized Shape Expansion (3D-GSE) algorithm. This was found to exhibit superior performance in terms of computational time and path costs over other well-established seminal algorithms in literature. Considering that a suitable directional sampling feature could potentially lead to a further superior performance of the 3D-GSE algorithm, this paper proposes two sampling schemes, namely basic and augmented directional sampling, and presents the 3D-GSE-D and 3D-GSE-AD algorithms, respectively. These algorithms, by default, have the benefits of the 3D-GSE algorithm. In addition, both the basic and augmented directional schemes sample random points with more preference towards the direction of the Goal point leading to lower path cost on average. While the basic directional scheme suffers from a higher computational time when the obstacle density is high along the direction towards the Goal, the augmented directional scheme is free from this drawback. Probabilistic analysis and extensive numerical simulation studies justify the performance of the 3D-GSE-D and the superiority of the 3D-GSE-AD in performance in terms of computational time efficiency and shortest path cost when compared with the 3D-GSE, existing directional and other seminal algorithms.

Recently proposed Generalized Shape Expansion (GSE) algorithm for planning of shortest collision-free path in 2-D environments has shown significant promise in improvement of its performance over several seminal algorithms from existing literature. Recognizing that a suitable directional sampling feature could potentially enhance the performance of the GSE algorithm further, this letter proposes two sampling schemes - basic and augmented directional sampling - and presents GSE-D and GSE-AD algorithms, respectively, as expansion over the GSE. These algorithms, by default, enjoy the advantages of the GSE. Both the directional sampling schemes enable drawing random sample points with more preference towards the direction of the Goal leading to lower cost of computed shortest path on an average. While the basic directional sampling strategy faces a drawback in computational time when obstacle density in the direction towards the Goal is high, the augmented directional sampling scheme is free of this limitation. Probabilistic analysis and extensive numerical simulation studies show the effectiveness of the GSE-D and GSE-AD in performance in terms of computational time efficiency and shortest path cost when compared with the GSE, other seminal and existing directional algorithms.

A novel algorithm is presented in this paper for motion planning of an unmanned aerial vehicle (UAV) from a start position to a goal position in a two-dimensional environment cluttered with stationary obstacles. The algorithm, termed 'GSE', leverages a generalized shape expansion (GSE)-based sampling strategy, the main contribution of the paper, to explore the workspace efficiently. Once the shortest path is found from start position to goal position, a locally optimal trajectory is obtained within the homotopy class using sequential convex programming. Numerical simulations on the performance of the GSE algorithm and comparison of the same with that of some existing well-established algorithms are performed. The computational efficiency of the GSE algorithm is found to be significantly higher than that of the algorithms in comparison, while the trajectory costs obtained by the GSE algorithm is found to be marginally better in comparison with others.