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.

During the 2010s decade, the increase of connectivity in the world led to the development of navigation applications that help vehicles to travel within the transportation network using real-time traffic information. Information-aware routing changed traffic patterns by spreading congestion in the network. Before information-aware routing, route choice was dictated by direction signs, themselves prescribed by city traffic plans. As a consequence, with these new routing behaviors, some traffic plans have been outdated.

From a game theoretical point of view, by providing vehicles with the fastest path to reach their destination, information-aware routing suggestions direct the state of traffic toward a Nash equilibrium. The gap between the state of a game and a Nash equilibrium can be measured with the average deviation incentive. Using the restricting path choice model, we show that the average deviation incentive monotonically decreases when information-aware routing behaviors increase.

On the ground, if information-aware routing behaviors might (or might not) increase the overall transportation efficiency, some local roads received more traffic than the one they are designed to sustain. In Los Angeles, CA, we measure a 3-fold increase in the flow of one I-210 off-ramp between 2014 and 2017. To our knowledge, this is likely a consequence of the rise of information-aware routing behaviors due to an increase in navigational-app usage. Travel time data shows the travel time equalization between the main Eastbound I-210 route between Pasadena, CA, and Azusa, CA, and some alternate routes using local roads. The travel time equalization expresses that the state of traffic is a Nash equilibrium, which demonstrates the presence of information-aware routing behaviors. However, the severity of information-aware routing cannot be quantitatively assessed globally due to the lack of available floating-car data (trajectory data). Qualitatively, many cities and neighborhoods reported negative externalities of cut-through traffic due to information-aware routing: Los Angeles, CA recorded several crashes on the steep Baxter Street, Leonia, NJ reported a fatality on the Ford Lee Road, and Fremont, CA faced the challenges of cut-through traffic on the Mission Boulevard. All around the world, cut-through traffic might induce higher travel times, delays, unreliable travel times for residents, noise, gas emissions, traffic accidents, decrease accessibility in affected neighborhoods, wrong directions, and infrastructure damage, among others. To mitigate these issues, many cities changed the design of their road network. Others used cap-and-trade techniques (e.g., access restriction for non-residents on the Ford Lee Road in Leonia, NJ), or Pigovian taxes (e.g., road pricing on Lombard Street in San Francisco, CA). The city of Fremont erected new stop signs, built speed bumps, and updated its traffic signal timing plans to decrease the Mission boulevard's attractivity.

To pick the best mitigation techniques to fight against cut-through traffic, we suggest using a digital twin of the city traffic. Traffic microsimulators can replicate, in the digital world, the movement of each vehicle within the road network. Because the challenges of running a traffic simulation are not apparent until one creates their own, we provide a blueprint to develop, calibrate and validate a traffic microsimulation. A traffic simulation of the Fremont, CA neighborhood affected by cut-through traffic due to information-aware routing is made open source, for anyone that would like to understand how information-aware routing might lead to cut-through traffic.

On the way, we realized that simulating the behaviors of each vehicle in the network is computationally expensive. Therefore, we proposed to cluster vehicles into a mean-field by developing a mean-field routing game. While macroscopic routing models already exist to estimate how, knowing the traffic demand, traffic evolves in the network, we envision that the mean-field routing game is the best tool to perform large-scale dynamic routing control. We also envision that large-scale dynamic routing control is enabled by navigational applications, with already existing features like eco-routing that have been launched in 2021 by Google Maps.

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

Mathematical models are a mathematical abstraction of the physical reality which is of great importance to understand the behavior of a system, make estimations and predictions and so on. They range from models based on physical laws to models learned empirically, as measurements are collected, and referred to as data-driven models. A model is based on a series of choices which influence its complexity and realism. These choices represent trade-offs between different competing objectives including interpretability, scalability, accuracy, adequation to the available data, robustness or computational complexity. The thesis investigates the advantages and disadvantages of models based on physical laws versus data-driven models through the example of signalized queuing networks such as urban transportation networks.

The dynamics of conservation flow networks are accurately represented by a first order partial differential equation.

Using Hamilton-Jacobi theory, the thesis underlines the importance to leverage physical laws to reconstruct missing information (\emph{e.g.} signal or bottleneck characteristics) and estimate the state of the network at any time and location. Noise and uncertainty in the measurements can be integrated in the model. When measurements are sparse, the state of the network cannot be estimated at every time and location on the network. Instead, the thesis shows how to leverage other characteristics, such as periodicity. From deterministic dynamics, the thesis derives the probability distribution functions of physical entities (\emph{e.g.} waiting time, density) by marginalizing the periodic variable. Using a Dynamic Bayesian Network formulation and exploiting the convexity structure of the system, the thesis shows how this modeling leads to realistic estimations and predictions, even when little measurements are available. Finally, the thesis investigates how sparse modeling and dimensionality reduction can provide insights on the large scale behavior of the network. Large scale dynamics and patterns are hard to model accurately based on physical laws. They can be discovered through data mining algorithms and integrated into physical models.

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.

This dissertation is mainly focused on assimilation of data into hydrodynamic models of water flow in open channel networks which is motivated by the need for accurate flow models in various applications such as emergency response and flood monitoring systems, automated gate systems and hydrological studies. We investigate application of different data assimilation techniques in different scenarios to incorporate the available flow measurements obtained from sensors into flow models to improve their accuracy.

Water flow in open channels is an instance of the so-called distributed parameters systems in which the dynamics of the system is described by a set of partial differential equations. As the flow model, the Saint-Venant equations, also known as shallow water equations, which are a set of first-order hyperbolic nonlinear partial differential equations are used. Different practical scenarios are considered. In a case in which streaming measurements of the flow are available and real-time estimation of the flow state is desired, we present how standard state estimation techniques such the Kalman filter, the Extended Kalman filter and the Unscented Kalman filter can be applied to integrate the available measurements into the shallow water equations. It is also shown how these techniques can be adapted to a case in which some of the model parameters are unknown to estimate unkown parameters along with the state of the system.

For data assimilation in large-scale networks which lead to high dimensional models, application of two sequential Monte Carlo methods, the optimal sampling importance resampling and the implicit particle filters, is considered. The computational cost of propagating each particle is higher in implicit particle filters, however, they provide more accurate results with smaller number of particles by choosing the particles in a way that they belong to the high probability regions of the posterior density function. We also propose a maximum-a-posteriori-based method to perform the state estimation which is shown to perform better in terms of both accuracy and computational cost for the application of interest.

For flow estimation in tidally influenced channels, an efficient estimation method which takes advantage of spectral decomposition of the state is proposed. The estimation problem is formulated as a least squares regression with an $l_1$-norm regularization, known as the LASSO, and a homotopy-based algorithm is implemented to solve the resulting optimization problem recursively as new measurements become available.

Finally, we consider the problem of optimal topology design in multi-agent systems for efficient average consensus. The network design problem is posed in two different ways. (1) Assuming that the maximum communication cost, i.e. the maximum number of communication links, is known, the goal is to find the network topology which results in the fastest convergence to the consensus (in presence of communication time delays on the links). (2) If a minimum performance of the protocol is required, the design problem is posed as finding the network with lowest possible communication cost which fulfills the required performance. The design problem is formulated as an optimization problem which is finally transformed to a mixed integer semidefinite program.

Large physical systems are increasingly prevalent, and designing estimation strategies for them has become both a practical necessity and a complicated problem. Their sensing infrastructure is usually ad-hoc, and the estimate of interest is often a complex function of the data. At the same time, computing power is rapidly becoming a commodity. We show with the study of two estimation tasks in urban transportation how the proper design of algorithms can lead to significant gains in scalability compared to existing solutions.

A common problem in trip planning is to make a given deadline such as arriving at the airport within an hour. Existing routing services optimize for the expected time of arrival, but do not provide the most reliable route, which accounts for the variability in travel times. Providing statistical information is even harder for trips in cities which undergo a lot of variability. This thesis aims at building scalable algorithms for inferring statistical distributions of travel time over very large road networks, using GPS points from vehicles in real-time. We consider two complementary algorithms that differ in the characteristics of the GPS data input, and in the complexity of the model: a simpler streaming Expectation-Maximization algorithm that leverages very large volumes of extremely noisy data, and a novel Markov Model-Gaussian Markov Random Field that extracts global statistical correlations from high-frequency, privacy-preserving trajectories.

These two algorithms have been implemented and deployed in a pipeline that takes streams of GPS data as input, and produces distributions of travel times accessible as output. This pipeline is shown to scale on a large cluster of machines and can process tens of millions of GPS observations from an area that comprises hundreds of thousands of road segments. This is to our knowledge the first research framework that considers in an integrated fashion the problem of statistical estimation of traffic at a very large scale from streams of GPS data.

This dissertation develops a general, scalable framework for controlling dynamical, networked systems based on mathematical optimization theory, with a strong focus on applications to freeway traffic management. The generality of the framework allows for controllers to consider high-level objectives applied to systems with complex, nonlinear dynamics.

A continuous freeway traffic model and its discretization was developed specifically for onramp metering control. The application serves as the motivating example behind the theory developed subsequently. To apply effective control on such systems, a discrete-adjoint-based model-predictive-control (MPC) approach for controlling networked systems of conservation laws is presented, with explicit derivations for ramp metering applications. Linear scalability of the method with respect to network size and time horizon is derived for the discrete adjoint computations. To enable a more asynchronous control architecture, the dissertation presents a distributed optimization algorithm for dynamical, networked systems. The algorithm allows for a physical network to be partitioned into subnetworks that optimize locally and communicate only with adjacent subnetworks to achieve a globally optimal performance.

Within the context of the Connected Corridors project associated with UC Berkeley PATH, the developed theory was implemented in a production-level traffic management and simulation environment. Numerical examples applied to the San Diego I15 freeway are presented alongside the theory to motivate the highly practical aspects of the work. Simulations demonstrate the superiority of the MPC approach over existing methods widely used in practice.

The optimization tools are applied to an investigation of security and vulnerabilities of traffic control systems. The potential impact of a compromise of freeway traffic metering lights is analyzed using MPC and multi-objective optimization tools. Several realizable scenarios that exploit traffic system vulnerability locations are constructed and simulated to illustrate the severity of compromises.

Investigations are made into optimal rerouting strategies while controlling only a subset of network flow. A novel behavioral model is developed to account for the interaction of controllable and uncontrollable agents sharing a single flow network, where latency is a function of total flow. Using static freeway traffic models and communication network models, a framework based on convex optimization techniques is presented for computing rerouting policies, with numerical examples given for both freeway and communication networks.