Motion planning in a plane using generalized Voronoi diagrams
- 1 April 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics and Automation
- Vol. 5 (2) , 143-150
- https://doi.org/10.1109/70.88035
Abstract
An algorithm for planning a collision-free path for a rectangle in a planar workspace populated with polygonal obstacles is presented. Heuristic techniques are used to plan the motion along a nominal path obtained from a generalized Voronoi diagram (GVD). The algorithm was demonstrated to be quite fast with execution times comparable to, or exceeding, those of the freeway method. Unlike the freeway method, the GVD technique can be successfully applied to difficult problems which arise in cluttered workspaces. The planned paths stay well away from the obstacles when possible and are somewhat shorter than the freeway paths due to parabolic arcs around corners. Furthermore, motion along the paths is smooth in the sense that rotations are performed during translation, not just at isolated points in the workspace.<>Keywords
This publication has 13 references indexed in Scilit:
- Multiresolution path planning for mobile robotsIEEE Journal on Robotics and Automation, 1986
- A “retraction” method for planning the motion of a discJournal of Algorithms, 1985
- A subdivision algorithm in configuration space for findpath with rotationIEEE Transactions on Systems, Man, and Cybernetics, 1985
- Automatic Synthesis of Fine-Motion Strategies for RobotsThe International Journal of Robotics Research, 1984
- On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifoldsAdvances in Applied Mathematics, 1983
- 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
- Spatial Planning: A Configuration Space ApproachIEEE Transactions on Computers, 1983
- Generalization of Voronoi Diagrams in the PlaneSIAM Journal on Computing, 1981
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979
- Efficient computation of continuous skeletonsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979