On the complexity of kinodynamic planning
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 306-316
- https://doi.org/10.1109/sfcs.1988.21947
Abstract
The following problem, is considered: 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. The simplified case of a point mass under Newtonian mechanics together with velocity and acceleration bounds is considered. The point must be flown from a start to a goal, amid 2-D or 3-D polyhedral obstacles. While exact solutions to this problem are not known, the first provably good approximation algorithm is given and shown to run in polynomial time.Keywords
This publication has 11 references indexed in Scilit:
- Planning a minimum-time trajectories for robot armsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Motion planning for an autonomous vehiclePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Global time optimal motions of robotic manipulators in the presence of obstaclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Planning constrained motionPublished by Association for Computing Machinery (ACM) ,1988
- New lower bound techniques for robot motion planning problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- On the time-optimality of bang-bang trajectories in 𝐑³Bulletin of the American Mathematical Society, 1987
- Time-optimal control of manipulatorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Remarks on the time-optimal control of two-link manipulatorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- An algorithm for shortest-path motion in three dimensionsInformation Processing Letters, 1985
- Spatial Planning: A Configuration Space ApproachIEEE Transactions on Computers, 1983