ASPPR: A New Assembly Sequence and Path Planner/Replanner for Monotone and Nonmonotone Assembly Planning

The Assembly Sequence and Path Planning (ASPP) problem concerns with computing a sequence of assembly motions for constituent parts of an assembled final product while finding collision-free and short paths for parts from their initial location to their final position. ASPP is a challenging problem due to being NP-hard, and is an important subproblem of the Assembly Planning problem, which is encountered frequently in the manufacturing industry and takes up more than half of the total production time. In this paper, a new method called Assembly Sequence and Path Planner/Replanner (ASPPR) is presented to solve the ASPP problem. ASPPR has a sequence-planning component, which is a simple greedy heuristic that in each iteration tries to locally minimize geometric interferences between parts being assembled along the main directions, and a path-planning component, which employs a sampling-based stochastic path planner to plan short paths for parts while avoiding workspace obstacles. Thanks to its replanning feature, the ASPPR method is able to identify and resolve cases where already-assembled parts impede the movements of subsequent parts. While majority of the methods in the literature deal with monotone problems in workspaces without obstacles, the proposed method has the advantage of considering obstacles in the workspace, allowing planning translational and rotational movements for parts, and handling nonmonotone assembly sequence plans, in which the parts need to be relocated to one or more intermediate positions before moving to their final assembled position. To test and measure the effectiveness of the ASPPR, eight problems (a mixture of monotone and non-monotone, in 2D and 3D, and benchmark and new) were solved with five different sampling-based algorithms (three existing and two new) in the path planning component, and the results of 30 runs for each case were thoroughly compared and analyzed. Analytical and statistical analyses showed that our newly proposed unidirectional and bidirectional variants of the original unidirectional and bidirectional Rapidly Exploring Random Trees (RRT) outperformed other planners in the Total Path Length, Total Number of Nodes, Total Number of Edges, Total Number of Collision Checks, and Total Time performance criteria. (C) 2020 Elsevier Ltd. All rights reserved.