Home
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.
The current system depends on the user interface for execution of a Petri net. The separation of logic between the core and GUI projects introduces the potential for Petri net execution independent of the GUI.
The design described below, is largely based on work by researchers and graduate students at the International Computer Sciences Institute (ICSI), work which was itself based on PIPE v2. Credit for those ideas belongs to Srini Narayanan, Jerry Feldman, Leon Barrett, and Malte Schilling. The initial implementation of the design is available in this pull request: https://github.com/sarahtattersall/PIPECore/pull/7/ This initial implementation would not have been possible without the thorough refactoring of PIPE done last year by Sarah Tattersall.
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.
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.
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).
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
- a.b : first 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"
- include "c", FQN: "a.b.c", unique name: "c"
- include "b", FQN: "a.b", unique name: "b"
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 the 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.)
Although only home places exist in the executable Petri net, both home and away places are saved to their corresponding PNML files, and re-built when those files are opened. In our example, if the file for "a" were opened by itself, it would have a place with Id "b.P0" that would behave like any other place. Only when the include hierarchy is opened, will the interface be re-established between the away place b.P0 in "a", and the home place P0 in "b".
The default scope of visibility of a place in the interface of an include, is the parents of that include. In our first 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:
- parent: the immediate parent of an include, e.g., a place in “c” would be visible in “b” but not in “a” or “bb”.
- parents & siblings: in addition to parents, the peers of an include under the same parent, e.g., a place in “b” would be visible in “bb”, as well as in "a" as its parent, but would not be visible in “c”. This might be useful in modeling peer-to-peer interactions. In such a case, the parent of the peers could just be an include 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 would 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.
So far, we've talked about how to make multiple Petri nets talk to one another in the same include hierarchy, through merge places. Next, we talk about how a Petri net can interface to an external system. Two mechanisms are proposed. First, another system can listen for changes in the marking of a given place, or can request an update to the marking of a place. Second, a type of transition can be configured, which when fired, passes control to an external system for processing, prior to marking the outbound places of the transition. In some cases, these two mechanisms are equivalent.
To make a place externally accessible, it is added to the interface for its include hierarchy, and flagged for external access. Just as for the merge case discussed above, adding a place to the interface changes the status of the place, but otherwise does not affect its behavior -- all interface-related behavior is implemented through the PlaceStatus associated with each Place. Providing access to a given place is accomplished through collaboration with the Runner interface (see Execution outside the GUI), which builds and runs executable Petri nets. The runner enables an external system to listen for changes to the marking of a given place, or to request that a given place be marked. Only places whose PlaceStatus is set for external access are available. Because what is being accessed through the runner is the executable Petri net, external requests are made using the fully-qualified name for the place.
The design of a Petri net is more clear when entry and exit places are distinct. When a place is added to the interface of its include hierarchy, it can be designated as either "input-only" or "output-only". This designation applies to both merge places and external places.
For access by an external system, an input-only place is an entry point, which the external system will mark to initiate Petri net processing. An output-only place is an exit point, to which the external system will listen for updates.
For the merge case, input-only and output-only are implemented through an "arc constraint" maintained by the place status, which controls what kind of arcs a place will accept, when it is accessed outside of its home Petri net. A place with an input-only arc constraint will only accept an inbound arc, and a place with an output-only arc constraint will only accept an outbound arc.
- Merge input: away place accepts only inbound arcs
- Merge output: away place accepts only outbound arcs
- External input: home place receives the marking
- External output: home place generates the marking
- External input, merge: home place receives the marking, away place accepts only inbound arcs
- External output, merge: home place generates the marking, away place accepts only outbound arcs
If neither input-only nor output-only are flagged, the place will accept any arc. There may be times when this is necessary, but it should probably be discouraged.
arc constraints
- so far, interface among PNs w/in same IH.
- interfaces to / from external systems: two approches
- External places
- start by adding a place to home net image
The Runner interface enables execution of Petri nets and include hierarchies independently from the GUI. The current implementation is PetriNetRunner, which supports the execution of a petri net or include hierarchy through the command line or through a Java program. Clients may request that execution be stopped after a given number of steps. An initial seed for pseudo-random operations can be provided; this is useful for generating repeatable test results, so that the "random" selection of the next enabled transition is in fact deterministic.
The current implementation is single-threaded -- a separate instance of PetriNetRunner is required for each Petri net or include hierarchy to be executed.
The following services are only available through the Runner API, not through command line invocation.
Program clients may listen for global events, including execution start and completion, and each "firing" -- the round (step) that has just completed, the transition that fired, and the prior and resulting marking of the executable Petri net.
Program clients may also listen for token changes to places that have External interface status. Clients may also request that External places be marked. Finally, clients may provide a context for external transitions.
- recursion: add limits to recursion?
- ids vs. names *component reuse
- multi-threading
- FQN vs. minimally unique names for EPN
- gui thoughts
- xml / pnml
- currently listening does not include consuming.