An efficient algorithm which finds collision free paths for a manipulator with 5 or 6 revolute joints is described. It solves the problem for four degree of freedom pick and place operations. Examples are given of paths found by the algorithm in tightly cluttered workspaces. The algorithm first describes free space in two ways: as freeways for the hand and payload ensemble and as freeways for the upperarm. Freeways match volumes swept out by manipulator motions and can be "inverted" to find a class of topologically equivalent path segments. The two freeway spaces are searched concurrently under projection of constraints determined by motion of the forearm.

A hierarchical representation for configuration space is presented, along with an algorithm for searching that space for collision-free paths. The detail of the algorithm are presented for polygonal obstacles and a moving object with two translational and one rotational degrees of freedom.

Free space is represented as a union of (possibly overlapping) generalized cones. An algorithm is presented which efficiently finds good collision free paths for convex polygonal bodies through space littered with obstacle polygons. The paths are good in the sense that the distance of closest approach to an obstacle over the path is usually far from minimal over the class of topologically equivalent collision free paths. The algorithm is based on characterizing the volume swept by a body as it is translated and rotated as a generalized cone and determining under what conditions generalized cone is a subset of another.