ptolemy.domains.petrinet.kernel
Class PetriNetDirector

java.lang.Object
  ptolemy.kernel.util.NamedObj
      ptolemy.kernel.util.Attribute
          ptolemy.actor.Director
              ptolemy.domains.petrinet.kernel.PetriNetDirector

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, Executable, Initializable, Changeable, Debuggable, DebugListener, Derivable, ModelErrorHandler, MoMLExportable, Moveable, Nameable

public class PetriNetDirector
extends Director

Petri net director.

This domain implements the basic Petri Net model where Places and Transitions form a bipartite graph and enabled Transitions can fire randomly. It also allows Transitions to be replaced by any other Actors in Ptolemy. It implements two forms of Hierarchical and compositional Petri nets. The first form of hierarchical and compositional Petri net semantics comes from the fact that a Transition can contain a sub-Petri-net which is invisible to the director of the container of the Transition. The second form of hierarchical and compositional Petri net semantics comes from a new Actor called PetriNetActor which is a collection of Places and Transitions, and those Places and Transitions are visible to the director of the container of the PetriNetActor. The users can choose which form of models to use, and/or mix them together.

The basic Petri net is a directed, weighted, bipartite graph consisting of two kinds of nodes, called Places and Transitions, where arcs are either from a Place to a Transition or from a Transition to a Place. In graphical representation, Places are drawn as circles, Transitions as bars or boxes. Arcs are labeled with their weights (positive integers). Labels of unity weight are usually omitted. Multiple arcs can exist between a Place and a Transition. A marking assigns to each Place p an nonnegative integer k, we say that p is marked with k tokens.

Please note here the term token is used differently from the general Ptolemy term token. Here a token is really the integer 1. k tokens is represented by the integer k.

A Transition t is said to be enabled if each input Place p of t is marked with at least the sum of w(p, t) tokens, where w(p, t) are the weights of the arcs from p to t.

An enabled Transition may or may not fire. When there are multiple enabled Transitions, any of them can fire randomly. A firing of an enabled Transition t removes w(p, t) tokens from each input Place p of t, and adds w(t, p) tokens to each output Place p of t, where w(t, p) and w(p, t) are the weights of the arcs from and to the Transition respectively.

A Transition without any input Place is called a source Transition, and one without any output Place is called a sink Transition. Note that a source Transition is unconditionally enabled, and that the firing of a sink Transition consumes tokens, but does not produce any.

Many variations of Petri net exist in the literature including: hierarchical Petri nets, colored Petri nets, timed Petri nets, fuzzy Petri nets, stochastic Petri nets, compositional Petri nets, and many of the combinations.

As pointed out earlier, in Ptolemy we implement the basic Petri net model plus two kinds of hierarchical and compositional Petri nets. This is made possible by defining the PetriNetActor. The PetriNetActor is a directed and weighted graph just like the basic Petri Net model. However, a PetriNetActor graph G = (V, E) contains three kinds of nodes: Places p_i, Transitions t_i, and PetriNetActors PA_i, i.e., V = {p_i} union {t_i} union {PA_i} , where each PA_i itself is again defined as a PetriNetActor. Places are assigned with non-negative integer markings. The default marking is 0. A Place is implemented by the atomic actor Place. A PetriNetActor is a TypedCompositeActor contains Places, Transitions and/or PetriNetActors.

Each node of V is called a component of the PetriNetActor G. Therefore the vertex set V of G is also called the component set of the PetriNetActor G. The concept of component is a key difference between the basic Petri net model and the hierarchical Petri net model defined here. In Ptolemy term, a component is an element in the entityList of the PetriNetActor. A PetriNetActor consists of components. A component can be a Place, a Transition, and a PetriNetActor component. A component can be enabled and fires if it is a Transition or it is a PetriNetActor component that contains other Transitions. When the firing method _fireHierarchicalPetriNetOnce() fires, it chooses one component to fire.

The definition of PetriNetActor defines one form of hierarchical and compositional Petri nets. It defines a hierarchical Petri net since the PetriNetActor G can contain other PetriNetActors PA_i as components. It defines a compositional Petri net since two PetriNetActors PA_1 and PA_2 of V can be connected through their ports to form a bigger Petri net G.

The second form of Hierarchical and compositional Petri net comes from the fact that a Transition can be any TypedCompositeActor in Ptolemy domains, which can have its own firing director. The content of the Transition is invisible to the director of the container of the Transition. Therefore it is possible to have a Transition contains other Places and Transitions and has a PetriNetDirector as the local director for the Transition.

The set of Transitions of the PetriNetActor G, or the Transition set of G, is defined to be the union of the Transitions t_i with the sets of Transitions of each PetriNetActor component PA_i. A member of the Transition set of G is therefore contained in G itself in which case the Transition is also a component of G, or it is contained in some PetriNetActor component PA_i. Therefore a Transition is a different concept from a Component in PetriNetActor graph. The method findTransitions() returns the Transition set of G.

A component has ports through which connections to other components are made. A Place or a Transition each has one input port and one output port, where multiple connections can be made. In our model, a PetriNetActor component can have multiple ports. A PetriNetActor component PA_j can be connected to Places p_i, Transitions t_i, or other PetriNetActor components PA_i through ports. A Place p_i can be connected to Transitions t_i, or to ports of PetriNetActor components PA_i. A Transition t_i can be connected to Places p_i or to ports of PetriNetActor components PA_i.

One restriction is that a port of a PetriNetActor component PA_i is either connected to Places or to Transitions, but not both. Another restriction is that a Place (Transition) is not allowed to be connected to another Place (Transition) through ports. Though no verification of these two conditions is checked, any violation of these two conditions will be reported by appropriate methods during the execution.

Multiple arcs can exist between any two components. The arcs can be marked by an nonnegative integer as their weights. Weight 1 can be omitted. The method _getWeightNumber(arc) obtains the weight assigned to the arc. If no weight is assigned, the default weight is 1.

For a Transition t, all Places p that can reach t through ports or without ports are the input Places of t. All Places that can be reached from t through ports or without ports are the output Places of t. Given a Transition t, the methods _findBackwardConnectedPlaces() and _findForwardConnectedPlaces() find the input and output Places of the Transition respectively.

A Transition t is enabled or ready in the PetriNetActor if for each input Place p of t, the marking of p is bigger than the sum of the weights of all arcs connecting p to t. The method isTransitionReady(transition) tests whether the given Transition is enabled/ready or not.

If a Transition t is enabled and t is contained in a PetriNetActor component PA_i, then the PetriNetActor component PA_i is also an enabled component. On the other hand, for any PetriNetActor component PA_i, if it contains an enabled Transition, then the PetriNetActor component PA_i is enabled. The method PetriNetActor.prefire() tests whether there is any enabled Transitions contained in the PetriNetActor component.

An enabled Transition may or may not fire. For the given PetriNetActor G, all its enabled components including Transitions t_i and PetriNetActor components PA_i are collected together in a list returned by _readyComponentList(). Suppose the list has n components of t_i and PA_i, each component has 1/n probability to be chosen to fire. The method _fireHierarchicalPetriNetOnce() chooses one component from the list to fire.

If an enabled Transition is chosen to fire, the method fireTransition() is called to fire the Transition and update the input and output Places of the Transition. The firing of the Transition is determined by its own director, if there is one, otherwise no action is needed. For each input Place of the Transition, its marking has to be decreased by the weight of each arc connecting the Place to the Transition. For each output Place, the marking will be increased by the weight of each arc connecting the Transition to the Place.

If a PetriNetActor component PA_i is chosen to fire, the director then recursively repeats the same procedure for PA_i as for the top level PetriNetActor G.

Finally, the firing of the hierarchical Petri net is continued until there is no more Transitions and components to fire, or it goes to infinite loop. Currently no action is taken for infinite loops.

Other form of firing sequence can be defined as well. We could randomly fire all the deeply contained Transitions. We could randomly fire the components in each hierarchy. [1] T. Murata, "Petri nets: properties, analysis and applications", Proceedings of the IEEE, VOl. 77, NO. 4, April 1989, pp. 541-579. [2] J. L. Peterson, "Petri Net Theory and the modeling of systems", Prentice Hall, 1981.

Since:

Ptolemy II 2.0

Version:

$Id: PetriNetDirector.java 57040 2010-01-27 20:52:32Z cxh $

Author:

Yuke Wang and Edward A. Lee

See Also:

Serialized Form

Accepted Rating:

Red (reviewmoderator)

Proposed Rating:

Red (yukewang)

Nested Class Summary

Nested classes/interfaces inherited from class ptolemy.kernel.util.NamedObj

NamedObj.ContainedObjectsIterator

Field Summary

Fields inherited from class ptolemy.actor.Director

_actorsFinishedExecution, _currentTime, _finishRequested, _initializables, _stopRequested, timeResolution

Fields inherited from class ptolemy.kernel.util.NamedObj

_changeListeners, _changeLock, _changeRequests, _debugging, _debugListeners, _elementName, _isPersistent, _verbose, _workspace, ATTRIBUTES, CLASSNAME, COMPLETE, CONTENTS, DEEP, FULLNAME, LINKS

Fields inherited from interface ptolemy.actor.Executable

COMPLETED, NOT_READY, STOP_ITERATING

Constructor Summary

PetriNetDirector(CompositeEntity container, java.lang.String name)
Construct a new Petri net director.

Method Summary

private java.util.LinkedList	_findBackwardConnectedPlaces(IORelation weight) For each relation, this method finds all the affected Places in the backward direction, i.e., the input Places.
private java.util.LinkedList	_findBackwardConnectedPlaces(TypedCompositeActor transition) This method finds all the Places that determines whether a transition is enabled or not.
private java.util.LinkedList	_findForwardConnectedPlaces(IORelation weight) This method finds the forward connected Places or output Places for a given relation.
private boolean	_fireHierarchicalPetriNetOnce(TypedCompositeActor container) This method is to test a PetriNetActor can be fired or not, and fires the PetriNetActor once if it can be fired.
private int	_getWeightNumber(IORelation weights) This method gets the weight assigned to the given relation.
private java.util.List	_readyComponentList(TypedCompositeActor container) This method finds all the enabled components in a container and returns the list.
java.util.LinkedList	findTransitions(TypedCompositeActor container) This method finds all Transitions of the given container, i.e., the Transition set of the container, which is supposed to be a PetriNetActor.
void	fire() This method fires enabled components of the PetriNetActor, by calling the method _fireHierarchicalPetriNetOnce(), one at a time until there is no more enabled components to fire.
void	fireTransition(TypedCompositeActor transition) This method fires an enabled Transition.
boolean	isTransitionReady(TypedCompositeActor transition) This method tests whether a given Transition is enabled or not.
boolean	postfire() Return false, indicating that the director does not wish to be scheduled for another iteration.

Methods inherited from class ptolemy.actor.Director

_description, _fireContainerAt, _isEmbedded, _isTopLevel, _transferInputs, _transferOutputs, addInitializable, attributeChanged, createSchedule, defaultDependency, finish, fireAt, fireAt, fireAtCurrentTime, getCausalityInterface, getCurrentTime, getErrorTolerance, getGlobalTime, getModelNextIterationTime, getModelStartTime, getModelStopTime, getModelTime, getNextIterationTime, getStartTime, getStopTime, getTimeResolution, implementsStrictActorSemantics, initialize, initialize, invalidateResolvedTypes, invalidateSchedule, isFireFunctional, isStopRequested, isStrict, iterate, newReceiver, prefire, preinitialize, preinitialize, removeInitializable, requestInitialization, setContainer, setCurrentTime, setModelTime, stop, stopFire, suggestedModalModelDirectors, supportMultirateFiring, terminate, transferInputs, transferOutputs, wrapup

Methods inherited from class ptolemy.kernel.util.Attribute

_checkContainer, _getContainedObject, _propagateExistence, clone, getContainer, moveDown, moveToFirst, moveToIndex, moveToLast, moveUp, setName, updateContent

Methods inherited from class ptolemy.kernel.util.NamedObj

_addAttribute, _adjustOverride, _attachText, _cloneFixAttributeFields, _debug, _debug, _debug, _debug, _debug, _exportMoMLContents, _getIndentPrefix, _isMoMLSuppressed, _markContentsDerived, _propagateValue, _recordDecoratedAttributes, _removeAttribute, _splitName, _stripNumericSuffix, _validateSettables, addChangeListener, addDebugListener, attributeList, attributeList, attributeTypeChanged, clone, containedObjectsIterator, deepContains, depthInHierarchy, description, description, event, executeChangeRequests, exportMoML, exportMoML, exportMoML, exportMoML, exportMoML, exportMoMLPlain, getAttribute, getAttribute, getAttributes, getChangeListeners, getClassName, getDecoratorAttribute, getDecoratorAttributes, getDerivedLevel, getDerivedList, getDisplayName, getElementName, getFullName, getModelErrorHandler, getName, getName, getPrototypeList, getSource, handleModelError, isDeferringChangeRequests, isOverridden, isPersistent, lazyContainedObjectsIterator, message, propagateExistence, propagateValue, propagateValues, removeChangeListener, removeDebugListener, requestChange, setClassName, setDeferringChangeRequests, setDerivedLevel, setDisplayName, setModelErrorHandler, setPersistent, setSource, sortContainedObjects, toplevel, toString, uniqueName, validateSettables, workspace

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

PetriNetDirector

public PetriNetDirector(CompositeEntity container,
                        java.lang.String name)
                 throws IllegalActionException,
                        NameDuplicationException

Construct a new Petri net director.

Parameters:

container - The container.

name - The name of the director.

Throws:

IllegalActionException - If the name has a period in it, or the director is not compatible with the specified container.

NameDuplicationException - If the container already contains an entity with the specified name.

Method Detail

fire

public void fire()
          throws IllegalActionException

This method fires enabled components of the PetriNetActor, by calling the method _fireHierarchicalPetriNetOnce(), one at a time until there is no more enabled components to fire. The enabled component can be an enabled Transition or an enabled PetriNetActor component. It is the job of the method _fireHierarchicalPetriNetOnce() to find all enabled components if there is any, to choose which enabled component to fire, and to update markings of related Places when a component fires.

Specified by:

fire in interface Executable

Overrides:

fire in class Director

Throws:

IllegalActionException - If the method _fireHierarchicalPetriNetOnce() throws exceptions, which can happen if the method isTransitionReady() or fireTransition() throws exceptions.

findTransitions

public java.util.LinkedList findTransitions(TypedCompositeActor container)

This method finds all Transitions of the given container, i.e., the Transition set of the container, which is supposed to be a PetriNetActor. A Transition can be contained in the top level PetriNetActor, or its PetriNetActor components. This method searches for Transitions recursively for each PetriNetActor component.

Parameters:

container - The container where the Transitions are contained.

Returns:

the list of Transitions contained by the container.

isTransitionReady

public boolean isTransitionReady(TypedCompositeActor transition)
                          throws IllegalActionException

This method tests whether a given Transition is enabled or not. A Transition is enabled if for each of the input Places, the marking of the Place is bigger than the sum of weights of edges connecting the Place to the Transition. The Transition itself is any TypedCompositeActor. The Transition can be a component of a PetriNetActor, or it is contained in some PetriNetActor component. This is one of the key methods for hierarchical Petri Nets. It is equivalent to the prefire() method for a Transition. The method first finds all the input Places of the Transition by calling the method _findBackwardConnectedPlaces(), and sets the temporary marking of the Places equal to the real marking; then it enumerates all the arcs connecting Places to the Transition and decreases the temporaryMarking of the Places reachable from the arc. If after all arcs have been enumerated and the temporaryMarking of all input Places are greater than 0, then the Transition is ready to fire, otherwise it is not ready to fire. The reason that we use a temporaryMarking here is to keep the initialMarking of the places unchanged when we test a Transition is ready or not.

Parameters:

transition - Transition to be tested to be enabled or not.

Returns:

true or false The tested transition is ready to fire or not.

Throws:

IllegalActionException - If the method "_getWeightNumber" throws exceptions, which can happen if the arcs are not assigned to some other value other than integers.

fireTransition

public void fireTransition(TypedCompositeActor transition)
                    throws IllegalActionException

This method fires an enabled Transition. The transition argument to this method must be an enabled Transition. If the given Transition is Opaque, then it fires the Transition first, otherwise no action is taken for the Transition; the method then updates the markings of the input Places and output Places of the Transition. The update of the marking is done one relation at a time. The input Places and output Places are found by the methods _findForwardConnectedPlaces() and _findBackwardConnectedPlaces() respectively.

Parameters:

transition - The transition to be fired.

Throws:

IllegalActionException - If the method _getWeightNumber() throws an exception.

postfire

public boolean postfire()
                 throws IllegalActionException

Return false, indicating that the director does not wish to be scheduled for another iteration. FIXME: This is provisional since there is currently no way to stop the execution of a Petri net model, so we just run once.

Specified by:

postfire in interface Executable

Overrides:

postfire in class Director

Returns:

False.

Throws:

IllegalActionException - Not thrown in this base class.

_readyComponentList

private java.util.List _readyComponentList(TypedCompositeActor container)
                                    throws IllegalActionException

This method finds all the enabled components in a container and returns the list. The firing method will choose one component from this list randomly to fire. A Transition is enabled if isTransitionReady() returns true on testing the transition. A PetriNetActor is an enabled component if it contains an enabled Transition, which is tested by the method petriNetActor.prefire().

Parameters:

container - Test how many components are ready to fire in the container.

Returns:

Return all the ready to fire components in the container.

Throws:

IllegalActionException - If isTransitionReady() or PetriNetActor.prefire() throws exception.

_fireHierarchicalPetriNetOnce

private boolean _fireHierarchicalPetriNetOnce(TypedCompositeActor container)
                                       throws IllegalActionException

This method is to test a PetriNetActor can be fired or not, and fires the PetriNetActor once if it can be fired. The method first finds all the enabled components returned by _readyComponentList(); then it randomly chooses one component to fire. If the chosen component is a PetriNetActor, this method is called recursively to fire the chosen PetriNetActor component; otherwise the chosen component must be a Transition represented by any TypedCompositeActor, and this method calls the method fireTransition() to fire the Transition.

Parameters:

container - The container of the hierarchical Petri net.

Returns:

true or false The PetriNetActor container can be fired or not.

Throws:

IllegalActionException - If _readyComponentList() or fireTransition() throws an exception.

_findForwardConnectedPlaces

private java.util.LinkedList _findForwardConnectedPlaces(IORelation weight)

This method finds the forward connected Places or output Places for a given relation. This is equivalent to find all Places reachable for this relation. This method is needed when we update the tokens in Places connected to a firing Transition. We can not use the method deeplyConnectedPortList() due to the duplication of ports in the list.

Parameters:

weight - The arc connecting transition output to ports or Places.

Returns:

List The output Places needed to be updated if the transition connected to the weight fires.

_findBackwardConnectedPlaces

private java.util.LinkedList _findBackwardConnectedPlaces(IORelation weight)

For each relation, this method finds all the affected Places in the backward direction, i.e., the input Places. Those Places determine whether a Transition is ready to fire or not. If ready, the firing Transition has to update the tokens in all these Places. The algorithm used in this method is the breadth first search of the graph.

Parameters:

weight - The arc connecting transition input to ports or Places.

Returns:

List The Places control the transition at the end of the weight is ready to fire or not.

_findBackwardConnectedPlaces

private java.util.LinkedList _findBackwardConnectedPlaces(TypedCompositeActor transition)

This method finds all the Places that determines whether a transition is enabled or not. It starts to trace each input relation of the transition and finds each of the Place connected to the relation. This allows duplicated copies of the same Place.It unites all the connected Places to each relation.

Parameters:

transition - A Transition of concern.

Returns:

List Returns all the backward connected Places to the transition.

_getWeightNumber

private int _getWeightNumber(IORelation weights)
                      throws IllegalActionException

This method gets the weight assigned to the given relation. The current hierarchical Petri Net allows multiple arcs connecting Places, transitions, and ports. Each arc can have an attribute "weight", or without such attribute. The default is assumed to be weight 1. This default weight can be changed into other weight if necessary.

Parameters:

weights - An arc in the PetriNetActor.

Returns:

The weight associated with the relation, default is 1.

Throws:

IllegalActionException - If attribute.getToken or token.intValue throws an exception, which may happen if the weight assigned to the relation is not an integer.