Generalized shape expansion-based motion planning for UAVs in three dimensional obstacle-cluttered environment

The problem of motion planning for an unmanned aerial vehicle (UAV) in an environment cluttered with stationary obstacles has found growing attention. To this end, several algorithms, both deterministic and sampling-based, have been reported in the literature. Recently, a sampling-based motion planning algorithm, named ’GSE’, has been presented for 2-D environment based on a novel sampling strategy-generalized shape expansion. Its effectiveness was found to be equivalent or even better in most aspects with respect to some existing seminal algorithms. Since for UAVs, 3-D environment is of more significance, this paper expands over the GSE algorithm and presents ’3D-GSE’ algorithm for generating shortest path and locally optimal trajectory from within the updated homotopy class using sequential convex programming in stationary obstacle-dense 3-D environments. The shape constructed by the 3D-GSE algorithm covers the available free space maximally, which is much more challenging than in case of 2-D environment. Thus, 3D-GSE exhibits its superiority in performance in terms of computational time efficiency when compared with well-established existing algorithms in extensive numerical simulation study. The trajectory costs obtained by the 3D-GSE algorithm is also found to be marginally better. With all these desired features, the 3D-GSE algorithm has a potential of real-time-implementation.