Skip to content

Home

Jump to bottom Edit New page
sjdayday edited this page Nov 30, 2014 · 49 revisions

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 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": fully-qualified name: "a", minimally unique name: "a"
    • include "b": fully-qualified name: "a.b", minimally unique name: "b"
      • include "c": fully-qualified name: "a.b.c", minimally unique name: "c"
        • include "b": fully-qualified name: "a.b.c.b", minimally unique name: "b.c.b"

Composition of Petri nets:

IncludeHierarchy class enables one Petri net to include other Petri nets.

Includes may be nested.

Includes may not be recursive. If "A" includes "B", "B" may not include "A"

Each include is given an alias name, to indicate its function.

The same Petri net may be included multiple times under different aliases, e.g., "left-leg", "right-leg"

In the editable Petri net, an include consists of a Petri net name, alias, and path.

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.

To ensure unique component IDs, each component in the executable Petri net is given a new ID consisting of its original ID prefixed with the concatenation of the alias IDs of the hierarchy in which it appears. Alias assignment for the top-level Petri net is optional, and defaults to none.

Example: a top-level net may have alias "root", and may include a net with alias "a", which may in turn include a net with alias "b". Place P0 may exist in each of the three nets. In the executable Petri net, the three places would have IDs "root.P0", "root.a.P0", and "root.a.b.P0", respectively. If the top-level net did not have an alias, the three places would have IDs "P0", ".a.P0" and ".a.b.P0", respectively.

The use of component aliases, known as "view IDs", generates uniqueness in the executable Petri net, while leaving each of the consitutent Petri nets unaffected.

A given component in a lower-level Petri net might have any of several view IDs at a given time, depending on the include hierarchy level at which it is animated or analyzed. Place "P1" in the net "b" might just be "P1" if only its own Petri net is being tested, but it will be "a.b.P1" if the parent net "a" is being tested, and it will be "root.a.b.P1" if the top-level net is being tested.

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

Add a custom footer
Add a custom sidebar
Clone this wiki locally