Approximate and adaptive algorithms for some optimal motion-planning problems

Robotic motion planning involves computing collision-free paths or trajectories for a robot moving amid obstacles. It is one of the most fundamental problems in robotics research. This dissertation presents three major results on some motion-planning problems. Our first result is a novel approximation algorithm for the kinodynamic motion-planning problem. We consider the case of a point robot moving in a d-dimensional configuration space, with constrained dynamics. The constraints are given by upper-bounding the $L\sb2$ norms of the accelerations and velocities. Contrary to the previous approximation methods which use a uniform discretization in time space, our method employs a non-uniform discretization in configuration space (thus also a non-uniform one in time space). The discretization is coarser in regions that are farther away from any obstacles. The major consequence of such a discretization is a considerable decrease in the size of the search space, and in the running time, for many cases when the obstacles are sparse or are unevenly distributed. The second result is a faster approximation algorithm for the 2D curvature-constrained shortest-path problem. In the problem, the robot is a point moving in a plane whose path has a maximum curvature of 1, and the obstacles are polygons with a total of n vertices. The objective is to compute for the robot a shortest collision-free path that connects a given initial location and orientation to a final location and orientation. Compared to the previously best known result of Jacobs and Canny, the running time of our algorithm improves roughly from $O(n\sp3)$ to $O(n\sp2).$ More importantly, our running time does not depend on the total length of the obstacle edges, which can be arbitrarily large. Our third result is an optimal algorithm for an on-line navigation problem, the wall problem with penetrable obstacles. In the original wall problem of Blum et al., the point robot is to reach an oriented infinite line while moving amid oriented rectangular obstacles which are impenetrable. We generalize the obstacles to be penetrable and to have different weights. The objective is to minimize the weighted Euclidean distance.