Nonuniform discretization for kinodynamic motion planning and its applications

The first main result of this paper is a novel nonuniform discretization ap proximation method for the kinodynamic motion-planning problem. The kinodyn amic motion-planning problem is to compute a collision-free, time-optimal t rajectory for a robot whose accelerations and velocities are bounded. Previ ous approximation methods are all based on a uniform discretization in the time space. On the contrary, our method employs a nonuniform discretization in the configuration space ( thus also a nonuniform one in the time space) . Compared to the previously best algorithm of Donald and Xavier, the runni ng time of our algorithm reduces in terms of 1/epsilon, roughly from O((1/e psilon)(6d-1)) to O((1/epsilon)(4d-2)), in computing a trajectory in a d-di mensional configuration space, such that the time length of the trajectory is within a factor of (1 + epsilon) of the optimal. More importantly, our a lgorithm is able to take advantage of the obstacle distribution and is expe cted to perform much better than the analytical result. This is because our nonuniform discretization has the property that it is coarser in regions t hat are farther from all obstacles. So for situations where the obstacles a re sparse, or the obstacles are unevenly distributed, the size of the discr etization is significantly smaller. Our second main result is the first known polynomial-time approximation alg orithm for the curvature-constrained shortest-path problem in three and hig her dimensions. We achieved this by showing that the approximation techniqu es for the kinodynamic motion-planning problem are applicable to this probl em.