# Modeling and Analysis of Connected Traffic Intersections Based on Modified Binary Petri Nets

Authors: Omar Yaqub; Lingxi Li
Journal: International Journal of Vehicular Technology
 (2013)

---

## Abstract

We propose an approach for the modeling and analysis of two connected traffic intersections based on Petri nets (PNs). We first use a PN to model an isolated four-way signalized intersection; then we extend it to model two successive signalized intersections. We find that this model has unbounded places, which in turn results in some confliction problems. Hence, we introduce the concept of modified binary petri nets (MBPNs) to overcome the limitation and resolve the confliction problem when we design our model and its controller. This MBPN model is a powerful tool and can be useful for the modeling and analysis of many other traffic applications.


---

## Body

## 1. Introduction

As a powerful tool that consists of a combined graphical and mathematical representation, Petri nets have been used for the modeling, control, and analysis in different applications including sensor networks [1], power systems [2, 3], manufacturing systems [4–7], and many other practical systems. In traffic management problems, Petri nets have been used to model the traffic network in different ways for a variety of purposes. It can be concluded that when vehicle flow has been studied, hybrid Petri nets (HPNs) are a suitable modeling tool because they consist of both continuous and discrete nodes that work together to reflect the dynamics of the overall traffic system. Continuous nodes are suitable for modeling continuous events such as vehicle flow while discrete nodes are used to represent discrete events such as phase change in traffic signal and enabling/disabling vehicle movement because of occurrences of emergent events such as accidents and the blocking of the road. In [8], a general HPN model for transportation system was developed. Traffic flow was described by continuous nodes and the events that affect the traffic dynamics were modeled through discrete nodes. In [9], a simple HPN was used to model the intersection of two one-way streets, while in [10] a continuous Petri net was used to model a nonsignalized intersection, and then were added discrete nodes that are essential to represent a four-way intersection with two-phase traffic light through an HPN. In [11], the authors developed an HPN model to improve the performance of special and emergency vehicles.In the aforementioned works on traffic network modeling and management, HPN models were adopted because they are more accurate to reflect the dynamics of the entire traffic network for certain applications. On the other hand, however, in some traffic network applications such as control and monitoring, only events are critical to be studied and analyzed. For these problems, discrete Petri nets as well as timed/colored Petri nets are the suitable modeling tools. In [12], the authors proposed a discrete Petri net model which describes the phase change of traffic light signal for an intersection. In [13], a discrete Petri net model for a small transportation system was developed to estimate the optimal travel route between the starting and destination points. In [14, 15], timed colored Petri nets were used to represent urban traffic light control systems and then a real-world supervisor of the modeled urban traffic light system was implemented. Deterministic and stochastic Petri nets were used in [16] to model railroad level crossing traffic control systems to identify and avoid the critical scenarios.Compared with HPN models, discrete Petri nets are much simpler in terms of modeling and analysis. Therefore, for applications that do not need to capture the detailed vehicle flow dynamics, discrete Petri nets are a good tool to use.  In this paper, we introduce a discrete Petri net model for two connected traffic intersections. This model is based mainly on higher-level event occurrences without considering details of lower-level continuous dynamics. For instance, it can tell us that the event of vehicles crossing an intersection during a specific traffic light phase from a specific entrance to a known destination has occurred, but without considering information such as how many vehicles have crossed the intersection or how much time this process has taken. The advantage is that this model can give us an abstract view of the event correlations about the entire complex traffic network. Therefore, it can be used to analyze the effect of the occurrence of a specific event at a specific node on other parts of the network. In addition, we propose a modified binary Petri net (MBPN) model that is suitable for the analysis and control of these connected intersections.The contributions of this paper are two-fold: (1) we develop a comprehensive discrete Petri net model for two connected intersections by considering both signal phase change and vehicle flow directions; and (2) we propose a modified binary Petri net model to resolve the potential confliction problem for the two-intersection PN.This paper is organized as follows. In Section2, the basics of discrete Petri nets are briefly reviewed. A discrete Petri net model for a single signalized intersection is described in detail in Section 3. In Section 4, two connected intersections are modeled by extending the single-intersection model and are analyzed in detail. In Section 5, we propose the modified binary Petri net for the purpose of monitoring and control. Conclusions and directions for future work are presented in Section 6.


## 2. Petri Nets Basics

In this section, the basic principles of (discrete) Petri net are briefly reviewed. The reader can find more details about Petri nets and their extensions in [17–19].A Petri net is a bipartite directed graph comprising of two types of nodes, calledplaces (drawn as circles) and transitions (drawn as bars), which are connected through arrows that are called arcs. A Petri net is called a marked Petri net if a nonnegative integer number of tokens (drawn as black dots) is assigned to each place.Thus, a marked Petri net is defined as(1)PN=(P,T,B-,B+,m0),
where P={p1,p2,…,pn} is a finite set of places consisting of n elements; T={t1,t2,…,tm} is a finite set of transitions consisting of m elements; B- is the input incident matrix, which captures the arc weights directed from places to transitions. For instance, B-(pi,tj) is the weight of the arc directed from the place pi to transition tj. If there is no such arc, then the element of B-(pi,tj) is set to be zero; B+ is the output incident matrix, which captures the arc weights directed from transitions to places. For instance, B+(pi,tj) is the weight of the arc directed from the transition tj to place pi. If there is no such arc, then the element of B+(pi,tj) is set to be zero; m0 is the initial marking (denotes the number of tokens in each place initially) of the Petri net.It is not difficult to see that the sizes of the input and output incident matrices aren×m.A transition is said to be enabled if each of its input places contains a number of tokens that is greater than or equal to the arc weight that connects that specific place to the transition. In other words, transitiontj is enabled at a specific marking mk if and only if
(2)mk(pi)≥B-(pi,tj),
for all input places pi to transition tj. The inequality is taken elementwise.   An enabled transition may fire. The firing of a transition is the mechanism of removing a specific number of tokens from each input place (which is equal to the weight of the arc directing from this specific input place to the transition) and depositing a specific number of tokens to each output place (which is equal to the weight of the arc directing the transition to this specific output place).LetS be a transition firing sequence; then we define s as the firing vector of sequence S in such a way that each element sj in s captures the number of times that transition tj fires in S. For instance, if S=t2t3t1t1 and the Petri net has four transitions, then s=[2110]T. For a given Petri net marked with a specific marking mk, we say that the firing sequence S  is enabled if and only if a specific marking mk′ exists in such a way that when the firing sequence S is applied to the given Petri net marked with mk it will produce the marking mk′. Mathematically, transition firings can be captured by state equation given as follows:
(3)mk′=mk+B·s,
where B is the incident matrix of the Petri net and it is defined as B=B+-B- (B- is the input incident matrix and B+ is the output incident matrix of the Petri net as defined earlier).Example 1.
Consider the Petri net shown in Figure1. The net consists of four places: p1, p2, p3, and p4 and four transitions: t1, t2, t3, and t4. Since p1 is the only place that has a token, the initial marking is written as m0=[1000]T. The input and output incident matrices (B-,B+) are given by
(4)B-=[1000010000100001],B+=[0001100010000110].
So the incident matrix B can be calculated as
(5)B=B+-B-=[-10011-10010-10011-1].
According to (2), it is not difficult to see that the only enabled transition is t1 at the initial marking. When t1 fires, one token is removed from place p1 and one token is added to p2 and p3, respectively, to result in the new marking m=[0110]T. Mathematically, the new marking can also be obtained by using (3), where mk is the initial marking m0, mk′ is the new marking, and the firing vector  s is given by [1000]T since we are looking for the result of firing t1 only once. Therefore, we have
(6)mk′=mk+B·s=[1000]+[-10011-10010-10011-1][1000]=[0110].Figure 1
A simple Petri net model.


## 3. Petri Net Model for a Single Intersection

### 3.1.   Structure of a Single Intersection

In Figure2, a four-bidirectional-road signalized intersection is shown with its accessible roads. Direction symbols {n,s,e,w} are used to define the four bidirectional roads. They represent the four directions north, south, east, and west, respectively. The set {Rwin,Rein,Rnin,Rsin,Rwout,Reout,Rnout,Rsout} represents the roads connecting to the intersection; the subset {Rwin,Rein,Rnin,Rsin} represents the incoming roads while the subset {Rwout,Reout,Rnout,Rsout} represents the outgoing roads.Figure 2
The structure of a single intersection.The Petri net model, which will be introduced in the following subsection, is designed based on the assumption that this intersection’s traffic light signals have four phases as a case of study as shown in Table1. However, note that the design concept can also be applied to other phase planes. In general, the number of phases for a four-bidirectional-signalized intersection is no more than eight, as shown in [12]. In particular, two- and six-phase plans [12, 20] are also applicable for such an intersection. Our PN model here can also be modified to account for two-phase and six-phase signalized traffic intersection. A phase is defined as an event of giving particular permissions to vehicles coming from specific directions to cross the physical area of the intersection towards specific destinations.Table 1
Four phases of the signalized intersection considered in this paper.
Phase
Enabled movements
1
2
3
4As shown in Table1, during Phase 1, vehicles flowing from east to south and from west to north are permitted to cross the intersection; during Phase 2, vehicles flowing from east to west (and north) and from west to east (and south) are permitted to cross the intersection; during Phase 3, vehicles flowing from north to east and from south to west are permitted to cross the intersection; and during Phase 4, vehicles flowing from north to south (and west) and from south to north (and east) are permitted to cross the intersection. It is not difficult to check that these signal phases do not conflict with each other and they comprise of a complete signal cycle.


### 3.2.   Petri Net Model of the Single Intersection

The discrete Petri net model for the four-bidirectional road (shown in Figure2) is depicted in Figure 3. The overall PN model is divided into 13 sub-PNs (modules), where each one is bounded by a dashed rectangular box. Eight of these modules represent the movement of vehicles while entering and crossing the intersection from left (Nlin, Slin, Elin, and Wlin) or from forward/right (Nfin, Sfin, Efin, and Wfin). On the other hand, the four sub-PNs (Nout, Sout, Eout, and Wout) represent movement of vehicles while leaving the intersection toward the four directions. Finally, the sub-PN (T) models the phase change of the traffic light signal.Figure 3
Petri net model for the single signalized intersection shown in Figure2.The sub-PN (T) consists mainly of four places (pp1, pp2, pp3, and pp4) and four transitions (tp1s, tp2s, tp3s, and tp4s) that represent the four different phases mentioned in Table 1. The other nodes in module  T exist only to make sure that the model offers a safe operation (no directional conflicts between vehicles while crossing the intersection). Having a token at the place ppk indicates that the kth phase is taking place while losing this token means the ending of this phase. Furthermore, firing of transition tpks reflects the starting of the kth phase. It is easy to note that the condition pp1+pp2+pp3+pp4=1  has to be satisfied all the time.Events related to vehicle movement through the intersection are described by other 12 sub-PNs; eight of them are used to model vehicles entering and crossing the intersection asIjin where I takes the notations (N, S, E, and W) and j takes either l (left) or f (forward and right). The subnet Ijin consists of five places and four transitions; having a token in place pijin implies that vehicles are entering the intersection from the ith incoming direction with the intention to take the direction of j. Similarly, having a token in place pijq indicates the event that there is a queue of vehicles waiting in the incoming direction i with the intention to cross the intersection directed j (left or forward/right). Furthermore, a token at the places pijp means that the permission is given to those vehicles in the queue to cross the intersection while a token existing in pijc represents the event that those vehicles are crossing the intersection.Finally, the other four sub-PNs (Nout, Sout, Eout, and Wout) are quite simple. Each of them consists of a place piout and a transition tiout. A token in the aforementioned places describes the event that vehicles are leaving the intersection at the outgoing direction i.


### 3.3. Dynamics of the Petri Net Model

The state evolution of the PN model shown in Figure3 is performed based mainly on the state equation given in (3) and on the assumption that whenever a transition is enabled it fires immediately. The fact that permission is given to vehicles entering the intersection from a specific direction towards a specific destination during a specific phase results in the consideration that this permission has to be canceled at the end of this phase no matter some vehicles cross the intersection or not. Consequently, eight conflicts might appear in the model between each coupled transitions (tijp,tijs). The proposed algorithm specifies a priority execution for each conflict. If the initial marking of the Petri net model is the one given in Figure 3, the only enabled transition is tp1s. Therefore, it fires immediately through removing a token from each input place to this transition (pp4,pp42) and adding a token to each output place of this transition (pp1, pp11, pwlp, and pelp). It simply means that the first phase starts (indicated via the token in place pp1in) and permission is given to vehicles to cross the intersection.To clarify the firing sequence, let us stick only to those vehicles that enter from west towards north. As shown in Figure3, initially a token exists in place pwlq, so vehicles are waiting in the west entrances to take left with the intersection. However, a conflict appears at this step between transitions (twlp,twls) since both of them are enabled and only one token is marked in their common input place pwlp. At this point, the algorithm will give the priority to transition telp, whose firing will result in removing tokens from the permission and queuing places (pwlp,pwlq) and adding a token to the place pwlc, which indicates that the event of vehicles crossing the intersection from west to north is taking place simultaneously with the occurrence of the event that vehicles are crossing the intersection from east to south.In the following step, three transitions are fired together, named (twlc, telc, and tp2s). Firing the transitions twlc, telc implies that vehicles are leaving the intersection towards south and north (through removing tokens from pwlc, pelc) and adding a token to each one of psout, pnout indicates the event that vehicles are leaving intersection towards south and north directions. Simultaneously, in the sub-PN, the transition tp2s fires will indicate the starting of the second phase.The necessity of having the sink transitiontwls is to make sure that vehicles cross the intersection safely; if we assume that no vehicles are waiting in the queue to cross the intersection from west to north during the first phase, the permission will still be available through the existence of a token in pwlp, which will lead to unsafe operation that vehicles coming from the west cross the intersection even after the ending of the first phase. Therefore, the role of the sink transition twls is to take away the permission if it has not been used during the first phase.We developed an algorithm to identify the enabled transitions at each time step and fire the enabled transitions immediately based on the state equation and the aforementioned priority rule. Given the initial marking, input and output incident matrices, the algorithm will firstly construct the column matrixA (which initially is equal to the initial marking); then it will calculate the subsequent markings by state equation given in (3) and compare them with the existing marking; if it is not equal to any of them, it will be saved as a new column in matrix A and will be used to find the subsequent markings. Otherwise, if the newly calculated marking is equal to any previous ones (any column in A), the algorithm will stop. Matrix A at this point consists of all possible markings in their order of occurrences.  The block diagram of the algorithm (Algorithm 1) for capturing the state evolution of the PN is shown in Figure 4.Figure 4
Block diagram of Algorithm 1 for capturing the state evolution of the Petri net shown in Figure3.In Table2, we capture the state (marking) evolution of the Petri net model shown in Figure 3 related to each step of transition firing. Note that this state evolution is partial since we only show the number of tokens in some important places. The first column in the table represents the initial marking of the Petri net.  When a specific event occurs at a specific firing step, it will be represented through the value “1” in the table. Similarly, the change of value from “1” to “0” in a specific table cell implies the ending of that specific event. Since the model consists of 56 places, it is not possible to include all of them in the table. We focus only on the places with essential meanings. It is to be noted that at each firing step, one and only one of the four phase places (pp1, pp2, pp3, and pp4) will take the value “1” (which is expected as previously mentioned). It is also not difficult to notice that during the 10th step, the current marking goes back to the second generated marking in Table 2, which indicates that the proposed PN model is live and reversible.Table 2
Partial state evolution of the single-intersection Petri net model shown in Figure3.
m
0
1st
2nd
3rd
4th
5th
6th
7th
8th
9th
10th
p
p
1
0
1
1
0
0
0
0
0
0
1
1
p
p
2
0
0
0
1
1
0
0
0
0
0
0
p
p
3
0
0
0
0
0
1
1
0
0
0
0
p
p
4
1
0
0
0
0
0
0
1
1
0
0
p
i
j
in
1
1
1
1
1
1
1
1
1
1
1
p
wl
c
,
p
el
c
0
0
1
0
0
0
0
0
0
0
1
p
wf
c
,
p
ef
c
0
0
0
0
1
0
0
0
0
0
0
p
nl
c
,
p
sl
c
0
0
0
0
0
0
1
0
0
0
0
p
nf
c
,
p
sf
c
0
0
0
0
0
0
0
0
1
0
0
p
w
out
0
0
0
0
0
1
0
1
0
1
0
p
e
out
0
0
0
0
0
1
0
1
0
1
0
p
n
out
0
0
0
1
0
1
0
0
0
1
0
p
s
out
0
0
0
1
0
1
0
0
0
1
0If we use a different initial marking, such as a marking that represents the case where no vehicles enter the intersection from north, south, and east, the value “1” will never exist at the placepwout during any firing step, which means that the event vehicles leave the intersection towards west will not take place. This is an expected logical result to avoid the conflicts of events.


## 3.1.   Structure of a Single Intersection

In Figure2, a four-bidirectional-road signalized intersection is shown with its accessible roads. Direction symbols {n,s,e,w} are used to define the four bidirectional roads. They represent the four directions north, south, east, and west, respectively. The set {Rwin,Rein,Rnin,Rsin,Rwout,Reout,Rnout,Rsout} represents the roads connecting to the intersection; the subset {Rwin,Rein,Rnin,Rsin} represents the incoming roads while the subset {Rwout,Reout,Rnout,Rsout} represents the outgoing roads.Figure 2
The structure of a single intersection.The Petri net model, which will be introduced in the following subsection, is designed based on the assumption that this intersection’s traffic light signals have four phases as a case of study as shown in Table1. However, note that the design concept can also be applied to other phase planes. In general, the number of phases for a four-bidirectional-signalized intersection is no more than eight, as shown in [12]. In particular, two- and six-phase plans [12, 20] are also applicable for such an intersection. Our PN model here can also be modified to account for two-phase and six-phase signalized traffic intersection. A phase is defined as an event of giving particular permissions to vehicles coming from specific directions to cross the physical area of the intersection towards specific destinations.Table 1
Four phases of the signalized intersection considered in this paper.
Phase
Enabled movements
1
2
3
4As shown in Table1, during Phase 1, vehicles flowing from east to south and from west to north are permitted to cross the intersection; during Phase 2, vehicles flowing from east to west (and north) and from west to east (and south) are permitted to cross the intersection; during Phase 3, vehicles flowing from north to east and from south to west are permitted to cross the intersection; and during Phase 4, vehicles flowing from north to south (and west) and from south to north (and east) are permitted to cross the intersection. It is not difficult to check that these signal phases do not conflict with each other and they comprise of a complete signal cycle.


## 3.2.   Petri Net Model of the Single Intersection

The discrete Petri net model for the four-bidirectional road (shown in Figure2) is depicted in Figure 3. The overall PN model is divided into 13 sub-PNs (modules), where each one is bounded by a dashed rectangular box. Eight of these modules represent the movement of vehicles while entering and crossing the intersection from left (Nlin, Slin, Elin, and Wlin) or from forward/right (Nfin, Sfin, Efin, and Wfin). On the other hand, the four sub-PNs (Nout, Sout, Eout, and Wout) represent movement of vehicles while leaving the intersection toward the four directions. Finally, the sub-PN (T) models the phase change of the traffic light signal.Figure 3
Petri net model for the single signalized intersection shown in Figure2.The sub-PN (T) consists mainly of four places (pp1, pp2, pp3, and pp4) and four transitions (tp1s, tp2s, tp3s, and tp4s) that represent the four different phases mentioned in Table 1. The other nodes in module  T exist only to make sure that the model offers a safe operation (no directional conflicts between vehicles while crossing the intersection). Having a token at the place ppk indicates that the kth phase is taking place while losing this token means the ending of this phase. Furthermore, firing of transition tpks reflects the starting of the kth phase. It is easy to note that the condition pp1+pp2+pp3+pp4=1  has to be satisfied all the time.Events related to vehicle movement through the intersection are described by other 12 sub-PNs; eight of them are used to model vehicles entering and crossing the intersection asIjin where I takes the notations (N, S, E, and W) and j takes either l (left) or f (forward and right). The subnet Ijin consists of five places and four transitions; having a token in place pijin implies that vehicles are entering the intersection from the ith incoming direction with the intention to take the direction of j. Similarly, having a token in place pijq indicates the event that there is a queue of vehicles waiting in the incoming direction i with the intention to cross the intersection directed j (left or forward/right). Furthermore, a token at the places pijp means that the permission is given to those vehicles in the queue to cross the intersection while a token existing in pijc represents the event that those vehicles are crossing the intersection.Finally, the other four sub-PNs (Nout, Sout, Eout, and Wout) are quite simple. Each of them consists of a place piout and a transition tiout. A token in the aforementioned places describes the event that vehicles are leaving the intersection at the outgoing direction i.


## 3.3. Dynamics of the Petri Net Model

The state evolution of the PN model shown in Figure3 is performed based mainly on the state equation given in (3) and on the assumption that whenever a transition is enabled it fires immediately. The fact that permission is given to vehicles entering the intersection from a specific direction towards a specific destination during a specific phase results in the consideration that this permission has to be canceled at the end of this phase no matter some vehicles cross the intersection or not. Consequently, eight conflicts might appear in the model between each coupled transitions (tijp,tijs). The proposed algorithm specifies a priority execution for each conflict. If the initial marking of the Petri net model is the one given in Figure 3, the only enabled transition is tp1s. Therefore, it fires immediately through removing a token from each input place to this transition (pp4,pp42) and adding a token to each output place of this transition (pp1, pp11, pwlp, and pelp). It simply means that the first phase starts (indicated via the token in place pp1in) and permission is given to vehicles to cross the intersection.To clarify the firing sequence, let us stick only to those vehicles that enter from west towards north. As shown in Figure3, initially a token exists in place pwlq, so vehicles are waiting in the west entrances to take left with the intersection. However, a conflict appears at this step between transitions (twlp,twls) since both of them are enabled and only one token is marked in their common input place pwlp. At this point, the algorithm will give the priority to transition telp, whose firing will result in removing tokens from the permission and queuing places (pwlp,pwlq) and adding a token to the place pwlc, which indicates that the event of vehicles crossing the intersection from west to north is taking place simultaneously with the occurrence of the event that vehicles are crossing the intersection from east to south.In the following step, three transitions are fired together, named (twlc, telc, and tp2s). Firing the transitions twlc, telc implies that vehicles are leaving the intersection towards south and north (through removing tokens from pwlc, pelc) and adding a token to each one of psout, pnout indicates the event that vehicles are leaving intersection towards south and north directions. Simultaneously, in the sub-PN, the transition tp2s fires will indicate the starting of the second phase.The necessity of having the sink transitiontwls is to make sure that vehicles cross the intersection safely; if we assume that no vehicles are waiting in the queue to cross the intersection from west to north during the first phase, the permission will still be available through the existence of a token in pwlp, which will lead to unsafe operation that vehicles coming from the west cross the intersection even after the ending of the first phase. Therefore, the role of the sink transition twls is to take away the permission if it has not been used during the first phase.We developed an algorithm to identify the enabled transitions at each time step and fire the enabled transitions immediately based on the state equation and the aforementioned priority rule. Given the initial marking, input and output incident matrices, the algorithm will firstly construct the column matrixA (which initially is equal to the initial marking); then it will calculate the subsequent markings by state equation given in (3) and compare them with the existing marking; if it is not equal to any of them, it will be saved as a new column in matrix A and will be used to find the subsequent markings. Otherwise, if the newly calculated marking is equal to any previous ones (any column in A), the algorithm will stop. Matrix A at this point consists of all possible markings in their order of occurrences.  The block diagram of the algorithm (Algorithm 1) for capturing the state evolution of the PN is shown in Figure 4.Figure 4
Block diagram of Algorithm 1 for capturing the state evolution of the Petri net shown in Figure3.In Table2, we capture the state (marking) evolution of the Petri net model shown in Figure 3 related to each step of transition firing. Note that this state evolution is partial since we only show the number of tokens in some important places. The first column in the table represents the initial marking of the Petri net.  When a specific event occurs at a specific firing step, it will be represented through the value “1” in the table. Similarly, the change of value from “1” to “0” in a specific table cell implies the ending of that specific event. Since the model consists of 56 places, it is not possible to include all of them in the table. We focus only on the places with essential meanings. It is to be noted that at each firing step, one and only one of the four phase places (pp1, pp2, pp3, and pp4) will take the value “1” (which is expected as previously mentioned). It is also not difficult to notice that during the 10th step, the current marking goes back to the second generated marking in Table 2, which indicates that the proposed PN model is live and reversible.Table 2
Partial state evolution of the single-intersection Petri net model shown in Figure3.
m
0
1st
2nd
3rd
4th
5th
6th
7th
8th
9th
10th
p
p
1
0
1
1
0
0
0
0
0
0
1
1
p
p
2
0
0
0
1
1
0
0
0
0
0
0
p
p
3
0
0
0
0
0
1
1
0
0
0
0
p
p
4
1
0
0
0
0
0
0
1
1
0
0
p
i
j
in
1
1
1
1
1
1
1
1
1
1
1
p
wl
c
,
p
el
c
0
0
1
0
0
0
0
0
0
0
1
p
wf
c
,
p
ef
c
0
0
0
0
1
0
0
0
0
0
0
p
nl
c
,
p
sl
c
0
0
0
0
0
0
1
0
0
0
0
p
nf
c
,
p
sf
c
0
0
0
0
0
0
0
0
1
0
0
p
w
out
0
0
0
0
0
1
0
1
0
1
0
p
e
out
0
0
0
0
0
1
0
1
0
1
0
p
n
out
0
0
0
1
0
1
0
0
0
1
0
p
s
out
0
0
0
1
0
1
0
0
0
1
0If we use a different initial marking, such as a marking that represents the case where no vehicles enter the intersection from north, south, and east, the value “1” will never exist at the placepwout during any firing step, which means that the event vehicles leave the intersection towards west will not take place. This is an expected logical result to avoid the conflicts of events.


## 4. Petri Net Model for Two Connected Intersections

In this section, we generalize the PN model obtained from the previous section to two connected intersections. The structure of two connected intersections is shown in Figure5; if we call the intersection on the left side Intersection-1 and the intersection on the right side Intersection-2, then we can say that the east output of Intersection-1 is the west input to Intersection-2 while the west output of Intersection-2 is the east input to Intersection-1.Figure 5
The structure of two connected intersections.For this case, the Petri net model for traffic network shown in Figure5 consists of two-single intersection PN models connected to each other. However, minor modifications are done for each model. For Intersection-1 model, the arcs connecting telin to pelin and tefin to pefin have been removed; while for Intersection-2 model, arcs connecting twlin to pwlin and twfin to pwfin have been removed. To distinguish between the PN nodes belonging to each intersection, we added (2) as the subscript for each node symbol in Intersection-1, similarly adding (3) for Intersection-2. The two-single intersection models are connected to each other through their east and west inputs/outputs nodes, the PN model for the connection between two intersections is shown in Figure 6.Figure 6
Petri net model for the connections between two intersections.During the event that vehicles are leavingIntersection-1, a token existing at pe(1)out will result in the firing of transition te(1)out, which removes the token from pe(1)out and adds a token to both places pwf(2)in and pwl(2)in that represents the occurrence of the event that vehicles are entering Intersection-2 from the west.  However, this step does not perform very smoothly when we execute the two-intersection model using Algorithm 1.The case is that, during one-phase cycle (the four phases took place once successively), transitionste(1)out and tw(2)out fire three times because places pe(1)out and pw(2)out are charged three times per cycle since there are vehicles leaving Intersection-1 east directed and Intersection-2 west directed during three phases in a cycle. On the other hand, the four places, pef(1)in, pel(1)in, pwf(2)in, and pwl(2)in, gain three tokens each per cycle and release only one of these tokens since the transitions downstream fire only once per cycle. It is obvious that this firing mechanism will lead the Petri net to be unbounded. Physically, the model will not be considered as a good representation for event occurrences because at some point if no vehicle enters the network through one of the three entrance of Intersection-1: west, north, and south, there will be still vehicles traveling from Intersection-1 to Intersection-2 which is not a real case. That is because places pef(1)in, pel(1)in will have tokens to feed the net of Intersection-2. The same case of unreal representation will exist for vehicles traveling from Intersection-2 towards Intersection-1.To tackle this modeling issue, we have tried several approaches. Firstly, a Petri net controller was designed based on [21] to keep the number of tokens in each of the four places not exceeding one. This controller worked for these four places but it transferred the unbounded problem to the upstream places pe(1)out and pw(2)out. Adding another controller places to control these two nodes will not solve the problem because it causes conflicts which stop the execution of Algorithm 1 when it is used for the new model (with the controller). Designing a controller for the six places in one step will cause similar problem. Therefore, we propose the concept of the modified binary Petri net (MBPN), which will be presented in detail in the next section.


## 5.  Modified Binary Petri Nets

### 5.1.   Introduction to Modified Binary Petri Nets

As it can be seen from the previous discussions, we use PNs to determine whether an event has occurred or not based on the occurrence of other events. Modeling in such a way can be easily done through representing the occurrence of a specific event by associating a token in a specified place that describes this event. However, modeling in this traditional way will lead to problems in our models as discussed above.Thus, we propose the concept of the modified binary Petri net (MBPN). The idea is to follow the traditional Petri net firing mechanisms, but with a restriction that no places can be marked with more than one token. Thus, the MBPN can be defined as follows.(i)
The weights of all arcs in the MBPN are ones, which indicates that the net is ordinary and all elements in the input and output incidents matrices can only be zeros or ones.(ii)
The initial marking of the MBPN can only be zero or one for each place.(iii)
State evolution from one marking to another is performed through the following two steps:
(1)
we calculate markingmk′ according to traditional state equation of Petri nets:
(7)mk′=mk+B·s;(2)
we update the marking in places according to the number of tokens as follows:(8)mk′(p)={0for  placespsuch  thatmk′(p)=0,1for  placespsuch  thatmk′(p)≥1.Based on this definition, it is easy to see that for MBPN we have the following:(i)
elements of incident matrices take only three values −1, 0, or 1;(ii)
any modified binary Petri net is bounded since the number of states is less than or equal to2n, where n is the number of places.To illustrate the differences between the traditional PN and the MBPN, we can use the example provided in Figure 1 for illustration. If Algorithm 1 is applied for traditional PN, the marking evolution will be given by
(9)[1000]→t1[0110]→t2,t3[0002]→t4[1001]→t1,t4[1110]→t1,t2,t3[0112]→t2,t3,t4[1003]→t1,t4[1112]→t1,t2,t3,t4[1113]→t1,t2,t3,t4[1114]⋯[011r-1]→t1,t2,t3,t4[111r]→t1,t2,t3,t4[111r+1]⋯.
As it is shown above, the PN is unbounded due to place p4, in which the number of tokens will keep increasing after the marking [1112]T.Now we consider the MBPN. It is not difficult to see that the marking evolution is given by(10)[1000]→t1[0110]→t2,t3[0001]→t4[1000].
Thus, MBPN has bounded markings and avoids the potential problems in creating extra tokens for our connected traffic intersection model. In general, for traffic applications that can be represented through binary-state nodes (0 or 1), MBPN is a suitable modeling tool and can guarantee the smooth representation for event occurrences in these applications.


### 5.2.   Using MBPN Firing Mechanism for Studying the Two Connected Intersections

Now we investigate the PN model shown in Figure6. We use Algorithm 1 with a small modification that takes into account (8) mentioned above by MBPN. The algorithm performed 15 steps before it stopped due to the condition of having repeated markings. Because of the size of the PN model (P=112, T=88), we do not show markings for all places in the net. Instead, in Table 3, we show the markings of the places which represent the connections between two intersections. It is easy to note that the MBPN framework resolves the issue of unbounded states and is a more realistic tool for the modeling and analysis of certain traffic applications other than traditional PNs.Table 3
A partial set of marking evolution of MBPN model for two connected intersections.
m
0
1st
2nd
3rd
4th
5th
6th
7th
8th
9th
10th
11th
12th
13th
14th
15th
p
p
1
(
1
)
,
p
p
1
(
2
)
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
p
p
2
(
1
)
,
p
p
2
(
2
)
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
p
p
3
(
1
)
,
p
p
3
(
2
)
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
p
p
4
(
1
)
,
p
p
4
(
2
)
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
p
e
(
1
)
out
0
0
0
0
0
1
0
1
0
1
0
0
0
1
0
1
p
wl
(
2
)
in
0
0
0
0
0
0
1
0
1
1
1
0
0
0
1
1
p
wf
(
2
)
in
0
0
0
0
0
0
1
0
1
1
1
1
1
0
1
1
p
w
(
2
)
out
0
0
0
0
0
1
0
1
0
1
0
0
0
1
0
1
p
el
(
1
)
in
0
0
0
0
0
0
1
0
1
1
1
0
0
0
1
1
p
ef
(
1
)
i
n
0
0
0
0
0
0
1
0
1
1
1
1
1
0
1
1


### 5.3. Discussions on Potential Extensions to Traffic Networks

Starting from two connected intersections model, we can expand the approach proposed in this paper to study traffic network with much more complex dynamics. To see this implication, assuming that we have a complex traffic network consisting ofn intersections, we can derive its input incident matrix B- composed from input incident block matrices as:
(11)B-=[B1-0⋯0⋮B2-0⋮0⋮⋱000⋯Bn-],
where B1-,B2-,…,Bn- are the input incident matrices for intersections  I1,I2,…,In, respectively. The sizes of these block matrices may be different because they depend on the intersection specifications such as the number of incoming and outgoing roads connected to them and the number of phases applied to them. Note that the off-diagonal entries are zeros because intersections are connected through transitions to places.For the output incident matrix, the diagonal block matrices will be the output incident matricesB1+,B2+,…,Bn+ for the intersections I1,I2,…,In. Off-diagonal block matrices represent the connection between two intersections. For instance,  B1-2+ represents the connections from intersection I1 to intersection I2, B2-1+ represents the connection from I2 to I1, and so forth. The general form of the output incident matrix for the overall traffic network can be written as
(12)B+=[B1+B2-1+⋯Bn-1+B1-2+B2+⋯⋮⋮⋮⋱⋮B1-n+B2-n+⋯Bn+].
From the discussions above, we observe that we can easily expand the two-intersection model proposed in this paper to a large traffic network with much more intersections. In addition, the MBPN model proposed can guarantee the boundedness of places in the net; thus, it is suitable for capturing the event occurrences of the overall traffic network.


## 5.1.   Introduction to Modified Binary Petri Nets

As it can be seen from the previous discussions, we use PNs to determine whether an event has occurred or not based on the occurrence of other events. Modeling in such a way can be easily done through representing the occurrence of a specific event by associating a token in a specified place that describes this event. However, modeling in this traditional way will lead to problems in our models as discussed above.Thus, we propose the concept of the modified binary Petri net (MBPN). The idea is to follow the traditional Petri net firing mechanisms, but with a restriction that no places can be marked with more than one token. Thus, the MBPN can be defined as follows.(i)
The weights of all arcs in the MBPN are ones, which indicates that the net is ordinary and all elements in the input and output incidents matrices can only be zeros or ones.(ii)
The initial marking of the MBPN can only be zero or one for each place.(iii)
State evolution from one marking to another is performed through the following two steps:
(1)
we calculate markingmk′ according to traditional state equation of Petri nets:
(7)mk′=mk+B·s;(2)
we update the marking in places according to the number of tokens as follows:(8)mk′(p)={0for  placespsuch  thatmk′(p)=0,1for  placespsuch  thatmk′(p)≥1.Based on this definition, it is easy to see that for MBPN we have the following:(i)
elements of incident matrices take only three values −1, 0, or 1;(ii)
any modified binary Petri net is bounded since the number of states is less than or equal to2n, where n is the number of places.To illustrate the differences between the traditional PN and the MBPN, we can use the example provided in Figure 1 for illustration. If Algorithm 1 is applied for traditional PN, the marking evolution will be given by
(9)[1000]→t1[0110]→t2,t3[0002]→t4[1001]→t1,t4[1110]→t1,t2,t3[0112]→t2,t3,t4[1003]→t1,t4[1112]→t1,t2,t3,t4[1113]→t1,t2,t3,t4[1114]⋯[011r-1]→t1,t2,t3,t4[111r]→t1,t2,t3,t4[111r+1]⋯.
As it is shown above, the PN is unbounded due to place p4, in which the number of tokens will keep increasing after the marking [1112]T.Now we consider the MBPN. It is not difficult to see that the marking evolution is given by(10)[1000]→t1[0110]→t2,t3[0001]→t4[1000].
Thus, MBPN has bounded markings and avoids the potential problems in creating extra tokens for our connected traffic intersection model. In general, for traffic applications that can be represented through binary-state nodes (0 or 1), MBPN is a suitable modeling tool and can guarantee the smooth representation for event occurrences in these applications.


## 5.2.   Using MBPN Firing Mechanism for Studying the Two Connected Intersections

Now we investigate the PN model shown in Figure6. We use Algorithm 1 with a small modification that takes into account (8) mentioned above by MBPN. The algorithm performed 15 steps before it stopped due to the condition of having repeated markings. Because of the size of the PN model (P=112, T=88), we do not show markings for all places in the net. Instead, in Table 3, we show the markings of the places which represent the connections between two intersections. It is easy to note that the MBPN framework resolves the issue of unbounded states and is a more realistic tool for the modeling and analysis of certain traffic applications other than traditional PNs.Table 3
A partial set of marking evolution of MBPN model for two connected intersections.
m
0
1st
2nd
3rd
4th
5th
6th
7th
8th
9th
10th
11th
12th
13th
14th
15th
p
p
1
(
1
)
,
p
p
1
(
2
)
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
p
p
2
(
1
)
,
p
p
2
(
2
)
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
p
p
3
(
1
)
,
p
p
3
(
2
)
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
p
p
4
(
1
)
,
p
p
4
(
2
)
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
p
e
(
1
)
out
0
0
0
0
0
1
0
1
0
1
0
0
0
1
0
1
p
wl
(
2
)
in
0
0
0
0
0
0
1
0
1
1
1
0
0
0
1
1
p
wf
(
2
)
in
0
0
0
0
0
0
1
0
1
1
1
1
1
0
1
1
p
w
(
2
)
out
0
0
0
0
0
1
0
1
0
1
0
0
0
1
0
1
p
el
(
1
)
in
0
0
0
0
0
0
1
0
1
1
1
0
0
0
1
1
p
ef
(
1
)
i
n
0
0
0
0
0
0
1
0
1
1
1
1
1
0
1
1


## 5.3. Discussions on Potential Extensions to Traffic Networks

Starting from two connected intersections model, we can expand the approach proposed in this paper to study traffic network with much more complex dynamics. To see this implication, assuming that we have a complex traffic network consisting ofn intersections, we can derive its input incident matrix B- composed from input incident block matrices as:
(11)B-=[B1-0⋯0⋮B2-0⋮0⋮⋱000⋯Bn-],
where B1-,B2-,…,Bn- are the input incident matrices for intersections  I1,I2,…,In, respectively. The sizes of these block matrices may be different because they depend on the intersection specifications such as the number of incoming and outgoing roads connected to them and the number of phases applied to them. Note that the off-diagonal entries are zeros because intersections are connected through transitions to places.For the output incident matrix, the diagonal block matrices will be the output incident matricesB1+,B2+,…,Bn+ for the intersections I1,I2,…,In. Off-diagonal block matrices represent the connection between two intersections. For instance,  B1-2+ represents the connections from intersection I1 to intersection I2, B2-1+ represents the connection from I2 to I1, and so forth. The general form of the output incident matrix for the overall traffic network can be written as
(12)B+=[B1+B2-1+⋯Bn-1+B1-2+B2+⋯⋮⋮⋮⋱⋮B1-n+B2-n+⋯Bn+].
From the discussions above, we observe that we can easily expand the two-intersection model proposed in this paper to a large traffic network with much more intersections. In addition, the MBPN model proposed can guarantee the boundedness of places in the net; thus, it is suitable for capturing the event occurrences of the overall traffic network.


## 6. Conclusions and Discussions

In this paper, we developed a discrete Petri net model for a single traffic intersection and then extended it to represent a traffic network consisting of two connected intersections. This model was based on traditional Petri nets in order to analyze the effect of occurrence/nonoccurrence of specific events on other network nodes without considering the detailed dynamics. An algorithm was designed to capture transition firings based on the state equation and the priority assignment. We noticed that the traditional Petri net model for two connected intersections will lead to unbounded places in the model, which are not realistic for the monitoring and control. Thus, we introduced a modification to the traditional Petri nets to resolve this issue. We called this new type of Petri nets themodified binary Petri nets, which have a good representation for traffic network in terms of events occurrences and traffic dynamic correlations.One direction for our future work is to enhance the model with timing information by using timed transitions. By incorporating with time information, the new model will be suitable for event simulations in large traffic networks. Another interesting research direction is to identify a wider range of applications (e.g., routing, scheduling, etc.) of modified binary Petri nets in traffic systems and networks.



---

*Source: 192516-2013-04-04.xml*