Model checking multi-agent systems with logic based Petri nets

We introduce a class of Petri nets, simple logic Petri nets (SLPN), that are based on logical expressions. We show how this type of nets can be efficiently mapped into logic programs with negation: the corresponding answer sets describe interleaved executions of the underlying nets (Theorem 1). The absence of an answer set indicates a deadlock situation. We also show how to correctly model and specify AgentSpeak agents and multi-agent systems with SLPN’s (Theorem 2). Both theorems allow us to solve the task of model checking AgentSpeak multi-agent systems by computing answer sets of the obtained logic program with any ASP system.     

Modelling of batch production systems using Petri nets with dynamic tokens

This article deals with the qualitative modelling of batch production plants. The approach held is Petri net based. First a definition of a three-level net formalism is presented; the formalism extends the Valk's approach of nets in nets in which the tokens are other nets; in this extension the lower level net handles symbolic tokens. Then a methodology for the modelling of batch processes is proposed; in this methodology the upper level describes the plant layout, the next level models an entity that goes with the batch through the plant and specifies the material and the process routes that the batch must follow, and the third level represents detailed treatments to perform into the process cells using specific equipment. The use of the modelling formalism is illustrated through an example dealing with the coordination of a batch manufacturing system.     

Symbolic execution of concurrent systems using Petri nets

Techniques for analyzing sequential programs in order to improve their reliability have been widely studied in the past. Among the most interesting analysis techniques, we consider symbolic execution. However, analysis techniques for concurrent programs, and in particular symbolic execution, are still an open research area. In this paper, we define a method for symbolic execution of concurrent systems, based on an extension of the Petri net formalism, called EF nets. EF nets are a powerful, highly expressive and general formalism. Depending on the level of abstraction of actions and predicates that one associates to the transitions of the net, EF nets can be used as a high-level specification formalism for concurrent systems, or as a lower level internal representation of concurrent programs. Thus, the model is not dependent on a particular concurrent programming language, but it is flexible enough to be the kernel model for the representation of a wide set of systems and programming languages. In the paper, in order to support the analysis of a concurrent system or program, at first a general algorithm for symbolically executing an EF net is defined. Then, a more efficient algorithm is given for the particular, though important, subclass of EF nets, defined as safe EF nets. Such algorithm is proved to significantly help in reducing the amount of information needed to characterize a symbolic execution. Both the modelling power of the EF nets and the usefulness of the concurrent symbolic execution algorithms defined are illustrated by means of a case study.     

Sequential and distributed model checking of Petri nets

In this paper we present sequential as well as distributed algorithms for model checking computational tree logic over finite-state systems specified as Petri nets. The algorithms rely on an explicit representation of the systems state space but do not require the transition relation to be explicitly available; it is recomputed whenever required. This approach allows us to model check very large systems, with hundreds of millions of states, in a fast and efficient way. For the case studies addressed, the distributed algorithms scale very well, as they show efficiencies in the range of 60% to 95%, depending on the test cases and case studies at hand.     

Uncertainty management in expert systems using fuzzy Petri nets

The paper aims at developing new techniques for uncertainty management in expert systems for two generic class of problems using fuzzy Petri nets that represent logical connectivity among a set of imprecise propositions. One class of problems deals with the computation of fuzzy belief of any proposition from the fuzzy beliefs of a set of independent initiating propositions in a given network. The other class of problems is concerned with the computation of steady-state fuzzy beliefs of the propositions embedded in the network, from their initial fuzzy beliefs through a process called belief revision. During belief revision, a fuzzy Petri net with cycles may exhibit “limit cycle behavior” of fuzzy beliefs for some propositions in the network. No decisions can be arrived at from a fuzzy Petri net with such behavior. To circumvent this problem, techniques have been developed for the detection and elimination of limit cycles. Further, an algorithm for selecting one evidence from each set of mutually inconsistent evidences, referred to as nonmonotonic reasoning, has also been presented in connection with the problems of belief revision. Finally, the concepts proposed for solving the problems of belief revision have been applied successfully for tackling imprecision, uncertainty, and nonmonotonicity of evidences in an illustrative expert system for criminal investigation     

Fuzzy rule base systems verification using high-level Petri nets

In this paper, we propose a Petri nets formalism for the verification of rule-based systems. Typical structural errors in a rule-based system are redundancy, inconsistency, incompleteness, and circularity. Since our verification is based on Petri nets and their incidence matrix, we need to transform rules into a Petri nets first, then derive an incidence matrix from the net. In order to let fuzzy rule-based systems detect above the structural errors, we are presenting a Petri-nets-based mechanism. This mechanism consists of three phases: rule normalization, rules transformation, and rule verification. Rules will be first normalized into Horn clauses, then transform the normalized rules into a high-level Petri net, and finally we verify these normalized rules. In addition, we are presenting our approach to simulate the truth conditions which still hold after a transition firing and negation in Petri nets for rule base modeling. In this paper, we refer to fuzzy rules as the rules with certainty factors, the degree of truth is computed in an algebraic form based on state equation which can be implemented in matrix computation in Petri nets. Therefore, the fuzzy reasoning problems can be transformed as the liner equation problems that can be solved in parallel. We have implemented a Petri nets tool to realize the mechanism presented fuzzy rules in this paper.     

Reachability analysis of real-time systems using time Petri nets

Time Petri nets (TPNs) are a popular Petri net model for specification and verification of real-time systems. A fundamental and most widely applied method for analyzing Petri nets is reachability analysis. The existing technique for reachability analysis of TPNs, however, is not suitable for timing property verification because one cannot derive end-to-end delay in task execution, an important issue for time-critical systems, from the reachability tree constructed using the technique. In this paper, we present a new reachability based analysis technique for TPNs for timing property analysis and verification that effectively addresses the problem. Our technique is based on a concept called clock-stamped state class (CS-class). With the reachability tree generated based on CS-classes, we can directly compute the end-to-end time delay in task execution. Moreover, a CS-class can be uniquely mapped to a traditional state class based on which the conventional reachability tree is constructed. Therefore, our CS-class-based analysis technique is more general than the existing technique. We show how to apply this technique to timing property verification of the TPN model of a command and control (C2) system.     

Distributed control systems simulation using high level Petri nets

To deal with the complexity of the implementation of control systems for flexible manufacturing systems, formal methods of design are needed. In this work the modeling and validation tool selected is high level Petri nets. Based on this approach we have studied the problems that a distributed implementation can introduce. For the evaluation of different strategies of the model implementation and the scheduling of production tasks a simulator has been constructed. This simulator has been written in Ada language.     

Petri nets in dynamic process planning

A framework for combining Petri Nets with Computer Aided Process Planning (CAPP) systems is presented. The Petri Nets are used to provide realtime facility status information while the CAPP system is used to generate the revised process plans. Combining these two methodologies overcomes most of the weaknesses with the traditional CAPP systems. The result is a dynamic, realtime CAPP system.     

Fault detection for discrete event systems using Petri nets with unobservable transitions

In this paper we present a fault detection approach for discrete event systems using Petri nets. We assume that some of the transitions of the net are unobservable, including all those transitions that model faulty behaviors. Our diagnosis approach is based on the notions of basis marking and justification, that allow us to characterize the set of markings that are consistent with the actual observation, and the set of unobservable transitions whose firing enable it. This approach applies to all net systems whose unobservable subnet is acyclic. If the net system is also bounded the proposed approach may be significantly simplified by moving the most burdensome part of the procedure off-line, thanks to the construction of a graph, called the basis reachability graph.     

Real time identification of discrete event systems using Petri nets

The paper defines the identification problem for Discrete Event Systems (DES) as the problem of inferring a Petri Net () model using the observation of the events and the available output vectors, that correspond to the markings of the measurable places. Two cases are studied considering different levels of the system knowledge. In the first case the place and transition sets are assumed known. Hence, an integer linear programming problem is defined in order to determine a modelling the DES. In the second case the transition and place sets are assumed unknown and only an upper bound of the number of places is given. Hence, the identification problem is solved by an identification algorithm that observes in real time the occurred events and the corresponding output vectors. The integer linear programming problem is defined at each observation so that the can be recursively identified. Some results and examples characterize the identified systems and show the flexibility and simplicity of the proposed technique. Moreover, an application to the synthesis of supervisory control of systems via monitor places is proposed.     

Distributed dynamic programming using concurrent object-orientedness with actors visualized by high-level Petri nets

This paper deals with application of concurrent object-oriented programming with Actors to solve dynamic programming problems in a distributed computing environment. This area of research is often called distributed artificial intelligence. Using a dynamic programming example of chained matrix multiplication, a method of managing dynamic programming searches in a distributed programming environment with Actors is presented. Distributed computations with Actors are visualized by means of Time-Varying Automata (for cases with no intra-actor concurrency) or using a class of high-level nets called Hierarchical Colored Petri Nets (for cases with intra-actor concurrency). Design and implementation features of the specific Actor-based programming environment, using a concurrent extension of C++, are also discussed.     

Decision support in flexible manufacturing systems using timed Petri nets

Contingency response in a dynamic system such as a flexible manufacturing system requires that the system be able to identify and evaluate a number of alternatives. This paper shows how dummy transitions can be incorporated in a timed Petri net to model contingencies in the system such as machine or tool breakdown, quality deterioration, or production volume surge, etc. An algorithm is presented to evaluate system response in the steady state. A decision support system complete with a problem processor (incorporating the Petri net model), a database, and a query system is outlined.     

Compositional schedulability analysis of real-time systems using time Petri nets

This paper presents an approach to the schedulability analysis of real-time systems modeled in time Petri nets by separating timing properties from other behavioral properties. The analysis of behavioral properties is conducted based on the reachability graph of the underlying Petri net, whereas timing constraints are checked in terms of absolute and relative firing domains. If a specific task execution is schedulable, we calculate the time span of the task execution, and pinpoint nonschedulable transitions to help adjust timing constraints. A technique for compositional timing analysis is also proposed to deal with complex task sequences, which not only improves efficiency but also facilitates the discussion of the reachability issue with regard to schedulability. We identified a class of well-structured time Petri nets such that their reachability can be easily analyzed.     

Model checking multi-level and recursive nets

With the increasing complexity of the problems and systems arising nowadays, the use of multi-level models is becoming more frequent in practice. However, there are still few reports in the literature concerning methods for analyzing such models without flattening the multi-level structure. For instance, several variants of multi-level Petri nets have been applied for modeling interaction protocols and mobility in multi-agent systems and coordination of cross-organizational workflows. But there are few automated tools for analyzing the behavior of these nets. In this paper we explain how to detect faults in models based on a representative class of multi-level nets: the nested Petri nets. We translate a nested net into a verifiable model that preserves its modular structure, a PROMELA program. This allows the use of SPIN model checker to verify properties related to termination, boundedness and reachability.     

Performance analysis using Petri nets

The purpose of this paper is to focus on the implementation issues associated with using Petri nets for the performance analysis of discrete event dynamic systems while demonstrating several applications in manufacturing systems. Practical modeling issues will be discussed and several applications will be presented that illustrate the advantages and limitations of this methodology. These issues lead to the definition of several research problems in Petri nets for performance analysis.