Jean Gregoire

Xiangjun Qian

Emilio Frazzoli

Arnaud De

La Fortelle

Tichakorn Wongpiromsarn

Capacity-aware back-pressure traffic signal control

The control of a network of signalized intersections is considered. Previous work demonstrates that the so-called back-pressure control provides stability guarantees, assuming infinite queues capacities. In this paper, we highlight the failing of current back-pressure control under finite capacities by identifying sources of non work-conservation and congestion propagation. We propose the use of a normalized pressure which guarantees work conservation and mitigates congestion propagation, while ensuring fairness at low traffic densities, and recovering original back-pressure as capacities grow to infinity. This capacity-aware back-pressure control allows to improve performance as congestion increases, as indicated by simulation results, and keeps the key benefits of back-pressure: ability to be distributed over intersections and O(1) complexity.

I. INTRODUCTION

Congestion is one of the major problems in today's metropolitan transportation networks. Before investigating investments in order to enhance the capacity of the network, or policies to reduce the traffic load, one must wonder whether the network is used at its maximum capacity. Vehicle automation is expected to enable much more precise and intelligent coordination between vehicles, possibly reducing congestion [START_REF] Dresner | A multiagent approach to autonomous intersection management[END_REF]. However, automated cars are not currently ready for large commercial deployment. Human-driven cars can only be coordinated by traffic signals: more complex scheduling at intersections would require automation to be safe. That is why it is of high interest to study the theoretical maximum throughput of a network of intersections coordinated by traffic lights.

Traffic lights at intersections alternate the right-of-way of users (e.g., cars, public transport, pedestrians) to coordinate conflicting flows. A particular set of feasible simultaneous rights of way, called a phase, is decided for a certain period of time [START_REF] Papageorgiou | Review of road traffic control strategies[END_REF]. Controlling a traffic light consists of designing rules to decide which phase to apply over time.

Pre-timed policies activate phases according to a timeperiodic pre-defined schedule. There is much previous work on designing optimal pre-timed policies. However, such policies are not efficient under changing arrival rates which require adaptive control. Most used adaptive traffic signal control systems include SCOOT [START_REF] Hunt | The scoot on-line traffic signal optimisation technique[END_REF], SCATS [START_REF] Lowrie | Scats, sydney co-ordinated adaptive traffic system: A traffic responsive method of controlling urban traffic[END_REF], PRODYN [START_REF] Henry | The prodyn real time traffic algorithm[END_REF], RHODES [START_REF] Mirchandani | A real-time traffic signal control system: architecture, algorithms, and analysis[END_REF], OPAC [START_REF] Gartner | Opac: A demand-responsive strategy for traffic signal control[END_REF] or TUC [START_REF] Diakaki | A multivariable regulator approach to traffic-responsive network-wide signal control[END_REF]. These systems update some control variables of a configurable pre-timed policy on middle term, based on traffic measures, and apply it on short term. Control variables may include phases, splits, cycle times and offsets [START_REF] Papageorgiou | Review of road traffic control strategies[END_REF]. Such algorithms may differ in the way optimization is carried out (e.g., linear/dynamic programming, exhaustive enumeration) and in the modeling approach (e.g., queuing network model [START_REF] Osorio | A surrogate model for traffic optimization of congested networks: an analytic queueing network approach[END_REF], cell transmission model [START_REF] Lo | Dynamic network traffic control[END_REF], store-and-forward [START_REF] Aboudolas | Store-andforward based methods for the signal control problem in large-scale congested urban road networks[END_REF], petri nets [START_REF] Di Febbraro | On applying petri nets to determine optimal offsets for coordinated traffic light timings[END_REF]). Many major cities currently employ these systems which proved to be able to yield various benefits, including travel time and fuel consumption reduction, as well as safety improvements [START_REF] Shepherd | A review of traffic signal control[END_REF].

More recently, based on the seminal paper [START_REF] Tassiulas | Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks[END_REF], feedback controls have been proposed both in the case of deterministic arrivals [START_REF] Varaiya | The max-pressure controller for arbitrary networks of signalized intersections[END_REF], or stochastic arrivals [START_REF] Varaiya | A universal feedback control policy for arbitrary networks of signalized intersections[END_REF], [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF]. Time is slotted and at every time slot, a feedback controller decides the phase to apply based on current queue length estimation. This requires real-time queues estimation, but it enables to be much more reactive than other traffic controllers and to have stability guarantees. Reference [START_REF] Tassiulas | Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks[END_REF] introduced the so-called back-pressure control which computes the control to apply based on queue lengths, and can achieve provably maximum stability. This algorithm was originally applied to wireless communication networks [START_REF] Neely | Dynamic power allocation and routing for satellite and wireless networks with time varying channels[END_REF], [START_REF] Neely | Dynamic power allocation and routing for time-varying wireless networks[END_REF], and some effort has been required to apply the approach in the context of a network of intersections [START_REF] Varaiya | A universal feedback control policy for arbitrary networks of signalized intersections[END_REF], [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF]. A key feature of this algorithm is that it can be completely distributed over intersections, in the sense that it can be implemented by running an algorithm of complexity O(1), requiring only local information, at each intersection.

However, the strong assumption of current back-pressure traffic control algorithms is the unboundedness of queue capacities. Indeed, when the queue at the entry of an intersection grows so much that it reaches the upstream intersection, congestion will propagate: this is a non-negligible and easy to observe phenomenon. The phenomenon is commonly referred as blocking in queuing theory, and many blocking types can be considered [START_REF] Perros | Queueing networks with blocking[END_REF]. In worst-case scenario, blocking results in deadlocks whose resolution can be of high complexity [START_REF] Kundu | Deadlock free buffer allocation in closed queueing networks[END_REF], [START_REF] Gregoire | Priority-based coordination of robots[END_REF]. An off-line optimization of a pre-timed policy is proposed in [START_REF] Osorio | A surrogate model for traffic optimization of congested networks: an analytic queueing network approach[END_REF], [START_REF] Osorio | An analytic finite capacity queueing network model capturing the propagation of congestion and blocking[END_REF]. The standard queuing network model with fixed service times of servers [START_REF] Bocharov | Queueing theory[END_REF] is modified to account for blocking causing inter-queue interactions. The notion of effective service rate aims at accounting for both service and blocking. An expression of the blocking probability of each queue, i.e., the probability of the queue to be full, can be derived. The idea is to include in the optimized objective function penalties for high blocking probability. The method proved to be efficient to improve performance as congestion increases. However, it is for off-line optimization of fixedcycle signals for a certain scenario (given arrival rates). In this paper, we aim at building a feedback control that can adapt on-line to varying situations. Some works applied to wireless communication networks have proposed feedback controls that can achieve maximum throughput under queue boundedness constraints [START_REF] Giaccone | Throughput region of finitebuffered networks[END_REF]. However, they suppose the absence of arrivals at internal nodes, cannot be easily implemented, and are thus not suitable for our application.

This paper proposes to keep the fundamental idea of backpressure control, that is pressure computation at every node of the network, in order to keep the resulting key benefits: ability to be distributed over intersections and O(1) complexity. However, we propose to take into account the queue capacities for the computation of pressures. The idea is to normalize pressures, so that full queues all exert the same normalized maximal pressure independently from their capacity. Following the idea of [START_REF] Giaccone | Throughput region of finitebuffered networks[END_REF], this normalization is expected to decrease the blocking probability.

The paper is organized as follows. Section II describes the phase-based queuing network model. Section III presents the current back-pressure traffic signal control of [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF] and proves its lack of work conservation and its inability to avoid congestion propagation under finite queue capacities. Section IV proposes the use of normalized pressures and proves the benefits in terms of work-conservation and congestion mitigation. Simulations of Section V show the efficiency of the approach proposed in this paper and Section VI concludes and opens perspectives.

II. MODEL

A. Queuing network topology

The network of intersections is modelled as a directed graph of nodes (N a ) a∈N and links (L j ) j∈L . Nodes represent roads with queuing vehicles, and links enable transfers from node to node. This is a standard queuing network model.

N 2 N 1 Q 1 Q 2 C 4 N 4 C 3 Q 3 Q 4 N 3 C 8 N 8 C 7 Q 7 Q 8 N 7 C 6 N 6 C 5 Q 6 Q 5 J i λ 1 λ 2 λ 5 λ 6 λ 4 λ 3 λ 7 λ 8 N 5 C 1 C 2 Q' 5 Q' 6 Q' 3 Q' 4 Q' 1 Q' 2 Q' 8 Q' 7 N' 5 N' 6 N' 3 N' 4 N' 8 N' 7 N' 2 N' 1
Fig. 1: A junction with 4 incoming nodes and 4 outgoing nodes which corresponds to the intersection depicted in Figure 2.

Every signalized intersection is modelled as a server managing a junction which consists of set of links. Junctions (J i ) i∈J are supposed to form a partition of links. For every junction J, I(J) and O(J) denote respectively the inputs and the outputs of J. Inputs (resp.outputs) of junction J are nodes N such that there exists a link L ∈ J pointing from (resp. to) N .

The reader should consider the introduction of junctions in the model as an overlay of the queuing network model.

For the sake of simplicity, we do not represent links in the queuing network representation of Figure 1 and we assume that at every junction, there exists a link from any input to any output. If the link does not exist physically, the flow through it will be always zero.

Every server maintains an internal queue for every input/output, and server work enables to transfer vehicles from an input to an output of the junction. As standard in queuing network control, time is slotted, and each (time) slot k ∈ N maps to a certain period of time. Due to routing of vehicles, there are several queues at node N a and Q ab (k) denotes the number of vehicles at node N a in slot k waiting to leave node

N a for N b . Q a (k) := b Q ab (k)
denotes the total number of vehicles waiting at node N a .

B. Arrival and routing processes

Let A a (k) denote the number of vehicles that exogenously arrive at node N a during slot k. We assume that the arrival process A a (k) is rate-convergent with rate λ a which represents the expected number of arrivals per time slot at node N a in the long-term. The arrival process is not controlled, it is an exogenous process. There are also endogenous vehicle transfers allowed by links at junctions. We let f ca (k) denote the number of vehicles leaving N c for N a during slot k. When a vehicle enters node N a at slot k endogenously (originating from another node), or exogenously (inserted into the network through the arrival process), it increments one of the queues Q ab (k), unless it leaves the network at N a . We assume that the ratio of vehicles added to Q ab (k) is rate-convergent with rate r ab ∈ [0, 1]. Rates r ab represent the long-term routing ratios of vehicles entering N a . Because some vehicles leave the network at N a and are not added to some queue, the routing ratios do not necessarily sum to 1 and 1b r ab ≥ 0 represents the exit rate at node N a . The queue dynamics is as follows:

Q ab (k+1) = Q ab (k)-f ab (k)+r ab (k) c f ca (k) + A a (k) , (1)
where r ab (k) is rate-convergent with rate r ab .

C. Phase-based control

At every time slot, the service offered by servers at junctions is controlled by activating a given signal phase p i at every junction J i from a predefined finite set of feasible phases P i . When phase p i is activated during one slot, µ ab (p i ) represents the maximum number of vehicles transferred from N a to N b during that slot. Figure 2 depicts the 4 typical phases of a 4 inputs/4 outputs junction. Each global phase p = (p i ) i∈J results in a different service µ(p).

Two phenomena may affect the actual number of vehicles being transferred. First, only the vehicles which are currently at a queue at the beginning of the time slot can leave the queue during that slot. Second, and this is the phenomenon highlighted in this paper, above a certain queue length, a node is full and cannot accept vehicles any more.

N 1 N 2 N 3 N 4 N 5 N 6 N 7 N 8 N 1 N 2 N 3 N 4 N 5 N 6 N 7 N 8 N 1 N 2 N 3 N 4 N 5 N 6 N 7 N 8 N 1 N 2 N 3 N 4 N 5 N 6 N 7 N 8 (a) (b) (c) (d)
Fig. 2: A typical set of feasible phases at a junction. For phase (c), we have µ 26 (p (c) ) > 0 and µ 37 (p (c) ) > 0.

Let p(k) denote the phase control through time (the only controlled variable), the number of vehicles transferred from N a to N b during slot k is:

f ab (k) = δ(Q b (k), C b ) min(Q ab (k), µ ab (p(k)) (2)
The function δ(q, c) models blocking due to downstream congestion, and returns 1 if q < c, and 0 else. C b is referred as the capacity of node N b : it is the maximum queue length from which the node cannot accept vehicles any more. We say that node

N b is full at time slot k if Q b (k) ≥ C b .
The blocking phenomenon is illustrated in Figure 3. Note that this simple binary model is conservative because in reality, even if a node is full at the beginning of the time slot, some vehicles may be able to enter this node if the downstream junction gives the right-of-way to vehicles in that node. This effect will not be considered in this paper. Fig. 3: Since the red-colored middle node is full, it cannot accept vehicles any more, even if the traffic light gives the right-of-way to vehicles going to this node.

III. FAILING OF BACK-PRESSURE CONTROL UNDER BOUNDED QUEUES CONSTRAINTS

A. Back-pressure control

Back-pressure control consists of a feedback control law that decides the phase to apply at every time slot based on current queues lengths. Let φ denote the control law, the phase control p satisfies at every time slot k:

p(k) = φ(Q(k)) (3)
where Q(k) denotes the network state at slot k, that is the queues lengths matrix [Q ab (k)] a,b∈N . The control law maps the current network state to the phase to apply. The backpressure control law is defined component-wise for each junction as described by Algorithm 1. It only requires aggregated queues lengths Q a (k) and binary variables d ab (k) ∈ {0, 1} indicating the presence of vehicles waiting at N a to leave N a for N b . The latter can be measured using loop detectors on the dedicated lanes at the entry of the junction.

Algorithm 1 Back-pressure control law at junction

J i for N a ∈ I(J i ) ∪ O(J i ) do Π a (k) ← P a (Q a (k)) end for for N a ∈ I(J i ), N b ∈ O(J i ) do 5: W ab (k) ← d ab (k) max (Π a (k) -Π b (k), 0) end for p i (k) ← arg max pi∈Pi a,b W ab (k)µ ab (p i ) return Phase p i (k) to apply in time slot k at junction J i
The idea of back-pressure control is to compute pressures at every node of the network based on queue lengths and to allow flows with a high upstream pressure and a low downstream pressure, like opening a tap. Current back-pressure traffic signal control [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF], [START_REF] Varaiya | A universal feedback control policy for arbitrary networks of signalized intersections[END_REF] uses Algorithm 1 with linear pressure functions P a (Q a ) = Q a : the pressure exerted by a node equals its queue length. Algorithm 1 proceeds as follows:

• First, pressures at input/output nodes are computed. If linear pressures are used, the pressure exerted by node

N a at slot k is P a (Q a (k)) = Q a (k) • Then, the pressure difference associated to each flow from an input N a to an output N b of the junction is computed, it equals max (Π a (k) -Π b (k), 0
), and it is multiplied by d ab (k) to account for the presence/absence of vehicles waiting at N a willing to leave N a for N b . • For each phase p i ∈ P i , the total pressure release allowed by p i is computed: it equals the sum of pressure differences through each link of the junction weighted by the flow of vehicles that can be transferred through the corresponding link when phase p i is activated, that is

a,b W ab (k)µ ab (p i )
• Finally, the returned phase p i (k) is the phase p i maximizing the weighted sum

a,b W ab (k)µ ab (p i ).
This control law is proved to be stability-optimal under infinite capacities, i.e., the queuing network is stabilized for all arrival rates that can be stably handled considering all control policies. The two key properties of back-pressure control are its ability to be distributed over junctions and its O(1) complexity. Under bounded queues constraints, with linear pressure functions, pressure at N a saturates at P a = C a for Q a = C a . In the following, we show that this saturation at different levels for every node may result in a loss of work conservation and congestion propagation as presented in the sequel.

B. Loss of work conservation

First of all, the notion of work and work-conservation is defined in our context. We say that the server at junction J i works during slot k if there are transfers through links of the junction during the slot. A control is work-conserving if the existence of an input N a and an output N b such that Q ab (k) > 0 and Q b (k) < C b is sufficient to ensure that the server of the junction works during slot k. A loss of workconservation is clearly a sign of inefficiency. Due to limited queues capacities, back-pressure control under linear pressure functions is not work-conserving as stated in Theorem 1, with a concrete example depicted in Figure 4.

Theorem 1 (Loss of work-conservation under back-pressure). Under bounded queues constraints, back-pressure control is not work-conserving in the general case.

Proof. Consider the network of Figure 4. Suppose that the middle junction has two feasible phases: p ab with µ ab (p ab ) > 0, and p cd with µ cd (p cd ) > 0. Suppose that at time slot

k, Q b (k) = C b , Q a (k) > C b and Q c (k) < Q d (k).
Then, W ab (k)µ ab (p ab ) > 0 and W cd µ cd (p cd ) = 0. Hence, the phase to apply at the middle junction computed by Algorithm 1 is

p ab . Since, Q b (k) = C b , Equation (2) implies that f ab (k) = 0.
As a result, the middle junction will not work, because the selected phase is p ab , but due to downstream congestion, transfers to N b are not feasible. However, choosing phase p cd would have enabled the server to work. The proved loss of work conservation is an important property since the subsequent inefficiency results in congestion propagation as highlighted in the following.

Q a > Q b Q b Q d Q c < Q d

C. Congestion propagation and deadlocks

As depicted in Figure 5, loss of work conservation may result in congestion propagation, both to the node which has the right-of-way but cannot empty because of downstream congestion, and to the node which has not the right-of-way.

Q a > Q b Q b Q d Q c < Q d
Fig. 5: Congestion propagation due to a loss of work conservation. Since N b is full f ab (k) = 0 and N a is not emptied, so congestion propagates to N a . Moreover, N c is also not emptied because vehicles do not have the right-of-way under the selected phase, so congestion propagates to both nodes N a and N c .

In worst-case scenario, such congestion propagation can lead to deadlocks, as depicted in Figure 6.

Q a 1 > 2Q b 1 Q a 2 > 2Q b 2 Q a 3 > 2Q b 3 Q b 3 Q b 2 Q b 1
Fig. 6: A deadlock for back-pressure control. Q 1 a , Q 2 a and Q 3 a will be ever growing.

IV. CAPACITY-AWARE TRAFFIC CONTROL

The following presents our approach to take into account the limited queues capacities by using normalized pressures in back-pressure control to enforce work-conservation and mitigate congestion propagation. First of all, the reasons that motivate devising convex normalized pressures are introduced in the sequel.

A. Purpose of a convex normalized pressure and criteria 1) Purpose of a convex pressure: When a node approaches full occupancy, every additional vehicle is more and more problematic as the queue grows. That is why it makes sense to define a pressure such that the marginal pressure, i.e., the increase in pressure due to an additional vehicle, rises as the queue grows. This remark justifies the use of a convex pressure.

2) Purpose of a normalized pressure: When a node N b is full, it does not make sense to have a node N a such that P a -P b > 0, since the "tap" associated to the flow from N a to N b cannot be opened. That is why we propose to normalize the pressures so that any full node will exert a pressure that equals 1, while an empty node does not exert any pressure.

The simplest normalization that could be carried out would consist of using relative pressure functions P a (Q a ) = Q a /C a . However, in order to have strictly convex pressures and to respect the fairness requirement proposed below, the normalization will be slightly more complex.

3) Requirement for fairness at low traffic density: At low traffic density, there is no reason to be unfair. Indeed, even a random choice of phases would stabilize the network. So, unfairness would not be justified by any global stabilization goal. Suppose that we use relative pressures functions P a (Q a ) = Q a /C a , then an additional vehicle causes an increase in pressure of 1/C a , i.e., as high as capacity decreases. However, at low traffic density the marginal pressure should be uniform over nodes. We say that pressure functions {P a (Q a ) : a ∈ N } are fair at low traffic density if:

∃K > 0 : ∀a ∈ N , dP a dQ a (0) = K (4)
4) Requirements for stability guarantees conservation: Finally, it is important to ensure that as capacities grow to infinity, the original back-pressure control is recovered, to take advantage of the stability guarantees in the context of infinite capacities. That is why a requirement for the pressure function P a (Q a ) is to be linear for Q a /C a → 0. If pressure functions are fair, P a (Q a ) = KQ a +o a (Q a /C a ) in Landau notation, and the pressure function is linear at low occupancy. As a result, if the queues are always much under maximum occupancy, i.e., if the infinite queues capacities assumption is valid, the backpressure control and its stability guarantees are recovered. Now we have presented criteria that should respect the modified pressure in order to be capacity-aware and fair at low traffic density, we propose in the following a convex normalized pressure which respects the above criteria.

B. Example of normalized pressure

The proposed pressure function should just be considered as an example of a pressure function fulfilling the presented requirements:

P a (Q a ) = min   1, Qa C∞ + 2 -Ca C∞ Qa Ca m 1 + Qa Ca m-1    (5)
At low occupancy, the pressure at node N a is linear:

P a (Q a ) ≃ Q a /C ∞ ,
so pressure functions are fair and respect the requirement for stability guarantees conservation. The function is convex: the slope of the pressure increases as occupancy grows. Pressure over congestion threshold is normalized: ∀a ∈ N , ∀Q a ≥ C a , P a (Q a ) = 1. The shape of pressure functions for two different capacities is depicted in Figure 7. One can observe that the pressure function leaves the initial linear behavior at lower occupancy as capacity decreases.

The parameters m and C ∞ determine the shape of pressure functions; m locates the transition from the linear regime, while C ∞ determines the slope of the pressure at low occupancy, and is such that a node which capacity is C ∞ will have a linear pressure. We assume that all capacities are lower than C ∞ and m > 1.

C. Work-conservation

As expected, pressure normalization enables to ensure workconservation. This can be easily visualized in Figure 8 where one can observe that the deadlock of Figure 6 is resolved. In the following, we prove Theorem 2 which states workconservation under convex normalized pressure.

Theorem 2 (Work-conservation under normalized pressures).

Assume that pressure functions P a are increasing functions taking values in [0, 1], P a (0) = 0 and P a (C a ) = 1. Assume also that in case of equality, the arg max of Line 7 in Algorithm 1 privileges phases p i such that there exists a, b with Q ab (k) > 0, Q b (k) < C b and µ ab (p i ) > 0. Then, back-pressure control using normalized pressures is workconserving.

Proof. Suppose that back-pressure control using normalized pressure functions is not work-conserving. Then, there exists a server at a junction J i which does not work during some slot k, while there exists a phase pi such that for some a, b,

µ ab (p i ) > 0, Q ab (k) > 0 and Q b (k) < C b .
Let p i (k) denote the phase at junction J i computed by Algorithm 1. If the server at the junction does not work during slot k under phase p i (k), then for all c, d such that

µ cd (p i (k)) > 0 we have either Q cd (k) = 0, or Q d (k) ≥ C d (
otherwise, the server would work). In the first case, d cd (k) = 0, and in the second case,

Π d (k) = 1. Since W cd (k) = d cd (k) max (Π c (k) -Π d (k), 0) and Π c (k) ≤ 1, we necessarily have W cd (k) = 0. As a result, for phase p i (k), we have cd W cd (k)µ cd (p i (k)) = 0.
On the other hand, by positivity of flows and weights, we Fig. 8: Work-conservation and deadlock resolution using normalized pressure functions. The pressure at full nodes equals 1, while it is strictly lower than 1 at non-full nodes. As a result, the phase computed by Algorithm 1 enables to empty full nodes.

have cd W cd µ cd (p i ) ≥ 0. If cd W cd (k)µ cd (p i ) > 0, it is absurd because pi should have been selected by Algorithm 1 instead of p i (k). If cd W cd (k)µ cd (p i ) = 0, it is also absurd because cd W cd (k)µ cd (p i ) = cd W cd (k)µ cd (p i (k)),

V. SIMULATION RESULTS

In this section, we compare the performance of our proposed capacity-aware back-pressure control with current backpressure [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF], [START_REF] Varaiya | A universal feedback control policy for arbitrary networks of signalized intersections[END_REF] and a non-optimized fixed cycle traffic light given as reference.

A. Simulation setup

We have implemented our traffic signal control schemes on the top of the traffic simulator SUMO (Simulation of Urban MObility) [START_REF] Krajzewicz | Recent development and applications of SUMO -Simulation of Urban MObility[END_REF]. SUMO is a widely recognized open-source traffic simulation package including a traffic simulator as well as supporting tools. The simulator is microscopic, inter-and multi-modal, space-continuous and time-discrete, providing a fair approximation of real world traffic scenarios.

We adopt a non-uniform network with several types of roads and intersections (Figure 9). All roads are bi-directional. Roads V2, V4, V6, V8, H1, H3, H5 and H7 possess only one lane on each direction while the rest of roads have two lanes. Close to the intersection, each road has an additional dedicated left-turn lane. Due to the difference in the number of lanes, there are four types of intersections (Figure 10). Each intersection has four phases, as described in Figure 2. The network is open as vehicles may leave and enter the system at all roads. We generate traffic flows using ActivityGen available in SUMO supporting tools. ActivityGen considers the road network as a city. It takes as inputs, in particular, the city population, the spatial distribution of the population, the working zones, and produces traffic flows with on/off peak patterns. In our network, we set the habitation area to northern city (area in blue rectangle in Figure 9) and the working zone resides in the southern city (area in red dashed rectangle in Figure 9). We design the test scenarios with a city population ranging from 10000 to 39000 people. We simulate the traffic during a typical 3-hour morning peak (7 am to 9 am). An exemplary histogram of vehicle arrivals in the morning peak is given in Figure 11. All Vehicles adopt the default vehicle model of SUMO. A python interface, called TraCI, is provided in SUMO package which enables real-time traffic control. In particular, queues lengths can be retrieved by deploying loop detectors and the phase of traffic lights (more precisely the program) can be updated. We implemented control schemes as a python application. The application interacts with SUMO through TraCI to retrieve queue lengths and to control traffic lights. Three control schemes have been implemented:

1) Current back-pressure of [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF], [START_REF] Varaiya | A universal feedback control policy for arbitrary networks of signalized intersections[END_REF]: the duration of a time slot is set to 15 seconds, including 4 seconds of yellow phase. 2) Capacity-aware back-pressure: the capacity of roads is computed using the lane length retrieved through TraCI and the vehicle length and gap. The length of the default vehicle in SUMO is 5 meters and the minimum gap is 2.5 meters. As a result, the capacity of a lane is its length in meters divided by 7. A complete test run compares the three control schemes under 4 different populations. To ensure comparability, the same random seed is given to ActivityGen module for all simulations of a test run.

B. Results and analysis

Figure 12 depicts the evolution of the number of vehicles in the network under four population scenarios. We also measure periodically the total time spent by vehicles averaged over vehicles currently in the network, which is a good performance indicator, since users of the network want to minimize their travel time. The evolution of the total time spent is depicted in Figure 13. We observe that for a small population of 10000, all control schemes have a similar performance, even if the queue is slightly greater under the non-optimized fixed cycle control scheme. For a population of 27000, back-pressure and capacity-aware back-pressure have similar performance, while they both outperform the fixed-cycle control scheme. As population grows (leading to a growth of flows through the network), for a population of 33000 and 39000, capacity-aware back-pressure outperforms back-pressure control. Therefore, the performance gain of capacity-aware back-pressure mainly occurs at heavy load. Figure 14 presents a typical configuration that may occur under back-pressure control, while it is alleviated in capacity-aware back-pressure control. Figure 14(a) provides a bird eye view on the intersection between H5 and V4. H5 is a 2-lane main street and V4 has only one lane. V4 has reached its full capacity downstream. Figure 14(b) offers a closer look on the intersection. Since back-pressure control does not consider the capacity of roads, the left turn phase (phase (c) of Figure 2) of H5 is always activated because the queue difference of corresponding lanes is among the largest. However, it is inefficient and not work-conservative to activate this phase as no vehicle can join the downstream node of V4. Under the same situation, with capacity-aware backpressure control scheme, the pressure on the downstream node of V4 will be 1, and phase (a) would be activated instead of phase (c) allowing vehicles on H5 going straight to continue their journey (work-conservation is recovered). This qualitative analysis on the example of Figure 14 is in accordance with quantitative results that show an increase in the average total time spent for back-pressure for a population of 33000 and a drift for a population of 39000 (see Figure 13).

VI. CONCLUSIONS AND PERSPECTIVES

In this paper, we adapt current back-pressure control to take into account bounded queues constraints. The lack of workconservation of current back-pressure control is proved, and identified as a source of congestion propagation through the network. This phenomenon is caused by pressure saturation at queues that have reached maximum capacity.

Normalized pressure functions are proved to ensure workconservation and this property tends to indicate that congestion propagation will be mitigated. Simulations confirm the efficiency of the approach. It is remarkable that performance have been increased under bounded queues constraints as indicated by simulations, while the ability to distribute the However, for very high arrival rates, and in particular above the capacity region, congestion will necessarily eventually propagate through the network. In this case, vast areas of the network will be congested and inter-junctions interactions due to blocking tend to indicate that phase control should be carried out on groups of junctions belonging to the same congested region. Nevertheless, this task is of high complexity due to the exponential complexity of inter-junctions interactions.

Finally, future works on back-pressure signal control should consider the feedback loop between traffic signal control and driver behaviour, and in particular driver routing choice. One can expect drivers at a junction to change their routing choice if the traffic light gives the right-of-way in favour of some particular output nodes due to traffic conditions. It is of high interest to take into account such behaviours, since they may stabilize or unstabilize the queuing network.

Fig. 4 :

 4 Fig. 4: Example of loss of work conservation of back-pressure control with linear pressure functions.

Fig. 7 :

 7 Fig. 7: Plot of the convex normalized pressure function with parameters C ∞ = 500 and m = 4 for two different congestion thresholds C a = 50 and C a = 100.

  and again, pi should have been selected by Algorithm 1 instead of p i (k) because an equality holds but contrary to p i (k), there exists for pi an input N a and an output N b with µ ab (p i ) > 0, Q ab (k) > 0 and Q b (k) < C b (see the second assumption in the theorem).

Fig. 9 :

 9 Fig. 9: The road network used for simulations.

Fig. 10 :

 10 Fig. 10: Four intersection types depending on the number of lanes of incoming roads.

Fig. 11 :

 11 Fig. 11: Vehicle arrivals histogram during the morning peak hour (7 am to 9 am) when the city population is set to 33000.

  5. The time slot setting is the same as in back-pressure: 15 seconds, and the parameters of the convex normalized pressure of Equation (5) are m = 2 and C ∞ = 200. 3) Non-optimized fixed cycle control: traffic lights periodically switch the applied phase following the sequence (a)-(c)-(b)-(d) of Figure 2. A complete cycle lasts 60 seconds, in which phase (a) and (b) last 16 seconds and phase (c) and (d) last 6 seconds. The yellow time between two phases is set to 4 seconds. The duration of phases is fixed arbitrarily, it is not optimized.

Fig. 12 :

 12 Fig. 12: Comparison of the total queue length in the network through time under different population scenarios: 10000, 27000, 33000 and 39000. Time is in seconds. FC refers to the fixed-cycle control scheme, BP to back-pressure and BPC to capacity-aware back-pressure.

Fig. 13 :

 13 Fig. 13: Comparison of the average total time spent in the network through time under different population scenarios: 10000, 27000, 33000 and 39000. Time is in seconds. FC refers to the fixed-cycle control scheme, BP to back-pressure and BPC to capacity-aware back-pressure.

Fig. 14 :

 14 Fig.14:A typical inefficient configuration in back-pressure control when capacities are not considered. The screen shot is captured at time 7135 with a population of 39000


Jean Gregoire
email: jean.gregoire@mines-paristech.fr.

Emilio Frazzoli
email: frazzoli@mit.edu

Arnaud De

La Fortelle

Tichakorn Wongpiromsarn
email: tichakorn@tcels.or.th

Back-pressure traffic signal control with unknown routing rates

Keywords: road traffic, traffic lights, traffic control, transportation control, queuing theory, back-pressure, network control

The control of a network of signalized intersections is considered. Previous works proposed a feedback control belonging to the family of the so-called back-pressure controls that ensures provably maximum stability given pre-specified routing probabilities. However, this optimal back-pressure controller (BP*) requires routing rates and a measure of the number of vehicles queuing at a node for each possible routing decision. It is an idealistic assumption for our application since vehicles (going straight, turning left/right) are all gathered in the same lane apart from the proximity of the intersection and cameras can only give estimations of the aggregated queue length. In this paper, we present a back-pressure traffic signal controller (BP) that does not require routing rates, it requires only aggregated queue lengths estimation (without direction information) and loop detectors at the stop line for each possible direction. A theoretical result on the Lyapunov drift in heavy load conditions under BP control is provided and tends to indicate that BP should have good stability properties. Simulations confirm this and show that BP stabilizes the queuing network in a significant part of the capacity region.

INTRODUCTION

In today's metropolitan transportation networks, traffic is regulated by traffic light signals which alternate the right-of-way of users (e.g., cars, public transport, pedestrians). Congestion is a major problem resulting in a loss of utility for all users due to delayed travel times over the network [START_REF] Shepherd | A review of traffic signal control[END_REF]. That is why it is of high interest to find a control policy that can stabilize a network of signalized intersections under the largest possible arrival rates. Under traffic light control, a particular set of feasible simultaneous movements, called a phase, is decided for a period of time [START_REF] Papageorgiou | Review of road traffic control strategies[END_REF]. Controlling a traffic light consists of designing rules to decide which phase to apply over time. Pre-timed policies activate phases according to a time-periodic pre-defined schedule, and the signal settings can be fixed by optimization, assuming within-day static demand [START_REF] Cascetta | Models and algorithms for the optimization of signal settings on urban networks with stochastic assignment models[END_REF]; [START_REF] Miller | Settings for fixed-cycle traffic signals[END_REF]; [START_REF] Gartner | Optimization of traffic signal settings by mixed-integer linear programming part i: The network coordination problem[END_REF]. They are not efficient under changing arrival rates which require adaptive control. Many major cities currently employ adaptive traffic signal control systems including SCOOT Hunt et al. (1982), SCATS [START_REF] Lowrie | Scats, sydney co-ordinated adaptive traffic system: A traffic responsive method of controlling urban traffic[END_REF], PRODYN Henry et al. (1984), RHODES Mirchandani and Head (2001), OPAC Gartner (1983) or TUC [START_REF] Diakaki | A multivariable regulator approach to traffic-responsive network-wide signal control[END_REF]. These systems update some control variables of a configurable pre-timed policy on middle term, based on traffic measures. Control variables may include phases, splits, cycle times and offsets [START_REF] Papageorgiou | Review of road traffic control strategies[END_REF]. More recently, feedback control algorithms that ensure maximum stability have been proposed both under deterministic arrivals [START_REF] Varaiya | The max-pressure controller for arbitrary networks of signalized intersections[END_REF], and stochastic arrivals [START_REF] Varaiya | A universal feedback control policy for arbitrary networks of signalized intersections[END_REF]; [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF]. These algorithms are based on the so-called back-pressure control presented in the seminal paper [START_REF] Tassiulas | Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks[END_REF] for applications in wireless communication networks and require real-time queues estimation. An optimal backpressure traffic signal controller (BP*) is presented in [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF] and [START_REF] Varaiya | A universal feedback control policy for arbitrary networks of signalized intersections[END_REF]. They are defined under different modelling assumptions but they are algorithmically equivalent. The key benefit of backpressure control is that it can be completely distributed over intersections, i.e., it requires only local information and it is of O(1) complexity. However, the strong assumptions of the model in [START_REF] Varaiya | A universal feedback control policy for arbitrary networks of signalized intersections[END_REF] (and also implicitly in [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF]) is that controllers require routing rates and a measure of the number of vehicles queuing at every node of the network for each possible routing decision. However, in reality, apart from the proximity of the intersection, vehicles (going straight, turning left, turning right, etc.) are all gathered, and it is difficult to estimate the number of vehicles queuing for each di-rection (see Figure 1). Cameras can give good estimations of the total number of vehicles queuing at a given node, but not the direction of vehicles. However, it is feasible to detect if there are some vehicles (or no vehicle) that want to go to a given destination, if we assume the existence of dedicated lanes from the proximity of the intersection with loop detectors at the stop line. The back-pressure control proposed in this paper(BP) requires such loop detectors and an estimation of the total number of vehicles queuing at each node (gathering all possible directions). It does not assume any knowledge of routing rates. We evaluate the performance of BP with regards to the optimal BP* control. The contribution of the paper is to provide a back-pressure traffic signal controller based on more realistic assumptions on the available measurements than state-of-the-art back-pressure traffic signal control and to show in simulations that stability is conserved in a significant part of the capacity region.

Dedicated lanes indicated by road markings

The paper is organized as follows. Section 2 describes the queuing network model. Sections 3 is mainly expository: it describes BP* highlighting its stability-optimality. The contributions of the paper are presented in Section 4 and 5. Section 4 exhibits BP and a theoretical result on the Lyapunov drift that tends to indicate that it should have good stability properties. The simulations of Section 5 confirm this and show that BP stabilizes the network in a significant part of the capacity region. Section 6 concludes the paper and opens perspectives.

MODEL

As standard in queuing network control, time is slotted, and each time slot maps to a certain period of time during which a control is applied. It is convenient to use a fixed pre-defined time slot length, whose size corresponds to the minimal duration of a phase. When the time slot size is fixed, the traffic signal control problem consists of computing at the beginning of each time slot t the phase to apply during slot t. The network of intersections is modelled as a directed graph of nodes (N a ) a∈N and links (L j ) j∈L . Nodes represent lanes with queuing vehicles, and links enable transfers from node to node: this is a standard queuing network model.

It is a multiple queues one server queuing network. Every signalized intersection is modelled as a server managing a

N 2 N 1 Q 1 Q 2 C 4 N 4 C 3 Q 3 Q 4 N 3 C 8 N 8 C 7 Q 7 Q 8 N 7 C 6 N 6 C 5 Q 6 Q 5 J i λ 1 λ 2 λ 5 λ 6 λ 4 λ 3 λ 7 λ 8 N 5 C 1 C 2
Fig. 2. A junction with 4 incoming nodes and 4 outgoing nodes which corresponds to the intersection depicted in Figure 3. junction which consists of set of links. Junctions (J i ) i∈J are supposed to form a partition of links. For every junction J, I(J) and O(J) denote respectively the inputs and the outputs of J. Inputs (resp. outputs) of junction J are nodes N such that there exists a link L ∈ J pointing from (resp. to) N . The reader should consider the introduction of junctions in the model as an overlay of the queuing network model. For the sake of simplicity, we do not represent links in the queuing network representation of Figure 2.

Every server maintains an internal queue for every input/output, and server work enables to transfer vehicles from an input to an output of the junction. The internal queue at node N a is a vector Q a and Q ab (t) denotes the number of vehicles in the queue of node N a entering N b upon leaving N a . The aggregated queue length

Q a (t) = b Q ab (t)
denotes the total number of vehicles at node N a considering all possible routings after exiting N a . In this paper, queues are supposed to have infinite capacities: there is no blocking (see Gregoire et al. (2013a) for an adaptation of back-pressure traffic signal control in the context of finite capacities).

At every time slot t, servers work, resulting in vehicles transfers. Under phase-based control, the transmission rate offered by servers are set by activating a given signal phase p i at each junction J i from a predefined finite set of feasible phases P i at every time slot t. Let P = i∈J P i denote the set of feasible global phases. Each global phase p = (p i ) i∈J ∈ P results in a different service matrix µ(p) where µ ab (p) represents the transmission rate offered by servers to transfer vehicles from N a to N b in a time slot when phase p is activated. The transmission rate is assumed to be binary, µ ab (p) ∈ {0, s ab }: it is zero or it equals the saturation rate s ab . Only the vehicles which are at a node at the beginning of time slot t can be transferred from that node to another node during slot t. Figure 3 depicts the 4 typical phases of a 4 inputs/4 outputs junction.

N 1 N 2 N 3 N 4 N 5 N 6 N 7 N 8 N 1 N 2 N 3 N 4 N 5 N 6 N 7 N 8 N 1 N 2 N 3 N 4 N 5 N 6 N 7 N 8 N 1 N 2 N 3 N 4 N 5 N 6 N 7 N 8 (a) (b) (c) (d)
Fig. 3. A typical set of feasible phases at a junction. For example, supposing that service rates equal 0 or 1, the non zero service rates for phase (a

)
for i ∈ J do for a ∈ I(J i ), b ∈ O(J i ) do Π ab (t) ← P ab [Q ab (t)] end for for a ∈ I(J i ), b ∈ O(J i ) do 10: W ab (t) ← max (Π ab (t) -c r bc Π bc (t), 0) end for p ⋆ i (t) ← arg max pi∈Pi a∈I(Ji),b∈O(Ji) W ab (t)µ ab (p i )
end for return Phase p ⋆ (t) to apply in time slot t 15: end function pressure Π ab (t) and the weighted downstream pressure c r bc Π bc (t). BP* consists of selecting the phase that maximizes the weighted sum. Moreover, we assume that in case of equality the selected phase p * (t) always satisfies µ ab (p * (t)) = 0 if W ab (t) = 0.

Optimal stability

The following theorem states that under linear pressure functions with strictly positive slope, BP* as defined by Algorithm 1 is optimal in terms of stability, i.e. stabilizes the network for all arrivals rates that can be stabilized considering all possible control strategies. It is an extension of the results of [START_REF] Varaiya | A universal feedback control policy for arbitrary networks of signalized intersections[END_REF], because vehicles can enter/exit the network at any node, there is no distinction between exit nodes and internal nodes. Moreover, in contrast with [START_REF] Varaiya | A universal feedback control policy for arbitrary networks of signalized intersections[END_REF]; [START_REF] Wongpiromsarn | Distributed traffic signal control for maximum network throughput[END_REF], pressure functions are just assumed to be linear with strictly positive slope in this paper: P ab (Q ab ) = θ ab Q ab , θ ab > 0. Theorem 1. (Back-pressure optimality). Assuming that pressure functions are linear with strictly positive slopes, BP* as defined by Algorithm 1 is stability-optimal.

Proof. Due to space limitations, the full proof is not provided in this paper and is available in the supplementary material [START_REF] Gregoire | Supplementary material to: Back-pressure traffic signal control with unknown routing rates[END_REF]. Stability is proved using the Lyapunov function

V (t) = V(Q(t)) = a,b θ ab Q ab (t) 2 .
The existence of B, η > 0 such that:

E{V (t + 1) -V (t)|Q(t)} ≤ B -η a,b Q ab (t), (1)
enables to conclude stability for the queuing network using the sufficient condition proved in [START_REF] Neely | Dynamic power allocation and routing for satellite and wireless networks with time varying channels[END_REF].

BP CONTROLLER

The controller

Back-pressure control proposed in Section 3 requires complete knowledge of the queues lengths matrix Q(t) and the routing rates. For our application, a complete knowledge of Q(t) is not realistic because dedicated lanes for turning vehicles are only from the proximity of the junction. Farther, all vehicles are gathered and the controller does not have access to the direction of every vehicle in the absence of vehicle-to-infrastructure communications. That is why we propose in the present paper a controller that uses only the aggregated queues lengths Q a (t) = b Q ab (t), i.e. a queue length without direction information. It is defined by Algorithm 2. It computes the phase to apply at every time slot without requiring neither routing rates nor complete knowledge of queues lengths matrix Q(t) and takes as inputs the aggregated queues lengths Q a (t) = b Q ab (t). However, it still requires vehicle detectors variables d ab (t) ∈ [0, 1] defined below:

d ab (t) = min(Q ab (t)/s ab , 1) (2)
The

for i ∈ J do for a ∈ I(J i ) ∪ O(J i ) do Π a (t) ← P a [Q a (t)] end for for a ∈ I(J i ), b ∈ O(J i ) do 10: W ab (t) ← d ab (t) max (Π a (t) -Π b (t), 0) end for p ⋆ i (t) ← arg max pi∈Pi a∈I(Ji),b∈O(Ji)
W ab (t)µ ab (p i ) end for return Phase p ⋆ (t) to apply in time slot t 15: end function Algorithm 2 defines BP control. Note that for transfers from N a to N b , the upstream pressure is now Π a (t) and the downstream pressure is Π b (t): individual queue pressures Π ab (t) are not required. Moreover, the difference between the upstream pressure and the downstream pressure is multiplied by d ab (t) to form W ab (t). Hence, if at time slot t, there is no vehicle at N a going to N b , the weight W ab (t) associated to transfers from N a to N b vanishes.

Behaviour of the Lyapunov drift under heavy load conditions

Let us consider the Lyapunov function V(Q) and its evolution through time V (t) defined below:

V (t) = V(Q(t)) = a θ a Q a (t) 2 = a θ a ( b Q ab (t)) 2 (3)
Let us define heavy load conditions at time slot t as states of the network such that if the right-of-way is given to any individual queue, it can be emptied at saturation flow, i.e. there are enough vehicles in the individual queue to ensure saturation:

∀a, b ∈ N , Q ab (t) ≥ s ab (4)
The following theorem proves that under heavy load conditions the Lyapunov drift respects the sufficient condition for network stability if λ + ǫ ∈ Λ r , for sufficiently large ǫ. Theorem 2. (Lyapunov drift under heavy load conditions). Assume λ + ǫ ∈ Λ r , BP control as defined in Algorithm 2 is applied and the network is in heavy load conditions, then there exists B, η > 0 such that :

E{V (t + 1) -V (t) | Q(t)} ≤ B -η a Q a (t) (5)
for sufficiently large ǫ.

Proof. Due to space limitations, the full proof is not provided in this paper and is available in the supplementary material [START_REF] Gregoire | Supplementary material to: Back-pressure traffic signal control with unknown routing rates[END_REF].

The above theorem tends to indicate that the network should have good stability properties because the condition for stability is verified in heavy load conditions for λ sufficiently interior to the capacity region. Unfortunately it does not enable to conclude that the network is stable in a significant part of the capacity region. Indeed, heavy load conditions can not be guaranteed at all time, and when an individual queue Q ab is below the saturation flow s ab , it is a constraint for the emptying of Q a , that can unstabilize the queuing network. Hence, the characterization of the stability region of the queuing network under BP control with the modelling assumptions presented in Section 2 is still a challenging problem. That is why we propose to implement the two back-pressure controllers and to compare their behaviour. The results of the simulations are presented in the next section.

SIMULATIONS

The simulation platform

The model and the algorithms presented in this paper have been implemented into a simulator coded in Java. It simulates a grid network and every junction of the grid has 4 inputs, 4 outputs, and 4 feasible phases as depicted in Figure 3. The height and the width are parameters. Every individual flow allowed by phases of Figure 3 equals 10 (it is the saturation rate). Vehicles are generated at each node N a at an arrival rate λ a that can be set as desired.

The arrival process generates individual arrivals as well as batches of 10 vehicles. The routing ratios are fixed at the beginning of the simulation.

Behaviour of the two back-pressure controllers

Simulations have been carried out for a 21×21 square grid network (see Figure 4). First of all, we present simulations results in the case of a network that has been configured with the same arrival rates and routing rates at every node of the network.

Simulation results for a particular network and particular arrival/routing rates The numerical results of Figure 5 correspond to the following parameters. Turn left probability when a vehicle enters a node: 0.2; turn right probability when a vehicle enters a node: 0.2; go straight probability when a vehicle enters a node: 0.5; exit probability when a vehicle enters a node: 0.1; probability of a batch: 0.05; pressure functions P a (Q a ) = Q a and P ab (Q ab ) = Q ab (θ a = θ ab = 1); vehicles are generated at every node with the same arrival rate λ > 0 that can be set as desired at the beginning of the simulation.

Experiments are carried out at height different arrival rates: λ = 0.4, 0.5, 0.6, 0.65, 0.7, 0.75, 0.8 and 0.9 vehicles per time slot. Figure 5 depicts the global queue of the network over time, i.e. a Q a (t) = a,b Q ab (t), for the height arrival rates, under BP* control and under BP control. One can observe in Figure 5 that under BP* control, the queuing network is stabilized for λ ≤ 0.7 and gets unstable from λ = 0.75. Under BP control, it is stabilized for λ ≤ 0.65 and gets unstable from λ = 0.7. First of all, it proves that as expected, BP control is not stability-optimal. However, in the particular setting of this experiment, (uniform arrivals/routing rates and grid network), the performance of BP and BP* are very close, and the optimality gap is around 0.05/0.7 ≃ 10%, i.e. a performance of 90%.

However, such a uniform network is not realistic and the results of the next paragraph try to evaluate the performance of BP with regards to BP* with less specific routing/arrival parameters.

Evaluation of BP with regards to BP* on several samples of parameters

In the following simulations, the routing/arrival process parameters are not uniform over nodes any more. 10 samples of parameters have been generated. For each sample, the routing/arrival rates are generated as follows. For each direction (straight, left, right), (uniformly) random values between 0 and 1 are generated, say y s , y l , y r ; a (uniformly) random value between 0 and 0.1 is generated for exits, say y ω ; and the routing rates are set by normalization of the generated real values, i.e. for the left direction for example, the routing rate is y l /(y s + y l + y r + y ω ). The arrivals rates are set by generating a (uniformly) random value between 0 and 1 for every node, say λ 0 a . At the beginning of the simulation, a parametrizable scaling value x enables to fix the actual arrival rate of the current simulation: λ a = xλ 0 a , where x has the same value over nodes. The value of 0.1 for the scale of exits is quite arbitrary and, loosely speaking, fixes the averaged number of travelled nodes before exiting the network.

Note that the routing rates and the values λ 0 a are fixed for a given sample. However, the value of λ a depends on the value of x set at the beginning of the simulation. The parameter x enables to define a performance for BP with regards to BP* for a given sample. We let x vary and we observe the maximum value of x such that the network is stable under BP versus BP* (say x * max for BP* and x BP max for BP). We define the performance of BP with regards to BP*, or more shortly the performance of BP (because BP* is optimal), as follows:

performance(BP) = x BP max /x * max (6)
As for previously presented simulations, the probability of a batch is 0.05 and the pressure functions are linear with slope 1. Figure 6 depicts the performance obtained for the 10 samples, the average performance and the standard deviation. The average performance is around 80%, i.e. the optimality gap is about 20%. The simulation results prove that the performance of BP is affected by the routing/arrival rates. Hence, the distribution (over samples) of the performance would be different for a different distribution of routing/arrival rates. Nevertheless, in the particular setting of the experiment, the average optimality gap of 20% seems again a low price to pay with regards to the much more realistic assumptions on the measurements available to compute the control.

Fig. 6. Performance distribution for ten samples. The point above the axis represents the average performance over samples and the horizontal bar is the standard deviation.

However, these promising results can not be extended to any kind of network of intersections and further simulations with a more general structure of network should be carried out to confirm the closeness of performance.

We are currently implementing our algorithms in a traffic simulator in order to test the performance of BP control with real traffic data of the city of Singapore.

CONCLUSION AND PERSPECTIVES

The simulation results of this paper prove that BP is not optimal but tend to indicate that it stabilizes the queuing network in a significant part of the capacity region. The benefits of BP originate from the more realistic assumptions on queues measurements. Computing the phase to apply only requires aggregated queues lengths estimation that can be provided by cameras, and loop detectors at dedicated lanes. The optimality gap, around 20% in the particular setting of the experiments, seems a low price to pay for the benefits of relaxed assumptions on the available measurements. However, simulations have been conducted in a grid network, which is a particular structure, and with synthetic data which can strongly differ from real traffic data. To confirm the closeness of performance, simulations should be carried out in a more advanced traffic network simulator.

Finally, the emergence of vehicle-to-infrastructure communications opens avenues to enhance traffic signal control. The traffic signal controllers can have access, in particular, to the destination node of every vehicle. As a result, backpressure control with a multiple-commodity queuing network model, as proposed in [START_REF] Neely | Dynamic power allocation and routing for satellite and wireless networks with time varying channels[END_REF] in the context of wireless communication networks, should be investigated.

Fig. 1 .

 1 Fig. 1. Dedicated lanes for turning vehicles. The dedicated lanes are indicated by road markings when vehicles approach the intersection. Apart from the proximity of the intersection, vehicles are all gathered.

Fig. 4 .

 4 Fig. 4. The 21 × 21 grid network used for the presented simulations.

Fig. 5 .

 5 Fig. 5. Evolution of the global queue of the network over time for height arrival rates. Comparison of the behaviour of the network under BP/BP* control.

  Queues lengths matrix Q(t), Pressure functions P ab (Q ab ) for all a, b ∈ N , Routing matrix r.

	function BP*
	5:
	3. BP* CONTROLLER
	3.1 The controller
	In the following, we expose BP* signal control. It is an ex-
	tension of the algorithm proposed in Varaiya (2009) where
	internal/exit links are not differentiated, because exits may
	occur at any link of the network. It is quite equivalent
	to the back-pressure controller of Wongpiromsarn et al.
	(2012), assuming the nodes carry direction information.
	Loosely speaking, the idea of back-pressure control is to
	compute pressure at every node based on node occupancy
	and to open flows which have a high upstream pressure
	and a low downstream pressure, like opening a tap.

are µ 31 , µ 36 , µ 24 and µ 27

Exogenous arrivals occur at every node of the network. Let A a (t) denote the number of vehicles that exogenously arrive at node N a during slot t. The arrival process A a (t) is assumed to be rate convergent with long-term arrival rate λ a ≥ 0. When a quantity of vehicles arrives at node N a ∈ I(J i ) during slot t, exogenously and endogenously, it is split and added into queues Q ab , b ∈ O(J i ). The routing process is exogenous and assumed to be rate convergent with ratios r ab with b r ab ≤ 1 (see the supplementary material

[START_REF] Gregoire | Supplementary material to: Back-pressure traffic signal control with unknown routing rates[END_REF]

for more details). Exits are modelled by assuming that the routing matrix is non-conservative. 1b r ab represents the exit rate of vehicles entering node N a , it is the ratio of vehicles directly removed from the network when entering node N a , i.e. not added to any queue Q ab . Note that the only variable that is controlled is the activated phase at every time slot t, denoted by p(t), and yielding a service matrix µ(p(t)) during slot t.

Algorithm 1 defines BP* control. At every junction i, for each phase p ∈ P i , the weighted sum a,b W ab (t)µ ab (p) is computed. W ab (t), the weight associated to transfers from N a to N b , is the difference between the upstream Algorithm 1 BP* control Require:

  variable d ab (t) can be measured by loop detectors positioned at dedicated lanes.

	Algorithm 2 BP control
	Require:
	Queues lengths Q a (t),
	Pressure functions P a (Q a ),
	Loop detectors variables d ab (t).
	function BP
	5:

ACKNOWLEDGEMENTS

This work was supported in part by the Singapore National Research Foundation through the Future Urban Mobility Interdisciplinary Research Group at the Singapore-MIT Alliance for Research and Technology.