# Your search: "author:Bayen, Alexandre"

## filters applied

## Type of Work

Article (16) Book (1) Theses (17) Multimedia (0)

## Peer Review

Peer-reviewed only (21)

## Supplemental Material

Video (0) Audio (0) Images (0) Zip (0) Other files (0)

## Publication Year

## Campus

UC Berkeley (30) UC Davis (0) UC Irvine (2) UCLA (2) UC Merced (0) UC Riverside (2) UC San Diego (0) UCSF (2) UC Santa Barbara (2) UC Santa Cruz (1) UC Office of the President (9) Lawrence Berkeley National Laboratory (1) UC Agriculture & Natural Resources (0)

## Department

University of California Institute of Transportation Studies (9) Institute of Transportation Studies at UC Berkeley (8) California Partners for Advanced Transportation Technology (1) UC Berkeley Center for Future Urban Transport: A Volvo Center of Excellence (1) UC Berkeley Transportation Sustainability Research Center (1)

University of California Transportation Center (2) Center for Research in Energy Systems Transformation (CREST) (1)

## Journal

## Discipline

Engineering (9) Social and Behavioral Sciences (3) Physical Sciences and Mathematics (1)

## Reuse License

## Scholarly Works (34 results)

Modeling real-world processes as convex optimization or variational inequality problems is a common practice as it enables to leverage powerful mathematical tools for the study of such processes. For example, in economics, knowing the consumer utility function enables to adjust prices to achieve some demand level. In control, a low complexity controller requires less computation for little performance loss. In transportation science, the selfish behavior of agents (from shorted path routing) leads to an aggregate cost in the network worse than the system’s optimum, and which can be analytically quantified. Taxation schemes can be designed to incentivize system optimal drivers’ decisions.

In the first part of our work, we briefly review fundamental results in convex optimization, variational inequality theory, and game theory. We also focus on the selfish routing game, which is a popular game-theoretical framework to model the urban transportation network. In particular, we study the impact of the increasing penetration of routing apps on road usage. Its conclusions apply both to manned vehicles in which human drivers follow app directions, and unmanned vehicles following shortest path algorithms. To address the problem caused by the increased usage of routing apps, we model two distinct classes of users, one having limited knowledge of low-capacity road links. This approach is in sharp contrast with some previous studies assuming that each user has full knowledge of the network and optimizes his/her own travel time. We show that the increased usage of GPS routing provides a lot of benefits on the road network of Los Angeles, such as decrease in average travel times and total vehicle miles traveled. However, this global increased efficiency in urban mobility has negative impacts as well, which are not addressed by the scientific community: increase in traffic in cities bordering highway from users taking local routes to avoid congestion.

In the second part, we explore the ability of low complexity game-theoretical models to accurately approximate real transportation systems. For example, system mischaracterizations in selfish routing can cause taxes designed for one problem instance to incentivize inefficient behavior on different, yet closely-related instances. Hence, we want to be able to measure the quality of the learned model. In the present work, we present a statistical framework for the fitting of equilibrium models based on measurements of edge flows using the (standard) empirical risk minimization principle, by choosing the fit giving the lowest expected loss (the distance between the observed and predicted outputs) under the empirical measure. Hence, for the class of models of interest, it is critical to be able to have theoretical guarantees on the quality of the fit. We then present a computational methodology for imputing the map of an equilibrium model, and propose a statistical hypothesis test for validating the trained model against the true one.

In the third part, we explore existing work for estimating link and route flows, and we propose two novel frameworks for traffic estimation. In the first framework, we focus on estimating the highway traffic, which is modeled as a discretized hyperbolic scalar partial differential equations. The system is written as a switching dynamical system, with a state space partitioned into an exponential number of polyhedra in which one mode is active. We propose a feasible approach based on the interactive multiple model (IMM), and apply the k-means algorithm on historical data to partition modes into clusters, thus reducing the number of modes. In the second framework, we develop a convex optimization methodology for the route flow estimation problem from the fusion of vehicle count and cellular network data. The proposed approach is versatile: it is compatible with other data sources, and it is model agnostic and thus compatible with user equilibrium, system-optimum, Stackelberg concepts, and other models. The framework is validated on the I-210 corridor near Los Angeles, where we achieve 90% route flow accuracy with 1033 traffic sensors and 1000 cellular towers covering a large network of highways and arterials with more than 20,000 links.

The research presented in this dissertation aims to develop computationally tractable models and algorithms for the reliable and efficient utilization of capacity restricted transportation networks via route selection and demand redistribution, motivated by the fact that traffic congestion in road networks is a major problem in urban communities. Three related topics are considered, 1) route planning with reliability guarantees, 2) system optimal dynamic traffic assignment, and 3) controlling user equilibrium departure times.

Route planning can in many practical settings require finding a route that is both fast and reliable. However, in most operational settings, only deterministic shortest paths are considered, and even when the link travel-times are known to be stochastic the common approach is to simply minimize the expected travel-time. This approach does not account for the variance of the travel-time and gives no reliability guarantees. In many cases, travelers have hard deadlines or are willing to sacrifice some extra travel-time for increased travel-time reliability, such as in commercial routing applications where delivery guarantees need to be met and perishables need to be delivered on time. The research presented in this dissertation develops fast computation techniques for the reliable routing problem known as the stochastic on-time arrival (SOTA) problem, which provides a routing strategy that maximizes the probability of arriving at the destination within a fixed time budget.

Selfish user optimal routing strategies can, however, lead to very inefficient traffic equilibria in congested traffic networks. This "Price of Anarchy" can be mitigated using system optimal coordinated routing algorithms. The dissertation considers the system optimal dynamic traffic assignment problem when only a subset of the network agents can be centrally coordinated. A road traffic dynamics model is developed based on the Lighthill-Williams-Richards partial differential equation and a corresponding multi-commodity junction solver. Full Lagrangian paths are assumed to be known for the controllable agents, while only the aggregate split ratios are required for the non-controllable (selfish) agents. The resulting non-linear optimal control problem is solved efficiently using the discrete adjoint method.

Spill-back from under-capacitated off-ramps is one of the major causes of congestion during the morning commute. This spill-back induces a capacity drop on the freeway, which then creates a bottleneck for the mainline traffic that is passing by the off-ramp. Therefore, influencing the flow distribution of the vehicles that exit the freeway at the off-ramp can improve the throughput of freeway vehicles that pass this junction. The dissertation studies the generalized morning commute problem where vehicles exiting the freeway at the under-capacitated off-ramp have a fixed desired arrival time and a corresponding equilibrium departure time schedule, and presents strategies to manipulated this equilibrium to maximize throughput on the freeway via incentives or tolls.

The recent increase in the availability of very large data sets

has enabled major breakthroughs in Artificial Intelligence.

Automated devices are now able to achieve a higher level of performance in computer vision, playing perfect and imperfect information games, and language processing which now compares to that of humans.

Such progress is largely due to improved Single Instruction Multiple Data computing capabilities and higher bandwidth in distributed computing systems

and innovative methods to leverage them.

A plethora of algorithms and theories developed in the field of Machine Learning enable better identification of system dynamics and extensive control of the corresponding systems. However, the vast majority of research focuses on problems dealing with homogenous observation data sets or control environment.

Additionally, a large amount of work has focused on data sets comprising only of images, videos featuring similar sampling frequencies, and of time series with regular and identical timestamps of observation.

Such a setting is not representative of the actual way data sets are collected and problems present themselves to practitioners.

The present work delves into a more realistic setting where a unified representation of the data or control problem of interest is not available. We deal with a collection of heterogeneous sub-parts that relate one to another but do not naturally present themselves to practitioners in a homogenous fashion.

Our main objective is to design methods that are readily applicable to heterogenous data sets and control problems in the distributed setting. The development of techniques that can be employed without additional pre-processing of the data makes them more practical to use by a broader range of individuals, companies and institutions.

We first focus on large multi-variate time series comprising of observations that are not synchronous in time. We then tackle Partial Differential Equations featuring a spatial continuum of distinct states.

After this initial focus on the identification of dynamics in time series -- otherwise referred to as time series analysis -- we delve into the topic of control. Control leverages the knowledge we gather about a system in order to have it reach a particular desirable state.

Part of the new work presented in the current work therefore focuses on the control of distributed cohorts of agents subject to individually unique constraints.

Finally, we extend the work conducted separately to heterogenous time series analysis and control and devise strategies beneficial for neural policies that identify system dynamics and optimal actions as part of the same module.

As we move from system identification to distributed control our aim is to find representations of the initial heterogenous problem that are homogenous and enable communication avoidance.

In each of the chapters of the present work, we methodically design an alternate unifying and summarizing representation of the initial data set or control problem of interest.

Our motivation to find small, concise yet expressive representations is that they enable scalable computations in the distributed setting.

When utilizing cohorts of computers inter-connected by a medium such as an ethernet or wireless network, communication time presents the main factor in the overall computing time.

Decreasing the size of the messages that need to be transmitted therefore minimizes the overhead created by the need to communication information from a machine to another. With less time wasted in communication, we maximize the benefit of having more computational power and memory in the form of a distributed system.

We find by designing communication avoiding homogenous representations that statistical efficiency appears as a natural by-product.

To that end, we leverage elements of stochastic process and point process theory, distributed spectral representations of linearized Partial Differential equations, convex duality and stochastic optimization, and finally specific regularization schemes in Reinforcement Learning of deep neural policies.

The present work features novel results on the estimation of cross-correlation of irregularly observed time series with event-driven sampling. A new analysis of the linearized Aw-Rascle-Zhang system of Partial Differential Equations is developed that unravels conditions for travelling waves to expand in the system. A comparative study of a dual splitting algorithm we developed for distributed control reveals new results that highlight how the messages being transmitted are more useful to the cohort of agents for control than for an adversary to eavesdrop on individuals. The regularization scheme we developed for neural control policies enabled extensive and robust control ability that compares with cutting edge parametric control strategies despite that no preliminary calibration is needed with our method.

The applications entailed in our numerical experiments span the fields of quantitative finance, macroscopic traffic modeling, Mobility-as-a-Service, electrical load balancing, and optimal ramp metering for freeways.

The alternate representations we develop are statistically efficient, scale naturally and are readily usable with collections of data-sets or controllers which may not rely on similar representational conventions.

The Sacramento-San Joaquin River Delta in California becomes inadequate in fresh water resources, while the water demand in California keeps increasing. Large-scale numerical flow models, for example Delta Simulation Model II (DSM2) and River, Estuary, And Land Model (REALM), used as crucial water resources management tools, are capable of providing critical information about tidal forcing and salinity transport in the bays and channels of the Delta. Reliable flow estimation and prediction of these models, however, largely depend on an accurate representation of open boundary conditions and initial conditions, which are usually calibrated against historical data sets acquired from Eulerian measurements near the boundaries.

In large watershed, unfortunately, these measurements have demonstrated many intrinsic limitations, for example small spatial coverage and sparse temporal sampling. Also, existing Eulerian sensors have many recorded failures, such as broken gauges, sensor drifts, process leaks, improper measuring devices, and many other random sources. More importantly, if the hydraulic system is radically altered, as in the case of extensive levee failures, the historical data sets can be of limited usage.

In this dissertation, a sensing-modeling system featuring rapidly deployed Lagrangian drifters is developed. The system is capable of predicting regional flows and transport in the Delta in a real-time mode, without dependence on historical data.

Lagrangian data is obtained when floating drifters move along with the flow and report their locations. The data provides instant information about the flow, including flow advections and eddy dispersions, and is further assimilated into underlying shallow water equation (SWE) models to characterize the flow state.

Different approaches to facilitate the flow estimation have been investigated in this dissertation. First, a variational assimilation method (Quadratic Programming) is applied to a 1D SWE model (Linearized Saint-Venant equations). The assimilation method poses the problem of estimating the flow state in a channel network as a quadratic programming by minimizing a quadratic cost function -- the norm of the difference between the drifter observations and the model velocity predictions -- and expressing the constraints in terms of linearized equalities and inequalities. The problem is then efficiently solved using a fast and robust algorithm. The approach is easy to implement and low in computation costs.

Later, a sequential assimilation method (Ensemble Kalman Filtering) is implemented to a 2D SWE model (depth-integrated Navier-Stokes equations). The assimilation method involves a series of state analysis and updates, where the observed Lagrangian data is incorporated into the state one step at a time to incrementally correct the model prediction. The implementation of this method demands powerful computation ability, and is achieved on high-performance computing clusters at NERSC.

To assess the performance of the proposed data assimilation methods, we investigated a distributed network of channels, subject to quasi-periodic tidal forcing, in the Sacramento-San Joaquin River Delta. Field operational experiments were carried out with a fleet of over 70 floating drifters, deployed within approximately 0.55 km^{2} of the river network. During the experiments, more than 325,000 GPS readings were taken from the floating drifters and collected, in real time, onto a central server. It is the first experiment of this kind conducted at such scale, where high-density Lagrangian data have been collected in a real river environment and successfully assimilated over a full tidal cycle.

It is demonstrated that both of the proposed assimilation methods (i.e., QP in 1D SWE model and EnKF in 2D SWE model) can handle the Lagrangian data with sufficiently accurate estimations. In many practical cases, the 1D flow estimation is adequate for water resource management to retrieve critical flow characteristics in a prompt and efficient manner. In the case of complex channel geometry, however, the 2D flow estimation is vital to describe the hydraulic system.

Mixed autonomy characterizes problems surrounding the gradual and complex integration of automation and AI into existing systems. In the context of mobility, we consider: how will the gradual introduction of self-driving cars change urban mobility? In this dissertation, we develop machine learning and optimization techniques to address three key challenges: 1) quantifying the behavior of such complex systems, 2) addressing inherent sensing limitations, and 3) mitigating negative effects of introducing the automation.

We demonstrate that deep reinforcement learning (RL) can serve as a unifying framework for studying the behavior of disparate and complex scenarios common in mixed autonomy systems. In particular, using deep RL, we find that automating a small fraction of vehicles in various traffic scenarios can result in a significant system-level velocity increase and numerous emergent driving behaviors. We demonstrate through the development of variance reduction techniques for policy gradient methods, that deep RL has the potential to scale to high-dimensional control systems, such as traffic networks and other mixed autonomy systems. We additionally present Flow, an open source RL platform with the goal of easing the design and study of disparate traffic scenarios. To address sensing limitations inherent when only parts of a system are automated, sensor fusion is explored. In particular, we introduce a convex optimization method for cellular network measurements from AT&T at the scale of the Greater Los Angeles Area, to address a flow estimation problem previously believed to be intractable. Finally, when automation reduces the cost of the activity (of transport), anticipated negative effects include induced demand and increased energy consumption. We study how the design of the mobility system itself can mitigate these effects. In particular, joint work with Microsoft Research provides insight into how high-occupancy vehicle lanes can simultaneously satisfy comfort and time preferences of users, and provide system benefits. We introduce combinatorial optimization methods based on clustering and local search for the resulting ridesharing problem. Together, these learning and optimization methods demonstrate that a small number of vehicles and sensors can be harnessed for significant impact on urban mobility, and shed light into the future study of mixed autonomy systems.

The research presented in this dissertation is motivated by the need for well-posed mathematical models of traffic flow for data assimilation of measurements from heterogeneous sensors and flow control on the road network.

A new 2 X 2 partial differential equation (PDE) model of traffic with phase transitions is proposed. The system of PDEs constitutes an extension to the Lighthill-Whitham-Richards model accounting for variability around the empirical fundamental diagram in the congestion phase. A Riemann solver is constructed and a variation on the classical Godunov scheme, required due to the non-convexity of the state-space, is implemented. The model is validated against experimental vehicle trajectories recorded at high resolution, and shown to capture complex traffic phenomena such as forward-moving discontinuities in the congestion phase, which is not possible with scalar hyperbolic models of traffic flow. A corresponding mesoscopic interpretation of these phenomena in terms of drivers behavior is proposed.

The structure of the uncertainty distribution resulting from the propagation of initial uncertainty in weak entropy solutions to first order scalar hyperbolic conservation laws is characterized in the case of a Riemann problem. It is shown that at shock waves, the uncertainty is a mixture of the uncertainty on the left and right initial condition, and the consequences of this specific class of uncertainty on estimation accuracy is assessed in the case of the extended Kalman filter and the ensemble Kalman filter. This sets the basis for filtering-based traffic estimation and traffic forecast with appropriate treatment of the specific type of uncertainty arising due to the mathematical structure of the model used, which is of critical importance for road networks with sparse measurements.

As a first step towards controlling general distributed models of traffic, a benchmark problem is investigated, in the form of a first order scalar hyperbolic conservation law. The weak entropy solution to the conservation law is stabilized around a uniform solution using boundary actuation. The control is designed to be compatible with the proper weak boundary conditions, which given specific assumptions guarantees that the corresponding initial-boundary value problem is well-posed. A semi-analytic boundary control is proposed and shown to stabilize the solution to the scalar conservation law. The benefits of introducing discontinuities in the solution are discussed. For traffic applications, this method allows us to pose the problem of ramp metering on freeways for congestion control and reduction of the amplitude of the capacity drop, as well as the problem of vehicular guidance for phantom jam stabilization on road networks, in a proper mathematical framework.