Latombe This is the first year of a three-year continuing award. This research will investigate the spatial reasoning issues raised by such questions as In which order can a product be assembled, what parts should be removed from the assembled product to allow the extraction of a specified subassembly, and what is the complexity of the required motions and grasps. The effort will also develop efficient algorithms to answer these questions, given a CAD description of a product. The goals of this research include: (1) Developing assembly planning algorithms that take a wide range of constraints into account, including part collision, subassembly stability, grasping, and fixturing, in order to produce realistic assembly plans; (2) Improving the computational complexity of these algorithms in order to make them efficient enough to be eventually applicable to products made of several hundreds or thousands of parts, for which automated reasoning tools are particularly critical; (3) Developing algorithms for inferring the inherent complexity of an assembly product, i.e., a lower-bound on the complexity of all assembly plans for this product along various dimensions (e.g., number of steps, hands, motions, degrees of freedom); and (4) Studying incremental versions of the above algorithms that will be applicable at low marginal cost while a new assembly product is being designed, in order to provide quick, pertinent feedback to the designers. These issues will be investigated with the use of the ``non-directional blocking graph,'' which addresses the intrinsic structure of a product as determined by the potential interference relations among its components. Because the intrinsic interference structure of a product is a compact representation of all feasible assembly plans, not just of a few of them, it should make it possible to estimate inherent complexity measures of the product and generate plans with the lowest complexity, without having to explicitly enumerate all assembly plans.
