ABSTRACT
The first main result of this paper is a novel non-uniform approximation method for the kinody namic motion-planning problem. The kinodynamic motion-planning problem is to compute a collision-free, minimum-time trajectory for a robot whose acceler ations and velocities are constrained. Previous ap proximation methods are all based on a uniform dis cretization 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 Don ald and Xavier, the running time of our algorithm reduces in terms of 1/e, roughly from 0 ( ( l /e ) 6^ 1) to 0 ( ( l /e )Ad~2), in computing a trajectory in a ddimensional configuration space, such that the time length of the trajectory is within a factor of (1 + e) of the optimal. More importantly, our algorithm is able to take advantage of the obstacle arrangement, and is ex pected 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 ob stacles. So for the above mentioned situations, the total number of discretized grids will be significantly smaller.
