A Hierarchical Assembly Planning system

Abstract

This dissertation addresses the problem of generating feasible assembly sequences for a mechanical product from a description of it in a fundamentally new way. An operation is a motion to bring together two subassemblies to build another larger subassembly. A series of such operations which make the product from the individual parts is an assembly sequence plan or assembly plan. Current assembly planners suffer from certain problems. Firstly, they cannot find plans for large assemblies because they run into combinatorial problems. Not only that, their architecture is such that they do not appear to be modifiable to be able to handle large assemblies in a meaningful manner. Secondly, they cannot meaningfully capture measures of goodness for a plan in many cases. This dissertation makes an attempt to rectify this situation. A new hierarchical input data structure is introduced and is shown to confer certain advantages in finding a plan. One of these is the fact that case-based knowledge or advice may be incorporated easily so that better goodness measures for plans for specific structures may be realized. The input structure is also closely tied to a new planning algorithm introduced in this dissertation, which finds plans that are not necessarily optimal but close to optimal. Although in the worst case, the time complexity remains exponential, the expected time complexity of this algorithm can be polynomial with respect to the number of parts when the number of levels in the input hierarchy grows in proportion to the log of the number of parts. Furthermore, when similar substructures are repeated within an assembly, the planner can reuse subplans, thus producing better plans more quickly. An assembly planner called Hierarchical Assembly Planner (HAP,) was implemented using the above methods. Experimental results are shown for several products7 demonstrating that the predicted time savings from suboptimizing and reusing plans for similar structures are in fact realized.