Computing metric and topological properties of configuration-space obstacles
- 7 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 170-176
- https://doi.org/10.1109/robot.1989.99985
Abstract
The author describes an algorithm that takes two polygons as input, and computes a representation of their corresponding configuration-space obstacle, including contact information. The algorithm's output includes a full metric and topological description of the obstacle surface, as well as the set of polygon features that are in contact for each point of the surface. The representation is exact, up to the limits of floating-point arithmetic. The algorithm has been implemented and test-run on over 40 input pairs; run times varied between 12 and 135 s.Keywords
This publication has 7 references indexed in Scilit:
- A Voronoi method for the piano-movers problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- A practical exact motion planning algorithm for polygonal objects amidst polygonal obstaclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Generation of configuration space obstacles: the case of a moving sphereIEEE Journal on Robotics and Automation, 1988
- A simple motion-planning algorithm for general robot manipulatorsIEEE Journal on Robotics and Automation, 1987
- A search algorithm for motion planning with six degrees of freedomArtificial Intelligence, 1987
- On the “piano movers'” problem I. The case of a two‐dimensional rigid polygonal body moving amidst polygonal barriersCommunications on Pure and Applied Mathematics, 1983
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979