Extension of Batches Petri Nets by Bi-parts batch places Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin Aix Marseille Université, CNRS, ENSAM, Université de Toulon, LSIS UMR 7296, 13397, Marseille, France radhia.gaddouri@lsis.org, leonardo.brenner@lsis.org, isabel.demongodin@lsis.org Abstract. This paper proposes an extension of Batches Petri Nets by a new definition of the batch place called Bi-parts Batch place (BB- place). The flow-density equations that govern the dynamics of control- lable batches inside a BB-place is now defined by a triangular relation. To take into account controlled events, the behaviors of batches are dis- cussed according to a variation of speeds and of maximum flows. The switching dynamics of controllable batches is defined on three behaviors: free, congestion and decongestion behaviors. We also propose the compu- tation of the instantaneous firing flow vector associated with continuous and batch transitions thanks to a resolution of a linear programming problem. An example of traffic road illustrates the novel extensions pro- posed in this paper. Keywords: Petri Nets, Discrete Event Systems, Hybrid systems, Flow, Batch, Traffic road 1 Introduction For modeling, analysis and control of discrete event systems like manufacturing systems or traffic road systems, Petri nets are well utilized. Moreover, the dis- crete Petri net formalism has been extended to also encompass continuous and hybrid models [1], thus offering formal techniques for expressing both funda- mental discrete event and continuous time behaviors. Hybrid Petri nets combine the interest of the continuous Petri nets for the representation of the flows and those of the discrete Petri nets for the representation of the controls [4]. In order to integrate variable delays on continuous flows, 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 defined on the concept of batches. A batch consists in regrouping all elements of the flow 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 defined 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 2 Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin a flow-density relation representing a switching between free and accumulation behaviors. To represent a more general flow-density relation as the triangular fundamental diagram of traffic road domain [6], the batch place is extended to a Bi-parts Batch place (BB-place) defined by four continuous characteristics: a maximum speed, a maximum density, a length and a maximum flow. The hybrid dynamics is now defined 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 modifica- tion of maximum flows associated to continuous and batch transitions. Finally, to compute the instantaneous firing flow 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 defini- tions on batches Petri nets. Section 3 presents the extension of the batch place, called Bi-parts Batch place, and defines the states and the behaviors of control- lable batches. The instantaneous firing flow vector is determined thanks to the resolution of a linear programming problem. In Section 4, an example of traffic road system illustrates these contributions. 2 Backgrounds on Batches Petri Nets and controllable batches This section recalls some concepts and definitions used in this paper. For more details on Batches Petri Nets, the reader is referred to [3], [10], [12] and [13]. 2.1 Some definitions Definition 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 finite set of places partitioned into the three classes of discrete, continuous and batch places. – T = T D ∪ T C ∪ T B is a finite 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 ∈ P B the triple γ(pi ) = (Vi , dmax i , 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 ∈ T D , then T ime(tj ) = dj denotes the firing delay associated with the discrete transition; • if tj ∈ T C ∪ T B , then T ime(tj ) = Φj denotes the maximal firing flow associated with the continuous or batch transition. Extension of Batches Petri Nets by Bi-parts batch places 3  We denote the number of places and transitions, resp., m = |P| and n = |T| and use the following notations: mX = |P X | and nX = |T X | for X ∈ {D, C, B}. The preset and postset of transition tj are: • tj = {pi ∈ P | P re(pi , tj ) > 0} and t•j = {pi ∈ P | P ost(pi , tj ) > 0}. 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 defined as C = P ost − P re. Definition 2 The marking of a GBPN at time τ is defined as m(τ ) = [m1 (τ ).. mi (τ )..mm (τ )]T where: – if pi ∈ P D then mi ∈ N ,i.e, the marking of a discrete place is a non negative integer. – if pi ∈ P C then mi ∈ R≥0 ,i.e, the marking of a continuous place is a non negative real. – if pi ∈ P B then mi = {βh , ..., βr },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 vari- ables, has been defined 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, defined as follows. Definition 3 A controllable batch Cβr (τ ) at time τ , is defined by a quadruple, Cβr (τ ) = (lr (τ ), dr (τ ), xr (τ ), vr (τ )) where lr (τ ) ∈ R≥0 is the length, dr (τ ) ∈ R≥0 is the density, xr (τ ) ∈ R≥0 is the head position and vr (τ ) ∈ R≥0 is the speed. An instantaneous batch flow of Cβr (τ ) is defined 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 (τ ) ≤ dmax i (density constraint) and 0 ≤ vr (τ ) ≤ Vi (speed constraint). Definition 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 i of a batch place pi is defined as follows. If at time τ , batch place pi has an output control- lable batch OCβr (τ ), then dout out i (τ ) = dr (τ ), else di (τ ) = 0.  Note that the output density of place pi at time τ depends on the marking m(τ ) and can also be denoted by dout i (m). Definition 5 The marking quantity vector q ∈ Rm associated with a marking m is defined as follows: if pi ∈ P D ∪ P C  mi qi = P , βr ∈mi lr · dr if pi ∈ P B 4 Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin 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.  Definition 6 The maximal capacity of batch place pi ∈ P B is Qi = Si · dmax i . A place such that qi (τ ) = Qi is called a full batch place.  2.2 Conditions of enabling The enabling and firing 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 defined [12]. Condition 7 A discrete transition tj ∈ T D is enabled at m if for all pi ∈ • tj , mi ≥ P re(pi , tj ). A discrete transition tj ∈ T D that is enabled at a marking m and has also been continuously enabled for a time equal to its firing delay, fires yielding a new marking m0 = m + C(·, tj ).  Condition 8 A continuous transition tj ∈ T C is enabled at m if for all pi ∈ (d) tj , mi ≥ P re(pi , tj ). We say that the continuous transition is: – strongly enabled if ∀pk ∈ (c) tj , mk > 0. – weakly enabled if ∃pr ∈ (c) tj , mr = 0.  Condition 9 A batch transition tj ∈ T B is enabled at m if: – ∀pi ∈ (d) tj , mi ≥ P re(pi , tj ). – ∀ps ∈ (b) tj , dout s > 0. We say that the batch transition is: – strongly enabled if ∀pk ∈ (c) tj , mk > 0. – weakly enabled if ∃pr ∈ (c) tj , mr = 0.  2.3 Batch dynamics A flow-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 = dmax i and its batch flow verifies 0 ≤ ϕr ≤ Φmax i , while every free batch respects ϕr = Vi · dr . Extension of Batches Petri Nets by Bi-parts batch places 5 φ Φi max Vi ϕr 0 d dr di max Free batch Accumulated batch Fig. 1. Relation flow-density of a batch place 2.4 Instantaneous firing flows The instantaneous firing flow (IFF) ϕj (τ ) ≤ Φj , associated with a continuous or a batch transition tj ∈ T C ∪ T B , represents the quantity of firing of transition tj C B by time unit. The IFF vector at time τ is denoted by ϕ(τ ) ∈ Rn +n . 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. Definition 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) = {pi ∈ P C | mi = 0} be the subset of empty continuous places; – PF (m) = {pi ∈ P B | qi = Qi } be the subset of full bach places. Any admissible IFF vector ϕ, at m, is a feasible solution of the following linear set:   (a) 0 ≤ ϕj ≤ Φj  ∀tj ∈ T C ∪ T B  (b) ϕj = 0 ∀tj ∈ TN (m)    (c) C(pi , ·) · ϕ ≥ 0 ∀pi ∈ P∅ (m)  (1)   (d) C(p i , ·) · ϕ ≤ 0 ∀pi ∈ PF (m) (e) P ost(pi , ·) · ϕ ≤ Vi · dmax ∀pi ∈ P B     i (f ) P re(pi , ·) · ϕ ≤ Vi · di (m) ∀pi ∈ P B out  The set of all feasible solutions is denoted S(N, m).  3 Triangular Batches Petri Nets Triangular Batches Petri Nets (TrBPN) extends the GBPN formalism by asso- ciated a new continuous characteristic to the batch place. This new place, called Bi-parts Batch place (BB-place) integrates a triangular flow-density relation, the propagation speed of congestion and the critical density, concepts that are observed in traffic systems. 6 Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin 3.1 Definitions and notations Firstly we extend the definition of a GBPN, by enriching the characteristic function γ of a batch place pi by a new parameter corresponding to a maximum flow Φmax i . Nodes of a Triangular Batches Petri Nets are represented in Fig. 2. discrete continuous Bi-parts batch place: 3.5 place place Vi , dmaxi , Si , Φmaxi discrete continuous batch dj Φj Φj transition transition transition Fig. 2. Nodes of Triangular Batches Petri Nets Definition 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 ∈ P BB , the quadruple γ(pi ) = (Vi , dmax i , Si , Φmax i ) that represents, respectively, a maximum speed, a maximum density, a length and a maximum flow.  Definition 12 The marking of a BB-place at time τ is a series of controllable batches. If pi ∈ P BB then mi = {Cβh , · · · , Cβr }.  From these definitions, we associate to a BB-place pi a new flow-density relation with a triangular form that must respected by controllable batches. This relation can adequately represent the different situations and states of the flow circulating inside a BB-place. In fact it has a propagation speed of congestion and a critical density that are defined as follows: Definition 13 For a BB-place pi with γ(pi ) = (Vi , dmax i , Si , Φmax i ), the propaga- tion speed of congestion, denoted Wi and, the critical density dcri i are respectively defined by: Φmax i · Vi Wi = max (2) di · Vi − Φmax i Φmax i dcri i = (3) Vi  Definition 14 The flow-density relation that governs the dynamics of control- lable batches inside BB-places with γ(pi ) = (Vi , dmax i , Si , Φmax i ) is defined as follows: Extension of Batches Petri Nets by Bi-parts batch places 7 if 0 ≤ dr ≤ dcri  dr .Vi i ϕr = max (4) Wi .(di − dr ) if dcri i < dr ≤ dmax i  To allow a dynamic reconfiguration of flow systems with accumulation behav- ior 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 flow of the BB-place. The critical density and the maximum flow will be named respectively instantaneous critical density dcri i (τ ) and instan- taneous maximum flow φmax i (τ ) when the speed of a BB-place is time-varying, 0 ≤ vi (τ ) ≤ Vi , but the propagation speed of congestion is assumed to be con- stant, Wi . φ Φi max Vi φi max (τ) vi (τ) -Wi 0 dcrii di cri (τ) dmaxi d Fig. 3. Relation flow-density of a BB-place Proposition 15 Let a BB-place pi with γ(pi ) = (Vi , dmax i , Si , Φmax i ), and a cri speed vi (τ ). At time τ an instantaneous critical density di (τ ) and an instan- taneous maximum flow φmax i (τ ) are defined as follow: Wi .dmax i dcri i (τ ) = , (5) vi (τ ) + Wi φmax i (τ ) = vi (τ ).dcri i (τ ) (6) Φmax with 0 ≤ φmax i (τ ) ≤ Φmax i and i Vi ≤ dcri max i (τ ) ≤ di .  Proof. For a density dr = dcri cri i (τ ) > di , we have from (4): φmax i (τ ) = Wi .(dmax i − dcri i (τ )) (7) From both the expression of the instantaneous maximum flow in (6) and (7), we deduce: 8 Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin vi (τ ).dcri max i (τ ) = Wi .(di − dcri i (τ )) ⇒ Wi .dmax i = vi (τ ).dcri cri i (τ ) + Wi .di (τ ) = dcri i (τ ).(vi (τ ) + Wi ) Wi .dmax i ⇒ dcri i (τ ) = vi (τ ) + Wi  Note that the instantaneous critical density of BB-place pi at time τ depends on the instantaneous speed vi (τ ) and can also be denoted by dcrii (vi ). By the same, for the instantaneous maximum flow, can also be denoted by φmax i (vi ). Definition 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 (τ ) ≤ dcri i (τ ); – Cβr is called a congested controllable batch if its density is greater than the critical density of pi : dr (τ ) > dcri i (τ ).  3.2 Variation of speeds and flows in BPN We assume that the dynamic evolution of batches inside a BB-place pi takes into account the variation the maximum flow 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 ∈ P BB is a BB- place, vi ∈ [0, Vi ] is an instantaneous speed of BB-place and τ is the date of occurrence of this event. – A controlled flows event is a triplet (tj , φj , τ ); where tj ∈ T C ∪T B is a contin- uous or batch transitions, φj ∈ [0, Φj ] is a instantaneous flow 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 ). Extension of Batches Petri Nets by Bi-parts batch places 9 – 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. Vi φ Batch before speed variation Φmaxi vi Batch after speed variation φmaxi (vi) Cβ1 Cβ2 v’i φmaxi (v’i) Cβ2 Cβ3 Cβ1 Wi 0 d dcrii dcrii (vi) dcrii (v’i) dmaxi Fig. 4. Batch’s changes after a decreasing of BB-place speed 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 0 lower than dcri cri i (τ ) at speed vi (i.e., d1 < di (τ )). 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 0 greater than dcri cri i (τ ) at speed vi (i.e., d2 > di (τ )). When the BB-place 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. 10 Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin φ Vi Batch before speed variation Φmaxi Batch after speed variation v’i φ i (v’i) max Cβ1 Cβ2 vi φmaxi (vi) Cβ3 Cβ2 Cβ1 Wi 0 d dcrii dcrii (v’i) dcrii (vi) dmaxi Case 1 Case 2 Case 3 Fig. 5. Batch’s changes after a increasing of BB-place speed Variation of continuous or batch transition flow: States and characteris- tics of batches change when the maximum flow of continuous or batch transition is changed, we suppose that the flow φj of continuous or batch transition place tj changes at time τ from φj (τ ) to φ0j (τ ). Two situations must be considered: easier the flow 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 flow of continuous or batch transition changes, batch Cβ1 becomes a congested batch with new density and new speed Cβ10 (τ ) = (l1 , d01 , x1 , v10 ). – case 2: Cβ2 = (l2 , d2 , x2 , v2 ) is a congested controllable batch. When the flow of continuous or batch transition changes, batch Cβ2 becomes com- pletely congested, its density increases and its speed decreases Cβ20 (τ ) = (l2 , d02 , x2 , v20 ). φ φ Batch before flow variation Batch after flow variation φmaxi φmaxi φj (τ) vi vi Wi Cβ1 Cβ2 Wi ϕ (τ) Cβ2 φ'j(τ) Cβ2 φ'j(τ) ϕ (τ) = φj(τ) Cβ1 Cβ1 Cβ2 0 cri 0 cri d i (vi) dmaxi d d i (vi) dmaxi d a) b) Fig. 6. Variation of batch transition flow: decreasing and increasing of flow B) φ0j (τ ) > φj (τ ): two cases have to be considered (see Fig.6 b)) Extension of Batches Petri Nets by Bi-parts batch places 11 – case 1: Cβ1 = (l1 , d1 , x1 , v1 ) is a free controllable batch. When the flow 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 flow 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 Dynamics of controllable batch Let us first 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. Definition 17 The input (resp., output) flow of a batch place or continuous place pi at time τ is the sum of all flows entering (resp., leaving) the place and can be written, respectively, as: – φin P i (τ ) = P tj ∈• pi P ost(pi , tj ) · ϕj (τ ) = P ost(pi , ·) · ϕ(τ ). out – φi (τ ) = tj ∈p• P re(pi , tj ) · ϕj (τ ) = P re(pi , ·) · ϕ(τ ). i Definition 18 At time τ , various static functions can be applied on batches composing the marking of batch place pi : – Create. If the input flow of pi is not null, i.e., φin i (τ ) 6= 0, a controllable batch Cβr (τ ) = (0, dr (τ ), 0, vr (τ )) with dr (τ ) = φin i (τ )/vi (τ ) and vr (τ ) = vi (τ ), is created and added to the marking of pi , i.e., mi (τ ) = mi (τ ) ∪ {βr (τ )}. – 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 (τ ) \ {βr (τ )}. – Merge. If two batches with the same density and the same speed are in con- tact, 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 (τ ) \ {βh (τ )} – 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 : in- putting, moving and existing. Between two events, a batch can move in three different behaviors: free behavior, congestion behavior and decongestion behav- ior. 12 Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin (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 different 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 ac- cording 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 flow equals to the output flow of pi , or which is free with a lower batch flow than the output flow, 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 (τ )) φout φout with: dr0 (τ ) = dmax i − W i i ; vr0 (τ ) = d 0i (τ ) and xr0 (τ ) = Si r 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 conges- tion 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 dmax i −Wi i 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 (τ )) φout φout with dr (τ ) = dmax i − W i i , vr (τ ) = dri(τ ) and xr (τ ) = Si φout and vr0 (τ ) = vi , dr0 (τ ) = i vi and xr0 (τ ) = Si Extension of Batches Petri Nets by Bi-parts batch places 13 3.4 IB-state and events 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 in- variant state defined as follow: Definition 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 fired: tj ; e.2 a continuous place becomes empty: mni = 0; e.3 a discrete transition becomes enabled mni = 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 flow of a batch transitions is modified: φj (τ ) = φ0j (τ ); c.2 the speed of a BB-place is modified: 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 oc- curred 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 Computation of instantaneous firing flows To computate the instantaneous firing flows (IFF) ϕ, the speed vi of batch place pi and the flow 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 flow of continuous and batch transitions φj . Any admissible IFF vector ϕ, at m, is a feasible solution of the following linear set: 14 Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin – TN (m) ⊂ T C ∪ T B be the subset of continuous and batch transitions that are not enabled at m; – P∅ (m) = {pi ∈ P C | mi = 0} be the subset of empty continuous places; – PF (m) = {pi ∈ P BB | qi = Qi } be the subset of full BB-places.    (a) 0 ≤ ϕj (τ ) ≤ φj ∀tj ∈ T C ∪ T B (b) ϕj (τ ) = 0 ∀tj ∈ TN (m)      (c) C(pi , .).ϕ(τ ) ≥ 0 ∀pi ∈ P∅ (m)   (d) C(pi , .).ϕ(τ ) ≤ 0 ∀pi ∈ PF (m) (8) cri (e) P ost(p , .).ϕ(τ ) ≤ v (τ ).d (τ ) ∀pi ∈ P BB  i i    i (f ) P re(pi , .).ϕ(τ ) ≤ vi (τ ).di (τ ) ∀pi ∈ P BB out     (g) P re(pi , .).ϕ(τ ) ≤ vi (τ ).dcri i (τ ) ∀pi ∈ P BB   Proof. Constraints (a)-(d) are not changed compared to the linear program (1) in Def. 10. The constraint (e) in (1) becomes the constraint (e), it means that the flow arriving in a BB-place P ost(pi , .).ϕ should not exceed the maximum flow of BB-place pi which is now defined by φmax i = vi .dcri i . Then, the constraint (f) in (1) is now duplicated in two constraints (f) and (g) as follows: the constraint (f), implies that the total flow exiting BB-place pi P re(pi , .).ϕ should not be greater than the output flow vi .dout i generated by the output batch exiting the place. The constraint (g) implies that the total flow leaving the BB-place P re(pi , .).ϕ should not exceed the maximum flow φmax i = vi .dcri i of BB-place pi . In the case of a free batch, the flow exiting P re(pi , .).ϕ will be limited by the constraint (f), and in the opposite case, i.e a congested batch, the P re(pi , .).ϕ is limited in constraint (f) by a flow vi .douti which is greater than the maximum flow of BB-place vi .dcri i . Therefore in this case it is the constraint (g) will prevail, as it limits the flow exiting P re(pi , .).ϕ by the maximum flow. 3.6 Dynamics of a TrBPN 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 un- dergoes 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 firing flow 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 defined previously. Fig. 7 shows the most important steps of this dynamics. Extension of Batches Petri Nets by Bi-parts batch places 15 Initial marking Controlled Events NO at current date YES 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 Fig. 7. Dynamics of a triangular Batches Petri Nets 4 Example To illustrate the main contributions of this paper, we consider a traffic road intersection composed of three sections and a traffic light as shown by Figure 8. L2 Фout2 S2 Фin2 Section 1(1lane) 2(1lane) 3(1lane) Ф 1in S1 Li (km) 12 3.6 9 in Ф 3 Vmaxi (km/h) 120 120 60 L1 dmaxi (veh/km) 320 320 320 Φmaxi (veh/h) 7000 4080 4080 S3 Φini (veh/h) 0 3060 1040 L3 Φouti (veh/h) 4100 4080 4080 Фout3 Fig. 8. Traffic road intersection Section S1 has an output flow equal to 4100 veh/h. This output flow of S1 is divided into an input flow of S2 equal to 3060 veh/h and an input flow of S3 16 Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin 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 flow of section S1 is supposed null meaning that no vehicles enters the intersection. Some traffic events appear during the evolution of the traffic: 1- 10.8 minutes after the beginning, an accident appears at the end of section S2 reducing its output flow 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. V4= 120 dmax4= 320 s4 = 3.6 p4 Φ4= 3060 Φmax4 =4080 Φ5 = 4080 V3= 120 dmax3 = 320 p3 s3 = 12 t4 t5 Φ3= 0 Φmax3=7000 V5= 60 dmax5 = 320 t3 s5 = 9 p5 Φ 6= 1040 Φmax5=4080 Φ7 = 4080 t6 t7 p1 d1 = 0.1 t1 t2 d2 = 0.12 p2 Fig. 9. TrBPN of the traffic road intersection The TrBPN model for this traffic road intersection is shown in Figure 9. Discrete places p1 , p2 represent, respectively, the green and red traffic light. Delays d1 = 0.1h and d2 = 0.12h of discrete transitions t1 and t2 represent, respectively, the durations of green and red traffic light. BB-places p3 , p4 and p5 represent, respectively, sections S1 , S2 and S3 . Maximum flows Φ3 , Φ4 , Φ5 , Φ6 and Φ7 of batch transitions t3 , t4 , t5 , t6 and t7 represent the maximum input/output flow 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 traffic Extension of Batches Petri Nets by Bi-parts batch places 17 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, {OCβ3 (τ0 )}, 0, 0). The three traffic events cited above, correspond to controlled events in the TrBPN formalism that are defined, according to Section 3.2, by: – traffic event 1 is related to transition t5 : (t5 , 2040, 10.8); – traffic event 2 is related to BB-place p5 : (p5 , 20, 13.8); – traffic event 3 is also related to BB-place p5 : (p5 , 60, 27). To be able to compute the instantaneous firing flow using linear program- ming, we define as objective function to maximize the output flows of the sec- tions, i.e., the IFF of batch transitions, J = max {ϕ}. 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 firing flow vector solving of the linear program (9) below. Results obtained are ϕ3 (τ0 ) = 0, ϕ4 (τ0 ) = 3060, ϕ5 (τ0 ) = 0, ϕ6 (τ0 ) = 1040, and ϕ7 (τ0 ) = 0.   (a) 0 ≤ ϕ4 ≤ 3060   (a’) 0 ≤ ϕ6 ≤ 1040    (a”) 0 ≤ ϕ3 ≤ 0      (b) ϕ5 = ϕ7 = 0   (e) ϕ3 ≤ 7000 (9)  (e’) ϕ4 ≤ 4080     (e”) ϕ6 ≤ 4080     (f) ϕ4 + ϕ6 ≤ 4100    (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 flow of transition t5 is modified 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; 18 Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin (Ev9, delay: 0.01 h) Destruction of the output batch of BB-place p5 , OCβ500 = 0 . (m1, m2) (φ3,φ4, φ5, φ6, φ7) (1,0) ϕ3= 0, ϕ4 = 3060, ϕ5= 0 OCβ3= (12, 34.1, 12, 120) ϕ6 = 1040, ϕ7= 0 Cβ4= (0, 25.5, 0, 120) Cβ5= (0, 17.33, 0, 60) t1 , OCβ3 = 0 / 0.1 Cβ4= (0, 25.5, 0, 120) ϕ3= 0, ϕ4 = 0, ϕ5= 0 Cβ5= (0,17.33, 0, 60) (0,1) ϕ6 = 0, ϕ7= 0 Cβ4= (3.6, 25.5, 3.6, 120) Cβ4= OCβ4/ 0.03 OCβ4= (3.6, 25.5, 3.6, 120) ϕ3= 0, ϕ4 = 0, ϕ5= 3060 Cβ5= (3.6, 17.33, 3.6, 60) (0.1) ϕ6 = 0, ϕ7= 0 OCβ4’= (0, 176.96, 3.6, 11.52) Cβ4= (3.6, 25.5, 3.6, 120) φ5 = 2040 /0.03 Cβ4= (3.6, 25.5, 3.6, 120) (0,1) ϕ3= 0, ϕ4 = 0, ϕ5= 2040 OCβ4’= (0, 176.96, 3.6, 11.52) ϕ6 = 0, ϕ7= 0 Cβ5= (3.6, 17.33, 5.4, 60) OCβ4’= (0.22, 176.96, 3.6, 11.52) OCβ4’ = 0 / 0.04 ϕ3= 0, ϕ4 = 0, ϕ5= 0 Cβ5= (3.6, 17.33, 7.8, 60) (0,1) ϕ6 = 0, ϕ7= 0 Cβ5= (3.6, 17.33, 9, 60) t2 , Cβ5 = OCβ5 / 0.02 ϕ3= 0, ϕ4 = 0, ϕ5= 0 OCβ5= (3.6, 17.33, 9, 60) (1,0) ϕ6 = 0, ϕ7= 1040 OCβ5= (2.6, 17.33, 9, 20) v5 = 20 /0.01 ϕ3= 0, ϕ4 = 0, ϕ5= 0 OCβ5= (2.6, 17.33, 9, 20) (1,0) ϕ6 = 0, ϕ7= 346.6 OCβ5= (0.6, 17.33, 9, 20) t1/ 0.1 Cβ5= (0.6, 17.33, 9, 20) ϕ3= 0, ϕ4 = 0, ϕ5= 0 OCβ5’= (0, 320, 9, 0) (0,1) ϕ6 = 0, ϕ7= 0 OCβ5’= (0.6, 320, 9, 0) t2 , v5 = 60 / 0.12 ϕ3= 0, ϕ4 = 0, ϕ5= 0 Cβ5’= (0.6, 320, 9, 0) (1,0) OCβ5’’= (0, 17.33, 9, 60) ϕ6= 0, ϕ7= 1040 OCβ5’’= (0.6, 17.33, 9, 60) OCβ5’’ = 0 / 0.01 ϕ3= 0, ϕ4 = 0, ϕ5= 0 (1,0) ϕ6= 0, ϕ7= 0 Fig. 10. Evolution graph of the TrBPN model We detail now two events of the set of timed events that illustrate our con- tributions in TrBPN: a modification of maximum flow 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 flow of batch transition t5 is reduced to 2040 veh/h. The output flow of the output batch OCβ4 is now higher then the maximum flow 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 (τ3 ) = (3.6, 25.5, 3.6, 120) and OCβ40 (τ3 ) = (0, 176.96, 3.6, 11.52) according to Def.18. The batch Cβ4 is a free batch while Extension of Batches Petri Nets by Bi-parts batch places 19 OCβ40 is congested batch. The batch Cβ5 (τ3 ) = (3.6, 17.33, 5.4, 60) of BB-place p5 is also a free batch and continues to move freely inside BB-place keeping its length, only its position change. This case corresponds to the case 1 of A) in the section of variation of flow (see Section 3.2). 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 (τ3 ) = 0,ϕ4 (τ3 ) = 0, ϕ5 (τ3 ) = 2040, ϕ6 (τ3 ) = 0 and ϕ7 (τ3 ) = 0).    (a) 0 ≤ ϕ5 ≤ 2040  (a’) 0 ≤ ϕ3 ≤ 0   (b) ϕ4 = ϕ6 = ϕ7 = 0 (10) (f) ϕ ≤ 3060  5    (g) ϕ5 ≤ 4080  At Ev6, there is a controlled event that decreases the batch place speed (v5 = 20 km/h). The output batch OCβ5 (τ6 ) = (2.6, 17.33, 9, 20) is a free batch and has its speed reduce to 20 km/h. In this case, the speed reduction do not change. The state of the output batch OCβ5 (τ6 ) remains in a free batch. However, this speed reduction implies in a reduction of the flow of the batch to 346.6 veh/h. This case corresponds to the case 3 of A) in the section of decrease in the maximum speed of BB-place (see Section 3.2). We recompute the IFF of all enabled continuous and batch transitions and we obtain (ϕ3 (τ6 ) = 0,ϕ4 (τ6 ) = 0, ϕ5 (τ6 ) = 0, ϕ6 (τ6 ) = 0 and ϕ7 (τ6 ) = 346.6). We remark that the reduction of the flow of the batch OCβ5 (τ6 ) is observed in the IFF of ϕ7 (τ6 ). 5 Conclusion We proposed in this paper an extension of Batches Petri Nets by a new definition 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 flow parameter. This maximal flow, the speed and the density allow us to define a new dynamic equations of flow-density. These equations represent more accurately the bi-part behavior observed in the systems flow based on the triangular diagram. To include this bi-part behavior in this new extension of BPN, we redefined some concepts like, the states of batches, conditions of enabling and firing transitions. Additionally, a definition of controlled events was proposed in this paper and it allows a manual control of the speed of BB-place and the maximal flow 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 traffic in transportation systems than BPN. The next step is to use the control laws already defined in the literature to test and analyze the performance of these laws (such as the 20 Radhia Gaddouri, Leonardo Brenner, and Isabel Demongodin Ramp Metering System (RMS), and Variable Speed Limit (VSL)) in order to reduce congestion. References 1. H. Alla and R. David: Continuous and hybrid Petri Nets: Journal of Circuits, Sys- tems, and Computers. 8, 159–188 (1998) 2. I. Demongodin and N. Audry and F. Prunet: Batches Petri nets: IEEE International Conference on Systems, Man and Cybernetics, pp. 607–617, 1993. 3. I. Demongodin: Generalised Batches Petri Net: hybrid model for high speed systems with variable delays: Discrete Event Dynamic Systems: 11, 137–162 (2001) 4. R. David and H. Alla: Discrete, Continuous, And Hybrid Petri Nets: Springer Verlag, (2005) 5. J. LeBail and H. Alla and R. David: Hybrid Petri Nets: Revue TSI. 11, 95–120 (1992) 6. C.F. Daganzo: The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory: Transportation Research Part B: Methodological 4, 269–287 (1994) 7. N. Audry and I. Demongodin and F. Prunet: Modelling of high throughput pro- duction lines by using generic models described in Batches Petri nets: International Conference on Robotics and Automation, pp. 807–812, USA (1994) 8. M. Papageorgiou and C. Diakaki and V. Dinopoulou and A. Kotsialos and Y. Wang: Review of road traffic control strategies: Proc. of the IEEE: 12, 2043–2067 (2003) 9. R. Gaddouri and L. Brenner and I. Demongodin: Mesoscopic event model of highway traffic by Batches Petri nets: 6th International Conference on Management and Control of Production and Logistics, pp. 317-324., Fortaleza, Brazil (2013) 10. I. Demongodin: Modeling and analysis of transportation networks using Batches Petri Nets with controllable batch speed: 30th International Conference on Applica- tions and Theory of Petri Nets (Lecture Notes in Computer Science): 5606, springer, pp. 204–222., Berlin(2009) 11. N. Audry and F. Prunet: Controlled batches Petri Nets: International Conference on Systems, Man and Cybernetics, pp. 1849–1854.,Canada(1994) 12. I. Demongodin and A. Giua: Linear programming techniques for analysis and con- trol of batches Petri nets: 10th International Workshop on Discrete Event Systems, pp. 1–6., Berlin, Germany(2010) 13. I. Demongodin and A. Giua: Dynamics and steady state analysis of controlled Generalized Batches Petri Nets: INonlinear Analysis: Hybrid Systems. 12, 33-34 (2014). 14. F. Balduzzi and A. Giua and G. Menga: First-order hybrid Petri nets: a model for optimization and control: IEEE Transaction on Robotic and Automation. 4, 382–399 (2003).