This paper proposes an extension of Batches Petri Nets by a new de nition of the batch place called Bi-parts Batch place (BBplace). The ow-density equations that govern the dynamics of controllable batches inside a BB-place is now de ned by a triangular relation. To take into account controlled events, the behaviors of batches are discussed according to a variation of speeds and of maximum ows. The switching dynamics of controllable batches is de ned on three behaviors: free, congestion and decongestion behaviors. We also propose the computation of the instantaneous ring ow vector associated with continuous and batch transitions thanks to a resolution of a linear programming problem. An example of tra c road illustrates the novel extensions proposed in this paper.
For modeling, analysis and control of discrete event systems like manufacturing systems or tra c road systems, Petri nets are well utilized. Moreover, the discrete Petri net formalism has been extended to also encompass continuous and hybrid models [1], thus o ering formal techniques for expressing both fundamental discrete event and continuous time behaviors. Hybrid Petri nets combine the interest of the continuous Petri nets for the representation of the ows and those of the discrete Petri nets for the representation of the controls [4]. In order to integrate variable delays on continuous ows, basic hybrid Petri nets have been extended to Batches Petri Nets (BPNs) [2] [3]. BPNs introduce new kinds of places and transitions: the batch places and the batch transitions. A batch transition acts like a continuous transition while a batch place is de ned on the concept of batches. A batch consists in regrouping all elements of the ow with the same behavior. Moreover, a batch is a set of entities (parts, vehicles , etc.) moving through a transfer zone at the same speed. A batch is de ned by three characteristics: a length, a density and a position. Inside a batch place, an event hybrid approach allows to describe the evolution of batches. More generally, in the BPN formalism, the dynamics of batches inside a batch place is governed by a ow-density relation representing a switching between free and accumulation behaviors. To represent a more general ow-density relation as the triangular fundamental diagram of tra c road domain [6], the batch place is extended to a Bi-parts Batch place (BB-place) de ned by four continuous characteristics: a maximum speed, a maximum density, a length and a maximum ow. The hybrid dynamics is now de ned by three behaviors: free, congestion and decongestion behaviors. This dynamics allows batches to switch between free and congested states. The switching of batch states is also discussed according to controlled events, such as the variation of maximum speeds of BB-places or the modi cation of maximum ows associated to continuous and batch transitions. Finally, to compute the instantaneous ring ow vector we adapt the linear programming problem previously proposed for BPN [12] to BB-places.
This paper is organized as follows. Section 2 recalls some concepts and de nitions on batches Petri nets. Section 3 presents the extension of the batch place, called Bi-parts Batch place, and de nes the states and the behaviors of controllable batches. The instantaneous ring ow vector is determined thanks to the resolution of a linear programming problem. In Section 4, an example of tra c road system illustrates these contributions. 2
Backgrounds on Batches Petri Nets and controllable batches This section recalls some concepts and de nitions used in this paper. For more details on Batches Petri Nets, the reader is referred to [3], [10], [12] and [13]. 2.1
De nition 1 A Generalized Batches Petri Nets (GBPN) is a 6-tuple N = (P; T; P re; P ost; ; T ime) where: { P = P D [ P C [ P B is a nite set of places partitioned into the three classes of discrete, continuous and batch places. { T = T D [ T C [ T B is a nite set of transitions partitioned into the three classes of discrete, continuous and batch transitions. { P re; P ost : (P D T ! N) [ ((P C [ P B) T ! R 0) are, respectively, the pre-incidence and post-incidence matrices, denoting the weight of the arcs from places to transitions and from transitions to places. { : P B ! R3 0 is the batch place function. It associates with each batch place pi 2 P B the triple (pi) = (Vi; dimax; Si) that represents, respectively, a speed, a maximum density and a length. { T ime : T ! R 0 associates a non negative number with every transition: if tj 2 T D, then T ime(tj ) = dj denotes the ring delay associated with the discrete transition; if tj 2 T C [ T B, then T ime(tj ) = j denotes the maximal ring ow associated with the continuous or batch transition.
We denote the number of places and transitions, resp., m = jPj and n = jTj and use the following notations: mX = jP Xj and nX = jT Xj for X 2 fD; C; Bg. The preset and postset of transition tj are: tj = fpi 2 P j P re(pi; tj ) > 0g and tj = fpi 2 P j P ost(pi; tj ) > 0g. Similar notations may be used for pre and post transition sets of places and its restriction to discrete, continuous or batch transitions is denoted as (d)pi = pi \ T D, (c)pi = pi \ T C , and (b)pi = pi \ T B. The incidence matrix of a GBPN is de ned as C = P ost P re. De nition 2 The marking of a GBPN at time mi( )::mm( )]T where: is de ned as m( ) = [m1( ):: { if pi 2 P D then mi 2 N ,i.e, the marking of a discrete place is a non negative integer. { if pi 2 P C then mi 2 R 0 ,i.e, the marking of a continuous place is a non negative real. { if pi 2 P B then mi = f h; :::; rg,i.e, the marking of a batch place is a series of batches.
A batch, i.e., a group of discrete entities characterized by continuous variables, has been de ned for Batches Petri Nets. When, three continuous variables are associated with it, it is called a batch. When, four continuous variables are considered [10], it is called a controllable batch, de ned as follows. De nition 3 A controllable batch C r( ) at time , is de ned by a quadruple, C r( ) = (lr( ); dr( ); xr( ); vr( )) where lr( ) 2 R 0 is the length, dr( ) 2 R 0 is the density, xr( ) 2 R 0 is the head position and vr( ) 2 R 0 is the speed. An instantaneous batch ow of C r( ) is de ned by: 'r( ) = vr( ):dr( ).
Some constraints on batches composing the marking of a batch place, pi, have to be respected: 0 lr( ) xr( ) Si (position and length constraints), 0 dr( ) dimax (density constraint) and 0 vr( ) Vi (speed constraint). De nition 4 A controllable batch C r( ) of batch place pi, which has its head position equals to the length of the batch place, i.e., xr( ) = Si, is called an output controllable batch, denoted OC r( ). The output density dout of a batch i place pi is de ned as follows. If at time , batch place pi has an output controllable batch OC r( ), then diout( ) = dr( ), else diout( ) = 0.
Note that the output density of place pi at time m( ) and can also be denoted by diout(m). depends on the marking De nition 5 The marking quantity vector q 2 Rm associated with a marking m is de ned as follows: qi =
mi P r2mi lr dr if pi 2 P D [ P C if pi 2 P B ; i.e., for a batch place it represents the sum of the quantities of the batches it contains, while it coincides with the marking for other places.
De nition 6 The maximal capacity of batch place pi 2 P B is Qi = Si dimax. A place such that qi( ) = Qi is called a full batch place. 2.2
The enabling and ring conditions of timed discrete transitions of a GBPN are those of timed transitions of discrete Petri nets. The enabling conditions of continuous transitions are those of First Order Hybrid Petri Nets [14] and Hybrid Petri Nets [4] i.e., one distinguishes weakly and strongly enabled transitions. Similar conditions for batch transitions have been de ned [12].
Condition 7 A discrete transition tj 2 T D is enabled at m if for all pi 2 tj , mi P re(pi; tj ).
A discrete transition tj 2 T D that is enabled at a marking m and has also been continuously enabled for a time equal to its ring delay, res yielding a new marking m0 = m + C( ; tj ).
Condition 8 A continuous transition tj 2 T C is enabled at m if for all pi 2 (d)tj , mi P re(pi; tj ). We say that the continuous transition is: Condition 9 A batch transition tj 2 T B is enabled at m if: { strongly enabled if 8pk 2 (c)tj , mk > 0: { weakly enabled if 9pr 2 (c)tj , mr = 0: { 8pi 2 (d)tj , mi P re(pi; tj ).
{ 8ps 2 (b)tj , dsout > 0.
We say that the batch transition is: { strongly enabled if 8pk 2 (c)tj , mk > 0: { weakly enabled if 9pr 2 (c)tj , mr = 0: 2.3
A ow-density relation is intrinsically associated with a batch place pi that governs the dynamics of batches. In a GBPN, this relation is a linear function when the density is strictly inferior to the maximal density of pi. Moreover, a batch place describes the transfer of batches according to a switching dynamics between two behaviors: the free behavior and the accumulation behavior [3]. According to this relation, described in Fig. 1, every accumulated batch has the same density, i.e. dr = dimax and its batch ow veri es 0 'r imax, while every free batch respects 'r = Vi dr.
Extension of Batches Petri Nets by Bi-parts batch places ϕ The instantaneous ring ow (IFF) 'j ( ) j , associated with a continuous or a batch transition tj 2 T C [ T B, represents the quantity of ring of transition tj by time unit. The IFF vector at time is denoted by '( ) 2 RnC+nB . In [12], a method for computing the IFF of enabled continuous and batch transitions has been introduced. It is based on the resolution of a linear programming problem that takes the net structure and the current state into account.
De nition 10 Given a marked GBPN (N; m) with incidence matrix C, let: { TN (m) T C [ T B be the subset of continuous and batch transitions that are not enabled at m; { P;(m) = fpi 2 P C j mi = 0g be the subset of empty continuous places; { PF (m) = fpi 2 P B j qi = Qig be the subset of full bach places.
Any admissible IFF vector ', at m, is a feasible solution of the following
linear set:
>8 (a) 0 'j j 8tj 2 T C [ T B
>>>> (b) 'j = 0 8tj 2 TN (m)
>< (c) C(pi; ) ' 0 8pi 2 P;(m)
>>>>> ((ed)) PCo(psit;(p)i; ') '0 Vi dimax 88ppii 22 PPFB(m)
>: (f ) P re(pi; ) ' Vi diout(m) 8pi 2 P B
The set of all feasible solutions is denoted S(N; m).
(
Triangular Batches Petri Nets Triangular Batches Petri Nets (TrBPN) extends the GBPN formalism by associated a new continuous characteristic to the batch place. This new place, called Bi-parts Batch place (BB-place) integrates a triangular ow-density relation, the propagation speed of congestion and the critical density, concepts that are observed in tra c systems.
Firstly we extend the de nition of a GBPN, by enriching the characteristic function of a batch place pi by a new parameter corresponding to a maximum ow imax. Nodes of a Triangular Batches Petri Nets are represented in Fig. 2. discrete place
continuous 3.5 place
Bi-parts batch place: Vi , dmaxi , Si , Φmaxi dj discrete transition Φj continuous transition Φj batch transition De nition 11 A Triangular Batches Petri Nets (TrBPN) is a GBPN with a new batch place called Bi-parts Batch place (BB-place). The set of BB-places of a TrBPN is denoted as P BB. The batch place function for a BB-place is : P BB ! R4>0. Its associates with BB-place pi 2 P BB, the quadruple (pi) = (Vi; dimax; Si; imax) that represents, respectively, a maximum speed, a maximum density, a length and a maximum ow.
De nition 12 The marking of a BB-place at time batches. If pi 2 P BB then mi = fC h; ; C rg. is a series of controllable
From these de nitions, we associate to a BB-place pi a new ow-density relation with a triangular form that must respected by controllable batches. This relation can adequately represent the di erent situations and states of the ow circulating inside a BB-place. In fact it has a propagation speed of congestion and a critical density that are de ned as follows: De nition 13 For a BB-place pi with (pi) = (Vi; dimax; Si; imax), the propagation speed of congestion, denoted Wi and, the critical density dcri are respectively i de ned by:
Wi = dimax imVaix Vi
max
i
dcri =
i
max
i
Vi
(
Wi:dimax
Proof. For a density dr = dicri( ) > dicri, we have from (
To allow a dynamic recon guration of ow systems with accumulation behavior by manual control we propose here a variation of a BB-place speed. Indeed the variation of the speed of BB-place imposes a variation of the critical density and the maximum ow of the BB-place. The critical density and the maximum ow will be named respectively instantaneous critical density dicri( ) and instantaneous maximum ow imax( ) when the speed of a BB-place is time-varying, 0 vi( ) Vi, but the propagation speed of congestion is assumed to be constant, Wi.
Φi max ϕi max (τ) 0 ϕ
Vi vi (τ)
-Wi dcrii di cri (τ) 'r = dr:Vi Wi:(dimax
if 0 dr dr) if dicri < dr vi( ):dicri( ) = Wi:(dimax
dicri( )) ) Wi:dimax = vi( ):dicri( ) + Wi:dicri( ) = dicri( ):(vi( ) + Wi) ) dicri( ) =
Note that the instantaneous critical density of BB-place pi at time depends on the instantaneous speed vi( ) and can also be denoted by dicri(vi). By the same, for the instantaneous maximum ow, can also be denoted by imax(vi). De nition 16 States of batches. Let C r( ) = (lr( ); dr( ); xr( ); vr( )) be a controllable batch of BB-place pi, with vi( ) the instantaneous speed of pi. { C r is called a free controllable batch if its density is lower than the critical density of pi: dr( ) dicri( ); { C r is called a congested controllable batch if its density is greater than the critical density of pi: dr( ) > dicri( ). 3.2
We assume that the dynamic evolution of batches inside a BB-place pi takes into account the variation the maximum ow of continuous and batch transitions and the maximum speed of pi. For this we present two controlled events as follow: { A controlled speed event is a triplet (pi; vi; ), where pi 2 P BB is a BBplace, vi 2 [0; Vi] is an instantaneous speed of BB-place and is the date of occurrence of this event. { A controlled ows event is a triplet (tj ; j ; ); where tj 2 T C [T B is a continuous or batch transitions, j 2 [0; j ] is a instantaneous ow of continuous or batch transitions and is the date of occurrence of this event. Variation of a speed of BB-place: States and characteristics of batches change when the maximum speed of the BB-place is changed, we suppose that the speed of BB-place pi changes at time from vi( ) to vi0( ). Two situations must be considered: easier the speed decreases or increases: i.e., vi0 < vi, or increases, i.e., vi0 > vi.
A) vi0( ) < vi( ): three cases have to be considered (see Fig.4 ). { case 1: C 1 = (l1; d1; x1; v1) is a free controllable batch. When the speed of BB-place changes, batch C 1 reduces its speed but keeps its density. It stays a free batch C 1 = (l1; d1; x1; vi0). { case 2: C 2 = (l2; d2; x2; v2) is a congested controllable batch with a higher speed than vi0 (v2 > vi0). When the speed of BB-place changes, batch C 2 reduces its speed to vi0 but keeps its density. It becomes a free batch with C 2 = (l2; d2; x2; vi0). { case 3: C 3 = (l3; d3; x3; v3) is a congested controllable batch with a lower speed than vi0 (v3 < vi0). When the speed of BB-place changes, C 3 keeps its speed and its density while it stays a congested batch.
Φmaxi dcrii
Vi vi
Batch before speed variation
Batch after speed variation Cβ2
Cβ2 v’i
Cβ3
Wi dmaxi d
B) vi0( ) > vi( ): three cases have to be considered (see Fig.5) { case 1: C 1 = (l1; d1; x1; v1) is a free controllable batch and its density is lower than dicri( ) at speed vi0 (i.e., d1 < dicri( )). When the BB-place speed changes, batch C 1 increases its speed to vi0 and keeps its density. It stays a free batch with C 1 = (l1; d1; x1; vi0) (see case 1 in Fig.5). { case 2: C 2 = (l2; d2; x2; v2) is a free controllable batch and its density is greater than dcri( ) at speed vi0 (i.e., d2 > dicri( )). When the BB-place i speed changes, batch C 2 keeps its density but increases its speed to a speed v20 that respects vi < v20 < vi0. It becomes a congested batch with C 2 = (l2; d2; x2; v20) (see case 2 in Fig.5). { case 3: C 3 = (l3; d3; x3; v3) is a congested controllable batch. When the speed of BB-place changes, this batch does not changed and stays a congested batch.
Φmaxi ϕmaxi (v’i) dcrii Case 1
Cβ2 Cβ2 vi
Cβ3 0 dmaxi
d v’i
Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin ϕ Vi Batch before speed variation
Batch after speed variation
tics of batches change when the maximum ow of continuous or batch transition is changed, we suppose that the ow j of continuous or batch transition place tj changes at time from j( ) to 0j( ). Two situations must be considered: easier the ow decreases i.e., 0j( ) < j( ), or increases, i.e., j( 0) > j( ).
A) 0j( ) < j( ): two cases have to be considered (see Fig.6 a)) { case 1: C 1 = (l1; d1; x1; v1) is a free controllable batch. When the ow of continuous or batch transition changes, batch C 1 becomes a congested batch with new density and new speed C 0 ( ) = (l1; d01; x1; v10). 1 { case 2: C 2 = (l2; d2; x2; v2) is a congested controllable batch. When the ow of continuous or batch transition changes, batch C 2 becomes completely congested, its density increases and its speed decreases C 20( ) = (l2; d02; x2; v20).
ϕ ϕmaxi ϕj (τ) φ (τ) Cβ1
vi ϕ'j(τ) 0 B) 0j( ) > j( ): two cases have to be considered (see Fig.6 b)) { case 1: C 1 = (l1; d1; x1; v1) is a free controllable batch. When the ow of continuous or batch transition changes, batch C 1 stays a free batch. { case 2: C 2 = (l2; d2; x2; v2) is a congested controllable batch. When the ow of continuous or batch transition changes, batch C 2 becomes a free batch with C 2 = (l2; d02; x2; vi): its speed becomes equal to the speed of batch place and its density is reduced. 3.3
Let us rst recall some concepts necessary to the understanding of the evolution of controllable batches, dedicated to a bacth place that can be also applied to a BB-place.
De nition 17 The input (resp., output) ow of a batch place or continuous place pi at time is the sum of all ows entering (resp., leaving) the place and can be written, respectively, as: { { iin( ) = Ptj2 pi P ost(pi; tj ) 'j ( ) = P ost(pi; ) '( ).
iout( ) = Ptj2pi P re(pi; tj ) 'j ( ) = P re(pi; ) '( ).
De nition 18 At time , various static functions can be applied on batches composing the marking of batch place pi: { Create. If the input ow of pi is not null, i.e., iin( ) 6= 0, a controllable batch C r( ) = (0; dr( ); 0; vr( )) with dr( ) = iin( )=vi( ) and vr( ) = vi( ), is created and added to the marking of pi, i.e., mi( ) = mi( ) [ f r( )g. { Destroy. If the length of a batch, C r( ), is null, lr( ) = 0, and if it is not a created batch, xr( ) 6= 0, batch C r( ) is destroyed, noted C r( ) = 0, and removed from the marking of pi, i.e., mi( ) = mi( ) n f r( )g. { Merge. If two batches with the same density and the same speed are in contact, they can be merged. Let batches C r( ) = (lr( ); dr( ); xr( ); vr( )) and C h( ) = (lh( ); dh( ); xh( ); vh( )), such that xr( ) = xh( ) + lr( ), dr( ) = dh( ) and vr( ) = vh( ). In this case, batch C r( ) becomes C r( ) = (lr( )+lh( ); dr( ); xr( ); vr( )), batch h( ) is destroyed, h( ) = 0, and mi( ) = mi( ) n f h( )g { Split. It is always possible to split a batch into two batches in contact with the same density and the same speed.
The density and the speed of batches cannot varied in time while their value can change when an event occurs. In other words, these both characteristics are piecewise constants while the length and the position are linear in time. Consequently, for any batch C r( ) = (lr( ); dr( ); xr( ); vr( )), it holds: d_r = v_r = 0.
Inside a BB-place, various equations govern the dynamics of batches : inputting, moving and existing. Between two events, a batch can move in three di erent behaviors: free behavior, congestion behavior and decongestion behavior. (Free behavior ) Controllable batch C r( ) = (lr( ); dr( ); xr( ); vr( )) of BB-place pi
is in a free behavior, if it moves freely at its transfer speed vr( ). Three di erent dynamics can occur.
{ Input. A created controllable batch, C r( ) = (0; dr( ); 0; vr( )), without contact with another batch or in contact with a downstream batch C h( ) that has a greater speed (i.e., vh( ) vr( )), freely enters in place pi according to x_r = l_r = vr( ). { Move. A controllable batch, C r( ) = (lr( ); dr( ); xr( ); vr( )), which is a free batch, freely moves inside BB-place pi according to x_r = vr( ); l_r = 0. { Exit. An output controllable batch C r( ) = (lr( ); dr( ); Si; vr( )), which has its ow equals to the output ow of pi, or which is free with a lower batch ow than the output ow, freely exits from place pi according to x_r = 0; l_r = vr( ). (Congestion behavior ) Controllable batch C r( ) = (lr( ); dr( ); xr( ); vr( )) of BB-place pi is in a congestion behavior, if it cannot move at its speed but must reduces it, i.e., it starts a congestion.
An output controllable batch OC r( ) of BB-place pi, which is in a congested behavior at time , is split into two batches in contact (Def. 18) as follow: { C r( ) = (lr( ); dr( ); Si; vr( )) and OC r0 ( ) = (0; dr0 ( ); xr0 ( ); vr0 ( )) with: dr0 ( ) = dimax Wiouit ; vr0 ( ) = dr0io(ut) and xr0 ( ) = Si
From time on, the evolution of both batches C r and OC r0 is governed by (Eq.21) and (Eq.22) in [9]
A complete and general description of the equations that govern the congestion behavior can be found in [9]. Note that in the dynamics of congestion, we out assume that the density of a batch in a congestion behavior is equal to dimax Wii that can easily deduced from Eq. 4. When a batch starts a congestion, it is split into two batches in contact where the downstream batch is congested. (Decongestion behavior ) Congested controllable batch C r( ) = (lr( ); dr( ); xr( ); vr( )) of BB-place pi is in a decongestion behavior, if it can move with a higher speed.
At time , the congested output batch OC r( ) is split into two batches in contact (see Def. 18) as follow:
{ OC r( ) = (lr( ); dr( ); Si; vr( )) and OC r0 ( ) = (0; dr0 ( ); xr0 ( ); vr0 ( )) with dr( ) = dimax
Wiouit , vr( ) = drio(ut) and xr( ) = Si
out and vr0 ( ) = vi, dr0 ( ) = vii and xr0 ( ) = Si
In the dynamics of Triangular Batches Petri Nets are based on a discrete event approach with linear or constant continuous evolutions between two timed events. Then between two events or two dates, the state of the hybrid model has an invariant state de ned as follow: De nition 19 The invariant behavior state (IB-state) of a TrBPN corresponds to a period of time such that: { the marking in the discrete places is constant; { the IFF of the continuous and batch transitions is constant; { the reserved marking of discrete and continuous places is constant.
The IB-state changes if and only if one (or possibly several at the same time) of the following kind of events occurs: { Internal events (timed events inside a BB-place) i.1 a batch becomes an output batch C r = OC r; i.2 two batches meet; i.3 an output batch is destroyed OC r = 0. { External events e.1 a discrete transition is red: tj ; e.2 a continuous place becomes empty: min = 0; e.3 a discrete transition becomes enabled min = a; e.4 a batch becomes an output batch (i.e. event i.1 above); e.5 an output batch is destroyed (i.e. event i.3 above); { Controlled events c.1 the ow of a batch transitions is modi ed: j ( ) = 0j ( ); c.2 the speed of a BB-place is modi ed: vi( ) = vi0( ).
As in Batches Petri Nets, the behavior of a TrBPN can be represented by an evolution graph where a node represents an IB-state of the dynamic model. The nodes are linked by arcs with a labeled transition that determines the occurred events and the past delay between two consecutive IB-states (see [3]). An example of evolution graph will be given in Section 4. 3.5
To computate the instantaneous ring ows (IFF) ', the speed vi of batch place pi and the ow of continuous and batch transitions j are considered as variables that can be suitably chosen by a supervisor to drive the evolution of the net. The computation of IFF for a TrBPN is deduced from Def. 10.
Proposition 20 Given a TrBPN (N; m) with incidence matrix C. For a given speed of BB-place vi( ) and a ow of continuous and batch transitions j .
Any admissible IFF vector ', at m, is a feasible solution of the following linear set: { TN (m) T C [ T B be the subset of continuous and batch transitions that are not enabled at m; { P;(m) = fpi 2 P C j mi = 0g be the subset of empty continuous places; { PF (m) = fpi 2 P BB j qi = Qig be the subset of full BB-places. >8 (a) 0 'j ( ) j 8tj 2 T C [ T B >>>> (b) 'j ( ) = 0 8tj 2 TN (m) <>>> (c) C(pi; :):'( ) 0 8pi 2 P;(m)
(d) C(pi; :):'( ) 0 8pi 2 PF (m)
>>> (e) P ost(pi; :):'( ) vi( ):dicri( ) 8pi 2 P BB
>>>> (f ) P re(pi; :):'( ) vi( ):diout( ) 8pi 2 P BB
>: (g) P re(pi; :):'( ) vi( ):dicri( ) 8pi 2 P BB
(
Then, the constraint (f) in (
The dynamics of Triangular Batches Petri Nets is based on a discrete event approach with linear or constant continuous evolutions between timed events. Between two timed events, the state of the net has an invariant behavior state (IB-state) (see Def. 19).The state of the system is calculated only when it undergoes discontinuity. This dynamic tests on the existence of controlled event at current date (see Section. 3.2), determines the state of batches (see Def. 16) and the enabled transitions (see Def. 3.5) to calculate the instantaneous ring ow of continuous and batch transition.Then all timed events that change the global state of system are computed, the date of the nearest event, which is the nearest in time, becomes the current date and at this instant, new markings are computed. This dynamics is stopped when there is no event or when there is an invariant state (IB-state) already de ned previously. Fig. 7 shows the most important steps of this dynamics.
Extension of Batches Petri Nets by Bi-parts batch places
Initial marking Controlled Events at current date
YES
NO
Determination of dynamic characteristics of batch places Modification in the maximum flows of continuous and batch transitions
Determination of the characteristics and states of batches
Determination of the enabled transitions Compute the instantaneous firing flows (IFF) for TC and TB
Compute the next events dates Shift to the nearest time event date
Compute the new marking To illustrate the main contributions of this paper, we consider a tra c road intersection composed of three sections and a tra c light as shown by Figure 8. Фin1
L1
S1
Фin2 Фin3
L3
S3
L2
S2 Фout3 Фout2
Section Li (km) Vmaxi (km/h) dmaxi (veh/km) Φmaxi (veh/h) Φini (veh/h) Φouti (veh/h)
Section S1 has an output ow equal to 4100 veh=h. This output is divided into an input ow of S2 equal to 3060 veh=h and an input equal to 1040 veh=h. In other words, a part of outgoing vehicles of S1 goes to the second section S2 and the other one goes to the third section S3. The input ow of section S1 is supposed null meaning that no vehicles enters the intersection. Some tra c events appear during the evolution of the tra c: 1- 10:8 minutes after the beginning, an accident appears at the end of section
S2 reducing its output ow to 2040 veh=h; 2- 13:8 minutes after the beginning, there is a reduction in the maximum speed of section S3 that becomes equal to 20 km=h; 3- 13:2 minutes after the reduction in the speed of S3, there is an increase in the speed of S3 that becomes equal to 60 km=h.
The initial state of this intersection is: in section S1, there are 409 vehicles having a speed of 120 km=h. They are supposed uniformly distributed from the entrance to the end of section S1 with a density of 34:1 veh=km. Both sections S2 and S3 are empty.
Φ3= 0 t3
The TrBPN model for this tra c road intersection is shown in Figure 9. Discrete places p1, p2 represent, respectively, the green and red tra c light. Delays d1 = 0:1h and d2 = 0:12h of discrete transitions t1 and t2 represent, respectively, the durations of green and red tra c light. BB-places p3, p4 and p5 represent, respectively, sections S1, S2 and S3. Maximum ows 3, 4, 5, 6 and 7 of batch transitions t3, t4, t5, t6 and t7 represent the maximum input/output ow of each section.
The initial state of intersection, 409 vehicles distributed in section S1, are represented in the TrBPN model by the output controllable batch OC 3( 0) = (12; 34:1; 12; 120) that composes the initial marking of place p3. As the tra c light is supposed to be green, place p1 contains one token while place p2 is emptied. The initial marking of the model is m( 0) = (1; 0; fOC 3( 0)g; 0; 0).
The three tra c events cited above, correspond to controlled events in the TrBPN formalism that are de ned, according to Section 3.2, by: { tra c event 1 is related to transition t5: (t5; 2040; 10:8); { tra c event 2 is related to BB-place p5: (p5; 20; 13:8); { tra c event 3 is also related to BB-place p5: (p5; 60; 27).
To be able to compute the instantaneous ring ow using linear programming, we de ne as objective function to maximize the output ows of the sections, i.e., the IFF of batch transitions, J = max f'g.
At the initial state ( 0 = 0 h), BB-place p3 contains an output batch OC 3( 0) =
(12; 34:1; 12; 120) and there are no controlled events at this date. Following the
dynamics of TrBPN (Figure 7), we determine the enabled transitions (t1; t3; t4
and t6) and we compute the instantaneous ring ow vector solving of the linear
program (
>>>>8>>>>> (((aaa')")) 00 0 ''64'3 130004600
>>>< ((eb)) ''53= '770=000
>>>>>>>>>> (((fee)'")) '4 ''+46 '6 440088400100
>:> (g) '4 + '6 7000
(
At this initial state, there is a creation of two batches in BB-places p4 and p5, respectively C 4( 0) and C 5( 0). The state of the output batch OC 3( 0) is free (see Def.16).
From the initial IB-state, nine IB-states have been reached as it is shown in
the evolution graph in Figure 10. The set of timed events are:
(Ev1, delay: 0.1 h) Discrete transition (t1) is enabled; destruction of the output
batch of BB-place p3, OC 3 = 0;
(Ev2, delay: 0.03 h) Batch C 4 of BB-place p4 becomes an output batch, OC 4;
(Ev3, delay: 0.03 h) Maximum ow of transition t5 is modi ed and becomes 5 =
2040veh=h;
(Ev4, delay: 0.04 h) Output batch of p4 is destroyed, OC 40 = 0;
(Ev5, delay: 0.02 h) Discrete transition t2 is enabled; batch C 5 of place p5 becomes
an output batch OC 5;
(Ev6, delay: 0.01 h) Speed of BB-place p5 is reduced, v5 = 20km=h;
(Ev7, delay: 0.1 h) Discrete transition t1 is enabled;
(Ev8, delay: 0.12 h) Discrete transition t2 is enabled and speed of p5 is increased,
v5 = 60km=h;
(Ev9, delay: 0.01 h) Destruction of the output batch of BB-place p5, OC 500 = 0 .
(
We detail now two events of the set of timed events that illustrate our contributions in TrBPN: a modi cation of maximum ow of batch transition t5, and a variation of the maximum speed of BB-place p5. These both events are controlled events.
At Ev3, there is a controlled event due to an accident and the maximum ow
of batch transition t5 is reduced to 2040 veh=h. The output ow of the output
batch OC 4 is now higher then the maximum ow of batch transition t5 and
the output batch adopt a congestion behavior. In this case, the output batch
OC 4 is split into two batches C 4(
To compute the IFF of all enabled continuous and batch transitions, we
solve the linear program of the equation 10 and we obtain the follow results
('3(
At Ev6, there is a controlled event that decreases the batch place speed (v5 =
20 km=h). The output batch OC 5(
We recompute the IFF of all enabled continuous and batch transitions and
we obtain ('3(
Conclusion We proposed in this paper an extension of Batches Petri Nets by a new de nition of batch place called Bi-parts Batche place (BB-place). To model a variable delay inspired in the triangular fundamental diagram, we improve the function of a batch place with a maximal ow parameter. This maximal ow, the speed and the density allow us to de ne a new dynamic equations of ow-density. These equations represent more accurately the bi-part behavior observed in the systems ow based on the triangular diagram. To include this bi-part behavior in this new extension of BPN, we rede ned some concepts like, the states of batches, conditions of enabling and ring transitions. Additionally, a de nition of controlled events was proposed in this paper and it allows a manual control of the speed of BB-place and the maximal ow of batch and continuous transitions. Another contribution of this paper is the proposition of a method to compute the IFF that take into account the bi-parts behavior of the BB-place proposed in this paper. An application of all these contributions is shown in the example in the section 4. The Triangular Batches Petri Nets formalism proposed in this paper allows us to represent more accurately the vehicle tra c in transportation systems than BPN. The next step is to use the control laws already de ned in the literature to test and analyze the performance of these laws (such as the Ramp Metering System (RMS), and Variable Speed Limit (VSL)) in order to reduce congestion.