Non-uniform discretization approximations for kinodynamic motion planning and its applications

The first main result of this paper is a novel non-uniform approximation method for the kinodynamic motion-planning problem. The kinodynamic motion-planning problem is to compute a collision-free, minimum-time trajectory for a robot whose accelerations and velocities are constrained. Previous approximation methods are all based on a uniform discretization in time space. On the contrary, our method employs a non-uniform discretization in configuration space (thus also a non-uniform one in time space). Compared to the previously best algorithm of Donald and Xavier, the running time of our algorithm reduces in terms of IIE, roughly from O((1/epsilon)(6d-1)) to O((1/epsilon)(4d-2)), in computing a trajectory in a dimensional configuration space, such that the time length of the trajectory is within a factor of (1 + epsilon) of the optimal. More importantly, our algorithm is able to take advantage of the obstacle arrangement, and is expected to perform much better than the analytical result in many cases when the obstacles are sparse or when the obstacles are unevenly distributed. This is because our non-uniform discretization has the property that it is coarser in regions that are farther away from all obstacles. So for the above mentioned situations, the total number of discretized grids will be significantly smaller. Our second main result is the first known polynomial-time approximation algorithm for the curvature-constrained shortest-path problem in 3 and higher dimensions. We achieved this by showing that the approximation techniques for the kinodynamic motion-planning problem are applicable to this problem.