Motion planning in a plane using generalized Voronoi diagrams

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.<>