Knowledge intensive Petri net framework for concurrent intelligent design of automatic assembly systems

The integration of design and planning of flexible assembly system has been recognized as a tool for achieving efficient assembly in a production environment that demands assembly with a high degree of flexibility. This paper proposes a concurrent intelligent approach and framework for the design of robotic flexible assembly systems. The principle of the proposed approach is based on the knowledge Petri net formalisms, incorporating Petri nets with more general problem-solving strategies in AI using knowledge-based system techniques. The complex assembly systems are modeled and analyzed by adopting a formal representation of the system dynamic behaviors through knowledge Petri net modeling from the specifications and the analysis of those models. A template is first defined for a knowledge Petri net model, and then the models for assembly system individuals are established in the form of instances of the template. The design of assembly systems is implemented through a knowledge Petri net-based function–behavior–structure model. The research results show that the proposed knowledge Petri net approach is applicable for design, simulation, analysis and evaluation, and even layout optimization of the flexible assembly system in an integrated intelligent environment. The integration of assembly design and planning process can help reduce the development time of assembly systems.     

An object-oriented knowledge based Petri net approach to intelligent integration of design and assembly planning

Artificial intelligence can play an important role in the reduction of manufacturing costs and the enhancement of production efficiency and product quality. In order to assist designers in the early stages of a product development this paper develops an intelligent methodology for integration of design and assembly planning processes, including product design, assembly evaluation and redesign, assembly process planning, design of assembly system and assembly simulation, subjected to both econo-technical and ergonomic evaluations. A new unified class of object-oriented knowledge based Petri nets called OOKPNs, incorporating knowledge based expert systems and fuzzy logic into ordinary place–transition Petri nets, is defined and used for the representation and modeling of the distributed design processes. A prototype intelligent integrated design and assembly planning system (IIDAP) is implemented through distributed blackboard structure with concurrent integration of multiple cooperative knowledge sources and software. It consists essentially of the networked agents and the meta-system, each of which is a knowledge Petri net system with the capabilities of problem solving, learning and conflict resolution, and can be obtained through the inheritance, polymorphism and dynamic binding of instances of OOKPNs. In IIDAP system, both C/C++ language and COOL (CLIPS object-oriented language) are used to incorporate a Petri net tool, a geometric modeling and design tool, a planner and simulator and an evaluation tool. By use of this system, product design and assembly planning can be carried out simultaneously and intelligently in an entirely computer-aided concurrent design and assembly planning system. The design of manufacturable, cost-effective, usable products can therefore be achieved rapidly and flexibly. The developed methodology and system have been successfully applied to assembly design and planning of a micro switch.     

A knowledge intensive multi-agent framework for cooperative/collaborative design modeling and decision support of assemblies

Multi-agent modeling has emerged as a promising discipline for dealing with decision making process in distributed information system applications. One of such applications is the modeling of distributed design or manufacturing processes which can link up various designs or manufacturing processes to form a virtual consortium on a global basis. This paper proposes a novel knowledge intensive multi-agent cooperative/collaborative framework for concurrent intelligent design and assembly planning, which integrates product design, design for assembly, assembly planning, assembly system design, and assembly simulation subjected to econo-technical evaluations. An AI protocol based method is proposed to facilitate the integration of intelligent agents for assembly design, planning, evaluation and simulation process. A unified class of knowledge intensive Petri nets is defined using the O-O knowledge-based Petri net approach and used as an AI protocol for handling both the integration and the negotiation problems among multi-agents. The detailed cooperative/collaborative mechanism and algorithms are given based on the knowledge objects cooperation formalisms. As such, the assembly-oriented design system can easily be implemented under the multi-agent-based knowledge-intensive Petri net framework with concurrent integration of multiple cooperative knowledge sources and software. Thus, product design and assembly planning can be carried out simultaneously and intelligently in an entirely computer-aided concurrent design and assembly planning system.     

Dynamic scheduling in flexible assembly system based on timed Petri nets model

This paper investigates a scheduling model for optimal production sequencing in a flexible assembly system. The system features a set of machines working together in the same workspace, with each machine performing a subset of operations. Three constraints are considered: (1) the precedence relation among the operations specified by the assembly tree; (2) working space that limits concurrent operations; and (3) the variation of process time. The objective is to find both a feasible assignment of operations to machines and schedule tasks in order to minimize the completion time for a single product or a batch of products. The assembly process is modeled using timed Petri nets and task scheduling is solved with a dynamic programming algorithm. The method calculates the time required precisely. A detailed case study is discussed to show the effectiveness of the model and algorithm.     

面向对象Petri网在柔性贴装系统仿真中的应用

Petri网十分适合分析、设计柔性制造系统。在Petri网基础上引入面向对象(OO)技术,采用面向对象Petri网(OPN),建立了一个PCB元件柔性贴装系统的完整的OPN模型。并利用对象之间的消息传递技术实现了两个共享工作区和物料区的机械手的无冲突工作,为其它复杂的多机械手柔性装配系统的建模提供了数学和图形工具。     

Assembly sequence planning of rigid and flexible parts

Assembly sequence planning (ASP) is the process of computing a sequence of assembly motions for constituent parts of an assembled final product. ASP is proven to be NP-hard and thus its effective and efficient solution has been a challenge for the researchers in the field. Despite the fact that most assembled products like ships, aircrafts and automobiles are composed of rigid and flexible parts, no work exists for assembly/disassembly sequence planning of flexible parts. This paper lays out a theoretical ground for modeling the deformability of flexible assembly parts by introducing the concept of Assembly stress matrix (ASM) to describe interference relations between parts of an assembly and the amount of compressive stress needed for assembling flexible parts. Also, the Scatter Search (SS) optimization algorithm is customized for this problem to produce high-quality solutions by simultaneously minimizing both the maximum applied stress exerted for performing assembly operations and the number of assembly direction changes. The parameters of this algorithm are tuned by a TOPSIS-Taguchi based tuning method. A number of ASP problems with rigid and flexible parts were solved by the presented SS and other algorithms like Genetic and Memetic algorithms, Simulated Annealing, Breakout Local Search, Iterated Local Search, and Multistart Local Search, and the results and their in-depth statistical analyses showed that the SS outperformed other algorithms by producing the best-known or optimal solutions with highest success rates.     

Robustness analysis of non-ordinary Petri nets for flexible assembly systems

Non-ordinary controlled Petri nets (NCPNs) have the advantages to model flexible assembly systems in which multiple identical resources may be required to perform an operation. However, existing studies on NCPNs are still limited. For example, the robustness properties of NCPNs have not been studied. This motivates us to develop an analysis method for NCPNs. Robustness analysis concerns the ability for a system to maintain operation in the presence of uncertainties. It provides an alternative way to analyse a perturbed system without reanalysis. In our previous research, we have analysed the robustness properties of several subclasses of ordinary controlled Petri nets. To study the robustness properties of NCPNs, we augment NCPNs with an uncertainty model, which specifies an upper bound on the uncertainties for each reachable marking. The resulting PN models are called non-ordinary controlled Petri nets with uncertainties (NCPNU). Based on NCPNU, the problem is to characterise the maximal tolerable uncertainties for each reachable marking. The computational complexities to characterise maximal tolerable uncertainties for each reachable marking grow exponentially with the size of the nets. Instead of considering general NCPNU, we limit our scope to a subclass of PN models called non-ordinary controlled flexible assembly Petri net with uncertainties (NCFAPNU) for assembly systems and study its robustness. We will extend the robustness analysis to NCFAPNU. We identify two types of uncertainties under which the liveness of NCFAPNU can be maintained.     

A Petri net model for integrated process and job shop production planning

In this paper a new Petri net class (Chameleon systems) for modeling and analyzing joined process planning and job shop production planning is proposed based on the multi-level Petri net model introduced by Valk (1995). Chameleon system is a High-level Petri net extended with time that consists of a High-level Petri net modeling the workshop which is called system net and ordinary Petri net modeling the jobs and setups which act as tokens of the system net and therefore are called token nets. Process plans of the jobs are partial orders of operation groups and alternatives. The uncertainty of operation duration is captured by a new time model. The advantages of this new modeling approach are the following: (i) a modular construction of the joined process and job shop planning is allowed, (ii) classical known Petri net analysis methods can be applied and (iii) the analysis can be done at different levels of abstraction.     

Analysis of assembly operations’ difficulty using enhanced expert high-level colored fuzzy Petri net model

Majority of the products can be assembled in several ways that means the same final product can be realized by different sequences of assembly operations. Different degree of difficulty is associated with each sequence of assembly operation and such difficulties are caused by the different mechanical constraints forced by the different sequences of operations. In the past, few notable attempts have been made to represent and enumerate the degree of difficulty associated with an assembly sequence (in the form of triangular fuzzy number) by using the concept of assembly graph. However, such representation schemes do not possess the capabilities to model the user's reasoning and preferences. In this research, an intelligent Petri net model that combines the abilities of modelling, planning and performance evaluation for assembly operation is presented. This modelling tool can represent the issues concerning degree of difficulty associated with assembly sequences. The proposed mechanism is enhanced expert high-level colored fuzzy Petri net (EEHLCFPN) that is a hybrid of knowledge-based system and colored Petri net. An example encompassing assembly of subassemblies is considered to efficiently delineate the modelling capabilities of proposed hybrid petri net model.     

A Petri net-based methodology to increase flexibility in service-oriented holonic manufacturing systems

Distributed control systems such as the holonic manufacturing systems and service-oriented architectures have demonstrated to provide higher levels of flexibility, notably in the planning and scheduling functionalities, if well exploited. In scheduling, the use of fixed process plans generated by traditional planning approaches, usually leads to unrealistic schedules due to the lack of considerations of the workshop status. IPPS approaches try to break the gap between these two functionalities in favor of providing flexible plans adapting to the shop floor's state. A key element in the creation of flexible process plans is the definition of a process model capable of representing alternatives solutions to the sequencing problem and therefore increasing the potential solution space. This paper presents a methodology to increase planning flexibility in service-oriented manufacturing systems (SOHMS). The methodology introduces a Petri net service-oriented process model (SOP model) capable of computing a product's deadlock free sequential space and adapts to the fractal character of holonic architectures. A set of modeling rules, with illustrations, is presented for the automatic generation of the Petri net, based on a set of precedence conditions. To explore the solution space represented by the SOP model a holonic interaction protocol is presented. Moreover, a set of behavioral strategies is proposed in order to cope with the effects of a possible combinatorial explosion. A study case applied workshop example is presented to illustrate the modeling process of SOP models, compute the sequential solution space and demonstrate how this notably increases the number of potentially goods feasible solutions.     

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.     

Intelligent design and planning of manual assembly workstations: A neuro-fuzzy approach

The design of manual assembly workstations, as with most forms of designs, is highly iterative and interactive. The designer has to consider countless constraints and solutions for contradictory goals. In order to assist the designer in design process, it is required to develop a new intelligent methodology and system. This paper develops a neuro-fuzzy hybrid approach to intelligent design and planning of manual assembly workstations. Problems, related to workstation layout design, planning, and evaluation, are discussed in detail. A fuzzy neural network is used to predict the ranges of anatomical joint motions and to design or adjust workstations and tasks. The neuro-fuzzy computing scheme is integrated with operator's posture analysis and evaluation. For training and test purposes, experiment is carried out to simulate assembly tasks on a multi-adjustable assembly workstation equipped with a flexible PEAK motion measurement and analysis system. The trained neural network is capable of memorizing and predicting the joint angles associated with a range of workstation configurations. Thus, it can also be used for the design/layout and on-line adjustment of manual assembly workstations. Thus, the developed system provides a unified, computational intelligent framework for the design, planning and simulation of manual assembly workstations.     

Petri net dynamics-based scheduling of flexible manufacturing systems with assembly

This paper presents a heuristic search method based on Petri nets for scheduling flexible manufacturing systems with assembly (FMSA) by partially generating the reachability graph. FMSAs are modeled by two types of timed place Petri nets, called generalized symmetric (GSN) and asymmetric nets (GAN). GSN is a sub-class of GAN. The special Petri net structures of GSN and GAN allow us to efficiently solve their state equations for solutions that constitute a part of the proposed heuristic function. Considering the dynamic information of nets such as concurrency and synchronization, the part of the heuristic function is adjusted since state equation solutions may over-estimate the real cost. The adjustment is based on a lower bound of the real cost and on dynamically comparing the partial estimated cost and partial real cost during the search process. Extensive simulation study shows that in most cases this work obtain better solutions than prior work.     

时间Petri网的可调度分析及在FMS中的应用

在实时系统中,检查任务执行的计划是否满足要求的时间约束称为可调度分析.通过把时间特性与其他行为特性分离,提出了一种以时间Petri网建模的实时系统调度分析方法.如果特定任务的执行是可调度的,则可以计算任务执行的时间跨度,否则确定出不可调度的变迁以便于调整时间约束和纠正设计错误.提出了一种通过把复杂的任务序列分解成一些子序列来进行可调度性分析的综合时序分析技术,它不仅提高了效率,也有助于关于调度的可达性问题的讨论.讨论了柔性制造系统FMS中的车间装配子系统的可调度性.     

基于分层强化学习的通用装配序列规划算法

对于装配序列规划问题,现有算法大多聚焦于单一的目标构型.对于多目标构型以及大规模问题,现有算法往往存在维数灾难及泛化能力差等问题.为此,利用装配序列规划问题分层结构的特点,提出一种基于分层强化学习的适用于多构型装配任务的通用装配序列规划方法.首先,将装配序列规划问题构建为一个分层的马尔科夫决策过程,其中,上层进行序列规...     

Block assembly planning in shipbuilding using case-based reasoning

A process planning system using case-based reasoning (CBR) is developed for block assembly in shipbuilding. A block assembly planning problem is modeled as a constraint satisfaction problem where the precedence relations between operations are considered constraints. In order to find similar cases, we propose two similarity coefficients for finding similar cases and for finding similar relations. Due to the limited number of operation types, the process planning system first matches the parts of the problem and those of the case-based on their roles in the assembly, and then it matches the relations related to the matched part–pairs. The parts involved in more operations are considered first. The process planning system is applied to simple examples for verification and comparison. An interface system is also developed for extracting information from CAD model, for preparing data for process planning, and for visually verifying the assembly sequence.     

Modelling and performance maximization of an integrated automated guided vehicle system using coloured Petri net and response surface methods

The objective of this study is to model and maximize performance of an integrated Automated Guided Vehicle System (AGVS), which is embedded in a pull type multi-product, multi-stage and multi-line flexible manufacturing system (FMS). This study examines the impact of guide-path flexibility on system performance through the development of three different guide-path configurations which range from dedicated to flexible relationships between automated guided vehicles (AGVs) and machine/assembly station resources. The system is modelled using coloured Petri net method (CPN) and the simulation results lead to identify the resource redundancy which can be rectified to achieve lower overall cost of the system through the development of flexible guide-path configurations. The study is extended to seek global near-optimal conditions for each guide-path configuration using response surface method, which yields improvements in system throughput and cycle time along with a decrease in the numbers of AGVs.     

Application of robots in assembly automation

The development of flexible assembly is closely related to the introduction of robots in assembly automation. If has long been recognized that automatic parts assembly by robots is one of the most delicate and most difficult tasks in industrial robotics. This task involves two control problems, trajectory planning for the whole automatic assembly process and reduction of the reaction forces appearing between the parts being assembled. This paper addresses both aspects of this control task. The strategical control level for the manipulation of robots and various approaches to trajectory planning tasks in assembly processes are discussed. A new approach to the determination of the strategical control level, including various models (geometric, kinematic and dynamic) for manipulation robots, is briefly described.The last and most delicate phase of the assembly process is parts mating, which is rather like inserting a peg in a hole. In order to reduce the reaction forces appearing between the parts being assembled, force feedback control is applied. The experimental results of the industrial robot insertion process with force feedback are also presented in the paper.     

Robustness analysis of non-ordinary Petri nets for flexible assembly/disassembly processes based on structural decomposition

Design of robust supervisory controllers for manufacturing systems with unreliable resources has received significant attention recently. Robustness analysis provides an alternative way to analyse a perturbed system to quickly respond to resource failures. Although we have analysed the robustness properties of several subclasses of ordinary Petri nets (PNs), analysis for non-ordinary PNs has not been done. Non-ordinary PNs have weighted arcs and have the advantage to compactly model operations requiring multiple parts or resources. In this article, we consider a class of flexible assembly/disassembly manufacturing systems and propose a non-ordinary flexible assembly/disassembly Petri net (NFADPN) model for this class of systems. As the class of flexible assembly/disassembly manufacturing systems can be regarded as the integration and interactions of a set of assembly/disassembly subprocesses, a bottom-up approach is adopted in this article to construct the NFADPN models. Due to the routing flexibility in NFADPN, there may exist different ways to accomplish the tasks. To characterise different ways to accomplish the tasks, we propose the concept of completely connected subprocesses. As long as there exists a set of completely connected subprocesses for certain type of products, the production of that type of products can still be maintained without requiring the whole NFADPN to be live. To take advantage of the alternative routes without enforcing liveness for the whole system, we generalise the concept of persistent production proposed to NFADPN. We propose a condition for persistent production based on the concept of completely connected subprocesses. We extend robustness analysis to NFADPN by exploiting its structure. We identify several patterns of resource failures and characterise the conditions to maintain operation in the presence of resource failures.     

机器人化柔性装配过程的模糊自动机模型

机器人化柔性装配系统是现代制造系统的重要研究内容之一．装配过程的建模是许多研究工作的基础．本文在分析装配过程的特点的基础上，将模糊自动机的理论和方法应用于装配过程的建模研究中，提出了一种机器人化柔性装配过程的模糊自动机模型