26. Petri Nets

 

 

Petri nets are useful tools for modelling systems with control flow. In particular they aid in modelling systems with concurrency, and parallelism. A set of routines have been developed at UWO to serve as the basis for a manufacturing simulation. The routines will support a number of various Petri net functions. The basic operation of the Petri net may be simulated. As well the EOR transitions will also be modelled. An attempt has been made to add ‘colors’ to the tokens, but at the present there is insufficient information (i.e., no references) to verify the implementation.

 

The routines have been written in a user friendly way to allow simple application interface. Places and Transitions are specified with textual names. A brief theory of petri nets follows.

 

 

• These are like state diagrams, except multiple states can be active at the same time.

 

• Other techniques, such as GRAFCET, are based on Petri nets.

 

 

 

26.1 A Brief Outline of Petri Net Theory

[an error occurred while processing this directive]

 

There are four basic elements in a petri net; places, transitions, arcs, and tokens. If we are to think in terms of a factory, tokens are equivalent to work parts. Arcs are the paths the work will follow through the factory. Places are buffers where parts are stored temporarily, and transitions are equivalent to machines where the parts are used to make new parts.

 

 

 

The basic operation is that tokens are introduced to the network, and then transitions are fired in different orders, and thus tokens are created and destroyed at the transitions. The example below follows the petri net for a few cycles. The first figure shows the Petri Net with the initial markings.

 

 

 

 

 

The reader should note that there are a few interesting properties found in Petri nets.

 

• Transitions are fired when all of their inputs are satisfied, and the user specifies that transition.

• Most analysis of petri nets uses random firings of the transitions to obtain statistical performance.

 

Other basic references to the petri net theory are available in Peterson [1981] and Reisig [1985].

 

 

26.2 More Review

[an error occurred while processing this directive]

 

• Ideal for parallel control problems

 

 

 

 

 

 

 

 

• Basic logic functions are shown below,

 

 

• We can model various logic functions with Petri nets,

 

 

• Reachability allows us to determine if a state (set of places) is possible given an initial condition.

 

• Boundedness determines whether the number of states will be controlled, or grow/shrink.

 

 

• Deadlock and liveliness - will the controller find itself unable to continue.

 

• The procedure for producing ladder logic and other programs from the Petri Nets, is identical to producing Ladder Logic for SFC diagrams.

 

 

 

• Petri nets have been used for the modeling, control and validation of the control model [Teng and Black, 1988]

 

 

 

26.3 Using the Subroutines

[an error occurred while processing this directive]

 

26.3.1 Basic Petri Net Simulation

 

The subroutines are applied in a methodical manner. Before the user can integrate the subroutines into their program, they must draw out the petri net, and label all places and transitions. The example given above is illustrated below.

 

 

After these labels are determined, they are defined using the petri net subroutines. The arcs in the petri net are also defined in the program. There are defined with respect to the transitions. That is to say that an arc is an input to, or output from a transition. After the petri net structure has been defined, tokens may be placed in the places of the net. The tokens are as given in the previous example.

 

 

The transitions are then selectively fired in the net, by function calls in the program. This program also has calls to functions which print the petri net structure after each transition. The code is show below for the example above.

 

 

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

#include “global.h”

#include “petri.h”

 

 

int test1()

/*

* BASIC TEST NET (Peterson book, 1981, pg. 19)

*/

{

static int error;

static struct petri_net net;

static int p1, p2, p3, p4, p5;

static int t1, t2, t3, t4;

 

error = petri_init(&net);

p1 = petri_place(&net, “p1”);

p2 = petri_place(&net, “p2”);

p3 = petri_place(&net, “p3”);

p4 = petri_place(&net, “p4”);

p5 = petri_place(&net, “p5”);

 

t1 = petri_transition(&net, “t1”);

t2 = petri_transition(&net, “t2”);

t3 = petri_transition(&net, “t3”);

t4 = petri_transition(&net, “t4”);

 

petri_input(&net, p1, t1, 1);

petri_input(&net, p2, t2, 1);

petri_input(&net, p3, t2, 1);

petri_input(&net, p4, t2, 1);

petri_input(&net, p4, t3, 1);

petri_input(&net, p4, t3, 1);

petri_input(&net, p5, t4, 1);

 

petri_output(&net, p2, t1, 1);

petri_output(&net, p3, t1, 1);

petri_output(&net, p4, t1, 1);

petri_output(&net, p4, t1, 1);

petri_output(&net, p2, t2, 1);

petri_output(&net, p5, t3, 1);

petri_output(&net, p3, t4, 1);

petri_output(&net, p4, t4, 1);

 

petri_add_tokens(&net, p1, 1);

petri_add_tokens(&net, p4, 2);

petri_add_tokens(&net, p5, 1);

 

petri_print(&net);

 

petri_event(&net, t4);

petri_print(&net);

 

petri_event(&net, t1);

petri_print(&net);

 

petri_event(&net, t3);

petri_print(&net);

 

return error;

}

 

 

As can be seen this method of implementation is very simple. The user is able to define a number of nets, and refer to transitions and places by name.

 

 

 

26.3.2 Transitions With Inhibiting Inputs

 

In some cases we want to prevent a transition from firing. To do this, the idea of inhibiting inputs has been proposed. If a transition has an inhibiting input from a place, that has any tokens in it, then the transition cannot fire. Otherwise the transition may fire normally. A sample net has been devised for this case, it is seen below.

 

 

The program below shows that the inhibiting input is simply defined when the arc is defined.

 

 

 

int test2()

/*

* INHIBITED TEST NET (Peterson book, 1981, pg. 196)

*/

{

static int error;

static struct petri_net net;

static int p1, p2, p3, p4, p5, p6;

static int t1, t2, t3, t4;

 

error = petri_init(&net);

p1 = petri_place(&net, “p1”);

p2 = petri_place(&net, “p2”);

p3 = petri_place(&net, “p3”);

p4 = petri_place(&net, “p4”);

p5 = petri_place(&net, “p5”);

p6 = petri_place(&net, “p6”);

 

t1 = petri_transition(&net, “t1”);

t2 = petri_transition(&net, “t2”);

t3 = petri_transition(&net, “t3”);

t4 = petri_transition(&net, “t4”);

 

petri_input(&net, p1, t1, 1);

petri_input(&net, p2, t2, 1);

petri_input(&net, p3, t2, 1);

petri_input(&net, p5, t3, 1);

petri_input(&net, p3, t4, INHIBIT);

petri_input(&net, p4, t4, 1);

petri_input(&net, p6, t4, 1);

 

petri_output(&net, p1, t1, 1);

petri_output(&net, p3, t1, 1);

petri_output(&net, p2, t2, 1);

petri_output(&net, p4, t3, 1);

petri_output(&net, p5, t3, 1);

petri_output(&net, p6, t4, 1);

 

petri_add_tokens(&net, p1, 1);

petri_add_tokens(&net, p2, 1);

petri_add_tokens(&net, p5, 1);

petri_add_tokens(&net, p6, 1);

 

petri_print(&net);

 

petri_event(&net, t1);

petri_print(&net);

petri_event(&net, t3);

petri_print(&net);

petri_event(&net, t4);

petri_print(&net);

petri_event(&net, t2);

petri_print(&net);

petri_event(&net, t4);

petri_print(&net);

 

return error;

}

 

 

 

26.3.3 An Exclusive OR Transition:

 

The inhibitory inputs are complimentary to the exclusive or function. Thus another research proposed an Exclusive or transition which will fire when one (and only one) input is from a place with tokens. An example of a problem using this, a ring shift register was modelled. This net is modelled as shown below.

 

 

In this example the EOR transition is marked with a plus in a circle (at ‘t7’). When run, a token will appear in p1, p3, and p5 in a repeating cycle. The program to set this up is seen below.

 

 

 

int test3()

/*

* EOR TEST NET (Peterson book, 1981, discussed pg. 190)

* This is for a single bit shifter

*/

{

static int error;

static struct petri_net net;

static int p1, p2, p3, p4, p5, p6, p7, p8, p9, p10;

static int t1, t2, t3, t4, t5, t6, t7;

 

error = petri_init(&net);

p1 = petri_place(&net, “p1”);

p2 = petri_place(&net, “p2”);

p3 = petri_place(&net, “p3”);

p4 = petri_place(&net, “p4”);

p5 = petri_place(&net, “p5”);

p6 = petri_place(&net, “p6”);

p7 = petri_place(&net, “p7”);

p8 = petri_place(&net, “p8”);

p9 = petri_place(&net, “p9”);

p10 = petri_place(&net, “p10”);

 

t1 = petri_transition(&net, “t1”);

t2 = petri_transition(&net, “t2”);

t3 = petri_transition(&net, “t3”);

t4 = petri_transition(&net, “t4”);

t5 = petri_transition(&net, “t5”);

t6 = petri_transition(&net, “t6”);

t7 = petri_transition(&net, “t7”);

 

petri_input(&net, p6, t1, 1);

petri_input(&net, p7, t1, 1);

petri_input(&net, p2, t2, 1);

petri_input(&net, p7, t2, 1);

petri_input(&net, p4, t3, 1);

petri_input(&net, p7, t3, 1);

petri_input(&net, p1, t4, 1);

petri_input(&net, p3, t5, 1);

petri_input(&net, p5, t6, 1);

petri_input(&net, p8, t7, 1);

petri_input(&net, p9, t7, 1);

petri_input(&net, p10, t7, 1);

 

petri_output(&net, p1, t1, 1);

petri_output(&net, p3, t2, 1);

petri_output(&net, p5, t3, 1);

petri_output(&net, p2, t4, 1);

petri_output(&net, p8, t4, 1);

petri_output(&net, p4, t5, 1);

petri_output(&net, p9, t5, 1);

petri_output(&net, p6, t6, 1);

petri_output(&net, p10, t6, 1);

petri_output(&net, p7, t7, 1);

 

petri_type_transition(&net, t7, EOR);

 

petri_add_tokens(&net, p1, 1);

 

petri_print(&net);

 

petri_event(&net, t4);

petri_print(&net);

petri_event(&net, t7);

petri_print(&net);

petri_event(&net, t2);

petri_print(&net);

petri_event(&net, t5);

petri_print(&net);

petri_event(&net, t7);

petri_print(&net);

petri_event(&net, t3);

petri_print(&net);

petri_event(&net, t6);

petri_print(&net);

petri_event(&net, t7);

petri_print(&net);

 

return error;

}

 

 

 

 

26.3.4 Colored Tokens

 

This section should be considered incorrect. The theory has not been found, although the approach should adhere to the concept. The concept is that each token may now have a color, and a second bit of private information. If a transition is specified to be colored, it will only fire if tokens of the specified color are available at the inputs. The subroutines will then require that the user supply a new set of instance information so that new tokens may be issued.

 

The net used has tokens of mixed colors in it, an is seen below.

 

 

The code is shown below. The reader should note that a second subroutine is used. This is done because there is a bit of code which would be repeated for each update of tokens at the transition.

 

 

int test4()

/*

* COLOR TEST NET (Assumed for now)

* Two consumers of different colors and one input. The instances of tokens

* are kept track of.

*/

{

static int error, i;

static struct petri_net net;

static int p1, p2, p3;

static int t1, t2;

static int color1 = 1, color2 = 2;

static int instance[20], instance_pnt;

 

error = petri_init(&net);

p1 = petri_place(&net, “p1”);

p2 = petri_place(&net, “p2”);

p3 = petri_place(&net, “p3”);

 

t1 = petri_transition(&net, “t1”);

t2 = petri_transition(&net, “t2”);

 

petri_input(&net, p1, t1, 1);

petri_input(&net, p3, t1, 1);

petri_input(&net, p2, t2, 1);

petri_input(&net, p3, t2, 1);

 

petri_output(&net, p1, t1, 1);

petri_output(&net, p2, t2, 1);

 

petri_type_transition(&net, t1, COLORED);

petri_type_transition(&net, t2, COLORED);

 

for(i = 0; i < 20; i++) instance[i] = i;

instance_pnt = 0;

 

petri_add_color_token(&net, p1, color1, instance[instance_pnt]);

instance_pnt++;

petri_add_color_token(&net, p2, color2, instance[instance_pnt]);

instance_pnt++;

petri_add_color_token(&net, p3, color1, instance[instance_pnt]);

instance_pnt++;

petri_add_color_token(&net, p3, color2, instance[instance_pnt]);

instance_pnt++;

 

petri_print(&net);

sub4(&net, t2, color1, instance, &instance_pnt);

petri_print(&net);

sub4(&net, t1, color1, instance, &instance_pnt);

petri_print(&net);

sub4(&net, t1, color1, instance, &instance_pnt);

petri_print(&net);

sub4(&net, t2, color2, instance, &instance_pnt);

 

petri_print(&net);

 

return error;

}

 

 

 

 

 

int sub4(net, transition, color, instance, instance_pnt)

struct petri_net *net;

int transition, color, *instance, *instance_pnt;

{

static int error, i, list[20], n, outputs;

 

error = ERROR;

if(petri_in_event(net, transition, color) == NO_ERROR){

if(petri_get_consumed(net, transition, &color, list, &n, &outputs) == NO_ERROR){

for(i = 0; i <= n; i++) instance[list[i]] = -1000;

if(petri_set_produced(net, transition, &(instance[*instance_pnt]),outputs) == NO_ERROR){

*instance_pnt += outputs;

error = petri_out_event(net, transition);

}

}

}

 

return error;

}

 

 

 

 

26.3.5 Relational Nets

 

Relational nets will use various firing rules for each transition. This is by far the most useful for varied manufacturing conditions. An example is seen below.

 

 

This may be seen in the fifth test subroutine in the program.

 

 

 

26.4 C++ Software

[an error occurred while processing this directive]

 

At present there is one data structure used which holds structures for Places and for Transitions. Arc information is stored (redundantly) in both. These are defined when a Place or Transition number is requested for one that does not exist. Each place and transition have reference numbers, which are used by all other net functions.

 

The software is still undergoing development, and testing, thus a list of functions would be premature.

 

 

 

26.5 Implementation for a PLC

[an error occurred while processing this directive]

 

• Consider the example of a parts buffer. Parts enter the buffer and are added to the top of the stack. The part at the bottom of the stack is checked and sorted (ejected differently) based on a quality check.

 

 

• This can be implemented in ladder logic, but unlike the sequential techniques, there may be multiple tokens in the places, so counters are used to keep track of token counts.

 

 

 

 

 

• For practice,

 

 

 

 

26.6 Practice Problems

[an error occurred while processing this directive]

 

1. Develop a Petri net to control a part sorting station. Parts enter on a conveyor belt and are detected by a proximity sensor. The part can then be checked with a vision system that will signal to the PLC that the part is good/bad. There are then two cylinders that can eject the part into a good or bad bin.

 

 

26.7 References

[an error occurred while processing this directive]

 

Peterson, J.L., “Petri Net Theory and the Modelling of Systems”, Prentice-Hall, Inc., N.J., U.S.A., 1981.

 

Reisig, W., “Petri Nets; An Introduction”, Springer-Verlag, 1985.

 

[an error occurred while processing this directive]