Determining near optimal interference-free polyhedral configurations for stacking

This paper uses a configuration space (c-space) approach to finding a satisfactory stack of polyhedral parts; we tested this method with industrial sheet metal parts. The optimal configuration for a new part, added to an existing stack, minimizes distance from a user-specified desired position, lies inside a given c-space region and, avoids interference with parts already in the stack. We present an iterative c-space based method that works with discrete orientations and yet produces interference-free configurations close to the desired part configuration. Two techniques are used to speed up the most computationally intensive step of c-space obstacle computation. An algorithm to compute orientation ranges within which connectivity graph topology of the obstacle stays constant is presented. For every discrete orientation, we construct only a portion of the c-space obstacle in order to compute an interference-free configuration