Automated planning for stacking polyhedral sheet metal parts

This thesis presents a framework for automated planning for stacking identical polyhedral sheet metal parts. The stacking plan is near optimal with respect to a user-specified cost function and consists of a set of homogeneous transformations describing the configuration (position and orientation) of every part in the stack. Every part in the stack is stable and is located inside a convex volume typically obtained by extruding the allotted floor space area by the maximum permissible stack height. The stacking plan accounts for robot positioning errors.; Our framework eases the NP-hard task of planning by stacking parts incrementally. The problem is further simplified by using stability-based heuristics to generate discrete orientations for a part being added to a stack. For every discrete orientation, it is possible to use standard optimization algorithms to compute optimal positions that minimize the cost function.; Our framework provides a tool for computing near-optimal interference-free positions for a part being added to a stack. We have developed a method to compute the orientation interval over which the topology of the face-edge-vertex graph of a configuration space obstacle (set of positions resulting in interference) is constant. Within this interval, configuration space obstacle geometry for one orientation can be extrapolated to obtain the obstacle geometry for other orientations. Further, we are able to compute near-optimal interference-free configurations by computing only a partial description of the c-space obstacles. We also provide a tool to enumerate contacts, compute the set of instantaneous legal motions for a polyhedron constrained by contacts, and use this set to analyze part stability.; We have developed a prototype planner based on our framework. We use a quadratic cost function that accounts for floor space utilization and heights of centers of gravity of parts in a stack. Stacking plans generated by the planner ensure that the parts can be grasped using suction cups and can be added to the stack from the top. We discuss the performance of the planner for three example parts.; Automating planning for stacking completes the automation of process planning for sheet metal forming. Our results might be of interest to researchers in the areas of robot path planning, assembly modeling and planning, fixturing and optimal 3D layout problems.