ANalysis and COntrol on NETworks: trends and perspectives

(1)

Workshop

ANalysis and COntrol on NETworks:

trends and perspectives

Padova, March 9-11, 2016

Optimization based control of networks of discretized

PDEs: application to road traffic management

(2)

Associated Team “ORESTE”

ORESTE (Optimal RErouting Strategies for Traffic mangEment) is an associated team between Inria project-team OPALE and the Connected Corridors project at UC Berkeley.

I Paola Goatin (PI)

I Maria Laura Delle Monache ^I Alexandre Bayen (PI)

I Jack Reilly

I Samitha Samaranayake

I Walid Krichene

(3)

ORESTE project goals

I Optimize traffic flow in corridors

I ramp metering

I re-routing strategies

I Modeling approach:

I macroscopic traffic flow models

I discrete adjoint method for gradient computation

(4)

SUMMARY

1. Macroscopic models for road traffic

2. Discretized system

3. Quick review of the adjoint method

4. Numerical results

5. Application to optimal re-routing

6. Conclusion and perspectives

(5)

Outline of the talk

(6)

LWR model

[Lighthill-Whitham ’55, Richards ’56]

Non-linear transport equation: PDE for mass conservation

∂tρ + ∂xf (ρ) = 0 x ∈ R, t > 0

I ρ∈ [0, ρ^max] mean traffic density

I f (ρ) = ρv (ρ) flux function

Empirical flux-density relation: fundamental diagram

ρ

ρcr ρmax

f^max f (ρ)

0

Greenshield ’35

ρ

ρcr ρmax

f^max f (ρ)

vf f^max ρmax−ρcr

Newell-Daganzo

(7)

Extension to networks

m incoming arcs n outgoing arcs junction

I LWR on networks:

[Holden-Risebro, 1995; Coclite-Garavello-Piccoli, 2005; Garavello-Piccoli, 2006]

I LWR on each road

I Optimization problem at the junction

I Modeling of junctions with a buffer:

[Herty-Lebacque-Moutari, 2009; Garavello-Goatin, 2012; Bressan-Nguyen, 2015]

(8)

Extension to networks

m incoming arcs n outgoing arcs junction

I LWR on networks:

[Holden-Risebro, 1995; Coclite-Garavello-Piccoli, 2005; Garavello-Piccoli, 2006]

I LWR on each road

I Optimization problem at the junction

I Modeling of junctions with a buffer:

[Herty-Lebacque-Moutari, 2009; Garavello-Goatin, 2012; Bressan-Nguyen, 2015]

I Junction described with one or more buffers

I Suitable for optimization and Nash equilibrium problems

(9)

A model for ramp metering

I Two incoming links:

I Upstream mainline I1=] − ∞, 0[

I Onramp R1

I Two outgoing links:

I Downstream mainline I2=]0, +∞[

I Offramp R2

I1 I2

(10)

A model for ramp metering

Coupled PDE-ODE model:

I Classical LWR on each mainline I1, I2

∂tρ + ∂xf (ρ) = 0, (t, x )∈ R⁺× Iⁱ,

I Dynamics of the onramp described by an ODE (buffer)

dl (t)

dt = Fin(t)− γ^r1(t), t∈ R⁺,

I l (t) ∈ [0, +∞[ length of the onramp queue

I Fin(t) flux entering the onramp

I γr1(t) flux leaving the onramp (through the junction)

I Coupled at junctionwith an LP-optimization problem

(11)

A model for ramp metering

∂tρ + ∂xf (ρ) = 0, (t, x )∈ R⁺× Iⁱ,

I Dynamics of the onramp described by an ODE (buffer) dl (t)

dt = Fin(t)− γ^r1(t), t∈ R⁺,

(12)

A model for ramp metering

∂tρ + ∂xf (ρ) = 0, (t, x )∈ R⁺× Iⁱ,

I Dynamics of the onramp described by an ODE (buffer) dl (t)

dt = Fin(t)− γ^r1(t), t∈ R⁺,

I Coupled at junctionwith an LP-optimization problem

(13)

Junction solver: Demand & Supply

δ(ρ1) =

f (ρ1) if 0≤ ρ¹< ρ^cr, f^max ifρ^cr≤ ρ¹≤ 1,

ρ , f (ρ)

δ(ρ) f^max(ρ)

d (Fin, l) =

θγ_r1^max if l (t)> 0, min (Fin(t),θγ^max_r1 ) if l (t) = 0,

θ∈ [0, 1]control parameter

f^max if 0≤ ρ²≤ ρ^cr,

, f (ρ) σ(ρ)

f^max(ρ)

(14)

Junction solver: flux maximization

1. Mass conservation: f (ρ1(t, 0−)) + γ^r1(t) = f (ρ2(t, 0+)) + γr2(t) 2. f (ρ2(t, 0+)) maximum subject to 1. and

f (ρ2(t, 0+)) = min

(1− β)δ(ρ¹(t, 0−)) + d(Fⁱⁿ(t), l(t)), σ(ρ2(t, 0+))

3. Right of way parameter P∈ ]0, 1[ to ensure uniqueness:

f (ρ2(t, 0+)) = P f1(ρ(t, 0−)) + (1 − P) γ^{r 1} 4. Offramp treated as a sink (infinite capacity)

5. No flux from the onramp to the offramp is allowed

(15)

Riemann solver: feasible set

To find a solution of the problem we solve an LP-optimization problem

Γr1

Γ1

δ(ρ1)

d (Fin,¯l)

Γ1(1− β) + Γ^r1= Γ2

1. Define the spaces of the incoming fluxes

2. Consider the demands 3. Trace the supply line

4. The feasible set is given by Ω

(16)

Riemann solver: feasible set

Γr1

Γ1

δ(ρ1)

d (Fin,¯l)

Γ1(1− β) + Γ^r1= Γ2

Different situations can occur:

I Demand limited case

I Supply limited case

(17)

Riemann solver: feasible set

Γr1

Γ1

δ(ρ1)

d (Fin,¯l)

Γ1(1− β) + Γ^r1= Γ2

(18)

Riemann solver: feasible set

Γr1

Γ1

δ(ρ1)

d (Fin,¯l)

Γ1(1− β) + Γ^r1= Γ2

Ω

(19)

Riemann solver: feasible set

Γr1

Γ1

δ(ρ1)

d (Fin,¯l)

Γ1(1− β) + Γ^r1= Γ2

(20)

Riemann solver: feasible set

Γr1

Γ1

δ(ρ1)

d (Fin,¯l)

Γ1(1− β) + Γ^r1= Γ2

demand limited

(21)

Riemann solver: feasible set

Γr1

Γ1

δ(ρ1)

d (Fin,¯l)

Γ1(1− β) + Γ^r1= Γ2

supply limited

(22)

Riemann solver: optimal point

Demand limited case

The optimal point Q is the point of maximal demands

Γr1

Γ₁ δ(ρ1)

d (F_in,¯l)

Γ1(1− β) + Γ^r1= Γ2

Ω Q

(23)

Riemann solver: optimal point

Supply limited case

I We introduce the right of way parameter

I We set optimal point Q to be the point of intersection

I Different situations can occur depending on the value of the intersection point

I Q ∈ Ω

I Q /∈ Ω

−→ Optimal point: S

S

Γ1

δ(ρ1) Γ2

(24)

Riemann solver: optimal point

I Q ∈ Ω

I Q /∈ Ω

S

Γr1

d (Fin,¯l) Γ1

δ(ρ1) Γ2

Γ1=_1−P^P Γr1

(25)

Riemann solver: optimal point

I Q ∈ Ω

I Q /∈ Ω

S

Γ1

δ(ρ1) Γ2

Γ1= ^P Γr1

(26)

Riemann solver: optimal point

I Q ∈ Ω

I Q /∈ Ω

Q

S

Γr1

d (Fin,¯l) Γ1

δ(ρ1) Γ2

Γ2

Γ1=_1−P^P Γr1

(27)

Riemann solver: optimal point

I Q ∈ Ω

I Q /∈ Ω

S

Γ1

δ(ρ1) Γ2

Γ1= ^P Γr1

(28)

Riemann solver: optimal point

I Q ∈ Ω

I Q /∈ Ω −→ Optimal point: S

Q S

Γr1

d (Fin,¯l) Γ1

δ(ρ1) Γ2

Γ1=_1−P^P Γr1

(29)

Difference with

[Coclite-Garavello-Piccoli, 2005]

model

The traffic distribution across the junction is given by the distribution matrix A:

A =1 − β 1

β 0

Γ1

δ(ρ1,0)

Q

Γ₁

δ(ρ1,0) Γ₁=_1−P^P γr 1

Q

(30)

Riemann solver: theorem

Theorem

Delle Monache& al., SIAP, 2014

Fix P ∈ ]0, 1[. For every ρ^1,0,ρ2,0∈ [0, 1] and l⁰∈ [0, +∞[, there exists a unique admissible solution (ρ1(t, x ), ρ2(t, x ), l(t)) satisfying the priority (possibly in an approximate way). Moreover, for a.e. t> 0, it holds

(ρ1(t, 0−), ρ²(t, 0+)) =R^{l (t)}(ρ1(t, 0−), ρ²(t, 0+))

¯t t

0 x

ρ1,0 ρ2,0

ρˆ₁ ρˆ₂

ρ¯2

ρ¯1

(31)

Modified Godunov scheme

I At some ∆tⁿ, we might have multiple shocks exiting the junction at ¯t

I We divide the time step ∆tⁿ= (tⁿ, tⁿ⁺¹) into two sub-intervals

∆ta= (tⁿ, ¯t) and ∆tb= (¯t, tⁿ⁺¹)

I We solve in one time step two different Riemann Problems at the junction

I For ∆ta: Classical Godunov flux update

ρⁿ⁺¹_J = ρⁿJ−∆ta

∆x(ˆΓ1− F (ρⁿJ−1, ρⁿJ)) ρⁿ⁺¹₀ = ρⁿ0−∆ta

∆x(F (ρⁿ0, ρⁿ1) − ˆΓ2)

I For ∆tb: Modified flux update

(32)

Numerical simulations

(33)

Outline of the talk

(34)

Ramp metering discretized system H(~ ρ, ~u) = 0

i i

on-ramp i

i + 1 f_iⁱⁿ(k) f_i^out(k) fi +1ⁱⁿ (k)

ri(k) Di(k)

βi(k) f_i^out(k)

fi +1^out(k) . . .

block i

I Dynamics and junctions solutions based on the model described earlier

I Piecewise affine system

I Control parameter ui is a constraint on the ramp inflow ri(k)

(35)

Ramp metering discretized system H(~ ρ, ~u) = 0

Lower triangular forward system H(~ρ, ~u) = 0:

I hi ,k=ρi(k)− ρⁱ(k− 1) − {flux update eq. for cell i and time step k}

I H system of concatenated hi ,k

I H lower triangular

I Very efficient to solve H^Tx = b

(36)

Lower triangular forward system H(~ ρ, ~u) = 0

Figure: ^∂H_∂~_ρ matrix

(37)

Outline of the talk

(38)

Optimization of a PDE-constrained system

Optimization problem

minimize~u∈U J (~ρ, ~u) subject to H(~ρ, ~u) = 0

I ~ρ∈ X ⊆ R^NT: state variables

I ~u ∈ U ⊆ R^MT: control variables

Gradient descent: How to compute the gradient ∂J

∂~ρ

∂~u +∂J

∂~u ? On trajectories, H(~ρ, ~u) = 0 constant, thus

∂H

∂~ρ

∂~u +∂H

∂~u = 0 O(T²N²M)

(39)

Discrete adjoint method

Consider the Lagrangian

L(~ρ, ~u, λ) = J(~ρ, ~u) + λ^TH(~ρ, ~u) thus∇^~^uL =∇^~^uJ :

∇^uL(~ρ, ~u, λ) = ∂J

∂~u +∂J

∂~ρ

∂~u +λ^T ∂H

∂~u +∂H

∂~ρ

∂~u

= ∂J

∂~u +λ^T∂H

∂~u + ∂J

∂~ρ+λ^T∂H

∂~u

∂~ρ

∂~u Compute λs.t.

∂H

∂~ρ

T

λ=−∂J

∂~ρ

T

O(T²N²)

(40)

Exploiting system structure

The structure of the forward system influences the efficiency adjoint system solving

Solving for λ

∂H

∂~ρ

T

λ=−∂J

∂~ρ

T

Since ^∂H_∂~_ρ is lower triangular, ^∂H_∂~_ρ^T is an upper triangular matrix

=⇒ The adjoint system can be solved efficiently using backward substitution

Complexity reduction from O(T

²

NM) to O(NT + MT )

(41)

Exploiting system structure

The structure of the forward system influences the efficiency adjoint system solving

Solving for λ

∂H

∂~ρ

T

λ=−∂J

∂~ρ

T

Since ^∂H_∂~_ρ is lower triangular, ^∂H_∂~_ρ^T is an upper triangular matrix

=⇒ The adjoint system can be solved efficiently using backward substitution

(42)

Optimization algorithm

Algorithm 1 Gradient descent loop Pick initial control~uinit ∈ U^ad while not converged do

~

ρ = forwardSim(~u, IC , BC ) solve for state trajectory (forward system) λ = adjointSln(~ρ, ~u) solve for adjoint parameters (adjoint system)

∇^uJ =λ^{T ∂H}_∂~_u +^∂J_∂~_u compute the gradient (search direction)

~u← ~u − α∇^uJ ,α∈ (0, 1) s.t. ~u ∈ U^adupdate the control~u (update step) end while

(43)

Remarks on descrete adjoint

Strengths:

I Requires only one solution of adjoint system, independent of dim(~u) (unlike finite differences or sensitivity analysis).

I Extends existing simulation code

I General technique, can be applied in very different settings

Weaknesses:

I Optimization of the discretized problem, rather than approximation of the optimal solution of the continuous problem

I No proof of convergence

(44)

Outline of the talk

(45)

Numerical Results: case study

Figure: I15 South, San Diego: 31 km

N = 125 links and M = 9 onramps T = 1800 time-steps

∆t = 4 seconds (120 minutes time interval)

(46)

Numerical Results

Density and queue lengths without control

Density and queue difference with control

(47)

Model Predictive Control

Performance undernoisy input data: MPC loop

I initial conditions at time t and boundary fluxes on T_h(noisy inputs)

I optimal control policy on T_h

I forward simulation on T_u≤ T^h using optimal controls and exact initial and boundary data

I t → t + T^u

Comparison with Alinea (local feedback control without boundary conditions)

0.5 1.0 1.5 2.0 2.5 3.0 3.5

ReducedCongestion(%)

0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0

ReducedCongestion(%) Adjoint

Alinea

(48)

Running time

Convergence

10⁻¹ 10⁰ 10¹ 10² 10³

Running time (ms) 226

227 228 229 230 231 232 233 234

Totaltraveltime(veh-s) Finite differences

Adjoint

Simulation time

0 50 100 150 200 250 300 350 400 450 Running time (seconds)

0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5

ReducedCongestion(%)

Adjoint Alinea

(49)

Outline of the talk

(50)

Application to optimal re-routing

System Optimal Dynamic Traffic Assignment problem with Partial Control:

Multi-commodity flow:

ρi(k) =X

c∈C

ρi ,c(k)

accounting for compliant cc ∈ CC and non-compliant cⁿusers

I full Lagrangian paths known for the controllable agents

I knowledge of the aggregate split ratios for the non-controllable (selfish) agents.

Goal: Control compliant users to optimize traffic flow

(51)

Application to optimal re-routing

System Optimal Dynamic Traffic Assignment problem with Partial Control:

Multi-commodity flow:

ρi(k) =X

c∈C

ρi ,c(k)

accounting for compliant cc ∈ CC and non-compliant cⁿusers

I full Lagrangian paths known for the controllable agents

I knowledge of the aggregate split ratios for the non-controllable (selfish) agents.

Goal: Control compliant users to optimize traffic flow

(52)

Numerical study: synthetic network

[Ziliaskopoulos, 2001]

I Normal conditions: link capacity between cell 3 and cell 4 = 6 Optimal total travel time: 178

I Incident between cell 3 and cell 4: capacity goes to 0 Optimal total travel time: 211 (otherwise 244)

(53)

Synthetic network: partial control

(54)

Numerical study: real case

Figure: I210 with parallel arterial route, Arcadia (13 km)

N = 24 links 1 hour time-horizon

∆t = 30 seconds

(55)

Numerical Results

50% capacity drop between min 10 and min 30

(56)

Numerical Results

Arterial capacity used:

(57)

Outline of the talk

(58)

In summary

Results:

I Definition of appropriate junction solvers for ramp metering and multi-commodity

I Formulation of the corresponding finite horizon optimal control problems

I Gradient computation with O(NT + MT ) complexity

I Numerical tests showing the benefits on real field applications

Possible extensions:

I Variable speed limit, maximal queue length, ...

I Selfish agents response (Stackelberg games)

(59)

References

I M.L. Delle Monache, J. Reilly, S. Samaranayake, W. Krichene, P.Goatin and A. Bayen. A PDE-ODE model for a junction with ramp buffer, SIAM J. Appl. Math., 74(1) (2014), 22-39.

I J. Reilly, S. Samaranayake, M.L. Delle Monache, W. Krichene, P. Goatin and A. Bayen. Adjoint-based optimization on a network of discretized scalar conservation law PDEs with applications to coordinated ramp metering, J. Optim. Theory Appl., 167(2) (2015), 733-760.

I S. Samaranayake, W. Krichene, J. Reilly, M.L. Delle Monache, P. Goatin and A. Bayen. Discrete-time system optimal dynamic traffic assignment (SO-DTA) with partial control for horizontal queuing networks, in review.