ITS Berkeley

Speedup Techniques for the Stochastic On-Time Arrival Problem

Samaranayake, Samitha
Blandin, Sébastien
Bayen, Alex
2012

We consider the stochastic on-time arrival (SOTA) routing problem of finding a routing policy that maximizes the probability of reaching a given destination within a pre-specified time budget in a road network with probabilistic link travel-times. The goal of this work is to provide a theoretical understanding of the SOTA problem and present efficient computational techniques to enable the development of practical applications for stochastic routing. We present multiple speedup techniques that include a label-setting algorithm based on the existence of a minimal link travel-time on...

Large Scale Estimation in Cyberphysical Systems using Streaming Data: a Case Study with Smartphone Traces

Hunter, Timothy
Das, Tathagata
Zaharia, Matei
Abbeel, Pieter
Bayen, Alexandre M.
2012

Controlling and analyzing cyberphysical and robotics systems is increasingly becoming a Big Data challenge. Pushing this data to, and processing in the cloud is more efficient than on-board processing. However, current cloud-based solutions are not suitable for the latency requirements of these applications. We present a new concept, Discretized Streams or D-Streams, that enables massively scalable computations on streaming data with latencies as short as a second. We experiment with an implementation of D-Streams on top of the Spark computing framework. We demonstrate the usefulness of...

Understanding Road Usage Patterns in Urban Areas

Wang. Pu
Hunter, Timothy
Bayen, Alexandre M.
2012

In this paper, we combine the most complete record of daily mobility, based on large-scale mobile phone data, with detailed Geographic Information System (GIS) data, uncovering previously hidden patterns in urban road usage. We find that the major usage of each road segment can be traced to its own - surprisingly few - driver sources. Based on this finding we propose a network of road usage by defining a bipartite network framework, demonstrating that in contrast to traditional approaches, which define road importance solely by topological measures, the role of a road segment depends on...

Traffic Flow Estimation Using Higher-Order Speed Statistics

Bulteau, Edouard
Leblanc, Romain
Blandin, Sébastien
Bayen, Alexandre
2013

In this article, we consider the problem of estimating traffic flow on a multi-lane road using a set of point speeds, either crowd-sourced or collected from the fixed infrastructure. We specifically investigate the relation between higher-order speed moments and the expected value of traffic flow. The algorithm proposed is based on the selection of optimal covariates constructed as speed moments, for a class of conditional mean predictors. The second contribution of this article consists in the analysis of specific components of the speed moments with significant correlation with...

State Estimation in Large-scale Open Channel Networks Using Sequential Monte Carlo Methods: Optimal Sampling Importance Resampling and Implicit Particle Filters

Rafiee, Mohammad
Barrau, Axel
Bayen, Alexandre M.
2013

This article investigates the performance of Monte Carlo-based estimation methods for estimation of flow state in large-scale open channel networks. After constructing a state space model of the flow based on the Saint-Venant equations, we implement the optimal sampling importance resampling filter to perform state estimation in a case in which measurements are available at every time step. Considering a case in which measurements become available intermittently, a random-map implementation of the implicit particle filter is applied to estimate the state trajectory in the interval between...

Arriving on Time: Estimating Travel Time Distributions on Large-scale Road Networks

Hunter, Timothy
Hofleitner, Aude
Reilly, Jack
Krichene, Walid
Bayen, Alexandre
2013

Most optimal routing problems focus on minimizing travel time or distance traveled. Oftentimes, a more useful objective is to maximize the probability of on-time arrival, which requires statistical distributions of travel times, rather than just mean values. We propose a method to estimate travel time distributions on large-scale road networks, using probe vehicle data collected from GPS. We present a framework that works with large input of data, and scales linearly with the size of the network. Leveraging the planar topology of the graph, the method computes efficiently the time...

Floating Sensor Networks for River Studies

Tinka, Andrew
Rafiee, Mohammad
Bayen, Alexandre M.
2013

Free-floating sensor packages that take local measurements and track flows in water systems, known as drifters, are a standard tool in oceanography, but are new to estuarial and riverine studies. A system based on drifters for making estimates on a hydrodynamic system requires the drifters themselves, a communication network, and a method for integrating the gathered data into an estimate of the state of the hydrodynamics. This paper presents a complete drifter system and documents a pilot experiment in a controlled channel. The utility of the system for making measurements in unknown...

Mobile Phones as Seismologic Sensors: Automating Data Extraction for the iShake System

Reilly, J.
Dashti, Shideh
Ervasti, Mari
Bayen, Alexandre M.
2013

There are a variety of approaches to seismic sensing, which range from collecting sparse measurements with high-fidelity seismic stations to non-quantitative, post-earthquake surveys. The sparse nature of the high-fidelity stations and the inaccuracy of the surveys create the need for a high-density, semi-quantitative approach to seismic sensing. To fill this void, the UC Berkeley iShake project designed a mobile client-backend server architecture that uses sensor-equipped mobile devices to measure earthquake ground shaking. iShake provides the general public with a service to more easily...

State Estimation for Polyhedral Hybrid Systems and Applications to the Godunov Scheme

Thai, Jérôme
Bayen, Alexandre
2013

In this article, the problem of estimating the state of a discretized hyperbolic scalar partial differential equation is studied. The discretization of the Lighthill-Whitham-Richards equation with a triangular flux function using the Godunov scheme is shown to lead to a hybrid linear system or Switched Linear Systems (SLS) with a number of modes exponential in the size of the discretized model. Some geometric properties of the partition of the space into polyhedra (in which a mode is active) are exploited to find heuristics to reduce the number of modes to a representative set. This...

Phase Transition Model of Non-Stationary Traffic Flow: Definition, Properties and Solution Method

Blandin, Sébastien
Argote, Juan
Bayen, Alexandre M.
2013

We consider the problem of modeling traffic phenomena at a macroscopic level. Increasing availability of streaming probe data allowing the observation of non-stationary traffic motivates the development of models capable of leveraging this information. We propose a phase transition model of non-stationary traffic in conservation form, capable of propagating joint measurements from fixed and mobile sensors, to model complex traffic phenomena such as hysteresis and phantom jams, and to account for forward propagation of information in congested traffic. The model is shown to reduce to the...