Walid Krichene


I worked on the Mobile Millennium project at CCIT, the Connected Corridor project at PATH.
Currently I am part of the FORCES group (Foundations Of Resilient CybEr-physical Systems), and the ORESTE group (Optimal REroute Strategies for Traffic ManagEment) with INRIA.

Optimal Routing

I work on optimal routing of flow on congestion networks, with in mind application to traffic networks. Different models are considered, corresponding to different time scales:

  • A game-theoretic approach using Stackelberg games: this corresponds to the coarsest time scale, where the system is assumed to be in steady-state equilibrium.
    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.

  • A repeated game setting, where players make routing decisions on each day, and can adapt their strategies using previous outcomes. This corresponds to a day-to-day time scale.
    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 CPS Games (Cyber Physical Systems) 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. We are exploring other applications, including load-balancing for database queries.

  • A fully dynamic model using conservation PDEs: this corresponds to the finest time-scale.
    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 worked on travel time estimation on urban traffic networks, using graphical models. 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.