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 NP-complete 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.     

A hierarchical approach on assembly sequence planning and optimal sequences analyzing

Assembly sequence planning (ASP) is a critical technology that bridges product design and realization. Deriving and fulfilling of the assembly precedence relations (APRs) are the essential points in assembly sequences reasoning. In this paper, focusing on APRs reasoning, ASP, and optimizing, a hierarchical ASP approach is proposed and its key technologies are studied systematically. APR inferring and the optimal sequences searching algorithms are designed and realized in an integrated software prototype system. The system can find out the geometric APRs correctly and completely based on the assembly CAD model. Combined with the process APRs, the geometric and engineering feasible assembly sequences can be inferred out automatically. Furthermore, an algorithm is designed by which optimal assembly sequences can be calculated out from the immense geometric and engineering feasible assembly sequences. The case study demonstrates that the approach and its algorithms may provide significant assistance in finding the optimal ASP and improving product assembling.     

基于成本和并行装配的装配序列有向图求解

针对虚拟装配中装配序列规划问题,引入了有向图来描述装配过程中的零件以及零件间的装配约束关系。结合装配成本、并行装配、装配经验优化了装配关系有向图的拓扑排序算法。提出了将装配方向变化次数作为衡量装配成本的一项重要指标。提出了将单次可装配的零件数量作为装配优先方向的参考依据。文章最后给出了装配序列生成的具体算法。     

A General Framework for Assembly Planning: The Motion Space Approach

Assembly planning is the problem of finding a sequence of motions to assemble a product from its parts. We present a general framework for finding assembly motions based on the concept of motion space . Assembly motions are parameterized such that each point in motion space represents a mating motion that is independent of the moving part set. For each motion we derive blocking relations that explicitly state which parts collide with other parts; each subassembly (rigid subset of parts) that does not collide with the rest of the assembly can easily be derived from the blocking relations. Motion space is partitioned into an arrangement of cells such that the blocking relations are fixed within each cell. We apply the approach to assembly motions of several useful types, including one-step translations, multistep translations, and infinitesimal rigid motions. Several efficiency improvements are described, as well as methods to include additional assembly constraints into the framework. The resulting algorithms have been implemented and tested extensively on complex assemblies. We conclude by describing some remaining open problems. Received November 15, 1996; revised January 15, 1998.     

Chaotic particle swarm optimization for assembly sequence planning

Assembly sequence planning of complex products is difficult to be tackled, because the size of the search space of assembly sequences is exponentially proportional to the number of parts or components of the products. Contrasted with the conventional methods, the intelligent optimization algorithms display their predominance in escaping from the vexatious trap. This paper proposes a chaotic particle swarm optimization (CPSO) approach to generate the optimal or near-optimal assembly sequences of products. Six kinds of assembly process constraints affecting the assembly cost are concerned and clarified at first. Then, the optimization model of assembly sequences is presented. The mapping rules between the optimization model and the traditional PSO model are given. The variable velocity in the traditional PSO algorithm is changed to the velocity operator (vo) which is used to rearrange the parts in the assembly sequences to generate the optimal or near-optimal assembly sequences. To improve the quality of the optimal assembly sequence and increase the convergence rate of the traditional PSO algorithm, the chaos method is proposed to provide the preferable assembly sequences of each particle in the current optimization time step. Then, the preferable assembly sequences are considered as the seeds to generate the optimal or near-optimal assembly sequences utilizing the traditional PSO algorithm. The proposed method is validated with an illustrative example and the results are compared with those obtained using the traditional PSO algorithm under the same assembly process constraints.     

Artificial immune systems for assembly sequence planning exploration

Assembly sequence planning (ASP) needs to take relevant constraint factors such as the geometric characteristics and tool factors into consideration so as to work out a particular assembly sequence. At last, a product will come into being through the assembly of each part according to the assembly sequence. A problem encountered in ASP is that a larger number of components will cause more constraints to assembly a product, thus increasing the complexity of assembly problem. Therefore, it has been an objective for researchers to look for suitable methods for the solution space of feasible solutions.Among them, traditional genetic algorithms (GAs) belong to a random searching method. When the constraints are complicated in ASP, GAs often come out with a large number of solutions not feasible. Consequently, previous research results have proposed some approaches such as Guided genetic algorithms (Guided-GAs) or memetic algorithms (MAs) to enhance the structure of GAs to cope with the complexity of constraints in ASP problems. In this study, artificial immune systems (AIS) were proposed to help solve the assembly sequence problem. In AIS algorithm, the antibody (Ab) in the immune system is simulated to encounter one or more unknown antigens (Ags). Moreover, the clonal selection concept is employed in the immune system in which a better antibody will be selected in each generation of revolution and different antibodies will be cloned to protect the infection of the original antigen. With this mechanism, the shortcoming such as the traditional GAs to converge in local optimal solution will be overcome. Practical examples have demonstrated that AIS can solve the ASP problem with complicated constraints. Compared with guided genetic algorithms and memetic algorithms, AIS can generate the same or better solutions in terms of quality and searching time.     

Assembly sequence planning based on structure cells in open design

Advances in computer network technologies have enabled firms to increasingly utilize external resources to remain competitive. Based on the function-behavior-structure cell (FBSC) modeling and computer network technologies, consumers with design knowledge and experience, called co-designers in this research, can involve in the process of open design (OD) to share their requirements, experiences and knowledge. The structure cells (SCs) provided by the co-designers in OD and the relationships among them are critical for generating the optimal design scheme and assembly sequence planning. However, the existing assembly sequence planning (ASP) approaches mainly focus on identification of the assembly plan based on precedence relations of operations from the predefined parts in the design scheme without considering the utilization of resources available in OD. In this study, a new approach for ASP based on SCs in OD is proposed to tackle this problem. First, the assembly features of the SCs and their matching rules are described in OD, and an approach for calculating the matching intensity between SCs is developed for identifying the assembly relationships between SCs. The design scheme is generated according to the SCs and their assembly relationships. Second, the base part of the design scheme is determined by its correlation degree with other parts. The feasible assembly sequences are derived by reversing the disassembly sequences. As the increase of the number of parts in design scheme will result in the combinatorial explosion of feasible assembly sequences, a particle swarm optimization algorithm is presented to achieve the optimal assembly sequence. A case study is provided to demonstrate the feasibility and effectiveness of the proposed approach.     

A hybrid genetic algorithm for multi-objective product plan selection problem with ASP and ALB

Facing current environment full of a variety of small quantity customized requests, enterprises must provide diversified products for speedy and effective responses to customers’ requests. Among multiple plans of product, both assembly sequence planning (ASP) and assembly line balance (ALB) must be taken into consideration for the selection of optimal product plan because assembly sequence and assembly line balance have significant impact on production efficiency. Considering different setup times among different assembly tasks, this issue is an NP-hard problem which cannot be easily solved by general method. In this study the multi-objective optimization mathematical model for the selection of product plan integrating ASP and ALB has been established. Introduced cases will be solved by the established model connecting to database statistics. The results show that the proposed Guided-modified weighted Pareto-based multi-objective genetic algorithm (G-WPMOGA) can effectively solve this difficult problem. The results of comparison among three different kinds of hybrid algorithms show that in terms of the issues of ASP and ALB for multiple plans, G-WPMOGA shows better problem-solving capability for four-objective optimization.     

Haptic assisted aircraft optimal assembly path planning scheme based on swarming and artificial potential field approach

In this research, a novel near optimum automated rigid aircraft engine parts assembly path planning algorithm based on particle swarm optimization approach is proposed to solve the obstacle free assembly path planning process in a 3d haptic assisted environment. 3d path planning using valid assembly sequence information was optimized by combining particle swarm optimization algorithm enhanced by the potential field path planning concepts. Furthermore, the presented approach was compared with traditional particle swarm optimization algorithm (PSO), ant colony optimization algorithm (ACO) and genetic algorithm (CGA). Simulation results showed that the proposed algorithm has faster convergence rate towards the optimal solution and less computation time when compared with existing algorithms based on genetics and ant colony approach. To confirm the optimality of the proposed algorithm, it was further experimented in a haptic guided environment, where the users were assisted with haptic active guidance feature to perform the process opting the optimized assembly path. It was observed that the haptic guidance feature further reduced the overall task completion time.     

A physically based approach with human–machine cooperation concept to generate assembly sequences

Assembly plan is considered one of the important stages to minimize the cost of manufacturer and to ensure the safety of assembly operation, the main problem of assembly sequence planning approach is how to reduce the deviation from the real manufacture conditions. In this paper, we have extensively investigated a novel approach to automatically generate the assembly sequences for industrial field, which is especially applied to other large-scale structures. A physically based assembly representation model includes not only the pre-determined basic assembly information, such as precedence relations between parts or subassemblies, geometric constraints, different assembly types, and also the dynamic real-time physical properties, such as the center position of gravity, the force strength of the part, et al. This representation model considered the influences on optimum sequences by assembly operations will be modified by the feedback from interactive virtual environment. Then, we select the safety, efficiency and complexity as the optimization objectives. A hybrid search approach may be used to find the optimum assembly sequence, which will be integrated into an interactive assembly virtual environment (IAVE). It means that the results of assembly interaction can be provided to update the assembly planning model as a feedback, by which the approach will take advantages of the immune memory for local optimum search. The user can adjust the assembly sequences with obvious good objective by interaction with IAVE to improve the performance of the search algorithm. We describe human–machine cooperation (HMC) method for ASP in this work, by which human also can play a pivotal role instead of pure soft-computing. A series of numerical experiments are done to validate the performance of the physically based approach (PBA) to generate assembly sequence, which shows the efficiency and the operability to guide the assembly work.     

Single assembly sequence to flexible assembly plan by Autonomous Constraint Generation

The factory of the future is steering away from conventional assembly line production with sequential conveyor technology, towards flexible assembly lines, where products dynamically move between work-cells. Flexible assembly lines are significantly more complex to plan compared to sequential lines. Therefore there is an increased need for autonomously generating flexible robot-centered assembly plans. The novel Autonomous Constraint Generation (ACG) method presented here will generate a dynamic assembly plan starting from an initial assembly sequence, which is easier to program. Using a physics simulator, variations of the work-cell configurations from the initial sequence are evaluated and assembly constraints are autonomously deduced. Based on that the method can generate a complete assembly graph that is specific to the robot and work-cell in which it was initially programmed, taking into account both part and robot collisions. A major advantage is that it scales only linearly with the number of parts in the assembly. The method is compared to previous research by applying it to the Cranfield Benchmark problem. Results show a 93% reduction in planning time compared to using Reinforcement Learning Search. Furthermore, it is more accurate compared to generating the assembly graph from human interaction. Finally, applying the method to a real life industrial use case proves that a valid assembly graph is generated within reasonable time for industry.     

An enhanced genetic algorithm for automated assembly planning

Automated assembly planning reduces manufacturing manpower requirements and helps simplify product assembly planning, by clearly defining input data, and input data format, needed to complete an assembly plan. In addition, automation provides the computational power needed to find optimal or near-optimal assembly plans, even for complex mechanical products. As a result, modern manufacturing systems use, to an ever greater extent, automated assembly planning rather than technician-scheduled assembly planning. Thus, many current research reports describe efforts to develop more efficient automated assembly planning algorithms. Genetic algorithms show particular promise for automated assembly planning. As a result, several recent research reports present assembly planners based upon traditional genetic algorithms. Although prior genetic assembly planners find improved assembly plans with some success, they also tend to converge prematurely at local-optimal solutions. Thus, we present an assembly planner, based upon an enhanced genetic algorithm, that demonstrates improved searching characteristics over an assembly planner based upon a traditional genetic algorithm. In particular, our planner finds optimal or near-optimal solutions more reliably and more quickly than an assembly planner that uses a traditional genetic algorithm.     

Assembly Coplanner: co-operative assembly planner based on subassembly extraction

The distribution of assembly workstations enables assembly operations to be done in parallel, while the multiple routing of parts in flexible assembly systems allows the opportunistic scheduling of assembly operations. This paper presents an assembly planning system, called the Assembly Coplanner, which automatically constructs an assembly partial order and generates a set of assembly instructions from a liaison graph representation of an assembly based on the extraction of preferred subassemblies. Assembly planning in Coplanner is carried out by the co-operation of multiple planning agents, such as the geometric reasoner, the physical reasoner, the resource manager and the plan coordinator, under the constraints of finding a cost-effective assembly plan in a flexible assembly system. The Coplanner identifies spatial parallelism in assembly as a means of constructing temporal parallelism among assembly operations. This is achieved in the following way: (1) the selection of a set of tentative subassemblies by decomposing a liaison graph into a set of subgraphs based on feasibility and difficulty of disassembly; (2) the evaluation of each of the tentative subassemblies in terms of assembly cost represented by subassembly selection indices; and (3) the construction of a hierarchical partial order graph (HPOG) as an assembly plan. A case study applying the Coplanner to a mechanical assembly is illustrated in this paper.     

Towards online reinforced learning of assembly sequence planning with interactive guidance systems for industry 4.0 adaptive manufacturing

Literature shows that reinforcement learning (RL) and the well-known optimization algorithms derived from it have been applied to assembly sequence planning (ASP); however, the way this is done, as an offline process, ends up generating optimization methods that are not exploiting the full potential of RL. Today’s assembly lines need to be adaptive to changes, resilient to errors and attentive to the operators’ skills and needs. If all of these aspects need to evolve towards a new paradigm, called Industry 4.0, the way RL is applied to ASP needs to change as well: the RL phase has to be part of the assembly execution phase and be optimized with time and several repetitions of the process. This article presents an agile exploratory experiment in ASP to prove the effectiveness of RL techniques to execute ASP as an adaptive, online and experience-driven optimization process, directly at assembly time. The human-assembly interaction is modelled through the input-outputs of an assembly guidance system built as an assembly digital twin. Experimental assemblies are executed without pre-established assembly sequence plans and adapted to the operators’ needs. The experiments show that precedence and transition matrices for an assembly can be generated from the statistical knowledge of several different assembly executions. When the frequency of a given subassembly reinforces its importance, statistical results obtained from the experiments prove that online RL applications are not only possible but also effective for learning, teaching, executing and improving assembly tasks at the same time. This article paves the way towards the application of online RL algorithms to ASP.     

基于改进人工萤火虫算法的装配序列规划研究

装配是装备保养维护的重要环节,高效和无损地装配好拆卸维护的零件在战场上尤为重要.为了解决装配序列规划最优解问题,根据装配序列规划的特点,提出了基于人工萤火虫算法的离散SA-GSO算法.首先利用干涉矩阵对装配序列进行了可行性分析,并根据操作实际设定了适应度函数;然后针对人工萤火虫算法存在的易早熟等缺陷,利用模拟退火原理进行优化并对算法进行离散化,以适用于装配序列最优解问题;最后进行了实例验证,实验结果证明了该算法的可行性及有效性.     

虚拟环境中产品装配过程回溯方法研究

在记录虚拟装配过程的基础上，提出基于任务时间的虚拟装配过程整体回溯与基于任务对象的虚拟装配过程局部回溯方法．虚拟装配过程整体回溯以装配任务时间为回溯准则，允许将装配场景中零部件的方位与装配关系回溯到曾经存在的装配历史状态，而虚拟装配过程局部回溯，是根据装配序列中零件间装配约束与几何干涉方面存在的相关性进行装配过程的选择性回溯．文中方法在虚拟设计与装配原型系统开发中得到实现．实践表明，装配过程回溯方法有效地提高了虚拟环境中产品装配设计的效率。     

求解机械装配规划的新方法

本文提出一个求解机械装配规划的算法,其计算量～O(sN~2),其中s是零件所有可能装配方向的个数,N是工件的零件数(一般s～O(N)).而现行的求机械装配规划的算法,其计算量均随N的增加按指数律增加.     

Integrated knowledge-based Petri net intelligent flexible assembly planning

Automatic assembly planning is recognized as an important tool for reducing manufacturing costs in concurrent product and process development. A novel knowledge-based Petri net (KBPN) is defined, based on the incorporation of expert systems into the usual Petri nets, and used for a unified assembly knowledge representation scheme. A KBPN-approach integrated with a sequence generation algorithm is proposed for the modeling, planning, simulation, analysis and evaluation of the flexible assembly system (FAS). The developed KBPN-based assembly planning system (KAPS) can automatically adjust the deviations between the theoretical planning parameters and the process parameters of real assembly operations to guarantee the best strategies and plans (sequences) for flexible assembly. The research findings are exemplified with a simple assembly to show the effectiveness of the method.