ITS Berkeley

Convergence of Heterogeneous Distributed Learning in Stochastic Routing Games

Krichene, Syrine
Krichene, Walid
Dong, Roy
Bayen, Alexandre
2015

We study convergence properties of distributed learning dynamics in repeated stochastic routing games. The game is stochastic in that each player observes a stochastic vector, the conditional expectation of which is equal to the true loss (almost surely). In particular, we propose a model in which every player m follows a stochastic mirror descent dynamics with Bregman divergence Dψm and learning rates ηtm = θmt-αm. We prove that if all players use the same sequence of learning rates, then their joint strategy converges almost surely to the equilibrium set. If the learning dynamics are...

Modeling and Estimation of the Humans' Effect on the CO2 Dynamics Inside a Conference Room

Weekly, Kevin
Bekiaris-Liberis, Nikolaos
Jin, Ming
Bayen, Alexandre M.
2015

We develop a data driven, partial differential equation-ordinary differential equation model that describes the response of the carbon dioxide (CO2) dynamics inside a conference room, due to the presence of humans, or of a user-controlled exogenous source of CO2. We conduct three controlled experiments to develop and tune a model whose output matches the measured output concentration of CO2 inside the room, when known inputs are applied to the model. In the first experiment, a controlled amount of CO2 gas is released inside the room from a regulated supply, and in the second and third...

How Much GPS Data Do We Need?

Patire, Anthony D.
Wright, Mathew
Prodhomme, Boris
Bayen, Alexandre M.
2015

With the rapid growth of communications technologies, GPS, and the mobile internet, an increasing amount of real-time location information is collected by private companies and could be marketed for retail. This body of data offers transportation agencies potential opportunities to improve operations, but it also presents unique challenges. This article investigates the question of how much GPS data is needed to power a traffic information system capable of providing accurate speed (and thus travel time) information. A hybrid data framework is proposed to use real-time, GPS-based, point-...

Prediction of Traffic Convective Instability with Spectral Analysis of the Aw–Rascle–Zhang Model

Belletti, Francois
Huo, Mandy
Litrico, Xavier
Bayen, Alexandre M.
2015

This article starts from the classical Aw–Rascle–Zhang (ARZ) model for freeway traffic and develops a spectral analysis of its linearized version. A counterpart to the Froude number in hydrodynamics is defined that enables a classification of the nature of vehicle traffic flow using the explicit solution resulting from the analysis. We prove that our linearization about an equilibrium is stable for congested regimes and unstable otherwise. NGSIM data for congested traffic trajectories is used so as to confront the linearized model's predictions to actual macroscopic behavior of traffic....

Adjoint-Based Optimization on a Network of Discretized Scalar Conservation Laws with Applications to Coordinated Ramp Metering

Reilly, Jack
Samaranayake, Samitha
Delle Monache, Maria
Krichene, Walid
Goatin, Paola
Bayen, Alexandre M.
2015

The adjoint method provides a computationally efficient means of calculating the gradient for applications in constrained optimization. In this article, we consider a network of scalar conservation laws with general topology, whose behavior is modified by a set of control parameters in order to minimize a given objective function. After discretizing the corresponding partial differential equation models via the Godunov scheme, we detail the computation of the gradient of the discretized system with respect to the control parameters and show that the complexity of its computation scales...

Differential Privacy of Populations in Routing Games

Dong, Roy
Krichene, Walid
Bayen, Alexandre M.
Sastry, S. Shankar
2015

As our ground transportation infrastructure modernizes, the large amount of data being measured, transmitted, and stored motivates an analysis of the privacy aspect of these emerging cyber-physical technologies. In this paper, we consider privacy in the routing game, where the origins and destinations of drivers are considered private. This is motivated by the fact that this spatiotemporal information can easily be used as the basis for inferences for a person's activities. More specifically, we consider the differential privacy of the mapping from the amount of flow for each origin-...

Efficient Bregman Projections onto the Simplex

Krichene, Walid
Krichene, Walid
Bayen, Alexandre
2015

We consider the problem of projecting a vector onto the simplex Δ = x ∈ ℝ+d : Σi=1d xi = 1, using a Bregman projection. This is a common problem in first-order methods for convex optimization and online-learning algorithms, such as mirror descent. We derive the KKT conditions of the projection problem, and show that for Bregman divergences induced by ω-potentials, one can efficiently compute the solution using a bisection method. More precisely, an ω-approximate projection can be obtained in O(d log 1/ω). We also consider a class of exponential potentials for which the exact solution can...

Distributed Optimization for Shared State Systems: Applications to Decentralized Freeway Control via Subnetwork Splitting

Reilly, Jack
Bayen, Alexandre M.
2015

Optimal control problems on dynamical systems are concerned with finding a control policy, which minimizes a desired objective, where the objective value depends on the future evolution of the system (the state of the system), which, in turn, depends on the control policy. For systems which contain subsystems that are disjoint across the state variables, distributed optimization techniques exist, which iteratively update subsystems concurrently and then exchange information between subsystems with shared control variables. This article presents a method, based on the asynchronous...

Minimizing Regret on Reflexive Banach Spaces and Nash Equilibria in Continuous Zero-Sum Games

Balandat, Maximilian
Krichene, Walid
Tomlin, Claire J.
Bayen, Alexandre M.
2016

We study a general adversarial online learning problem, in which we are given a decision set X' in a reflexive Banach space X and a sequence of reward vectors in the dual space of X. At each iteration, we choose an action from X', based on the observed sequence of previous rewards. Our goal is to minimize regret, defined as the gap between the realized reward and the reward of the best fixed action in hindsight. Using results from infinite dimensional convex analysis, we generalize the method of Dual Averaging (or Follow the Regularized Leader) to our setting and obtain upper bounds on the...

From LOS to VMT, VHT and Beyond Through Data Fusion: Application to Integrate Corridor Management

Bayen, Alexandre
Gan, Qijian
Gomes, Gabriel
2016

Traffic performance metrics such as delay and Level Of Service (LOS), which are well documented in the Highway Capacity Manual (HCM), have been widely used by most of the transportation consulting companies, public agencies, and etc. For arterial delay analysis, prevailing commercial tools like Synchro have adopted the method proposed by the HCM, which is rooted in the Webster’s delay calculation proposed more than 50 years ago. The LOS is obtained using a lookup table that assigns a certain grade (from A to F) to the estimated delay according to its value. Without knowing detailed...