Assembly sequence and path planning for monotone and nonmonotone assemblies with rigid and flexible parts

The Assembly Sequence and Path Planning (ASPP) problem deals with finding a proper sequence of parts to be assembled into a finished product and short assembly paths for each part. The problem is a combination of Assembly Sequence Planning (ASP) and Assembly Path Planning (APP) subproblems, which are both NPcomplete and therefore intractable at large sizes. Nearly in all works on ASPP, it is assumed that planning is monotone (i.e., parts are moved only once, without considering intermediate placements) and each part is completely rigid. These are simplifying, yet limiting assumptions, since most assembled products like ships, aircraft, and automobiles are composed of rigid and flexible parts, and the generation of assembly sequence and path plans for most real-world products requires intermediate placement of parts to be taken into account. None of the existing works in the literature, however, have handled nonmonotone ASPP problems for rigid and flexible parts, and this issue remains largely untouched. In this paper, we present a new method called SPP-Flex for solving monotone and nonmonotone ASPP for rigid and flexible parts. SPP-Flex first utilizes a Directional Assembly Stress Matrix (DASM) for describing interference relations between all pairs of parts and the amounts of compressive stresses needed for assembling flexible parts and then obtains an initial tentative assembly sequence using a simple new greedy heuristic. Next, short assembly paths are iteratively computed and planned from initial to goal configurations of all parts using a novel sampling-based path planner called BXXT. If finding a free path for an active part fails due to obstruction of a previously assembled part, then such a part is identified, relocated, and its path replanned until the active part is moved to its final position. In case of failure again, if the part is flexible, through finite element analysis, it is determined if the part can still be assembled by undergoing elastic deformation. To evaluate the performance of the SPP-Flex and its components, two new products were designed and solved by four combinations of ASP and APP methods 20 times each, and the means and standard deviations of five performance criteria (total path length, total number of generated nodes and edges in the search tree, total number of collision (interference) checks, and total runtime) were calculated. Analysis of the computational results showed that the proposed greedy heuristic sequence planner together with the BXXT path planner/replanner outperformed other variations with at most 4.6% average gap in path length and 2.1% average gap in runtime compared to the best-found solution in all runs.

Automated summary

The ASPP problem aims to find the proper sequence of parts and short assembly paths, but most existing methods ignore the need for intermediate part placements. This paper introduces a new method called SPP-Flex, which outperforms other methods with a maximum gap of 4.6%.