Ph.D., Purdue University, December, 1994
Major Professor: Anthony A. Maciejewski
In this work, a topological characteristic of various classes of configuration space obstacles is explored. In particular, this thesis provides algorithms which establish the connectivity in configuration space of obstacles which are not path-connected in the manipulator's workspace. The goal of this research is to provide a tool for establishing classic representations of the configuration free space, such as the connectivity graph, or to provide more succinct representations, such as the ``abstract free space''. The robot models which are considered include SCARA-type manipulators modelled as line segments, polygonal representations of SCARA-type manipulators, and polyhedral representations of three degree of freedom spatial positioning manipulators, such as the first three links of a PUMA-type manipulator. Obstacles are considered which are due to polygons in the workspace of the SCARA-type manipulator or due to polyhedra in the workspace of the PUMA-type manipulator.
The basis of this algorithm is a concise characterization of obstacles in the manipulator's configuration space. The test which results is shown to be both necessary and sufficient for establishing the existence of an intersection between the obstacles and leads to an extremely efficient algorithm for computing the connectivity of the manipulator's free space. These algorithms have been demonstrated for the case of planning the motions of a single manipulator operating within a cluttered workspace.
This thesis concludes by presenting a mechanism which utilizes these results to determine the effects of the motions of one manipulator on the configuration space of the other. These algorithms are then used as a basis for a simple planner which is capable of rapidly computing collision-free paths for multiple SCARA manipulators operating within overlapping workspaces.