International Journal of Computer Networks & Communications (IJCNC)

AIRCC PUBLISHING CORPORATION

Decision-making system supported by adaptive coloured petri nets 

Haroldo Issao Guibu1,2and João José Neto2 

1Instituto Federal de Educação, Ciência e Tecnologia de São Paulo, Brazil

2Escola Politécnica da Universidade de São Paulo, Brazil

Abstract


This work presents a decision-making system supported by Adaptive Coloured Petri Net (ACPN). Experts in a given field can establish a set of rules for the proper functioning of a manufacturing process or even acompany, facilitating the decision-making process. However, whenever the scenario changes and new rules need to be incorporated into the rule set, or old rules need to be deleted or modified, the manager may find it difficult to reformulate this set of rules. An adaptive mechanism that facilitates the modification of the set of rules is fundamental to assist the manager in making decisions. The Adaptive Color Petri Net is a tool that enables the modification of the set of rules, transforming the IF-THEN rule format used by anauxiliary Extended Adaptive Decision Table in an equivalent ACPN subnet. 

Keywords


Adaptive Petri Nets, Coloured Petri Nets, Adaptive Decision Tables

1. Introduction 


In the area of decision-making systems, the tools most used by the specialists are the decision tables, which gave rise to several methods to help managers in their choices.Among the methods developed for decision making are the so-called multi criteria methods, which involve the adoption of multiple hierarchically linked decision tables. In the process of improving the decision tables, new features are incorporated and they provide the specialists the ability to describe their model in a more realistic way.

On the other hand, Petri nets were created by Carl Petri in the 1960s to study discrete events dynamic systems with the aim of communication between automata. Several extensions were made in the original Petri nets, with the introduction of timed transition, the expansion of the token concept and the possibility of dynamic network modification. Coloured Petri nets are an enhancement of the original Petri net in which tokens can be variables of various types, including integer, real, and string types, simplifying the network and enabling the concise description of complex problems, rendering them appropriate in modeling engineering and business problems.

Another enhancement of Petri Net is Adaptive Coloured Petri Net (ACPN)[5]. Adaptive Coloured Petri Net introduces an adaptive layer which involves Coloured Petri Net, and are composed of several functions that are capable to change the subjacent network topology, including or excluding places, transitions and arcs. This paper describes how the adaptive layer operates and the way of transcribing the rules of the tables for extended functions of Petri nets. By embedding a decision table in a Petri net, the simulation and analysis tools available in the Petri net development environments can be used, which leads to an increase in confidence in the decision criteria adopted.

2.Petri Nets 


2.1. Ordinary Petri Nets 

Petri nets (PN) were created by Carl Petri in the 1960s to model communication between automata, which at that time also encompassed Discrete Event Systems (DES). Formally, a Petri net is a quadruple PN= [P, T, I, O] where

P is a finite set of places;

T is a finite set of transitions;

I: (P x T) → N is the input application, where N is the set of natural numbers;

O: (T x P) → N is the output application, where N is the set of natural numbers

A marked network is a double MPN = [PN, M], where PN is a Petri net and M is a set with the same dimension of P such that M (p) contains the number of marks or tokens of place p.

At the initial moment, M represents the initial marking of the MPN and it varies over time as the transitions succeed. In addition to the matrix form indicated in the formal definition of the Petri nets, it is possible to interpret the Petri nets as a graph with two types of nodes interconnected by arcs that presents a dynamic behaviour, and also as a system of rules of the type “condition → action” which represent a knowledge base.

Figure 1 shows a Petri net in the form of a graph, in which the circles are the “Places”, the rectangles are the “Transitions”. The “Places” and the “Transitions” constitute the nodes of the graph and they are interconnected through the oriented arcs


Figure 1. Example of a Petri Net

2.2. Reconfigurable Petri Nets

 Several extensions of the Petri Nets were developed with the objective of simplifying the modelling of Discrete Events Systems, even for distributed environments. However, m Several extensions of the Petri Nets were developed with the objective of simplifying the modelling of Systems to Discrete Events, even for distributed environments. However, most extensions are not designed to model systems that change during their operation.

One group of Petri Nets extensions that attempts to tackle the problem of modelling systems that change during their operation is composed by the Self-Modifying Petri Nets [12], by the Reconfigurable Petri Nets via graph rewriting [8], by the Adaptive Petri Nets [1] and the Adaptive Fuzzy Petri Nets [6].Each of these extensions has its own characteristics, but they share the fact that they can modify, during execution, the firing rules of the transitions or the topology of the network.

With the same name, the same acronym, but of different origins, we find in the literature Reconfigurable Petri Nets (RPN) introduced in [3] and in [8].The work of Llorens and Oliver is an evolution of the work of Badouel and Oliver [1] and combines the techniques of graph grammars with the idea of Valk’s Self-Modifying Petri Net, creating a system of rewriting of the network. In their work, Llorens and Oliver demonstrated the equivalence between the RPN and the PN in terms of properties and also that the RPN are equivalent to the Turing machines regarding the power of expression.

In Figure 2 we have schematized a Reconfigurable Petri Net according to Guan [3]. There are two interdependent layers, the control layer and the presentation layer. The places of the control layer are different in their nature from the places of the presentation layer.

Each place of the control layer has associated a set of functions that is capable to change the topology of the presentation layer, that is, they reconfigure the presentation layer. The tokens of the places are actually functions designed to modify the topology of the presentation layer.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.3 Adaptive Coloured Petri Nets

The Adaptive Coloured Petri Net uses the same scheme of wrapping the underlying device (CPN) with an adaptive layer (AL)[5].

ACPN = (CPN, AL) where
CPN is the conventional coloured Petri net,
LA = (AF, AR) is the adaptive layer.
In turn, the adaptive layer is composed by the set of adaptive functions (AF) and by the set of rules type IF – THEN (AR).
AF is the set of adaptive functions and is embedded in the Adaptive Coloured Petri net.
AR is the set of rules that must be inserted in the Adaptive Coloured Petri net through the execution of the adaptive functions.
The basic adaptive functions are inspection, insertion or incorporation and exclusion of a rule.

The ACPN uses the same strategy of RPN devised by Guan, but the control layer is a kind of interpreter of Decision Tables previously defined in order to produce the decision layer.

3. Decision tables


The Decision Table is an auxiliary tool in describing procedures for solving complex problems [11].A Conventional Decision Table, presented in Table 1, can be considered as a problem composed of conditions, actions and rules where conditions are variables that must be evaluated for decision making, actions are the set of operations to be performed depending on the conditions at this moment, and the rules are the set of situations that are verified in response to the conditions.

Table 1. Conventional Decision Tables

A rule is constituted by the association of conditions and actions in a given column. The set of rule columns should cover all possibilities that may occur depending on the observed conditions and the actions to be taken. Depending on the current conditions of a problem, we look for which table rules satisfy these conditions:

  • If no rule satisfies the conditions imposed, no action is taken;
  • If only one rule applies, then the actions corresponding to the rule are executed;
  • If more than one rule satisfies the conditions, then the actions corresponding to the rules are applied in parallel.
  • Once the rules are applied, the table can be used again.
  • The rules of a decision table are predefined and new rules can only be added or deleted by reviewing the table.

3.1. Adaptive Decision Tables 

In 2001 Neto introduces the Adaptive Decision Table (ADT) [9]from a rule-driven adaptive device. In addition to rule lookup, an ADT allows you to include or exclude a rule from the rule set during device operation. As an example of its potential, Neto simulates an adaptive automaton to recognize sentences from context-dependent languages. In the ADT a conventional decision table is the underlying device to which a set of lines will be added to define the adaptive functions.

Adaptive functions constitute the adaptive layer of the adaptive device governed by rules. Modifying the rule set implies increasing the number of columns in the case of rule insertion, or decreasing the number of columns in the case of rule deletion. In both cases the amount of lines remains fixed. The Adaptive Decision Table (ADT) is capable to change its set of rules as a response to an external stimulus through the action of adaptive functions [11]. However, the implementation of more complex actions is not a simple task due to the limitation of the three elementary operations supported by ADT [11].

When a typical adaptive device is in operation and does not find applicable rules, it stops executing, indicating that this situation was not foreseen. For continuous operation devices, which do not have accepting or rejecting terminal states, stopping their execution would recognize an unforeseen situation and constitutes an error.

3.2. Extended Adaptive Decision Tables 

To overcome this problem faced by continuous operation devices, Tchemra[11]created a variant of ADT and called it Extended Adaptive Decision Table (EADT), shown in Table 2

Table 2. Extended Adaptive Decision Table


4. Examples of rule insertion and eadt transformation 


In this section two examples will be presented, the first showing the insertion of a rule into a manufacturing process[4] and the second example showing the transformation of an Adaptive Decision Table into an Adaptive Coloured Petri Net[5].

4.1 Rule insertion in manufacturing environment 

In Table 3 we have schematized an example of set of rules to be inserted in a ACPN.

Table 3. Set of rules to be transformed in ACPN functions

The rule R1 has three conditions (A <4, B = ON, C = X) and two actions (D = A + 2, E = ON).
To transform this rule into a part of a Petri net, a model (Place, Transition, Place) sketched in Figure 3 is used.


Figure 3. Basic model for transcribing a rule from Table 3

As the rules are inserted, they are grouped hierarchically, that is, the execution of the rules will depend on the sequence of decisions that occur in the Petri net. In Figure 4 the result of the insertion of three rules that compose a certain subset that make up the total of rules.

Figure 4. Subset of rules in a hierarchy

By inserting these rules in the Petri net, the knowledge generated by the expert is incorporated into the routine of monitoring the enterprise, alerting the manager in case of any decision implying non-compliance with the rules. Figure 5 shows the manufacturing process of a product from 4 raw materials, using three machines.

Figure 5. Petri net illustrating the manufacturing of a product from 4 raw materials

Machine 1 converts the raw materials MP1 and MP2 into part 1, machine 2 transforms the raw materials MP3 and MP4 into part 2, and machine 3 uses the two parts Pc1 and Pc2 to generate the Product.

In Figure 6 the subnetwork corresponding to the operation of the machine 1 and which is the same for the machines 2 and 3 is schematized.

Figure 6. Petri net illustrating the operation of machine 1 (maq1)

The operation of the machines specified by the Petri net of Figure 5 was defined by the manufacturing sector (ocupada=busy, livre=free, acabou=finished in portuguese).Subsequently, the quality control sector detected that the final product was not adequate, presenting a simple rule to improve product quality. If x1 of Pc1greater or equal x2 of Pc2, then complete the product, otherwise Pc1 and Pc2 should be directed for recycling, where x1 is the actual value of a parameter x for Part 1 and x2 is the actual value of the same parameter x for Part 2.

Figure 7. Petri sub-network corresponding to the quality control rule to be inserted

Figure 7 details the transformation of the rule inserted in the manufacturing Petri Net from a new IF-THEN rule, producing the new Petri Net schematized in Figure 8.


Figure 8. Modified Petri net after insertion of new control rule

Transforming the rule format is useful when the target format is more suitable for an application than the original format. In the example given, Petri nets are more used in manufacturing processes than Decision Tables. In addition, several methodologies developed for the Petri Nets make it possible to detect the existence of deadlocks and also the application of schemes that prevent their appearance in manufacturing networks.

4.2.EADT transformation into ACPN 

The transformation of EADT into ACPN is based on an algorithm composed of four main phases:

Phase I: definition of the underlying decision table, with the inclusion of the criteria, alternatives and rules of the decision problem;

Phase II: generation of the decision matrix, whose values represent the relative weights and preferences of criteria and alternatives of the decision maker;

Phase III: transformation of the decision matrix in a XML format, in order to incorporate as a set of rules.

Phase IV: appending the XML file to the basic ACPN, resulting in the second layer, the decision layer.

The following example was adapted from [11] to illustrate the sequence of phases mentioned above, based in a decision procedure proposed in [10]. This is a decision problem in which the decision maker needs to certify and select suppliers of a particular product for his company. Two suppliers A and B are analysed, according to the judgments of the decision-maker in accordance with selected for comparison:

C1 – Quality of services;

C2 – Flexibility for product delivery;

C3 – Distance from supplier and company location.

In phase I, criteria and alternatives to the problem are introduced in a conventional decision table, and the decision maker can create an initial set of rule, as shown in Table 4.

Table 4. Initial Decision Table

In this example, the comparisons between the criteria are shown in Table 5, in which the decision-maker judges the criteria pairs, obtaining the matrix of reciprocal judgments[11].

Table 5. Judgement Matrix

After checking the consistency of the values of judgment and normalization of values, the weights of each criterion are calculated, generating the vector of weights:

W = (0.62, 0.22, 0.16).

According to the judgment of the decision maker, the vector with the weight of each criterion represents the relative importance of each one. In this example, the resulting weights indicate that the criterion is more important in relative to others:

Quality: 0.62 – Flexibility: 0.22 -Distance: 0.16.

At this point, it is necessary to check the consistency of the criteria judgments.The matrix of comparison between the criteria of Table 4 is evaluated for the verification of the degree of consistency of the judgments, which is given by the consistency ratio (CR), as a function of the order of the matrix:

  1. a) vector of weights pe = (1.98, 0.69, 0.47)T
  2. b) consistency vector cs = (3.20, 3.08, 3.04)T
  3. c) eigenvalue λ𝑚𝑎𝑥 = 3.11
  4. d) consistency index CI = 0.05
  5. e) consistency ratio CR = 0.09

According to [10], the value of CR = 0.09 indicates that the judgments are consistent and acceptable since CR <10%, otherwise it would be necessary to review Table 5. The next operation is to obtain the performance matrix. For this, the alternatives are compared to the pairs, with each of the criteria. The comparisons made by the decision maker in the example are shown in Table 5.

Table 6. Pairwise comparison matrix


Table 7. Performance matrix Z

From the performance matrix Z we obtain vector ax containing the figures indicating the relative importance of the alternatives.

indicating that in this example the alternative A1 is much better than the alternative A2 and supplier A must be chosen. Figure 9 shows the Petri Net version of the initial decision table.

Figure 9. Petri Net equivalent of initial Decision Table


Figure 10. Petri Net Petri net of the decision-making process

Figure 10 summarizes the decision process in a graphical way.

5. Conclusions 


In this paper we show how to incorporate new rules into Adaptive Coloured Petri Nets in a manufacturing environment and how to incorporate decision tables into Adaptive Coloured Petri Nets in a business environment. Good management practices are often overlooked in a company’s day-to-day business due to the unawareness of the consequences of certain decisions, which are not always apparent because the business expert does not share his knowledge with the plant manager. Sharing two knowledge’s that are generally isolated provides a synergy for the company. These incorporations of rules and tables were facilitated by the reconfigurable nature of the Adaptive Coloured Petri Nets. Reconfigurable networks can be understood as a particular case of adaptive networks, where adaptation is achieved through reconfiguration of the network. The adaptive network is more general than the reconfigurable network because it can change its behaviour by maintaining the same configuration by modifying the trigger rules of the transitions.

In an adaptive network, rules that handle failures can be incorporated into the standard network, allowing greater agility in the operation without the need to stop the process until fault experts take over. The recommendations of the experts would already be incorporated into the standard Petri net used in the monitoring of the operation [14][15].Reconfigurable systems during operation are a trend in the design of control systems and the ability to incorporate procedures from related areas is a feature that cannot be underestimated.

References


[1]     Badouel E. ; Oliver, J. Reconfigurable Nets, a Class of High Level Petri Nets Supporting Dynamic Changes in Workflow Systems. (S.l.),1998.

[2]     Camolesi, A. R. Proposta de um Gerador de Ambientes para a Modelagem de Aplicações usando Tecnologia Adaptativa. Tese (Doutorado) —Escola Politécnica da Universidade de São Paulo, 2007.(in portuguese).

[3]     Guan S. U. ; Lim, S. S. Modeling adaptable multimedia and self-modifying protocol execution. Future Generation Computing Systems, vol.20, no 1, pp. 123-143, 2004.

[4]     Guibu H.I.; Neto, J.J. Incorporação de novas regras em uma Rede de Petri Colorida Adaptativa. In Memórias do XI Workshop de Tecnologia Adaptativa – WTA 2017. EPUSP, São Paulo. ISBN: 978-85-86686-90-0, pp. 128-132. 26 e 27 de Janeiro, 2017. (in portuguese)

[5]     Guibu H.I.; Neto, J.J. Use of Adaptive Coloured Petri Network in Support of Decision-Making. In DhinaharanNagalamai et al.(Eds) CoSIT2017 pp 17-27,2017.

[6]     Kheldoun, A., Barkaoui, K., Zhang, J., &Ioualalen, M. (2015, May). A High Level Net for Modeling and Analysis Reconfigurable Discrete Event Control Systems. In IFIP International Conference on Computer Science and its Applications_x000D_ (pp. 551-562). Springer International Publishing.

[7]     Little T. D. C.; Ghafoor, A. Synchronization and storage model for multimedia objects. IEEE J. Selected Areas Comm., pp. 413-427, Apr.1990., 1990.

[8]     Llorens, M. ; Oliver, J. Structural and dynamic changes in concurrent systems: Reconfigurable petri nets. IEEE Trans. Comput., vol. 53, no.9, pp. 11471158, 2004.

[9]     Neto, J. J. Adaptive rule-driven devices – general formulation and case study. Proc. 2001 Lecture Notes in Computer Science. Watson, B.W.and Wood, D. (Eds.): Implementation and Proc. 2001 Lecture Notes in Computer Science. Watson, B.W. and Wood, D. (Eds.): Implementation and Application of Automata 6th International Conf., Springer-Verlag,Vol.2494, pp. 234-250., 2001.

[10]   Saaty, T.L., “How to make a decision: the Analytic Hierarchy Process”, Interfaces, Vol. 24, No. 6, pp19–43, 1994

[11]   Tchemra, A. H. Tabela de decisão adaptativa na tomada de decisões multicritério. Tese (Doutorado), Escola Politécnica da USP, São Paulo, 2009(in portuguese).

[12]   Valk, R. Self-modifying nets, a natural extension of petri nets. Lecture Notes Lecture Notes in Com, vol. 62, pp. 464-476, 1978.

[13]   Zhang, J., Khalgui, M., Li, Z., Mosbahi, O., & Al-Ahmari, A. M. (2013). R-TNCES: A novel formalism for reconfigurable discrete event control systems. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 43(4), 757-772.

[14]   Zhang, J., Khalgui, M., Li, Z., Frey, G., Mosbahi, O., & Salah, H. B. (2015). Reconfigurable coordination of distributed discrete event control systems. IEEE Transactions on Control Systems Technology, 23(1), 323-330.

[15]   Zhang, J. (2015). Modeling and verification of reconfigurable discrete event control systems (Doctoral dissertation, XIDIAN UNIVERSITY).

Authors


Haroldo IssaoGuibu graduated in Electrical Engineering and MSc in Electrical Engineering in Polytechnic School of São Paulo (EPUSP) University,Brazil. Lecturer at Instituto Federal de Educação, Ciência e Tecnologia de São Paulo(IFSP) with main interest in Automation, PLC programming and Automation related adaptive technologies.

João José Neto graduated in Electrical Engineering  (1971), MSc in  Electrical Engineering (1975) and doctor in Electrical Engineering (1980), and “livre docente” associate professor (1993) in the Polytechnic School of São Paulo (EPUSP) University,Brazil. Nowadays he is the head of LTA – Adaptive Technology Laboratory at the Department of Computer Engineering and Digital Systems at the  EPUSP. His main experience is in the Computer Science area, with emphasis on the foundation of computer engineering and adaptivity. His main activities include adaptive devices, adaptive technology, adaptive automata and their applications to computer engineering and other areas, especially in adaptive decision making systems, natural language processing, compiler construction, robotics, computer education, intelligent system modeling, computer learning, pattern matching, inference and other applications founded on adaptivity and adaptive devices.

%d bloggers like this: