Dynamic composition of holonic processes to satisfy timing constraints with minimal costs

The flexible architecture provided by holonic manufacturing systems (HMS) poses challenges in planning and control of production processes. The challenges are due, in part, to the loosely coupled structure of holons and also to the complex interactions among holons. Development of new methodologies is required to optimize the holonic processes in HMS to achieve the objectives. In this paper, we concentrate on the development of method for the composition of holonic processes. We consider the holonic processes composition (HPC) problem to synthesize processes with minimal costs while meeting the timing constraints in HMS. We formulate this problem based on a hybrid model in which contract net protocol is adopted as the negotiation protocol and timed Petri net is used to analyze the timing and resource constraints. To specify the costs of operations, we augment the timed Petri net with a cost function. We formulate an optimization problem to minimize the cost while meeting the timing constraints based on the Petri net models. A solution to HPC can be represented by a collaborative Petri net. Our methodologies include a condition to check whether the timing constraints can be met, a condition for the existence of an optimal solution to the HPC problem and a multi-layer contract net protocol to find the minimal cost solution.     

Holarchy formation and optimization in holonic manufacturing systems with contract net

Holonic manufacturing systems (HMS) is based on the notion of holon, an autonomous, cooperative and intelligent entity to provide a econfigurable, flexible and decentralized manufacturing environment to respond to changing needs and opportunities. A set of holons that cooperate to achieve a goal forms a holarchy. How to design a mechanism to form a holarchy to achieve a goal while minimizing the overall cost is a challenge. The objectives of this paper are to propose models and develop collaborative algorithms to guide the holons to form a holarchy to coherently move toward the desired goal state ultimately. We adopt contract net protocol (CNP) to model mutual selection of holons in forming a holarchy. We formulate a holarchy optimization problem to minimize the cost subject to the feasibility constraints. To analyze the feasibility of a holarchy, a Petri net (PN) model is proposed. As classical PN models do not take into account the cost involved in firing transitions, we augment the PN model with cost functions in the problem formulation. Due to the distributed architecture of HMS, the internal structure of each potential holarchy that acts as bidder in CNP is not available to the manager. A key issue is to determine the feasibility of a holarchy without constructing the whole PN model of the given hierarchy. We study the feasible conditions for a holarchy and propose a collaborative algorithm to analyze the feasibility and award contracts to holons without constructing the whole model of a holarchy.     

Design of reconfiguration mechanism for holonic manufacturing systems based on formal models

One of the key design issues of holonic manufacturing systems (HMS) is to effectively respond to resource failures based on the flexible holonic architecture. The objective of this paper is to propose a viable design methodology to implement reconfiguration mechanism in HMS. A reconfiguration mechanism is developed to accommodate changes based on collaboration of holons without leading to chaos at the shop floor. To deal with resource failures in HMS, an impact function is defined to characterize the impact of resource failures on different holons in a holarchy. A collaborative reconfiguration mechanism based on an impact function is proposed to effectively reconfigure the systems to achieve minimal cost solutions. The design and implementation methodology combines contract net protocol for negotiation of holons, Petri net for the representation of individual product holons and resource holons and FIPA-compliant agent platform for publication/discovery of holons. A simulation system is developed to verify the proposed reconfiguration mechanism.     

Model and control holonic manufacturing systems based on fusion of contract nets and Petri nets

Holonic manufacturing systems (HMS) can be modeled as multi-agent systems to which contract net protocol can be effectively and robustly applied. However, the lack of analysis capability of contract nets makes it difficult to avoid undesirable states such as deadlocks in HMS. This paper presents a framework to model and control HMS based on fusion of Petri net and multi-agent system theory. The main results include: (1) a multi-agent model and a collaboration process to form commitment graphs in HMS based on contract net protocol, (2) a procedure to convert commitment graph to collaborative Petri net (CPN), and (3) feasible conditions and collaborative algorithms to award contracts in HMS based on CPNs.     

一种基于多Agent的计算机生成兵力协作方法

研究建立虚拟战场攻防对抗环境,为提高协作任务分配机制的鲁棒性、可扩展性和动态适应性,在经典合同网协议的基础上,通过引入交互信任度、熟人信任度和阈值等策略,提出了一种适合于基于多Agent系统（MAS）的计算机生成兵力（CGF）协作的集成合同网协议。为了保证协议的完整性、正确性和可靠性,利用赋色Petri网进行了形式化建模,分析和验证协议的灵活性、可达性和有界性等特性。对集成合同网协议,应用基于MAS的弹道导弹攻防对抗CGF系统进行协作仿真。仿真结果表明,集成合同网协议有效地降低了协作的通信代价,提高了系统的完成任务指标。     

Developing cooperation mechanism for multi-agent systems with Petri nets

Although the contract net protocol answers some of the questions in cooperative distributed problem solving (CDPS), it raises many others that CDPS researchers are still trying to answer. In contract net protocol, an agent may play the role of a manager or a bidder. Without a coordination mechanism, a manager may acquire excessive resources from the bidders in forming a collaborative network to execute the assigned task and thus hinder the progress of the tasks assigned to other managers due to resource contention. As a result, application of contract net protocol may not always lead to feasible solutions to accomplish tasks effectively. As a general framework for exchanging messages, the original contract net protocol does not prescribe how agents should cooperate. How to develop a collaborative mechanism to effectively perform the tasks is an important issue. This paper aims to improve the insufficiency of the contract net by developing a mechanism to facilitate cooperation of agents to accomplish their tasks while avoiding undesirable states and enhance the overall system performance in manufacturing systems. To achieve these objectives, detail process models about how agents accomplish their tasks are required. Due to the advantages in modeling concurrent, synchronous and/or asynchronous activities, Petri nets are adopted in this paper. Based on Petri net models, we study the information needed for agents to make cooperative decisions, mechanism to make agents cooperate, and how to enhance the performance in the system level by taking advantage of the agents’ cooperation capabilities. To characterize the condition for cooperation, we represent the collaborative networks formed based on the contract net protocol with Petri nets and then find the condition for a collaborative network to be feasible. The feasible condition also serves as a condition for the development of cooperation mechanism for managers. We propose a cooperation mechanism based on the idea of resource donation, including unilateral resource donation and reciprocal resource donation. Implementation architecture has also been proposed to realize our methodology.     

Development of context-aware workflow systems based on Petri Net Markup Language

The Petri Net Markup Language (PNML) is originally an XML-based interchange format for Petri nets. Individual companies may specify their process models in Petri nets and exchange the Petri nets with other companies in PNML. This paper aims to demonstrate the capabilities of PNML in the development of applications instead of an industrial interchange format only. In this paper, we apply PNML to develop context-aware workflow systems. In existing literature, different methodologies for the design of context-aware systems have been proposed. However, workflow models have not been considered in these methodologies. Our interests in this paper are to propose a methodology to automatically generate context-aware action lists for users and effectively control resource allocation based on the state of the workflow systems. To achieve these objectives, we first propose Petri net models to describe the workflows. Next, we propose models to capture resource activities. Finally, the interactions between workflows and resources are combined to obtain a model for the whole processes. Based on the combined model, we propose architecture to automatically generate context-aware graphical user interface to guide the users and control resource allocation in workflow systems. We demonstrate our design methodology using a health care example.     

A self-adaptation scheme for workflow management in multi-agent systems

Business processes, operational environment, variability of resources and user needs may change from time to time. An effective workflow management software system must be able to accommodate these changes. The ability to dynamically adapt to changes is a key success factor for workflow management systems. Holonic multi-agent systems (HMS) provide a flexible and reconfigurable architecture to accommodate changes based on dynamic organization and collaboration of autonomous agents. Although HMS provides a potential architecture to accommodate changes, the dynamic organization formed in HMS poses a challenge in the development of a new software development methodology to dynamically compose the services and adapt to changes as needed. This motivates us to study and propose a methodology to design self-adaptive software systems based on the HMS architecture. In this paper, we formulate a workflow adaptation problem (WAP) and propose an interaction mechanism based on contract net protocol (CNP) to find a solution to WAP to compose the services based on HMS. The interaction mechanism relies on a service publication and discovery scheme to find a set of task agents and a set of actor agents to compose the required services in HMS. We propose a viable self-adaptation scheme to reconfigure the agents and the composed services based on cooperation of agents in HMS to accommodate the changes in workflow and capabilities of actors. We propose architecture for our design methodology and present an application scenario to illustrate our idea.     

Collaborative reconfiguration mechanism for holonic manufacturing systems

Although holonic manufacturing systems (HMS) are recognized as a paradigm to cope with the changes in manufacturing environment based on a flexible architecture, development of reconfiguration mechanism is required to realize the advantages of HMS. Finding a solution from scratch to deal with changes in HMS is not an appropriate approach as it may lead to chaos at the shop floor. The objective of this paper is to propose a viable design methodology to achieve effective reconfiguration in HMS based on the cooperation of holons. We formulate and study a holarchy reconfiguration problem and define an impact function to characterize the impact of resource failures on different holons in a holarchy. A collaborative reconfiguration algorithm based on the impact function is proposed to effectively reconfigure the systems to achieve minimal cost solutions.     

Modeling production configuration using nested colored object-oriented Petri-nets with changeable structures

Configuring production processes based on process platforms has been well recognized as an effective means for companies to provide product variety while maintaining mass production efficiency. The production processes of product families involve diverse variations in manufacturing and assembly processes resulted from a large variety of component parts and assemblies. This paper develops a multilevel system of nested colored object-oriented Petri nets with changeable structures to model the configuration of production processes. To capture the semantics associated with production configuration decisions, some unique modeling mechanisms are employed, including colored Petri nets, object-oriented Petri nets, changeable Petri net structures, and net nesting. The modeling formalism comprises resource nets, manufacturing nets, assembly nets and process nets. The paper demonstrates how these net definitions are applied to the specification of production process variants at different levels of abstraction. Also reported is a case study in an electronics company. The system model is further analyzed with focus on conflict prevention and deadlock detection.     

Can I find a partner? Undecidability of partner existence for open nets

We study open nets as Petri net models of web services, with a link to the practically relevant language WS-BPEL. For those nets, we investigate the problem of operability which we consider as fundamental as the successful notion of soundness for workflow nets, i.e., Petri net models of business processes and workflows. While we could give algorithmic solutions to the operability problem for subclasses of open nets in earlier work, this article shows that the problem is in general undecidable.     

A Petri net-based approach for supporting aspect-oriented modeling

The concept of aspect-orientation allows for modularizing crosscutting concerns as aspect modules. Aspect-orientation originally emerged at the programming level, and has stretched over other development phases now. Among them aspect-oriented modeling (AOM) is a hot topic, and there are many approaches supporting it. Petri net is a good formalism which can provide the foundations for modeling software and simulating its execution, but fails to resolve the problem of crosscutting concerns to support AOM. So, this paper presents an approach which extends the Petri net so as to support the AOM. In this paper, the basic functions of the system are modeled as base net by Petri net, and the crosscutting concerns are modeled as aspect nets. In order to analyze the whole system, woven mechanism is proposed to compose the aspect nets and base net together. The problems about aspectaspect conflict and conflict relations may exist among the aspect nets matching the shared join point, thus this paper propose solutions to resolve them. The Object Petri net which is an extension of traditional Petri net is also extended so as to support aspect-oriented modeling here.     

基于熟人联盟及扩充合同网协议的多智能体协商模型

合同网协议可扩充性好，处理动态环境能力强，在多智能体系统协商中应用广泛．在分析了经典合同网协议的优缺点后，提出了基于熟人联盟及扩充合同网协议的多智能体系统协商模型．根据模型设计了适合扩充合同网协议的系统结构，引入了熟人联盟以及信任度参数，提出熟人联盟生成方法及信任度更新规则并构造了基于经典合同网协议的扩充合同网协议．最后通过对一个导弹防御例子的测试及分析，证实了该模型在保证协商质量的基础上，有效地降低了协商代价．     

多主体行为冲突的Petri网方法研究

将主体的动作分为内部动作和外部动作，单个主体的内部行为通过其对应的Petri网系统进行描述，进一步得到多主体系统对应的层次Petri网系统。通过主体间的外部动作关系的讨论分析得到多主体系统出现冲突的必要条件，并且Petfi网系统运行时的一个死标识对应多主体系统的一个冲突，特别是资源冲突。     

面向对象Petri网合同网协议模型的一种改进方案

传统合同网协议模型中,Agent之间通信量大,且角色固定,不能满足多Agem系统环境和任务的复杂性和动态性以及交互的灵活性和高效性.通过引入信任度和阈值,采用面向对象Petri网对合同网协议模型进行了改进,提出了一种新的适应系统环境及Agent能力变化的模型,并对改进模型进行了分析,表明模型具有角色可变性、并发性和通信量少的特点.     

Soundness-preserving reduction rules for reset workflow nets

The application of reduction rules to any Petri net may assist in its analysis as its reduced version may be significantly smaller while still retaining the original net’s essential properties. Reset nets extend Petri nets with the concept of a reset arc, allowing one to remove all tokens from a certain place. Such nets have a natural application in business process modelling where possible cancellation of activities need to be modelled explicitly and in workflow management where such process models with cancellation behaviours should be enacted correctly. As cancelling the entire workflow or even cancelling certain activities in a workflow has serious implications during execution (for instance, a workflow can deadlock because of cancellation), such workflows should be thoroughly tested before deployment. However, verification of large workflows with cancellation behaviour is time consuming and can become intractable due to the state space explosion problem. One way of speeding up verification of workflows based on reset nets is to apply reduction rules. Even though reduction rules exist for Petri nets and some of its subclasses and extensions, there are no documented reduction rules for reset nets. This paper systematically presents such reduction rules. Because we want to apply the results to the workflow domain, this paper focusses on reset workflow nets (RWF-nets), i.e. a subclass tailored to the modelling of workflows. The approach has been implemented in the context of the workflow system YAWL.     

多主体计划的Petri网方法及其研究

利用Petri网对主体Petri的各种行为进行描述和分析，通过Petri网系统的可达性分析考虑主体计划生成问题是求解单个主体计划问题的一种有效方法。系统中的每一个主体可以通过其Petir网系统进行描述，进而得到多主体系统相应的有界层次Petri网系统。利用层次Petri网系统的可达标识图得到多主体系统关于目标状态的可达动作序列的集合，对可行可达动作序列及其中动作间关系确定得到多主体系统的计划。     

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.     

Analysis of contract net in multi-agent systems

Application of contract net protocol requires the development of a bid evaluation procedure specific to the problem. Care must be taken to apply contract net protocol to tasks that involve precedence constraints among different operations and heterogeneous resources. The lack of a process model in the original contract net protocol makes it difficult to determine the feasibility of the resulting contracts. We propose a model to facilitate the development of the bid evaluation procedure by extending our previous results to handle tasks with more complex process structure. We formulate an optimization problem to find a minimal cost feasible execution sequence for a task.     

Petri网的组合积网及性能分析

Petri网是一种系统描述和分析的工具 .Petri网组合是由小系统的性质获得大系统性质的一种有效的分析方法 .本文提出了 Petri网的组合积运算 ,包括 Petri网的 型组合积运算和 型组合积运算、Petri网的并积运算 ,讨论了保持网的结构性质的条件 ,为复杂大系统的分析提供了新途径