ISSN:
1432-0541
Keywords:
Robot motion planning
;
Optimal control
;
Polynomial-timeɛ-approximation algorithm
;
Time-optimal trajectory
;
Shortest path
;
Kinodynamics
;
Polyhedral obstacles
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We consider the following problem: given a robot system, find a minimal-time trajectory that goes from a start state to a goal state while avoiding obstacles by a speed-dependent safety margin and respecting dynamics bounds. In [1] we developed a provably good approximation algorithm for the minimum-time trajectory problem for a robot system with decoupled dynamics bounds (e.g., a point robot in ℝ3). This algorithm differs from previous work in three ways. It is possible (1) to bound the goodness of the approximation by an error termɛ; (2) to bound the computational complexity of our algorithm polynomially; and (3) to express the complexity as a polynomial function of the error term. Hence, given the geometric obstacles, dynamics bounds, and the error termɛ, the algorithm returns a solution that isɛ-close to optimal and requires only a polynomial (in (1/ɛ)) amount of time. We extend the results of [1] in two ways. First, we modify it to halve the exponent in the polynomial bounds from 6d to 3d, so that the new algorithm isO(c d N 1/ɛ)3d ), whereN is the geometric complexity of the obstacles andc is a robot-dependent constant. Second, the new algorithm finds a trajectory that matches the optimal in time with anɛ factor sacrificed in the obstacle-avoidance safety margin. Similar results hold for polyhedral Cartesian manipulators in polyhedral environments. The new results indicate that an implementation of the algorithm could be reasonable, and a preliminary implementation has been done for the planar case.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01586636
Permalink
