STD-Trees: Spatio-temporal Deformable Trees for Multirotors Kinodynamic Planning

Abstract

In constrained solution spaces with a huge number of homotopy classes, standalone sampling-based kinodynamic planners suffer low efficiency in convergence. Local optimization is integrated to alleviate this problem. In this paper, we propose to thrive the trajectory tree growing by optimizing the tree in the forms of deformation units, and each unit contains one tree node and all the edges connecting it. The deforming proceeds both spatially and temporally by optimizing the node state and edge time durations efficiently. Deforming the unit only changes the tree locally yet improves the overall quality of a corresponding subtree. Further, to consider the computation burden and optimizing level, patterns to deform different tree parts in combination of different deformation units are studied and compared, all showing much faster convergence. The proposed deformation can be easily integrated into different RRT-based kinodynamic planning methods, and numerical experiments show that integrating the spatio-temporal deformation greatly accelerates the convergence and outperforms the spatial-only deformation.