Vertices correspond to collision-free configurations of the robot.
An edge exists between two vertices if a path between the two corresponding configurations can be found by a local planning method. Unfortunately, for some problems running times may still be unacceptably large and solutions sub-optimal. We provide speed and quality optimization strategies applicable in cluttered 3-dimensional workspaces. Speed improvements for roadmap construction are accomplished by parallel processing and faster failure detection techniques. Quality improvements for the roadmap constructed are accomplished by new roadmap building methods which result in roadmaps that better represent the connectivity of the free configuration space.