Petri Nets: Tutorial and Applications

1 Edward Lin, University of Maryland1 Petri Nets: Tutorial and ApplicationsJeffrey W. HerrmannEdward LinCIM LabInstitute for Systems ResearchUniversity of MarylandCollege Park, MarylandINSTITUTE FOR SYSTEMS RESEARCHA National Science Foundation Engineering Research Center, supported by NSF, the University of Maryland, Harvard University, and IndustryThe 32th Annual Symposium of the Washington Operations Research -Management Science CouncilWashington, 5, 1997 Edward Lin, University of Maryland2 OutlinelPurposelApplicationslWhat is a Petri Net?lDynamicslBasic ConstructslPropertieslAnalysis MethodslExtensions of Petri NetslResources for Petri NetslSummaryEdward Lin, University of Maryland3 PurposelTo describe the fundamentals of Petri nets so thatyou begin to understand what they are and howthey are give you resources that you can use to learnmore about Petri Lin, University of Maryland4 Petri Net ApplicationslManufacturing, production, and scheduling systemslSequence controllers (Programmable LogicController, PLC)

2 LCommunication protocols and networkslSoftware -- design, specification, simulation,validation, and implementationEdward Lin, University of Maryland5 Petri Nets -- Graphic ToollA bipartite directed graph containing places(circles), transitions (bars), and directed arcs(places <--> transitions).Places -- buffers, locations, statesTransitions -- events, actionsTokens -- partsloadingprocessingUnloadingEdward Lin, University of Maryland6 Petri Nets -- Mathematical ModelsA Petri net is a four-tuple:PN = <P, T, I, O>P: a finite set of places, {p1, p2, .., pn}T: a finite set of transitions, {t1, t2.}

3 , ts}I: an input function, (T x P) > {0, 1}O: an output function, (T x P) > {0, 1}M0: an initial marking, P > N<P, T, I, O, M0> -- a marked Petri netloadingprocessingUnloadingEdward Lin, University of Maryland7An ExamplelP = {p1, p2, p3}lT = {t1, t2, t3}lI = p1 p2 p3loadingprocessingUnloadingp1t1p2t2p3tt t123100010001 lO = p1 p2 p3lM0 = (1, 0, 0)ttt123010001100 Note:p1 is the input place of transition t1p2 is the output place of transition t1t3 Edward Lin, University of Maryland8 DynamicslEnabling Rule: A transition t is enabled if every input place contains atleast one tokenlFiring Rule: Firing an enabled transition removes one token from each input place of the transition adds one token to each output place of the transitionloadingprocessingUnloadingEdwa rd Lin, University of Maryland9 DynamicsloadingprocessingUnloadingInitia l State:loadingprocessingUnloadingState after t1 is fired:loadingprocessingUnloadingState after t2 is fired:loadingprocessingUnloadingState after t3 is fired.

4 T1t2t3 Edward Lin, University of Maryland10 Basic ConstructslSequential actionslDependencylConflict (decision, choice)lConcurrencylCycleslSynchronizati on - (mutually exclusive actions,resource sharing, communication, queues)Edward Lin, University of Maryland11 Sequential ActionsEach action is a Lin, University of Maryland12 DependencyA transition requires two Lin, University of Maryland13 Conflict ConstructOnly one of the two transitions can Lin, University of Maryland14 Concurrency ConstructThese two sequences can occur Lin, University of Maryland15 CyclesloadingprocessingUnloadingEdward Lin, University of Maryland16 SynchronizationloadingprocessingUnloadin gMachine can process one part at Lin.

5 University of Maryland17 Resource Sharingloadingprocessingpart 1unloadingloadingprocessingpart 2unloadingOne worker for two worker can work at one machine at a Lin, University of Maryland18 Buffer (Queue)The buffer can hold a limited number of parts. Edward Lin, University of Maryland19 CommunicationProgram 1 Program 2 Edward Lin, University of Maryland20An ExampleMachine States:LoadingProcessingWaiting for unloadingUnloadingMachine 1 Machine 2 RobotBufferBuffer State:Space availabilityEdward Lin, University of Maryland21 Put It TogetherLoadingProcessingWaitingforUnloa dingUnloadingMachine 1 Machine 2 RobotBuffer AvailableEdward Lin, University of Maryland22 Properties (Questions)PropertyExampleBoundedness- the number of tokens in a place is boundedWork-in-processSafeness- the number of tokens in a place never exceeds oneHardware devicesDeadlock-free- none of markings in R(PN, M0) is a deadlockResources competingReachability- find R(PN, M0)

6 Messages deliveryEdward Lin, University of Maryland23 Analysis MethodslEnumeration Reachability Tree Coverability TreelLinear Algebraic Technique State Matrix Equation Invariant Analysis: P-Invariant and T-invariantlSimulationEdward Lin, University of Maryland24 Reachability Tree (1)p1p2p4p3p5p6t1t2t3t4 Initialization:M0=(1,0,0,0,0,1)Step 1:M0 = (1,0,0,0,0,1)M1 = (0,1,0,1,0,1)t1 Step 2:M0 = (1,0,0,0,0,1)M1 = (0,1,0,1,0,1)M2 = (0,0,1,1,0,1)M4 = (0,1,0,0,1,1)t1t2t3 Edward Lin, University of Maryland25 Reachability Tree (2)p1p2p4p3p5p6t1t2t3t4M0 = (1,0,0,0,0,1)M1 = (0,1,0,1,0,1)M2 = (0,0,1,1,0,1)M4 = (0,1,0,0,1,1)M3 = (0,0,1,0,1,1)t1t2t3t3 Step 3:Step 4:M0 = (1,0,0,0,0,1)M1 = (0,1,0,1,0,1)M2 = (0,0,1,1,0,1)M4 = (0,1,0,0,1,1)M3 = (0,0,1,0,1,1)t1t2t3t3t2M3 Edward Lin, University of Maryland26 Reachability Tree (3)M0 = (1,0,0,0,0,1)M1 = (0,1,0,1,0,1)M2 = (0,0,1,1,0,1)M4 = (0,1,0,0,1,1)M3 = (0,0,1,0,1,1)t1t2t3t3t2t4M0M3p1p2p4p3p5p 6t1t2t3t4 Step 5.

7 Edward Lin, University of Maryland27 Reachability Tree/Graphp1p2p4p3p5p6t1t2t3t4M0 = (1,0,0,0,0,1)M1 = (0,1,0,1,0,1)M2 = (0,0,1,1,0,1)M4 = (0,1,0,0,1,1)M3 = (0,0,1,0,1,1)t1t2t3t3t2t4M0M3M0M1M2M4M3t 1t2t3t3t2t4 Edward Lin, University of Maryland28 Reachability Treet1p1t2p3p2(1, 0, 0)(1,1,0)(0,1,1)(1,2,0)(0,2,1)(0, 0, 1)(1,3,0)(0,3,1)(0,1,1)t2t1t3t1t2t3t1t2t 3(0,0,1)(1,4,0)t1(0,2,1)t2(0,4,1)t2(0,3, 1)t3t3 Edward Lin, University of Maryland29 Coverability Tree (1)t1p1t2p3p2t3(1,0,0)new m1 = (1, ,0)m2 = (0,1,1) newStep 1:t1t2 Step 2 (m1):(1,0,0) newnew m1 = (1, ,0)m2 = (0,1,1) newt1t2 Initialization:M0 = (1,0,0) newm1 = (1,1,0) >= (1,0,0)newold (1, ,0)t1new m3=(0, ,1)t2 Edward Lin, University of Maryland30 Coverability Tree (2)t1p1t2p3p2t3 Step 3 (m3):(1,0,0) newnew m1=(1, ,0)m2=(0,1,1) newt1t2old (1, ,0)t1m3=(0, ,1) newt2old (0, ,1)(1,0,0) newnew m1=(1, ,0)m2=(0,1,1) newt1t2new (1, ,0)t1m3=(0, ,1) newt2old (0, ,1)Step 4 (m2):m4 = (0,0,1) newt3t3t3 Edward Lin, University of Maryland31 Coverability Tree (3)(1,0,0) newm1=(1, ,0)newm2=(0,1,1)newt1t2(1, ,0)oldt1m3=(0, ,1)newt2old (0, ,1)Step 5 (m4).

8 Coverability Treem4 = (0,0,1)terminate(1, 0, 0)(1,1,0)(0,1,1)(1,2,0)(0,2,1)(0, 0, 1)(1,3,0)(0,3,1)(0,1,1)t1t2t3t1t2t3t1t2( 0,0,1)(1,4,0)t1(0,2,1)t2(0,4,1)t2(0,3,1) t3t3 Reachability Treet3t3 Edward Lin, University of Maryland32 Linear Algebraic TechniquelI = p1 p2 p3loadingprocessingUnloadingp1t1p2t2p3tt t123100010001 lO = p1 p2 p3lM0 = (1, 0, 0)ttt123010001100 Incidence MatrixlA = O - I = p1 p2 p3ttt12311 001110 1 State Equation: M = M0 + A, where is a vector with s elements t3 Edward Lin, University of Maryland33 Linear Algebraic TechniqueloadingprocessingUnloadingp1t1p 2t2p3 11 001110 1[]100[]100+=[]010 11 001110 1[]100[]110+=[]001 11 001110 1[]100[]111+=[]100t1 firedt1, t2 firedt1 t2 t3 firedt3 Edward Lin, University of Maryland34T-InvariantT-Invariant.

9 YA = 0, where Y is a s element vector Y is the number of transition firings -y1 + y3 = 0 y1 - y2 = 0 y2 - y3 = 0 11 001110 1= 0y1 = y2 = y3minimum t-invariant = (1, 1, 1)M0 []yy y12 3yq M0 Edward Lin, University of Maryland35T-InvariantloadingprocessingUn loadingp1t1p2t2p3(1,0,0)(0,1,0)(0,0,1)(1 ,0,0)(1,0,0) ---------------> (1,0,0)(1,1,1)t3 Edward Lin, University of Maryland36P-InvariantP-Invariant: AXT = 0, where X is a n element vector, X is the weight of each place -x1 + x2 = 0 -x2 + x3 = 0x1 - x3 = 0 11 001110 1= 0xxx123 x1 = x2 = x3minimum p-invariant = (1, 1, 1)The quantity S = x1 M(p1) + x2 M(p2) + x3 M(p3)Edward Lin, University of Maryland37P-InvariantloadingprocessingUn loadingp1t1p2t2p3(1,0,0)(0,1,0)(0,0,1)(1 ,0,0)The quantity S = x1 M(p1) + x2 M(p2) + x3 M(p3)1 = 1 M(p1) + 1 M(p2) + 1 M(p3)

10 T3 Edward Lin, University of Maryland38 SimulationlDiscrete event simulationlSame model for simulation and analysislNeed rules to resolve conflictslUseful for validation and visualizationEdward Lin, University of Maryland39 Extensions of Petri NetslEvent Graph (marked graph, decision-free) Each place has exactly one input transition and exactly one output transitionlDeterministic Timed Petri Nets Deterministic time delays with transitionslStochastic Timed Petri Nets Stochastic ti