Short summary
The focus of my research is algorithm design and implementation,
specifically in the area of control and optimization. Since my
arrival at UC Berkeley, I have been interested in the development of
computationally efficient optimization-based control and estimation
algorithms. I have applied them to systems modeled by partial differential equations (PDEs). My algorithms have been applied to three areas of Civil and
Environmental Engineering:
My specific interest is the integration of mobile measurements into
distributed parameter systems models such as PDEs. The applications
of my work to highway traffic and shallow water flows have benefited
from the rapid and recent expansion of the mobile internet. My work
on highway traffic is one of the early research instantiations of a
location based service, heavily relying on mobile participatory
sensing. My research on PDEs has laid some mathematical foundations
for Lagrangian sensing. My work is also an example of one the
aspects of the "web 2.0" paradigm: user-generated content. In the
present case, smartphones carried by humans act as sensors and share
information.
My contributions can
be summarized in four categories: mathematical results, algorithms,
experiments and testbeds, which are outlined below. I have produced
mathematical proofs as needed (in particular the existence and
uniqueness of solutions of PDEs) that are fundamental contributions
to the field. Most of the algorithms I have designed rely on the
application of specific techniques to the PDEs of interest, such as
viability theory, differential flatness, spectral analysis, finite
differences and convex optimization. Sometimes, I have used analytic
solutions, that were either known, or that I discovered. Almost all
my algorithms have been implemented, most of the time with field
data collected through experiments using testbeds built by my group.
Mathematical contributions.
- Proof of existence and uniqueness of a Barron-Jensen Frankowska solution to a \textit{Hamilton-Jacobi} PDE for a Cauchy problem. Extension of this proof
for the case of internal boundary conditions. Derivation of an
analytical solution to the problem in the case of piecewise affine
conditions.
- Derivation of a new PDE model for highway velocity evolution, called Lighthill-Whitham-Richards-v (LWR-v) model. Proof of
equivalence of the new model with the classical LWR PDE, in the
case of parabolic flux functions.
- Derivation of a nonlinear discrete time dynamical system model
for velocity compatible with the entropy solution of the LWR PDE,
called Cell Transmission Model-v (CTM-v). Extension to
general networks using linear programming.
\item Design of a controller for exponential stability of switched
linear hyperbolic PDEs.
Algorithmic contributions.
- Ensemble Kalman Filtering (EnKF) algorithms for real-time estimation
for the CTM-v model. EnKF algorithms for one-dimensional and
two-dimensional shallow water equations using Lagrangian sensing.
- Quadratic programming based data assimilation algorithm for
one-dimensional and two-dimensional shallow water equations.
- Data reconciliation algorithm for one-dimensional shallow
water equations using quadratic programming on a spectral
representation of the solution.
- Differential flatness-based controller design of a hydraulic system.
- Dual decomposition algorithm for optimal control of an
aggregate model of air traffic flow.
Experimental contributions.
- Field experiment, Mobile Century, February 8, 2008,
involving 100 cars measuring traffic on I-880 in California to
demonstrate the possibility of traffic reconstruction using cellular
phones.
- Field operational test, Mobile Millennium, launched
November 10, 2008 in Northern California, to enroll up to 10,000
users to participate in traffic data collection using cellular
phones (number of users to this day: more than 4,000).
- Field deployments, Georgianna Slough and Sacramento River,
to collect Lagrangian sensor data and to deploy a submarine and
static sensing equipment.
Testbeds.
- The Mobile Millennium system, built jointly with Nokia. This traffic information system
is operational in Northern California, and includes smartphone
software, which is downloadable from our website.
- Lagrangian floating sensor network. This testbed includes a
fleet of 20 floating sensors, some motorized, with communication,
sensing and control capabilities onboard the fleet.
Nation wide air traffic management using aggregate Eulerian flow models
My initial goal when I arrived at UC Berkeley was to contribute to Next Generation Air Traffic Control Systems (NGATS)
outlined by the Joint Program Development Office (JPDO) in
Washington, by developing mathematical techniques which can be
applied to both inter-aircraft control procedures and high level
traffic management problems.
Algorithms for multiple vehicle control. My
original Ph.D. work is in the design of computationally efficient
controller synthesis methods for networks of dynamical systems,
applied to air traffic control. The air traffic control environment
is a temporally evolving infrastructure, clustered into regions with
local control authorities and limited communication. Tasks in this
type of network cannot be achieved by the decentralized
superposition of classical controllers of dynamical systems, yet
treating the problem globally results in a physically and
computationally intractable centralized control problem. During my
Ph.D., I approached the problem of controlling subportions of the
airspace by abstracting the overall coordination of the agents into
subcomponents each of which I treated as a task scheduling problem.
Crucial to this task was maintaining the ability to map the
resulting schedule back to single tasks with corresponding proofs of
safety for aircraft. This work resulted in the following journal
publications, of which the content is a portion of my Ph.D. work:
Flight automation algorithms. During and after my
Ph.D., I also worked on collaborations with other students from the
Hybrid Systems Laboratory at Stanford to study the
possibility of automating specific portions of flights, such as
conflict avoidance in the en route airspace and landing. The
algorithms generated through this collaboration rely mainly on the
efficient computation of solutions to the Hamilton-Jacobi-Bellman partial differential
equation (HJB PDE), from which optimal control strategies can be
obtained. I have posed the problem of proving safety of maneuver
assignment in a network of vehicles as a differential game, in which
the propagation of an interface delimits the extent of an unsafe
region in space and time. This interface is represented by a wave
front described by the HJB PDE. This framework defines reachable
sets as subsets of the state space from which evolution of the
dynamical system will always remain safe. I generated a proof
unifying HJB PDE-based reachability analysis, minimum time to reach
formulations and viability theory. Thus, in addition to algorithms
for fast safety verification, my research has contributed to a
better understanding of the mathematical and numerical aspects of
reachability analysis. The algorithm was published in the IEEE Transactions on Automatic Control and two applications
for autopilots were subsequently published in specialized journals:
- A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games, I. Mitchell, A. Bayen and C. Tomlin, IEEE Transcations on Automatic Control, 50(7), pp. 947-957, July 2005, doi:10.1109/TAC.2005.851439
- Computational techniques for the verification and control of hybrid systems, C. Tomlin, I. Mitchell, A. Bayen and M. Oishi, Proceedings of the IEEE, 91(7), pp. 986-1001, July 2003, doi:10.1109/JPROC.2003.814621
- Aircraft autolander safety through optimal control based reach set computation, A. Bayen, I. Mitchell, M. Oishi and C. Tomlin , AIAA Journal on Guidance, Control and Dynamics, 30(1), pp. 68-77, January-February 2007, doi:10.2514/1.21562
- Invariance preserving abstractions of hybrid systems: application to user interface design, M. Oishi, I. Mitchell, A. Bayen and C. Tomlin, IEEE Transactions on Control Systems Technology, 16(2), pp. 229-244, March 2008, doi:10.1109/TCST.2007.903370
 Development of Eulerian models of Air Traffic
Flow. Towards the end of my Ph.D., I became interested in Eulerian models of air traffic flow, which are models
inspired from highway traffic flow theory. These models rely on
control volume based mass balances, which can either be expressed
using PDEs or dynamical systems. In joint work with NASA Ames, I
developed a new PDE based model of air traffic flow, and applied
this model to the en route airspace and arrival airspace in the
Chicago area, to show the possibility of using such mathematical
abstractions to perform high altitude traffic flow management. The
resulting journal article published in 2006 gave me a first
opportunity to become familiar with adjoint-based
optimization, a powerful technique which I have further developed
in my current research activities at Berkeley. In this article, we
solve the flow optimization problem as a general nonlinear
optimization program (hence the use of the general adjoint
formulation).
Convex formulation of traffic flow problems. I
worked on the reformulation of the nonlinear optimization program
described in the article above as a convex program. This initial
formulation of the problem is not convex. However, a specific
variable change and the introduction of additional variables enable
the convexification of the problem. Once this formulation posed, the
use of linear schemes to discretize the problem enable formulation
of the problem, so it can be solved numerically. The difficulty lies
in the discretization of the linear PDEs which appear in the
continuous problem (linear finite difference schemes have notorious
issues with nonsmooth solutions of these PDE). We developed a suite
of linear numerical schemes, out of which we identified a few such
that the numerical solution of the problem can be cast in a convex
form that works in practice. The resulting numerical problems were
implemented on a benchmark case for the Oakland airspace. The
results were published in the following article, which now serves as
a reference to show that the problem is convex:
 NAS-wide traffic flow management using linear
programming.}} When I arrived at Berkeley, I started to develop a
full National Airspace System (NAS) model of traffic flow.
Our fundamental question was to find the physical scale at which
traffic should be aggregated so that we could determine a
mathematical representation of traffic flow which would be
simultaneously accurate and computationally tractable, if
implemented at a NAS-wide level. This research resulted in a new
model called Large Capacity Cell Transmission Model or
CTM(L), which describes traffic as an integer linear dynamical
system on a multicommodity flow network. The construction of the
model and its implementation with Enhanced Traffic
Management System (ETMS) and Aircraft Situation Display to
Industry (ASDI) at a NAS-wide level resulted in a journal
submission which lays the foundation of the underlying mathematical
model we developed:
The figure above (click here to enlarge)} shows the underlying network constructed
in our algorithm from one full year of data (the amount of data
collected for one day can be seen from this figure. In our
work, the multicommodity flow structure is laid on top of the graph
shown above. In order to establish the
value of the model in the scientific community and air traffic
community, the performance of the model was compared with other
models (such as the PDE model developed at the end of my Ph.D. and
models developed in industry). This was published in several
conferences. A summary of the comparison work was published in
Networks and Heterogeneous Media, which is a journal with
emphasis on mathematical techniques applied to modeling. In order to
show the assets of our model, it was crucial not only to detail the
data work performed, but also to describe the underlying
mathematical techniques used, and compare their efficiency and
performance:
 Posed using the framework presented earlier, the traffic flow
management problem is NP-hard and therefore intractable in real
time at a NAS-wide level. The size of the problem is enormous.
Indeed, the model integrates all aggregated routes statistically
recorded for the nominal period of one year for the entire United
States. While this level of precision in the model is important for
accurate sector count control, it comes at the price of
computational cost. Our next efforts have thus focused on the
development of computationally efficient algorithms to control the
system, mainly based on linear programming relaxation and dual decomposition. Using these techniques, we were able to
solve sparse linear programs of up to 10 billion variables in
real-time (i.e. faster than the physical dynamics of the system,
i.e. the speed at which the traffic in the NAS evolves). More
specifically, we reduced a linear program with 5.10^9
variables and 10^10 constraints into 5.10^4 linear
programs with 10^6 variables and 2.10^6 constraints in a
decentralized manner, which made the decomposition work in real time
with reasonable memory requirements (it does not require any
parallel computing). The corresponding results were submitted to the
IEEE Transactions on Control Systems Technology, as a large
scale application of a known optimization technique:
Mobile Millennium: using cell phones as traffic sensors
Scope of Mobile Millennium. Starting in
September 2007 and during the span of 14 months, my research group
worked jointly with Nokia at an aggressive pace, to build one of
the first traffic monitoring systems based on GPS enabled
smartphones in the world. Some factors which make this system
different from similar systems include the following features:
- It is privacy aware, does not ``track'' people Nokia Privacy by designTM spatially
aware sampling.
- It is designed to use GPS information (not cell tower information).
- It is phone agnostic: currently for Nokia and Blackberry phones.
- It is carrier agnostic: currently for AT\&T, T-mobile and Verizon.
- It is free: the software is available for the public to
download.
- It does not require any car aftermarket device.
- It covers the highways and arterials (i.e. the secondary road network).
- It integrates other sources of data (taxi and bus GPS, loop
detector, historical, radar).
New mathematical approaches to the modeling and
estimation of highway traffic flow. Highway traffic flow is
traditionally modeled using networks of first order hyperbolic
conservation laws, a specific class of nonlinear PDEs. PDEs in this
class exhibit significant mathematical challenges due to the
nonlinearity of the phenomena involved, such as shock waves.
Reconstructing the solutions to these PDEs from fixed (Eulerian) measurements using inverse modeling and data
assimilation techniques has been done in the past. My research
agenda over the next few years is to define the mathematical basis
for highway traffic flow reconstruction using mobile
(Lagrangian) measurements, i.e. measurements obtained from
probe vehicles. For this, a new class of algorithms needs to be
developed, which relies on quantities measured by vehicles rather
than ground-based sensors. In the case of cellular phones, one has
access to the speed of specific cars through drivers equipped with
the device. This provides real-time information about vehicle
location, which was previously inaccessible. In mathematical terms,
this can be thought of as adding \textit{in traffic} boundary
conditions to a PDE problem: the availability of measurements inside
the computational domain adds constraints to be satisfied at
locations other than the boundary. For this, I derived an explicit
form of weak boundary conditions for scalar hyperbolic
conservation laws with concave fluxes which is directly applicable
to highways.
Static sensor network placement problems. Hosted
by the \textit{California Center for Innovative Transportation}
(CCIT), I started working on the problem of travel time
reconstruction from fixed measurements (loop detectors) and
transponder data (FasTrak toll tag readers onboard cars, in the case
of the Bay Area). This research, funded by the California Department
of Transportation, was a first step towards the development of inverse modeling techniques and data assimilation
techniques applicable to highway systems. The goal of the project
was to generate sensor deployment policies based on optimal sensor
placement: given a fixed number of sensors to be deployed, we wanted
to determine the configuration of sensors that provides the most
accurate travel time estimation for vehicles.For this, we worked on the construction of simple flow models and
optimization algorithms based on dynamic programming to minimize
travel time prediction error. This part of our work led to a
practical dynamic programming algorithm used for static sensor
placement, which we later used in the deployment of the
Mobile Millennium virtual monitoring infrastructure. This
part of my research contributes to a better understanding and use of
current technologies. This led to the following publication, which
has journal archival status in the Transportation Engineering
community (it goes through three successive rounds of edits before
fully accepted).
Inverse modeling for highway traffic flow. My
major contribution in the field of highway traffic monitoring is the
development of inverse modeling techniques which can incorporate
Lagrangian measurements to reconstruct highway traffic flow. The
fundamental difficulty in this task is the efficient use of flow
models as underlying constraints in an optimization program, which
tries to minimize the error between measurements and estimates.
These questions are common in oceanography and are relatively novel
in highway traffic flow monitoring. As mentioned before, the use of
the LWR PDE for inverse modeling purposes comes with some challenges
due to the mathematical nature of the solutions to the PDE (weak
solutions have shocks). This is a major difficulty in using
traditional inverse modeling techniques such as adjoint
based optimization, which involves differentiating a discontinuous
solution defined almost everywhere. Several approaches can be used
to alleviate these difficulties. My reasearch team investigated
\textit{Newtonian relaxation}, a technique which consists of adding
a source term to the PDE in order to minimize the discrepancy
between the observations and the predictions without differentiating
the PDE or the solution. This work is was submitted to Transportation Research B.
One of the benefits of Newtonian relaxation is the simplicity of the
method. In addition, the implementation is straightforward, since it
can use the same numerical code as the forward simulations of the
model. This method is common in oceanography, and has been widely
used because of its ease of implementation. However, no convergence
proof exists to show the optimality of the estimate. Therefore,
another avenue to pursue, which is more theoretical, is to use
underlying flow equations for which the nonsmoothness or
nondifferentiability can be mathematically properly handled.
The Moskowitz Hamilton-Jacobi PDE. In a joint
collaboration with a viability group at the University Paris
Dauphine
in France, we have produced a proof of the existence and
uniqueness of an upper semi continuous viscosity solution to a
Hamilton-Jacobi (HJ) PDE that models the cumulative number
of vehicles on the highway. The problem was posed by Newell in 1993
as part of his famous trilogy on traffic flow, but the mathematical
proof defining this solution as the viscosity solution of
Crandall-Evans-Lions (1983) or alternatively the upper semi
continuous viscosity solution of Barron-Frankowska (1993), had never
been formally done. The key ingredient which enabled the
aforementioned proof is the description of the solution in
epigraphical form, i.e. the characterization of the epigraph of the
solution as the capture basin of a target under specific dynamics.
This result relies on the foundational work of Professor Jean-Pierre
Aubin, the inventor of viability theory, whose visionary
mathematical contributions (differential inclusions, set valued
analysis, viability theory, morphological analysis) allowed for the
characterization of the solution of this PDE as a capture basin.
This is the main achievement of the following article.
 Lagrangian internal boundary conditions. One
project I am currently working on is to unify this mathematical
framework with the original formalism of Newell and its extensions
(Moskowitz function) due to Professor Carlos Daganzo. Our work
unifies the aforementioned upper semi continuous viscosity solution
of Barron-Frankowska, the entropy solution of the LWR PDE and a
viscosity supersolution of the Moskowitz problem posed by
Newell-Daganzo. The framework developed in the SIAM Journal
on Control and Optimization article is
general and can be extended to incorporate in traffic
boundary conditions in the form of Lagrangian data, without
altering the mathematical nature of the solution. This is a major
breakthrough: using this technique, one can now not only prescribe
initial and boundary conditions to a Cauchy problem for the
Moskowitz HJ PDE, but can also include internal conditions! This is
particularly important for highway traffic monitoring, since it is
extremely unusual for practical applications to have information at
all boundaries or junctions of the entire network all the time, and
to have initial conditions in every location. Now that additional
information is available from cellular phones, the added
"internal" information can be incorporated in the traffic flow
models as well. Because of the noise of the data, all data points
are not necessarily compatible with each other, which usually would
lead to an ill posed problem. The results obtained with my method
also enable us to characterize the well posedness of the problem: in
the presence of incompatible or self-contradicting data, the method
enables the identification of the data to be removed for
consistency. Note that this situation happens all the time in
practice, because of measurement error. This result is one of the
strongest contributions of my research. The result is not only a
scientific breakthrough, but the impact on practical problems is
enormous, since nearly 40% of the loop detectors in California
provide faulty measurements every day! The resulting algorithm has
already been tested in Next Generation Simulation (NGSIM)
data, for which video records constitute ground truth knowledge of
traffic. The theoretical results of the algorithm are available in
the following article.
Once the solution to the problem of incorporating internal boundary
conditions to the Cauchy problem for the Hamilton-Jacobi equation
was solved, the problem of numerical computation remained unsolved.
A second breakthrough happened when we discovered that for piecewise
affine data, the problem could be solved analytically. The
assumption of piecewise affine data is fairly common in numerical
analysis: most finite difference schemes make this assumption. The
method we proposed to solve this equation analytically has three
benefits over any finite difference scheme:
- It does not require any grid (neither in space nor time).
- It does not require any stability condition of CFL type.
- It does not have any numerical error beyond machine
accuracy evaluation of an analytical function.
As a result, the method has infinitesimal computational time and
memory requirements (compared to any finite difference scheme),
since it consists of the numerical evaluation of an algebraic
expression. This is a major contribution, which significantly
reduces the computational cost of any implementation (memory, CPU
time, data volume). Thus, this is a breakthrough with high potential
for real-time implementation. The details of the analytical
computation are explained in the following article.
From a mathematical perspective, we find ourselves extremely lucky
to have been able to discover a new analytical solution to a known
PDE in the 21st century! From a practical perspective, the impact of
this solution is enormous, since it reduces model computational time
virtually to zero. My group is currently working on the use of this
solution for robust travel time estimation, a problem which we
managed to reduce to linear programming using the aforementioned
analytical solution. This other breakthrough was published in a
preliminary form as a conference article being prepared for
publication in the SIAM Journal on Control and
Optimization.
 Distributed velocity models for highway traffic
reconstruction using Lagrangian measurements. Because cellular
phones can only measure velocity, not vehicle density on the
highway, we decided to create a new model to describe the evolution
of the velocity field on the highway. The problem turned out to be
harder than initially thought, as in some cases, such a model can be
found in PDE form, yet in others it can be proven it is not possible
to derive such a model. The main difficulty is to enforce
mass conservation and the entropy solution of the
LWR PDE at the same time when deriving the new model for velocity.
Our work identified the conditions in which such a model can be
derived in PDE form. In the cases in which this is not possible, we
derived a discrete model compatible with both mass conservation and
the entropy solution, which as a corollary does not have a
counterpart in the continuous time continuous space setting. Because
the resulting numerical models (obtained with finite differences)
are nonlinear and nonsmooth in both cases, we needed to derive an Ensemble Kalman Fitering (EnKF) algorithm to estimate the
state from Lagrangian measurements. Note that the nonsmoothness of
the system prevents us from using Extended Kalman Filtering, but the
linearity of the observation equation enables us to avoid using
Particle Filters. The resulting algorithm proved to perform
extremely well in practice, as was demonstrated in an experimental
field test Mobile Century, (see below). The algorithm is
now operational and running in the Mobile Millennium
system, performing online estimation in real-time for 9,000 PDEs
(all of Northern California's highway segments). The mathematical
results leading to this algorithm are described in the following
article.
 Design and implementation of a new traffic
information system. The architecture of the Mobile
Millennium system is illustrated here. It was jointly conceived by
Nokia and UC Berkeley. One of the key components of Mobile
Millennium is privacy. The
prototype architecture of the system was jointly designed jointly with Rutgers University
and was used for the privacy analysis of the system. Later, my team
and Nokia's team extended the initial design to make the prototype
operational. Mobile Millennium is currently operational in
Northern California. Nokia has already extended the system to the
rest of the United States, i.e. the three left columns of the system
are operational anywhere in the United States. The extension of the
UC Berkeley portion to the United States is currently underway in a
joint effort with Navteq and Nokia. The prototype architecture used
for our work is described in the journal status conference article
below. It is likely that a second article will be written now that
the system has been fully deployed. The architecture and the
processes have significantly changed. In addition numerous lessons
were learned, which are interesting in themselves and contribute to
the field of mobile and participatory sensing.
- Virtual trip lines for distributed privacy preserving traffic monitoring, B.Hoh, M. Gruteser, R. Herring, J. Ban, D. Work, J.-C. Herrera, A. Bayen, M. Annavaram, Q. Jacobson, Mobile Systems and Applications (MOBISYS), June 17-18 2008, Brekenridge, CO. doi:10.1145/1378600.1378604 [AR 18%]
Field testing Mobile Century and
launching Mobile Millennium.A proof of concept
experiment was necessary to demonstrate that the technology we
designed would work. Nicknamed the Mobile Century
experiment, the prototype privacy-aware data collection system was
tested on February 8, 2008, and used to estimate traffic conditions
for a day on the I-880 near San Francisco, CA. With the help of 165
UC Berkeley students which my group hired, 100 vehicles carrying
Nokia N95 phones drove repeated loops of six to ten miles
continuously for eight hours. The operation was supervised by 40
student officers, which I hired from the ASCE and IEEE student
organizations. The Mobile Century vehicles represented
approximately 2% - 5% of the total volume of traffic on the main
line of the highway during the experiment. This section of highway
was selected specifically for its complex traffic properties, which
include alternating periods of free-flowing, uncongested traffic,
and slower moving traffic during periods of heavy congestion. The
Ensemble Kalman Filtering algorithm described earlier was
implemented in a live system available to the press and the VIP
guests invited to the event. I held jointly a press conference with
Bob Iannucci, the CTO of Nokia, and Randy Iwasaki, the Chief Deputy
Director of the California Department of Transportation, during
which the press and the invitees could witness the performance of
the system.
During the press conference, a five car pile up accident happened
(none of our vehicles were involved), creating a massive traffic jam
that we captured on screen before any other traffic information
system available on that day. The results of
Mobile Century are summarized in the following article.
After the success of Mobile Century, a partnership was
created between UC Berkeley, Nokia, Navteq, the California
Department of Transportation and the US Department of Transportation
to establish Mobile Millennium, a traffic information
systems available to the public for free on their phones. After a
few months of ceaseless work, Mobile Millennium was
launched and opened to the public on November 10th, 2008 from the
Berkeley campus in a press conference held at the CITRIS
headquarters. Any user with the proper phone can now download the Mobile Millennium software from the Mobile Millennium website. More information about Mobile Millennium can be obtained at
the URL above. The website not only contains instructions on how to
download the software, it also presents the technology, contains
published articles related to the project and displays photographs
and video clips from our media and press events. Soon, it will
contain data obtained from the system, so that other universities
can also use the data for research purposes.
Towards stochastic dynamic routing in the
transportation network. As the traffic estimation engine becomes
more mature and robust and as the system expands, numerous other
problems have become of interest. In particular, the problem of
routing is of great interest for Nokia and other traffic information
providers. One of the main challenges on which my group has started
working is the quantification of uncertainty due to traffic
variability. Indeed, traffic lane shearing introduces different
speeds of heterogeneous drivers, leading to a range of travel times
for the same trip starting at the same time. My group has started
the development of new flow models which can be used to quantify
this uncertainty. In particular, the following article devises new
numerical schemes for traffic flow models with set valued
fundamental diagrams.
These traffic flow models will be used in the future developments of Mobile Millennium to quantify uncertainty in traffic flow,
which is useful to characterize the uncertainty in the travel time
estimation. In addition, traffic forecast algorithms are under
development to fuse historical demand data with current traffic
conditions (nowcast) in order to obtain forecast travel time.
Inverse modeling for shallow water flows using Lagrangian
sensor measurements
As part of my research agenda at UC Berkeley, I am developing
activities focused on inverse modeling for hydrodynamic systems
using Lagrangian sensors (floating drifters). This involves:
- Creating estimation, inverse modeling and data assimilation algorithms for shallow water flows using Lagrangian sensing (to reconstruct
currents, temperature, and salinity).
- Building hardware/software platforms to test the resulting algorithms and performing field tests.
The platform architecture is illustrated below. As for Mobile Millennium, my
long term goal is to work jointly with public agencies (in
particular the California Department of Water Resources and the US
Geological Survey) to make this testbed available for their
operational needs.
 Inverse modeling algorithms using Lagrangian sensing
for shallow water flows. One of the major challenges for
estimation in hydrodynamic systems when using mobile agents is
underactuation: most of today's floating sensors (motorized or not)
do not have sufficient actuation to sample the system wherever the
user would like them to go. Indeed, for most applications involving
sensor networks evolving in water, currents prevent vehicles from
being able to fully control their motion. Thus, the task of inverse
modeling using floating sensors consists of developing novel
algorithms to reconstruct currents using GPS measurements obtained
with a drifter fleet for which the position is not known a priori
and cannot be controlled. The challenge of performing inverse
modeling in shallow water flows is the computational time required
to reconstruct the flow (usually, adjoint-based optimization
techniques are used, which require a significant number of direct
and adjoint simulations, precluding the use of these techniques for
real-time computing). In general, adjoint based optimization is
often required to handle complex flows for which nonlinearities are
an essential part of the features to be estimated. The cases which I
have encountered for the specific applications of interest I have
tackled in California exhibit numerous features that can be captured
provided the right linearization is performed. This is one of the
contributions I have made in my work.
Variational data assimilation. One standard family
of data assimilation techniques is variational data assimilation. It
consists of minimizing a cost functional encoding the difference
between measurements and estimated variables in a given norm, under
constraints. The constraints can include the model (in the present
case a PDE), boundary and initial conditions, and additional
constraints. Depending on the problem, boundary or initial
conditions are unknown or given with such noise that they cannot be
used to solve the problem by forward simulations. In the general
case, variational data assimilation problems are difficult to solve
because even if the error functional is quadratic, usually, the
constraints are nonlinear (in particular, the PDE, or its
discretization). One of my contributions was to find the proper PDEs
or differentiation schemes to generate linear constraints for the
problems of interest (subcritical flows such as in the Sacramento
Delta). My contribution thus includes the generation of (linear)
finite volume and finite difference schemes to solve simplified
versions of the shallow water equations, in one and two dimensions.
The linearity of this numerical scheme enables the use of quadratic
programming as the main technique used for inverse modeling. The
inverse modeling algorithm is thus posed as a minimization program
in which a cost functional encoding the error between the
measurements and the predictions is quadratic, subject to linear
constraints. The advantages of the method are multifold:
- Optimality. By nature of the quadratic program, the
optimum is a global optimum.
- Long timesteps. Because implicit schemes can be
encoded as linear constraints, one can use longer timesteps (which
are usually not possible for explicit schemes as commonly used in
Kalman Filtering because of the CFL condition). This provides faster
computational times.
- Numerical software. Quadratic programming is a
standard tool for which numerous software can be found.
Using quadratic programming, I have created several variational data
assimilation algorithms which have been tested in simulation in the
form of twin experiments, which use a fully nonlinear model
to generate the flow in simulations, assume Lagrangian measurements
(simulated drifters in the nonlinear flow), and reconstruct the flow
using the algorithm (quadratic program solution). Several articles
have been published which tackle various problems (estimation of the
initial and/or boundary conditions) of the one-dimensional or
two-dimensional shallow water equations:
- Inverse estimation of open boundary conditions in tidal channels, I. Strub, J. Percelay, M. Stacey and A. Bayen, Ocean Modelling, 29(1), pp. 85-93, March 2009, doi:10.1016/j.ocemod.2009.03.002
- Comparison of two data assimilation algorithms for shallow water flows, I. Strub, J. Percelay, O.-P. Tossavainen, A. Bayen, Networks and Heterogeneous Media, (4)2, pp. 409-430, June 2009, doi:10.3934/nhm.2009.4.409
 For completeness, some of the methods developed as part of this
research are also compared in the articles with known techniques, in
particular with Ensemble Kalman Filtering (using the same algorithms
as for Mobile Millennium), which can handle the fully
nonlinear hydrodynamic equations. Using field data gathered with my
drifter hardware platform, the performance method has also been
assessed with experimental data.
Spectral methods based inverse modeling and
control. Because of the periodic nature of tidal forcing, a
spectral representation of one dimensional shallow water equation
solutions is extremely effective in characterizing the signal. In
the case of the Sacramento Delta, the bounded spectrum of the
forcing enables compact representations of the solutions, which are
practical for data assimilation. Using a distributed transfer
function analysis, I have created data reconciliation algorithms,
which rely on the spectral form of the solution. A quadratic
programming routine subsequently reconciliates the data in the
spectral domain. I have implemented this algorithm with static
sensors which were deployed from a boat for a few days in the
Sacramento river, and validated the results against static sensing
infrastructure (from the US Geological Survey). The contributions of
the corresponding article is the use of spectral decomposition of
the solution in reconciliation algorithm.
 Similar mathematical tools can be used for control as well, since
the spectral representation of the solution can also be used to
parametrize it as a function of given inputs. Indeed, spectral
methods are promising for our problems, given the oscillatory
nature of the signals and boundedness of the spectrum. In fact, we
proved the equivalence of the Laplace representation of the solution
with differential flatness on a simplification of the shallow water
equations (the Hayami model), which enabled us to design a
feedforward controller for the equations.
The corresponding algorithm was implemented using a SCADA system in
the Gignac Canal in Montpellier, France, to demonstrate the power of
the method. The results are remarkably accurate, and thus promising
for applications in California, where the Department of Water
Resources will start systematically automating gate operations in
the Delta for management purposes. The experimental results will
appear in the IEEE Control Systems Magazine as an
implementation article of the algorithm above.
 Hardware and software platform development. As for
\textit{Mobile Millennium}, I have built a testbed to demonstrate
the algorithms produced by my laboratory. In the present case, the
testbed has already generated significant amounts of data which are
now used by the Department of Water Resources and the Lawrence
Berkeley National Laboratory. The architecture of the system
developed in my lab is illustrated in the figure above,
and is similar to the Mobile Millennium architecture. In
addition to using the GSM network for communication, it also uses
ZigBee radios. Some of the details of the drifter hardware are shown in the figure above. Drifters are entirely manufactured in my
laboratory. Over the years, we have generated several prototypes,
some purely passive, some motorized. The standard motorized drifters now include
two motors. In the coming years, we will increase our fleet to
incorporate more drifters, so we can start to launch large scale
operations, in which the drifters become autonomous for 48 hours.
While they most likely will not have enough propulsion to fight the
currents, they will have just enough power to reach zero-velocity
locations, which we will use to stabilize them until the tides
reverse so they can navigate upstream the Delta again.
 In addition to the hardware developed in my lab, the operations I
have led have also integrated other equipment from colleagues, in
particular, submarines and static boat deployed sensors. In collaboration with the University of
Porto, we launched a submarine in the Georgianna Slough in Fall
2007, to start experiments with a heterogeneous fleet of vehicles
and integrated measurements with static sensors from my colleague
Professor Mark Stacey which was also deployed as part of our
operations. The group is planning further operations with the Porto research group, in which we will continue to deploy submarines in the Sacramento Delta.
 Drifter hardware: (A)
Fiberglass pipe; (B) Cast fiberglass; (C) Polycarbonate cap; (D)
Clasp; (E) Stand (not part of drifter); (F) Antenna plate; (G)
Electronics; (H) Battery; (I) Bulkhead; (J) GSM antenna connector;
(K) GPS module; (L) Gumstix module; (M) MMC card; (N) Bluetooth
antenna; (O) GSM module; (P) Power switch; (Q) Battery connector;
(R) GPS antenna; (S) Hole for GSM antenna (not shown); (T) Magnetic
switch; (U) Status LEDs; (V) Aluminum tube; (W) olycarbonate plate.
Systems biology
 Modeling, optimization and
simulation of bacterial motion. Bacteria such as Rhodobacter
sphaeroides use a single flagellum for propulsion and change of
orientation. Simple organisms such as this have inspired nanorobotic
designs with potential applications in medicine which motivates the
present work. Together, we developed an elastic model for a single
flagellum bacterium and analyzed the system based on optimization.
The model is based on the method of regularized Stokeslet
which allows for a discretization of the system into particles
connected by spring forces. An optimal elasticity distribution that
maximizes the mean forward speed was obtained. These elasticity
coefficients are obtained through the use of an adjoint-based
optimization scheme. The result was published as the following
journal article.Watch movies of swimming bacteria!
|
