Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: A Provably Good Approximation Algorithm for Optimal-Time Trajectory Planning
Authors: Donald, Bruce Randall
Xavier, Patrick G.
Keywords: computer science
technical report
Issue Date: Nov-1988
Publisher: Cornell University
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.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
88-947.pdf2.31 MBAdobe PDFView/Open
88-947.ps746.1 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us