Research

I worked on the Mobile Millennium project at CCIT, and am now working on the Connected Corridor project.

Optimal Routing

I work on optimal routing of flow on congestion networks, with in mind application to traffic networks. Two approaches are being explored:

• A game-theoretic approach using Stackelberg games:
  The problem is how to optimally route a fraction of the flow on a network, under non-cooperative selfish response. In other words, assume that a central coordinator has a number of cars (or paquets) to route to a destination, and that everyone else (every other car) is selfish in the sense that it will choose a route that minimizes its individual travel-time. What is the best strategy for the coordinator in order to minimize the total travel-time? This work is interested in Stackelberg routing games. Some of our results can be found on the publications page. I do this work jointly with Jack Reilly, Professor Saurabh Amin, and my advisor Professor Alex Bayen.

More recent work considers the routing game in a repeated setting, where players make routing decisions on each day, and can adapt their strategies using previous outcomes. We apply no-regret learning algorithms to model the population dynamics. In particular, the Multiplicative Weights Algorithm (MWA) with a decreasing learning rate, is proved to convegre to Nash equilibria. I recently gave a talk on the topic as part of the Cyber Physical Systems (CPS) talk series: Selfish Routing and the Experts Algorithm. An implementation of the algorithm is available on github, with appliations to Routing and zero-sum two player games.

• A dynamic model using conservatino PDEs:
  We use the adjoint method for solving PDE-constrained optimal control problems. We apply the adjoint method to traffic systems, for the optimal ramp metering problem, then for the routing problem. Part of this work is done in the ORESTE group, a collaborative effort between Berkeley and Inria.

Travel time estimation

I use graphical models to do travel time estimation on urban trafic networks. The Mobile Millennium project collects probe vehicle GPS locations at regular time intervals, from which one can infer travel time observations. The problem is to infer the current travel times from sparse, possibly noisy observations, and predict the evolution of travel time during the next time steps.

Some of the interesting questions include how to do approximate inference on large networks, for which exact inference is computationally intractable.