Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6787
 Title: A Provably Good Approximation Algorithm for Optimal-Time Trajectory Planning Authors: Donald, Bruce RandallXavier, Patrick G. Keywords: computer sciencetechnical report Issue Date: Nov-1988 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-947 Abstract: We consider the following problem: given a robot system, find a minimal-time trajectory from a start position and velocity to a goal position and velocity, while avoiding obstacles and respecting dynamic constraints on velocity and acceleration. Based on the theoretical results of [CDRX], we have developed and implemented a new, provably good approximation algorithm for the minimum-time trajectory problem. Our algorithm differs from previous work in three ways. First, it is possible to bound the goodness of the approximation by an error term $\epsilon$. Second, we can polynomially bound the running time (complexity) of our algorithm. Third, we can express the complexity as a polynomial function of the error term. Hence, one supplies the algorithm with the geometric obstacles, dynamics bounds, and the error term $\epsilon$. The algorithm returns a solution that is $\epsilon$-close to optimal, and promises to spend only a polynomial (in $(\frac{1}{\epsilon})$) amount to time computing the answer. In this paper, we describe the algorithm and explain the results in simple terms. We show how it can be applied to robotics, and report on an implementation and experiments. URI: http://hdl.handle.net/1813/6787 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat