eli5: What is a petri net?

182 views

eli5: What is a petri net?

In: 2

Anonymous 0 Comments

First let’s talk about (finite) automata.

An automaton is composed of **states**, for example for a traffic light on the street, it has three states RED, YELLOW, and GREEN; and of **transitions**, for example RED -> GREEN, GREEN -> YELLOW, and YELLOW -> RED.

The automaton describe the system: if you look at a traffic light an see that it is red, then you know that it is in the RED **state**, and there is only one **transition** going out of RED, it is RED -> GREEN, so you know that the traffic light is about to turn green.

[Well, to completely represent a traffic light, you’ll need additional information like the timing, and you can have all of that in an automaton, but I’m simplifying here]

So now, what if you have 2 traffic lights? There are two approaches:

1. The first approach is to increase the number of states, and have now (RED,RED), (RED,YELLOW), (RED,GREEN), (YELLOW,RED), etc and then have all the transitions (RED,RED) -> (RED,GREEN), etc. This approach works well but your automaton can easily get very big.

2. The second approach is to keep only 6 states RED_1,YELLOW_1,GREEN_1 and RED_2,YELLOW_2,GREEN_2, but have 2 **tokens** going through. That’s the basis of **Petri Nets**, instead of being in a single state at once, you can have multiple tokens going through your automaton.

But then, now that you have tokens, you can do more than just having simple transitions going from one state to another. In Petri Nets, you can have transitions that **merge two tokens in one**, or transitions that **split a token in two**.

For example, let’s take a simple coffee machine:

* The states in our simple example will be COFFEE_STOCK (which starts with 5 tokens), USER_ASKING_COFFEE (starts with 0 tokens), USER_RECEIVING_COFFEE (starts with 0 tokens), and NO_USER (starts with 1 token).

* The transitions will be NO_USER -> USER_ASKING_COFFEE when someone arrives at the coffee machine and wants some coffee. (COFFEE_STOCK + USER_ASKING_COFFEE) -> USER_RECEIVING_COFFEE for the machine serving some coffee, note that it merges one token from the stock with the user token, so if there is no longer any stock then the machine won’t be able to continue and serve coffee. USER_RECEIVING_COFFEE -> NO_USER when the person leaves with their coffee.

[Obviously, this is a gain a simplification as we have currently no way of recharging the coffee machine in this example so after 5 coffee it can never give any coffee ever again]