ITS Berkeley

A Necessary and Sufficient Condition for the Existence of Potential Functions for Heterogeneous Routing Games

Farokhi, Farhad
Krichene, Walid
Bayen, Alexandre M.
Johansson, Karl H.
2014

We study a heterogeneous routing game in which vehicles might belong to more than one type. The type determines the cost of traveling along an edge as a function of the flow of various types of vehicles over that edge. We relax the assumptions needed for the existence of a Nash equilibrium in this heterogeneous routing game. We extend the available results to present necessary and sufficient conditions for the existence of a potential function. We characterize a set of tolls that guarantee the existence of a potential function when only two types of users are participating in the game. We...

The Path Inference Filter: Model-Based Low-Latency Map Matching of Probe Vehicle Data

Hunter, Timothy
Abbeel, Pieter
Bayen, Alexandre M.
2014

We consider the problem of reconstructing vehicle trajectories from sparse sequences of GPS points, for which the sampling interval is between 1 s and 2 min. We introduce a new class of algorithms, which are altogether called the path inference filter (PIF), that maps GPS data in real time, for a variety of tradeoffs and scenarios and with a high throughput. Numerous prior approaches in map matching can be shown to be special cases of the PIF presented in this paper. We present an efficient procedure for automatically training the filter on new data, with or without ground-truth...

Indoor Occupant Positioning System Using Active RFID Deployment and Particle Filters

Weekly, Kevin
Zou, Han
Xie, Lihua
Jia, Qing-Shan
Bayen, Alexandre M.
2014

This article describes a method for indoor positioning of human-carried active Radio Frequency Identification (RFID) tags based on the Sampling Importance Resampling (SIR) particle filtering algorithm. To use particle filtering methods, it is necessary to furnish statistical state transition and observation distributions. The state transition distribution is obstacle-aware and sampled from a precomputed accessibility map. The observation distribution is empirically determined by ground truth RSS measurements while moving the RFID tags along a known trajectory. From this data, we generate...

Evaluating the Reliability of Phones as Seismic Monitoring Instruments

Dashti, Shideh
Bray, Jonathan D.
Reilly, Jack
Glaser, Steven D.
Bayen, Alexandre
Mari, Ervasti
2014

Emergency responders must “see” the effects of an earthquake clearly and rapidly for effective response. This paper presents a novel use of cell phone and information technology to measure ground motion intensity parameters. The phone sensor is an imperfect device and has a limited operational range. Thus, shake table tests were performed to evaluate their reliability as seismic monitoring instruments. Representative handheld devices, either rigidly connected to the table or free to move, measured shaking intensity parameters well. Bias in 5%-damped spectral accelerations measured by...

Assessment of Uncertainty Propagation in the Dynamic Response of Single-Degree-of-Freedom Structures Using Reachability Analysis

Scacchioli, Annalisa
Bayen, Alexandre M.
Stojadinović, Bozidar
2014

A novel method to compute the bounds of the response of structures to dynamic loads, including earthquakes, is presented. This method, based on reachability analysis, deterministically predicts the sets of states an elastic structural system can reach under uncertain dynamic excitation starting from uncertain initial conditions, where deterministic uncertainty ranges describe uncertainties. Ellipsoidal approximations of these reachable sets for three canonical dynamic problems are presented to demonstrate the applicability of this method to single-degree-of-freedom (SDOF) systems....

On the Convergence of No-Regret Learning in Selfish Routing

Krichene, Walid
Drighès, Benjamin
Bayen, Alexandre
2014

We study the repeated, non-atomic routing game, in which selfish players make a sequence of routing decisions. We consider a model in which players use regret-minimizing algorithms as the learning mechanism, and study the resulting dynamics. We are concerned in particular with the convergence to the set of Nash equilibria of the routing game. No-regret learning algorithms are known to guarantee convergence of a subsequence of population strategies. We are concerned with convergence of the actual sequence. We show that convergence holds for a large class of online learning algorithms,...

Computing the Log-Determinant of Symmetric, Diagonally Dominant Matrices in Near-Linear Time

Hunter, Timothy
Alaoui, Ahmed El
Bayen, Alexandre M.
2014

We present new algorithms for computing the log-determinant of symmetric, diagonally dominant matrices. Existing algorithms run with cubic complexity with respect to the size of the matrix in the worst case. Our algorithm computes an approximation of the log-determinant in time near-linear with respect to the number of non-zero entries and with high probability. This algorithm builds upon the utra-sparsifiers introduced by Spielman and Teng for Laplacian matrices and ultimately uses their refined versions introduced by Koutis, Miller and Peng in the context of solving linear systems. We...

Building-in-Briefcase (BiB)

Weekly, Kevin
Jin, Ming
Zou, Han
Hsu, Christopher
Bayen, Alexandre
Spanos, Costas
2014

A building's environment has profound influence on occupant comfort and health. Continuous monitoring of building occupancy and environment is essential to fault detection, intelligent control, and building commissioning. Though many solutions for environmental measuring based on wireless sensor networks exist, they are not easily accessible to households and building owners who may lack time or technical expertise needed to set up a system and get quick and detailed overview of environmental conditions. Building-in-Briefcase (BiB) is a portable sensor network platform that is trivially...

Environmental Sensing by Wearable Device for Indoor Activity and Location Estimation

Jin, Ming
Zou, Han
Weekly, Kevin
Jia, Ruoxi
Bayen, Alexandre M.
Spanos, Costas
2014

We present results from a set of experiments in this pilot study to investigate the causal influence of user activity on various environmental parameters monitored by occupant-carried multi-purpose sensors. Hypotheses with respect to each type of measurements are verified, including temperature, humidity, and light level collected during eight typical activities: sitting in lab / cubicle, indoor walking / running, resting after physical activity, climbing stairs, taking elevators, and outdoor walking. Our main contribution is the development of features for activity and location...

Autonomous River Navigation Using the Hamilton–Jacobi Framework for Underactuated Vehicles

Weekly, Kevin
Tinka, Andrew
Anderson, Leah
Bayen, Alexandre M.
2014

The feasibility of drifter studies in complex and tidally forced water networks has been greatly expanded by the introduction of motorized floating sensors. This paper presents a method for such motorized sensors to accomplish obstacle avoidance and path selection using the solutions to Hamilton-Jacobi-Bellman-Isaacs (HJBI) equations. The method is then validated experimentally.