Home

In progress: https://github.com/sarahtattersall/PIPECore/pull/7/

Hierarchical Petri Nets & External Interfaces

Problems and limitations

As Petri nets become large and complex, they become difficult to maintain and test. It should be possible to break a problem into smaller problems, and model each smaller problem with a smaller Petri net. It should be possible to implement and test changes in a small Petri net in at least partial isolation. It should also be possible to test a small Petri net as part of testing a composite Petri net in which it participates.

The current system works in isolation. The state of a Petri net cannot be viewed or modified externally. A Petri net cannot be used to drive the behavior of some other system.

Hierarchical Nets

Include hierarchy

The proposed approach to composing a large Petri net from multiple smaller nets is to define an "include hierarchy", where one top-level net includes other nets, which may in turn include other nets. Each Petri net is maintained in its own PNML file. The include hierarchy itself is maintained in a separate XML file:

  <?xml version="1.0" encoding="iso-8859-1"?>
  <include name="a" netLocation="/xml/gspn1.xml">
      <include name="b" netLocation="/xml/simpleNet.xml">
         <include name="c" netLocation="/xml/petriNet.xml"/>
      </include>
      <include name="bb" netLocation="/xml/petriNet.xml"/>
  </include>

In this example, the top-level (or root) include is named "a", and the Petri net at that level is gspn1.xml. The child level under "a" has two includes, "b" and "bb". Include "b" has one child, "c".

The example shows the same Petri net, "petriNet.xml", included in two different places in the hierarchy, with different names. The include name functions like a variable name, enabling the same code to be used for multiple functions. If one were modeling an animal, for example, a Petri net that models a leg might be included multiple times, with names "left-front", "right-rear", etc. To avoid recursion, the only restriction on including Petri nets is that one net may not include itself.

Separating editable from executable Petri nets

PIPE currently has two modes of operation, one where Petri nets are edited, and a second where Petri nets are executed, one or more steps at a time. The addition of include hierarchies makes this distinction more explicit. An individual Petri net is edited and persisted in its own file. This enables it to be tested and maintained independently. When multiple Petri nets are added to an include hierarchy, however, they must be merged into one Petri net for execution. The combined net is called an "executable Petri net", and it contains the components from all of the nets in the include hierarchy, prefixed for uniqueness using the namespace defined by the include hierarchy. The executable Petri net supports simulation and analysis, by maintaining the state of the Petri net over execution steps.

In the code the distinction between editing and execution is realized by dividing functions from the original PetriNet class across two classes:

• the PetriNet class is responsible for adding/modifying/deleting components in a Petri net, and supporting the persistence of a net as a PNML document.
• the ExecutablePetriNet class is responsible for maintaining the marking of the Petri net as it is updated by transitions firing, and supporting the analysis of the Petri net.

The editable Petri net is visible in the user interface for purposes of editing and persistence. The executable petri net is rebuilt automatically following any change in the editable Petri net, to support execution and analysis of the Petri net. The executable Petri net is not visible in the user interface, but a change in token counts for a given place in the executable Petri net is mirrored to the corresponding place in the editable Petri net, to enable the user to follow the flow of execution in the GUI.

Single Petri nets unaffected

The proposed extensions should not affect the use of PIPE for its primary purpose, editing and simulating single Petri nets. Therefore, include hierarchies are optional, and are maintained in separate files from Petri nets. Also, the distinction between editable and executable Petri nets causes no changes in the behavior of the user interface. Finally, if an include hierarchy is used, the root level (only) may be given a blank name, so that its component names in all contexts will be unchanged from the current default (see below, #Name uniqueness).

Name uniqueness

To ensure that all components in an executable Petri net are uniquely identified, each component Id is given a dotted prefix, built from the names in the include hierarchy. Each include has a fully-qualified name, which is built by concatenating each name in the hierarchy, proceeding down from the root, delimited by "." Examples, from the sample include hierarchy above:

• a : root include
  • a.b : first child under the root
    • a.b.c : first child under the first child
  • a.bb : second child under the root

Each component Id in the executable Petri net is prefixed with the fully-qualified name (FQN) of its include. Examples:

• a.P0 : P0 from gspn1.xml (include "a")
• a.b.c.P0 : P0 from petriNet.xml (include "a.b.c")
• a.bb.P0 : P0 from petriNet.xml (include "a.bb")

This convention can be cumbersome in large hierarchies, so for some purposes the name is reduced to the minimum necessary to ensure uniqueness, generally just the include name. In the example above, each of the names is unique, so "c" can be used in place of "a.b.c". However, the same name can be re-used at multiple levels of a hierarchy. When that is the case, the include closest to the root uses its the minimally unique name, and the minimally unique name for the lower level is the path down from the conflicting name:

• include "a", FQN: "a", unique name: "a"
  • include "b", FQN: "a.b", unique name: "b"
    • include "c", FQN: "a.b.c", unique name: "c"
      • include "b", FQN: "a.b.c.b", unique name: "b.c.b"

Interface: merge places

The sample include hierarchy above suggests that the net at level “a” needs services provided by the “b” and “bb” nets, and “b” in turns needs services provided by “c”. In this composition of components, “a” marks one or more places in “b”, which triggers processing in “b”. This may result in marking other places in “b”, which signal completion of processing in “b”, and which may in turn trigger subsequent processing in “a”. To encapsulate the function in “b” as much as possible, we define a subset of places in “b” as constituting the interface for “b”. The typical semantics of the interface is that one or more of the places are entry points, whose marking starts processing in “b”, and one or more of the places are exit points, whose marking return values to the caller.

Suppose place P0 in “b” is an entry point for processing that we would like to invoke from "a".

We add P0 to the interface for “b”, and define that it should be visible to nets that are parents of “b” in the include hierarchy. We say that P0 in “b” is the “home” place.

Place P0 is copied to the parent nets, “a” in this case, and becomes “available” to be used. The copied place is given the minimally unique Id corresponding to the home place, “b.P0” in this case.

To use the copied place in “a”, we add it to Petri net, at which point we call it an “away” place.

We can add arcs in “a” to b.P0 like we would for any other place in “a”. It is a place like any other, just with a different status.

Home and away places mirror each other’s token counts. If away place b.P0 is marked in “a”, then home place P0 in “b” will also be marked, and if the tokens in P0 in “b” are consumed, they will also be consumed in b.P0 in “a”. This enables us to view “a” and “b” as separate networks in the GUI, with separate home and away places laid out in the GUI as best expresses the logic.

step 1:

step 2:

step 3:

"Home", "away" (and "available") are just different states of one place. These states are merged when the executable Petri net is built, and only the home place is retained. Any arc to or from an away place is re-built to the corresponding home place, and the away place is dropped. (Available places are those that have not yet been added to a net, and are therefore ignored in building the executable Petri net.)

The natural scope of visibility of a place in the interface of an include, is the parents of that include. In our example, a place added to the interface in “c” would be accessible (available) in “b” and “a”, but not in “bb”. Other access scopes are supported:

• sibling: the peers of an include under the same parent, e.g., a place in “b” would be visible in “bb” but not in “a” or “c”. This might be useful in modeling peer-to-peer interactions. In such a case, the parent of the peers could just be an empty container with an empty Petri net, serving only to establish the peer relationship between the siblings, who communicate with each other directly through their interfaces.
• all: any other include in the hierarchy, e.g., a place in “bb” would be visible to “a”, “b” and “c”. This provides maximum flexibility, but should probably only be used in unusual circumstances, as its use will tend to introduce cyclic dependencies.

For simplicity, as currently implemented, the access scope at the top or root level of the include hierarchy cascades down through the hierarchy. I don’t know if more flexibility will be desirable. Each include is opened as a separate tab in the user interface; tabs are opened in a cascade until all included Petri nets are visible.

Each tab enables the separate editing of its corresponding Petri net, and persistence to and from a separate PNML file.

Animation or analysis can be done for any Petri net and its included Petri nets.

Upon entering animation or analysis modes for a given Petri net, an executable Petri net is built, consisting of all the components in the given Petri net and its included Petri nets.

Interface Places enable Petri nets in an include hierarchy to communicate:

A Place may be identified as an InterfacePlace, meaning that it will be added to the Interface of the IncludeHierarchy of the Petri net in which it is defined.

An InterfacePlace may have one of three statuses:

• Home: the InterfacePlace status in the Petri net in which its source Place is defined.
• Available: the InterfacePlace status when it exists in the Interface of Petri nets other than the home Petri net, but has not yet been added to the Petri net. InterfacePlaces are available to Petri nets that are in the parent hierarchy of the home Petri net, and are not available to Petri nets that are in the child hierarchy of the home Petri net. Discuss: InterfacePlaces are/are not available in Petri nets at the same level of include hierarchy as the home Petri net. For example, if an interface place is defined in home net "left", corresponding to place "root.left.P0", then it is/is not available to net "right" that is also a child of "root".
• InUse: the InterfacePlace status when it has been added to a Petri net. In use interface places mirror the token counts of their source place.

A given interface place may exist only once for a given Petri net.

Unique interface place IDs are created by suffixing the ID with "-I".

Example: net "root" includes net "a" which includes net "b", which has place "P0". "P0" is then added to the interface of net "b", which causes three interface places to be created:

• "b.P0-I" with home status in net "b"
• "a.b.P0-I" with available status in net "a"
• "root.a.b.P0-I" with available status in net "root"

Example (continued):

• If "a.b.P0-I" is added as a component to the root Petri net, its name is unaffected, but its status changes to in use, and its marking will mirror the marking of place "P0" in "b". Example (continued): When the "root" net is animated, an executable Petri net is created with these components:
• "root.a.b.P0" is the source place corresponding to "P0" in "b"
• "root.a.b.P0-I" is the interface place corresponding to the in-use interface place in "root"

Example (continued): a marking change to "root.a.b.P0" or to "root.a.b.P0-I" will be mirrored to the other, as well as to the source place, "P0" in "b".

InterfacePlaces will be persisted to / from the PNML documents for their corresponding Petr nets.

Discuss: should interface places have an explicit designation for input or output?

Discuss (future): ExternalInputPlace ("Sensor Place"), ExternalOutputPlace ("Motor Place")

Execution independent of the user interface:

• PetriNetRunner class supports the execution of a petri net through the command line or through a Java program.
• Long integer can be provided as a seed for pseudo-random selection of the next transition to fire. This enables test results to be repeatable.

###Status

• Separate editable from executable Petri nets: complete

• Include hierarchy (basic): complete

• PetriNetRunner: complete

• Interface places: in progress

• XML persistence (includes)

• XML persistence (interface places)

• GUI (includes)

• GUI (interface places)

• Include hierarchy (complete, e.g., no recursion)

• Module-gui integration

• Documentation

• Integrate and release

• Two weeks effort to date; 60+ additional tests.

Issues:

recursion: add limits to recursion? ids vs. names