Traffic Theory

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....

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...

Adaptive Averaging in Accelerated Descent Dynamics

Krichene, Walid
Bayen, Alexandre
Bartlett, Peter L
2016

We study accelerated descent dynamics for constrained convex optimization. This dynamics can be described naturally as a coupling of a dual variable accumulating gradients at a given rate η(t)η(t), and a primal variable obtained as the weighted average of the mirrored dual trajectory, with weights w(t)...

Heterogeneous Fleets of Active and Passive Floating Sensors for River Studies

Tinka, Andrew
Wu, Qingfang
Weekly, Kevin
Oroza, Carlos
Beard, Jonathan
Bayen, Alexandre
2016

Lagrangian sensing for tracing hydrodynamic trajectories is an innovative approach for studying estuarial environments. Actuated Lagrangian sensors are capable of avoiding obstacles and navigating when active and retain a passive hydrodynamic profile that is suited for Lagrangian sensing when passive. A heterogeneous fleet of actuated and passive drifting sensors is presented. Data assimilation using a high-performance computing (HPC) cluster that runs the ensemble Kalman filter (EnKF) is an essential component of the estuarial state estimation system. The performance of the mixed...

Hybrid Approach for Short-Term Traffic State and Travel Time Prediction on Highways

Allström, Andreas
Ekström, Joakim
Gundlegård, David
Ringdahl, Rasmus
Rydergren, Clas
Bayen, Alexandre M.
Patire, Anthony D.
2016

Traffic management and traffic information are essential in urban areas and require reliable knowledge about the current and future traffic state. Parametric and nonparametric traffic state prediction techniques have previously been developed with different advantages and shortcomings. While nonparametric prediction has shown good results for predicting the traffic state during recurrent traffic conditions, parametric traffic state prediction can be used during nonrecurring traffic conditions, such as incidents and events. Hybrid approaches have previously been proposed; these approaches...

Scalable Linear Causal Inference for Irregularly Sampled Time Series with Long Range Dependencies

Belletti, Francois
Sparks, Evan
Franklin, Michael J.
Bayen, Alexandre M.
Gonzalez, Joseph
2016

Linear causal analysis is central to a wide range of important application spanning finance, the physical sciences, and engineering. Much of the existing literature in linear causal analysis operates in the time domain. Unfortunately, the direct application of time domain linear causal analysis to many real-world time series presents three critical challenges: irregular temporal sampling, long range dependencies, and scale. Moreover, real-world data is often collected at irregular time intervals across vast arrays of decentralized sensors and with long range dependencies which make naive...

On Learning How Players Learn: Estimation of Learning Dynamics in the Routing Game

Lam, Kiet
Krichene, Walid
Bayen, Alexandre M.
2016

The routing game models congestion in transportation networks, communication networks, and other cyber physical systems in which agents compete for shared resources. We consider an online learning model of player dynamics: at each iteration, every player chooses a route (or a probability distribution over routes, which corresponds to a flow allocation over the physical network), then the joint decision of all players determines the costs of each path, which are then revealed to the players. We pose the following estimation problem: given a sequence of player decisions and the corresponding...