Data

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

Cooperative Control of Air Flow for HVAC Systems

Liu, Shuai
Long, Yushen
Xie, Lihua
Bayen, Alexandre M.
2013

A dynamic pressure and variable air volume (VAV) control strategy is proposed for building heating, ventilation and air-conditioning (HVAC) systems. The strategy consists in two level control, namely, pressure loop control and temperature loop control. The pressure control loop is to make sure that the air pressure at the inlet of each room is equal to a certain value while the temperature control loop is to control the room temperature which is achieved by adjusting the VAV box so that the supply air flow rate can be varied to achieve the room setting temperature. For the pressure control...

Large-Scale Estimation in Cyberphysical Systems Using Streaming Data: A Case Study With Arterial Traffic Estimation

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

Controlling and analyzing cyberphysical and robotics systems is increasingly becoming a Big Data challenge. We study the case of predicting drivers' travel times in a large urban area from sparse GPS traces. We present a framework that can accommodate a wide variety of traffic distributions and spread all the computations on a cluster to achieve small latencies. Our framework is built on Discretized Streams, a recently proposed approach to stream processing at scale. We demonstrate the usefulness of Discretized Streams with a novel algorithm to estimate vehicular traffic in urban networks...

Hybrid Traffic Data Collection Roadmap: Objectives and Methods

Bayen, Alexandre
Sharafsaleh, Mohammad
Patire, Anthony D.
2013

Traffic data is used to estimate current traffic conditions so that travelers and agencies can make better decisions about how to use and manage the transportation network. This research explores the fusion of probe data (vehicle speed and direction) with loop data (density, speed, and count) in the context of producing overall network speed and travel time estimates. Speed and travel time estimates are useful in many circumstances, but current system control strategies (ramp metering, for example) require density data. While it is difficult to significantly increase the quantity of loop...

Online Homotopy Algorithm for a Generalization of the LASSO

Hofleitner, Aude
Rabbani, Tarek
El Ghaoui, L.
Bayen, A.M.
2013

The LASSO is a widely used shrinkage method for linear regression. We propose an online homotopy algorithm to solve a generalization of the LASSO in which the l1 regularization is applied on a linear transformation of the solution, allowing to input prior information on the structure of the problem and to improve interpretability of the results. The algorithm takes advantage of the sparsity of the solution for computational efficiency and is promising for mining large datasets.

Precomputation Techniques for the Stochastic On-Time Arrival Problem

Sabran, Guillaume
Samaranayake, Samitha
Bayen, Alexandre M.
2013

We consider the stochastic on-time arrival (SOTA) problem of finding the optimal routing strategy for reaching a given destination within a pre-specified time budget and provide the first results on using preprocessing techniques for speeding up the query time. We start by identifying some properties of the SOTA problem that limit the types of preprocessing techniques that can be used in this setting, and then define the stochastic variants of two deterministic shortest path preprocessing techniques that can be adapted to the SOTA problem, namely reach and arc-flags. We present the...

Learning and Estimation Applications of an Online Homotopy Algorithm for a Generalization of the LASSO

Hofleitner, Aude
Rabbani, Tarek
Rafiee, Mohammad
Bayen, Alexandre M.
2014

The LASSO is a widely used shrinkage and selection method for linear regression. We propose a generalization of the LASSO in which the l1 penalty is applied on a linear transformation of the regression parameters, allowing to input prior information on the structure of the problem and to improve interpretability of the results. We also study time varying system with an l1-penalty on the variations of the state, leading to estimates that exhibit few “jumps”. We propose a homotopy algorithm that updates the solution as additional measurements are available. The algorithm takes advantage of...

Solutions to Estimation Problems for Scalar Hamilton–Jacobi Equations Using Linear Programming

Claudel, Christian G.
Chamoin, Timothée
Bayen, Alexandre M.
2014

This brief presents new convex formulations for solving estimation problems in systems modeled by scalar Hamilton-Jacobi (HJ) equations. Using a semi-analytic formula, we show that the constraints resulting from a HJ equation are convex, and can be written as a set of linear inequalities. We use this fact to pose various (and seemingly unrelated) estimation problems related to traffic flow-engineering as a set of linear programs. In particular, we solve data assimilation and data reconciliation problems for estimating the state of a system when the model and measurement constraints are...