GEOMETRIC REASONING ABOUT ASSEMBLY TOOLS

Planning for assembly requires reasoning about various tools used by h umans, robots, or other automation to manipulate, attach, and test par ts and subassemblies. This paper presents a general framework to repre sent and reason about geometric accessibility issues for a wide variet y of such assembly tools. Central to the framework is a nse volume enc oding a minimum space that must be free in an assembly state to apply a given tool, and placement constraints on where that volume must be p laced relative to the parts on which the tool acts. Determining whethe r a tool can be applied in a given assembly state is then reduced to a n instance of the FINDPLACE problem (Lozano-Perez, 1983). In addition, we present more efficient methods to integrate the framework into ass embly planning. For tools that are applied either before or after thei r target parts are mated, one method preprocesses a single tool applic ation for all possible states of assembly of a product in polynomial t ime, reducing all later state-tool queries to evaluations of a simple expression. For tools applied after their target parts are mated, a co mplementary method guarantees polynomial-time assembly planning. We pr esent a wide variety of tools that can be described adequately using t he approach, and survey tool catalogs to determine coverage of standar d tools. Finally, we describe an implementation of the approach in an assembly planning system and experiments with a library of over one hu ndred manual and robotic tools and several complex assemblies. (C) 199 8 Elsevier Science B.V.