Approximation algorithms for robotic motion planning

Robotic motion planning problems are some of the most fundamental problems in robotics research. Each problem computes for a robot paths or trajectories that are collision-free amid a specified set of obstacles and, in certain cases, cost-minimizing according to a user-defined cost function. This dissertation presents a number of results on several robotic motion planning problems.; Our first result is an approximation algorithm for the weighted region optimal path problem. In this problem, a point robot moves in a planar space composed of n triangular regions, each of which is associated with a positive unit weight. The objective is to find, for given source and destination points s and t, a path from s to t with the minimum weighted length. Our algorithm, BUSHWHACK, adopts a traditional approach that converts the original continuous geometric search space into a discrete graph $G$ by placing representative points on boundary edges. However, exploiting geometric structures that we call intervals, BUSHWHACK computes an approximate optimal path more efficiently by accessing only a sparse subgraph of $G$. Combined with the logarithmic discretization scheme introduced by Aleksandrov et al. [14], BUSHWHACK can compute an &epsis;-approximation in O($ne$(log $1e$ + log n) log $1e$) time.; We also study two other optimal path problems, which can be regarded as generalizations of the weighted region optimal path problem. In the first problem, a point robot with a bounded control velocity moves through a set of polygonal regions of given translational flow velocities. The cost of any path is defined to be the time it takes for the robot to traverse the path. In the second problem, a robot travels on the surface of a terrain consisting of polygonal faces with defined friction coefficients. The cost of any path on the terrain is defined to be the energy loss due to both friction and gravity. This problem adds anisotropism to optimal path planning by taking into consideration impermissible traversal directions resulted from overturn danger or power limitations.; Our third main result is a new sampling method for probabilistic roadmap (PRM) planners. The main idea of a PRM planner is to sample at random a robot's configuration space to construct a network, called a roadmap, that represents the geometry of the free space. Previous experimental results have shown that the existence of narrow passages in the configuration space creates significant difficulty for PRM planners to capture the connectivity of the free space. We present a hybrid sampling method in the PRM framework for finding paths through narrow passages. (Abstract shortened by UMI.)...