ARP - Petri nets analysis and simulation tool

Version 2.3 (December 1989) (This document was scanned and formatted from an old printed manual).

This software was developed at the Control and Microinformatics Laboratory (LCMI) of Electrical Engineering Department of the Federal University of Santa Catarina, Brazil, between 1985 and 1990.

WARNING: this program is reliable but quite old (1990). I'm no more providing any kind of support on it, please don't ask me to do so. Feel free to download the source code and modify/patch it if you want.

The ARP (Portuguese for “Petri Net Analyzer and Simulator”) tool is a program for helping design with Petri nets. It was developed in the LCMI/UFSC (Brazil) between 1985 and 1990. It provides some useful tools for place-transition, timed, and extended timed Petri nets.

The ARP tool was written in Turbo Pascal 6.0. It's structure is very modular and provides a simple and intuitive user interface, using textual windows. The program structure is modular and allows to easily design and integrate new tools for Petri net analysis or manipulation.

The program can be used on PC-like systems running DOS 3.0 or above (including all Windows variants), with 256 KBytes of RAM or more. It has two files:

• ARP.EXE - executable, main Program.
• ARP.OVR - overlay with several routines.

To start the program, just type “arp” in the command prompt (or double-click the program icon in Windows File Manager). After starting, it will present you the program main screen and enters the edition window:

The commands are activated by typing the highlighted characters of the options shown in the active window (that one with the highlighted frame). To leave a window, just type ESC, the space bar or any key not used by that window's options. Results are also presented in a text window, which can be scrolled using the arrow keys.

The edition window concentrates all the file manipulation functions. A Petri net file is just a flat ASCII text file with the extension ”.pn”, containging the Petri net description. A Petri net is described using a simple language, similar to Pascal, wich will be described later in this document. The commands allowed in the edition window are:

• Directory: produces a window informing the contents of the current directory. To see other disks, just type their corresponding letters (A, B, C, …). The spacebar exits the listing window. It is important to notice that ARP will use the last visited directory as working directory.
• Load: To load a text file containing a net description. You can type the file name, or just press <enter> to go to the directory listing in order to choose it.
• Save: to save the current file back to disk (this also renames the previous file to ”.bak”).
• Edit: to edit the current open file (a very simple text editor). In the editor, a help screen is available by typing “ESC”.
• Compile: to compile the current file, generating an internal description which is used by the other tools.

The language used for describing Petri nets in the ARP tool has a Pascal-like syntax. It allows to identify places and transitions by names with up to 20 characters. The accepted characters are:

A..z a..z 0..9!    + - # @ ^ %

The basic structure of a Petri net description is:

net network_name ;

constants declaration ;

nodes (places and transitions) declaration ;

structure (arcs) declaration ;

endnet.  

Constants can be defined as following:

const
   free_places = 7; 
   sent_items  = 10;
   TimeOut     = 45;  

The nodes declaration includes the declaration of transitions and places, with a maximum of 150 nodes of each type. The declaration of places has of the following form (the value between brackets indicates the initial marking of the declared places, with default zero and maximum 254):

nodes
   robot_stopped, mach1_running : place;
   robot_waiting, mach1_stopped,
   mach2_waiting                : place (1);
   items_in_stock               : place (free_places);  

The declaration of transitions is similar. In the case of time Petri nets (using the Merlin timing model), one can define the Static Earliest Firing Time (SEFT) and Static Latest Firing Time (SLFT) for each transtion, with default in [0,0]. The probability distribution function associated to each firing interval can also be defined (default is UNIFORM):

nodes
   robot_starts,
   robot_resets : transition;
   mach1_starts : transition [5,TimeOut];
   item_arrives : transition [0,5] EXPON (10);
   robot1_stops : transition [2,8] NORMAL (5);

The intervals accept integer values or constants between 0 and 32000. The probability distribution curves (used only by the performance evaluation module) accepted are:

• Uniform by default.
• NORMAL: normal with average in the center of the interval and shape defined by the ratio k between the value of the curve in the center and in the extremities of the interval (0 < k < 10000).
• EXPON : exponential with form defined by the ratio k between the value of the curve in the beginning and the end of the interval (0,0001 < k < 10000).

One should observe that the shapes of probability density curves does not depend on absolute values but only on the ratio between their maximum and minimum values.

The structure declaration allows to define the arcs bounding places to transitions and vice-versa. Its general form is:

transition:  (input places), (output places) ;

This structure must be repeated for each transition of the net. The names of the places are separate for commas. In the case of weighted arcs we have:

transition:  (..., weight * place, ... )

where the weight can be a numerical value or a constant between 0 and 254.

The example bellow illustrates the description language. The Petri net describes a manufacuring system with a machine-tool and a robot that feeds it, loading and unloading items from/to a stock.

Net Example;
Const
  Input_items = 2;  { items in the input of the machine-tool }

Nodes
  Stock:  Place (Input_items);  { item stock }

  { robot nodes }
  Robot_free:  Place (1); 
  Loading, Unloading:  Place;  
  Take_new_item: Transition [ 1,10 ];  
  Drop_old_item: Transition [ 3,5 ];  
  Load_machine, Unload_machine : Transition [ 5,15 ] Normal (5);  

  { machine-tool nodes } 
  Machine_busy:  Place;  
  Machine_free:  Place (1); 

Structure

  Take_new_item    : (Stock, Robot_free), (Loading);
  Load_machine     : (Loading, Machine_free), (Machine_busy, Robot_free);
  Unload_machine   : (Machine_busy, Robot_free), (Unloading, Machine_free);
  Drop_old_machine : (Unloading), (Stock, Robot_free);

endNet.

The state enumeration analysis is based on building a graph which represents all the states reachable in a Petri net by firing its transitions. The ARP tool uses the basic Karp-Miller algorithm, as described in [Peterson XX]. However, we introduce a small modification in the criteria used to attribute the ω symbol to a place marking (meaning infinite growth of tokens in that place). Our approach allows a more refined analysis of unlimited Petri nets. The maximum number of markings depends on the available memory.

For time Petri nets the states are grouped in state classes with common features. Each state class is composed by a marking and a firing domain (enabled transitions set, each transition with its respective dynamic firing interval).

When activated, this module shows the initial marking to be used in the state/class enumeration. The marking can be modified using the arrow keys and typing the desired values (between 0 and 254). To leave this window and to start the enumeration just press ESC. The program then builds the enumeration graph and produces three textual outputs:

• Observed properties
• Marking graph
• Marking contents

The observed properties output informs about some good properties verified in the generated graph:

• Limitation: the maximum number of tokens in each place for all the reached states. The places can be null, if they never received any tokens; binary, if they always have zero or one token; limited, if the number of tokens is always less or equal than a finite integer (bigger than 1); or not-limited, if the the number of tokens tends to infinite (represented by for ω). If not-limited places are found, the sequences of transition firings leading to token growth are indicated.
• Conservation: if the sum of tokens in all net places is constant for all reachable markings, the network is called strictly conservative.
• Liveness: this test is relative to transition firing. A transition is alive if, from any state of the generated graph, there is at least a firing sequence containing it. A transition is almost-alive if it was fired at least once during the graph building.
• Multi-enabling the state class enumeration in time nets can lead to incorrect results if multi-enabled transitions are found in the graph. A transition is multi-enabled if, for some marking, there are tokens enabling it to fire twice or more times.
• Safeness: the Petri net is safe if all its reachable states are safe. A state is safe if there is a firing sequence leading from it to the initial state.
• Livelocks: a livelock is a cycle of transition firings from which there is no issue. Net net then locks in the same state sequence forever. If livelocks are found in the net, the states and firing transitions entering them are shown.
• Deadlocks: a deadlock state presents no enabled transitions. If such states are detected in the network, the sequences of transitions firings leading to them are shown.

The graph output indicates the structure of a graph representing all the transitions firings leading from a marking to another. Each text line has the following form:

E37: (t4 [3,7]: E51) (t9 [5]: E102) 

This means that, from the E37 state the transition t4 can be fired (between 3 and 7 time units) leading to the E51 state, or the transition t9 can be fired (at 5 time units, leading to state E102).

The markings output text indicates the contents of each state and the firing domain of the transitions enabled in each state. Each text line has the following form:

E37:  { p1, p2, 3*p3, w*p4 } D:  { ta, tb [3], tc[4,9] } 

This indicates that in the E37 state the places p1 and p2 have one token each, the place p3 has 3 tokens and the place p4 has infinite tokens (a token growth was detected in this place). In the firing domain, transition ta firing is allowed in [0,0], tb in [3,3] and tc in [4,9] time units, respectively.

The invariant analysis determines, through calculations on the Petri net incidence array, sets of places or transitions with special features, as token conservation or cyclical behavior.

The linear place invariants indicate the conservative components of the net under analysis. Conservative components are sets of places in which the weighed sum of tokens is constant for any reachable marking. Any integer vector x_n such that C_mn x = 0 is a linear place invariant, where x_i is the weight of place p_i in the invariant (C_mn is the incidence array of a Petri net with m transitions and n places).

The linear transition invariants indicate the cyclical components of the network. A cyclical component is a set of transitions that when fired in some order forms a cycle leaving back to the starting state. Any integer vector y such that y_m C_mn = 0 is a linear transition invariant, where y_i indicates the number of firings of transition t_i needed to form the cycle (the firing order is not calculated). It must be observed that the invariants depend only on the structural features of the net, and not on its initial state. Therefore some indicated transition invariants can be unreachable for a given initial marking.

The invariant analysis module allows to define a set of mandatory or forbidden nodes. This allows to filter the results, showing only invariants that contain the mandatory nodes and not contain the forbidden nodes. For selecting mandatory or forbidden nodes you can use the arrow keys, ENTER and ESC.

As result, The module provides linearly independent invariant base and all the minimum positive invariantes (which are not superposition of other positive invariants). A covering test is also performed, and a topology test, indicating which invariants are state machines or event graphs:

• a state machine is a place invariant in which each transition bound to a place in the invariant has only one input arc and one output arc, both with unitary weight.
• An event graph is a transition invariant in which each place bound to a transition in the invariant has only one input arc and one output arc, both with unitary weight.

One must observe that such tests ignore the net timing information; only the topology aspects are considered.

The language equivalence verification allows to observe details of a Petri net behavior, focusing attention in some parts of the state graph and abstracting on the remaining. It consists on considering a set of transitions as being “visible” events, while the other transitions are considered invisible. From that, the state graph is reduced in order to get a minimum finite deterministic automata, containing only the visible events.

The user can define which transitions are visible (through the arrow keys, ENTER and ESC) and the program then calculates the state graph and process it in order to get the reduced automata containing only the visible transitions. It also calculates all the possible firing sequences in the reduced automata. In the firing path description, the symbols ”{” and ”}” indicate repetition. Therefore, a firing path described as “t1 {t3 t4}” means ” t1 t3 t4 t3 t4 …”. The module also allows the user to describe another state graph, in order to automatically compare it with the reduced automata found, but the graph matching is not completely implemented.

The simulation module allows the user to follow the net evolution, choosing the transitions to fire and observing the net state, step by step. The simulation window looks like this:

The right window has a diagram of the current simulation track. In the left side of the track the name of each state is shown (if memorized), or its depth from the initial state is indicated. In the right side of the track the name of each fired transition is indicated. The numbers indicated by ”«” show the number of transitions still not fired in each state.

If the track reachs a deadlock it finishes in a horizontal bar. If the state reached by a transition firing is duplicate of some state already in the track, this is indicated by a hatched line (in this case, the current state will not change).

The commands available are:

• Trace: turns on/off the simulation report generation. This report is a text describing details of the simulation performed.
• Memory: it allows to memorize states for rollback. A state can be memorized with any name not in used. At most 150 states can be memorized.
• Fire: allows to fire any transition enabled in the current state. The transitions still not fired are highlighted. If the firing time allowed for that transition is not defined, the simulator will ask it.
• Return: it allows to rollback to a previous state (backtracking), while they will have previous states in the evolution track. If the Petri netis not timed, it is also possible to “rewind” the net, i.e., to fire transitions in reverse order.
• Places: it allows to choose which places will have their marking indicated in the screen (default all).
• Edit: allows to modify the current marking or the dynamic firing interval [DEFT, DLFT] of each transition enabled in the current state. If the current state is modified, the current firing track is erased.
• State: allows to see details of any state in the track.

This module works with extended time Petri nets (Petri nets with a firing time interval associated to transitions, and a probability density function associated to each firing interval). Roughly, in this module the Petri net under evaluation is quickly and continuously played (simulated), while statistical information is gathered. The evaluation is concluded (and results are shown) when the statistical data reaches some stability criteria.

Two approaches for performance evaluation are considered: state-driven and event-driven. In the state-driven mode, the user defines an initial state (marking) and up to 10 final states. The evaluation module then simulates the net through simulation cycles. Each simulation cycle evolves the net from the initial state, by firing enabled transitions until a final state is reached. Transitions are fired at random times, respecting their associated firing intervals and firing probabilities. Also, if a deadlock state is found, or if a maximum number of firings is reached, the cycle is finished. After each cycle, statistical information is gathered and the net is put back in the initial state. Simulation cycles are repeated until a given precision is attained or the user press a key. The event-driven mode has a similar behavior, but the user defines an initial event (transition) and up to 10 final events (transitions). With this approach the user can estimate average times between events and the probability of occurrence of events.

During the evaluation some intermediate results are shown, just to give the user an idea of the final values and their convergence.

The user has as allowed options of input:

• Initial Marking: allows to define the initial marking to be used to start each simulation cycle.
• Target Markings: in the state aproach, defines each one of the states to reach. For bigger flexibility it is possible to define generic markings, attributing the symbol ”?” to the places whose marking does not need to be tested.
• Initial Event: in the event-driven approach, allows to define which the initial event (for time statistics).
• Target Events: in the event-driven approach, allows to define which events finish the simulation cycles.
• Max Fires: maximum number of transition firings allowed before reaching a destination. If this limit is reached the current simulation cycle is interrupted.
• Precision: defines the desired accuracy for the average access times.
• Conflicts: If two or more transitions have the same input arcs and firing intervals equal and punctual (SEFT=SLFT), they are said to be in conflict. This option allows to define firing probabilities among them.
• Reset: in the event-driven approach, after reaching a final state, the marking is normally reset back to the initial marking. This option allows to not reset the marking, causing a free and therefore more realistic evolution of the network.

The performance evaluation report contains the following statistical measures:

• Average time to access each destination.
• Minimum and maximum times to access each destination.
• Relative probabilities of access among destinations.
• Number of accesses to each destination.
• Average number of firings of each transition per simulation cycle.
• Average marking in each place, per time unit.
• Average waiting time for each transition to fire, after its enabling.
• Number of unsucessful cycles, in which no targets were reached.

The printing module transform the data into memory in a listing in the printer or a file. The output can be redirected by the user to a file in the current directory, where all the outputs are appended. The output file gets the ”.LST” extension.