A significant portion of roads, particularly in densely populated developing countries, lacks explicitly defined right-of-way rules. These understructured roads pose substantial challenges for autonomous vehicle motion planning, where efficient and safe navigation relies on understanding decentralized human coordination for collision avoidance. This coordination, often termed “social driving etiquette,” remains underexplored due to limited open-source empirical data and suitable modeling frameworks. In this paper, we present a novel dataset and modeling framework designed to study motion planning in these understructured environments. The dataset includes 20 aerial videos of representative scenarios, an image dataset for training vehicle detection models, and a development kit for vehicle trajectory estimation. We demonstrate that a consensus-based modeling approach can effectively explain the emergence of priority orders observed in our dataset, and is therefore a viable framework for decentralized collision avoidance planning.

This work introduces a multi-camera tracking dataset consisting of 234 hours of video data recorded concurrently from 234 overlapping HD cameras covering a 4.2 mile stretch of 8-10 lane interstate highway near Nashville, TN. Video is recorded in cooperation with Tennessee State Department of Transportation and its policies. The video is recorded during a period of high traffic density with 500+ objects typically visible within the scene and typical object longevities of 3-15 minutes. GPS trajectories from 270 vehicle passes through the scene are manually corrected in the video data to provide a set of ground-truth trajectories for recall-oriented tracking metrics, and object detections are provided for each camera in the scene (159 million total before cross-camera fusion). Initial benchmarking of tracking-by-detection algorithms is performed against the GPS trajectories, and a best HOTA of only 9.5% is obtained (best recall 75.9% at IOU 0.1, 47.9 average IDs per ground truth object), indicating the benchmarked trackers do not perform sufficiently well at the long temporal and spatial durations required for traffic scene understanding. Video data, scene information, and vehicle trajectories are made publicly available at i24motion.org.

Model predictive control (MPC) is a powerful control method that handles dynamical systems with constraints. However, solving MPC iteratively in real time, i.e., implicit MPC, remains a computational challenge. To address this, common solutions include explicit MPC and function approximation. Both methods, whenever applicable, may improve the computational efficiency of the implicit MPC by several orders of magnitude. Nevertheless, explicit MPC often requires expensive pre-computation and does not easily apply to higher-dimensional problems. Meanwhile, function approximation, although scales better with dimension, still requires pre-training on a large dataset and generally cannot guarantee to find an accurate surrogate policy, the failure of which often leads to closed-loop instability. To address these issues, we propose a triple-mode hybrid control scheme, named Memory-Augmented MPC, by combining a linear quadratic regulator, a neural network, and an MPC. From its standard form, we derive two variants of such hybrid control scheme: one customized for chaotic systems and the other for slow systems. The proposed scheme does not require pre-computation and is capable of improving the amortized running time of the composed MPC with a well-trained neural network. In addition, the scheme maintains closed-loop stability with any neural networks of proper input and output dimensions, alleviating the need for certifying optimality of the neural network in safety-critical applications. Note to Practitioners—This article was motivated by the need to reduce the amortized cost of MPC in repetitive industrial robotic applications, where long-term operational cost is important and safety is critical. Examples of such applications include factory robotic arm manipulation and fixed-route quadcopter payload transport. Unlike explicit MPC or function approximation, our approach does not require any pre-computation or pre-training. Rather, it attains task proficiency over time by learning a surrogate neural network on the spot and by gradually replacing the costly MPC with the more efficient surrogate model so long as safety permits. Consequently, the proposed scheme incurs a learning cost during the initial phase of the deployment but usually becomes more adept on the task afterwards, leading to amortized efficiency.

Congestion pricing policies are increasingly being considered to aid in congestion management and transportation funding in urban areas. This article presents a case study of the optimization of congestion pricing policy design using the Berkeley Integrated System for Transportation Optimization (BISTRO), an open-sourced transportation planning and decision support system (DSS) that uses an agent-based simulation (ABS) and optimization framework to evaluate transportation system interventions. The study exemplifies how the granularity offered by activity-based travel demand models and ABS can be leveraged to enhance the interpretability of multi-objective transportation policy optimization through rich analyses of the effects of policy design on both individual-and system-level outcomes. The location and size of a circular charging zone with two different pricing schemes (a cordon fee and a cordoned mileage fee) are encoded as inputs to an ABS with an activity-based travel model of 15,000 travelers. Through an analysis of the effects of various weighting schemes across congestion-, social-, and revenue-based objectives, we present a method for interpretation of the inherent trade-offs in transportation policy optimization and demonstrate the importance of cultivating transparency in policy DSS that use black-box optimization in order to produce explainable, defensible policy strategies. We find that cordoned mileage fees Pareto-dominate cordon tolls, enabling greater improvements across all objectives studied. However, the prioritization of congestion reduction poses a challenge for pricing optimization in that it may result in unnecessarily large mode shifts away from driving which significantly worsens travel cost burden. We explore the role of weighting schemes in shifting the priority of optimal pricing schemes to social equity while mitigating congestion and maintaining toll revenue.

Designing and validating controllers for connected and automated vehicles to enhance traffic flow presents significant challenges, from the complexity of replicating real-world stop-and-go traffic dynamics in simulation, to the intricacies involved in transitioning from simulation to actual deployment. In this work, we present a full pipeline from data collection to controller deployment. Specifically, we collect 772 km of driving data from the I-24 in Tennessee, and use it to build a one-lane simulator, placing simulated vehicles behind real-world trajectories. Using policy-gradient methods with an asymmetric critic, we improve fuel efficiency by over 10% when simulating congested scenarios. Our comprehensive approach includes reinforcement learning for controller training, software verification, hardware validation and setup, and navigating various sim-to-real challenges. Furthermore, we analyze the controller's behavior and wave-smoothing properties, and deploy it on four Toyota Rav4’s in a real-world validation experiment on the I-24. Finally, we release the driving dataset (Nice et al., 2021), the simulator and the trained controller (Lichtlé et al., 2022), to enable future benchmarking and controller design.

Autonomous driving systems present promising methods for congestion mitigation in mixed autonomy traffic control settings. In particular, when coupled with even modest traffic state estimates, such systems can plan and coordinate the behaviors of automated vehicles (AVs) in response to observed downstream events, thereby inhibiting the continued propagation of congestion. In this paper, we present a two-layer control strategy in which the upper layer proposes the desired speeds that predictively react to the downstream state of traffic, and the lower layer maintains safe and reasonable headways with leading vehicles. This method is demonstrated to achieve an average of over 15% energy savings within simulations of congested events observed in Interstate 24 with only 4% AV penetration, while restricting negative externalities imposed on traveling times and mobility. The proposed strategy that served as part of the "speed planner" was deployed on 100 AVs in a massive traffic experiment conducted on Nashville’s I-24 in November 2022.

Emerging vehicular systems with increasing proportions of automated components present opportunities for optimal control to mitigate congestion and increase efficiency. There has been a recent interest in applying deep reinforcement learning (DRL) to these nonlinear dynamical systems for the automatic design of effective control strategies. Despite conceptual advantages of DRL being model-free, studies typically nonetheless rely on training setups that are painstakingly specialized to specific vehicular systems. This is a key challenge to efficient analysis of diverse vehicular and mobility systems. To this end, this article contributes a streamlined methodology for vehicular microsimulation and discovers high performance control strategies with minimal manual design. A variable-agent, multi-task approach is presented for optimization of vehicular Partially Observed Markov Decision Processes. The methodology is experimentally validated on mixed autonomy traffic systems, where fractions of vehicles are automated; empirical improvement, typically 15-60% over a human driving baseline, is observed in all configurations of six diverse open or closed traffic systems. The study reveals numerous emergent behaviors resembling wave mitigation, traffic signaling, and ramp metering. Finally, the emergent behaviors are analyzed to produce interpretable control strategies, which are validated against the learned control strategies. Note to Practitioners—As vehicular systems such as real-world traffic systems and robotic warehouses become increasingly automated, optimizing vehicle movements sees an increasing potential to reduce congestion and increase efficiency. For many vehicular systems, simulations of varying fidelity are commonly used for analysis and optimization without the need to deploy real vehicles. This article describes a unified and practical approach for optimal control of vehicles in arbitrary simulated vehicular systems while permitting partial automation, where the behavior of fractions of vehicles at given times can be modelled but not controlled. As illustrated by the diverse traffic systems considered in this article, the presented methodology emphasizes ease of application within any simulated vehicular system while minimizing manual efforts by the practitioner. The control inputs consist of local information around each automated vehicle, while the control outputs are commands for longitudinal acceleration and lateral lane change. Experimental results are presented for relatively small simulated traffic systems, though the methodology can be adapted to larger vehicular systems with minor modifications. Experimentally optimized behaviors provide insights to the practitioner which may assist in designing simplified and interpretable control strategies. Implementation in real-world systems depends on two requirements: 1) a reliable fallback mechanism for ensuring safety of vehicles, and 2) sufficient fidelity of the simulator for simulated behaviors to transfer. These requirements are under active research for traffic systems and may be practical in some robotic settings. To facilitate robust transfer of policies from simulated to real-world systems, future extensions of this work may inject additional randomization into simulation while reducing the unmodeled stochasticity of targeted real-world systems as much as possible.

We study the ability of autonomous vehicles to improve the throughput of a bottleneck using a fully decentralized control scheme in a mixed autonomy setting. We consider the problem of improving the throughput of a scaled model of the San Francisco–Oakland Bay Bridge: a two-stage bottleneck where four lanes reduce to two and then reduce to one. Although there is extensive work examining variants of bottleneck control in a centralized setting, there is less study of the challenging multi-agent setting where the large number of interacting AVs leads to significant optimization difficulties for reinforcement learning methods. We apply multi-agent reinforcement algorithms to this problem and demonstrate that significant improvements in bottleneck throughput, from 20% at a 5% penetration rate to 33% at a 40% penetration rate, can be achieved. We compare our results to a hand-designed feedback controller and demonstrate that our results sharply outperform the feedback controller despite extensive tuning. Additionally, we demonstrate that the RL-based controllers adopt a robust strategy that works across penetration rates whereas the feedback controllers degrade immediately upon penetration rate variation. We investigate the feasibility of both action and observation decentralization and demonstrate that effective strategies are possible using purely local sensing. Finally, we open-source our code at https://github.com/eugenevinitsky/decentralized_bottlenecks .

Autonomous vehicle-based traffic smoothing con-trollers are often not transferred to real-world use due to challenges in calibrating many-agent traffic simulators. We show a pipeline to sidestep such calibration issues by collecting trajectory data and learning controllers directly from trajectory data that are then deployed zero-shot onto the highway. We construct a dataset of 772.3 kilometers of recorded drives on the I–24. We then construct a simple simulator using the recorded drives as the lead vehicle in front of a simulated platoon consisting of one autonomous vehicle and five human followers. Using policy-gradient methods with an asymmetric critic to learn the controller, we show that we are able to improve average MPG by 11% in simulation on congested trajectories. We deploy this controller to a mixed platoon of 4 autonomous Toyota RAV-4's and 7 human drivers in a validation experiment and demonstrate that the expected time-gap of the controller is maintained in the real world test. Finally, we release the driving dataset [1], the simulator, and the trained controller at https://github.com/nathanlct/trajectory-training-icra.

Proximal Policy Optimization (PPO) is a ubiquitous on-policy reinforcement learning algorithm but is significantly less utilized than off-policy learning algorithms in multi-agent settings. This is often due to the belief that PPO is significantly less sample efficient than off-policy methods in multi-agent systems. In this work, we carefully study the performance of PPO in cooperative multi-agent settings. We show that PPO-based multi-agent algorithms achieve surprisingly strong performance in four popular multi-agent testbeds: the particle-world environments, the StarCraft multi-agent challenge, the Hanabi challenge, and Google Research Football, with minimal hyperparameter tuning and without any domain-specific algorithmic modifications or architectures. Importantly, compared to competitive off-policy methods, PPO often achieves competitive or superior results in both final returns and sample efficiency. Finally, through ablation studies, we analyze implementation and hyperparameter factors that are critical to PPO's empirical performance, and give concrete practical suggestions regarding these factors. Our results show that when using these practices, simple PPO-based methods are a strong baseline in cooperative multi-agent reinforcement learning. Source code is released at https://github.com/marlbenchmark/on-policy.

This study focuses on the comprehensive investigation of stop-and-go waves appearing in closed-circuit ring road traffic wherein we evaluate various longitudinal dynamical models for vehicles. It is known that the behavior of human-driven vehicles, with other traffic elements such as density held constant, could stimulate stop-and-go waves, which do not dissipate on the circuit ring road. Stop-and-go waves can be dissipated by adding automated vehicles (AVs) to the ring. Thorough investigations of the performance of AV longitudinal control algorithms were carried out in Flow, which is an integrated platform for reinforcement learning on traffic control. Ten AV algorithms presented in the literature are evaluated. For each AV algorithm, experiments are carried out by varying distributions and penetration rates of AVs. Two different distributions of AVs are studied. For the first distribution scenario, AVs are placed consecutively. Penetration rates are varied from 1 AV (5%) to all AVs (100%). For the second distribution scenario, AVs are placed with even distribution of human-driven vehicles in between any two AVs. In this scenario, penetration rates are varied from 2 AVs (10%) to 11 AVs (50%). Multiple runs (10 runs) are simulated to average out the randomness in the results. From more than 3,000 simulation experiments, we investigated how AV algorithms perform differently with varying distributions and penetration rates while all AV algorithms remained fixed under all distributions and penetration rates. Time to stabilize, maximum headway, vehicle miles traveled, and fuel economy are used to evaluate their performance. Using these metrics, we find that the traffic condition improvement is not necessarily dependent on the distribution for most of the AV controllers, particularly when no cooperation among AVs is considered. Traffic condition is generally improved with a higher AV penetration rate with only one of the AV algorithms showing a contrary trend. Among all AV algorithms in this study, the reinforcement learning controller shows the most consistent improvement under all distributions and penetration rates.

The recent emergence of new technologies and systems such as connected and automated vehicles (CAVs), novel incentive and routing platforms, and shared mobility services is making a significant impact on traffic flow in road networks. The rapid development of these innovations, powered by new capabilities in data collection, communication, and vehicle autonomy raises both great opportunities and new challenges for managing and controlling the transportation network efficiently. It is thus imperative to integrate the emerging systems into a dynamic transportation network analysis, and to develop new methodologies, which coherently integrate dynamic traffic models with increasingly available data, and methods for large-scale computation. Consequently, they call for new theories, models, computational methods, and application scenarios to study dynamic transportation networks with the emerging technologies as essential components.

The rapid development ofautonomous vehicles(AVs) holds vast potential for transportation systems through improved safety, efficiency, and access to mobility. However, the progression of these impacts, as AVs are adopted, is not well understood. Numerous technical challenges arise from the goal of analyzing the partial adoption of autonomy: partial control and observation, multivehicle interactions, and the sheer variety of scenarios represented by real-world networks. To shed light into near-term AV impacts, this article studies the suitability of deepreinforcement learning(RL) for overcoming these challenges in a low AV-adoption regime. A modular learning framework is presented, which leverages deep RL to address complex traffic dynamics. Modules are composed to capture common traffic phenomena (stop-and-go traffic jams, lane changing, intersections). Learned control laws are found to improve upon human driving performance, in terms of system-level velocity, by up to 57% with only 4–7% adoption of AVs. Furthermore, in single-lane traffic, a small neural network control law with only local observation is found to eliminate stop-and-go traffic—surpassing all known model-based controllers to achieve near-optimal performance—and generalize to out-of-distribution traffic densities.

Motivated by earlier work and the developer of a new algorithm, the FollowerStopper, this article uses reachability analysis to verify the safety of the FollowerStopper algorithm, which is a controller designed for dampening stop-and-go traffic waves. With more than 1100 miles of driving data collected by our physical platform, we validate our analysis results by comparing it to human driving behaviors. The FollowerStopper controller has been demonstrated to dampen stop-and-go traffic waves at low speed, but previous analysis on its relative safety has been limited to upper and lower bounds of acceleration. To expand upon previous analysis, reachability analysis is used to investigate the safety at the speeds it was originally tested and also at higher speeds. Two formulations of safety analysis with different criteria are shown: distance-based and time headway-based. The FollowerStopper is considered safe with distance-based criterion. However, simulation results demonstrate that the FollowerStopper is not representative of human drivers - it follows too closely behind vehicles, specifically at a distance human would deem as unsafe. On the other hand, under the time headway-based safety analysis, the FollowerStopper is not considered safe anymore. A modified FollowerStopper is proposed to satisfy time-based safety criterion. Simulation results of the proposed FollowerStopper shows that its response represents human driver behavior better.

A wide range of reinforcement learning (RL) problems --- including robustness, transfer learning, unsupervised RL, and emergent complexity --- require specifying a distribution of tasks or environments in which a policy will be trained. However, creating a useful distribution of environments is error prone, and takes a significant amount of developer time and effort. We propose Unsupervised Environment Design (UED) as an alternative paradigm, where developers provide environments with unknown parameters, and these parameters are used to automatically produce a distribution over valid, solvable environments. Existing approaches to automatically generating environments suffer from common failure modes: domain randomization cannot generate structure or adapt the difficulty of the environment to the agent's learning progress, and minimax adversarial training leads to worst-case environments that are often unsolvable. To generate structured, solvable environments for our protagonist agent, we introduce a second, antagonist agent that is allied with the environment-generating adversary. The adversary is motivated to generate environments which maximize regret, defined as the difference between the protagonist and antagonist agent's return. We call our technique Protagonist Antagonist Induced Regret Environment Design (PAIRED). Our experiments demonstrate that PAIRED produces a natural curriculum of increasingly complex environments, and PAIRED agents achieve higher zero-shot transfer performance when tested in highly novel environments.

The current trend toward urbanization and adoption of flexible and innovative mobility technologies will have complex and difficult-to-predict effects on urban transportation systems. Comprehensive methodological frameworks that account for the increasingly uncertain future state of the urban mobility landscape do not yet exist. Furthermore, few approaches have enabled the massive ingestion of urban data in planning tools capable of offering the flexibility of scenario-based design. This article introduces Berkeley Integrated System for Transportation Optimization (BISTRO), a new open source transportation planning decision support system that uses an agent-based simulation and optimization approach to anticipate and develop adaptive plans for possible technological disruptions and growth scenarios. The new framework was evaluated in the context of a machine learning competition hosted within Uber Technologies, Inc., in which over 400 engineers and data scientists participated. For the purposes of this competition, a benchmark model, based on the city of Sioux Falls, South Dakota, was adapted to the BISTRO framework. An important finding of this study was that in spite of rigorous analysis and testing done prior to the competition, the two top-scoring teams discovered an unbounded region of the search space, rendering the solutions largely uninterpretable for the purposes of decision-support. On the other hand, a follow-on study aimed to fix the objective function. It served to demonstrate BISTRO’s utility as a human-in-the-loop cyberphysical system: one that uses scenario-based optimization algorithms as a feedback mechanism to assist urban planners with iteratively refining objective function and constraints specification on intervention strategies. The portfolio of transportation intervention strategy alternatives eventually chosen achieves high-level regional planning goals developed through participatory stakeholder engagement practices.

This paper presents the problem of block simplex constrained signal recovery, which has been demonstrated to be a suitable formulation for estimation problems in networks such as route flow estimation in traffic. There are several natural approaches to this problem: compressed sensing, Bayesian inference, and convex optimization. This paper presents new methods within each framework and assesses their respective abilities to reconstruct signals, with the particular emphasis on sparse recovery, ability to incorporate prior information, and scalability. We then apply these methods to route flow estimation in traffic networks of various sizes and network topologies. We find that both compressed sensing and Bayesian inference approaches are appropriate for structured recovery but have scalability limitations. The convex optimization approach does not directly incorporate prior information, but scales well and has been shown to achieve 90% route flow accuracy on a full-scale network of over 10 000 links and 280 000 routes on a synthetic benchmark based on the I-210 corridor near Los Angeles, CA, USA.

Autonomous vehicles promise safer roads, energy savings, and more efficient use of existing infrastructure, among many other benefits. Although the effect of autonomous vehicles has been studied in the limits (near-zero or full penetration), the transition range requires new formulations, mathematical modeling, and control analysis. In this article, we study the ability of small numbers of autonomous vehicles to stabilize a single-lane system of human-driven vehicles. We formalize the problem in terms of linear string stability, derive optimality conditions from frequency-domain analysis, and pose the resulting nonlinear optimization problem. In particular, we introduce two conditions which simultaneously stabilize traffic while imposing a safety constraint on the autonomous vehicle and limiting degradation of performance. With this optimal linear controller in a system with typical human driver behavior, we can numerically determine that only a 6% uniform penetration of autonomously controlled vehicles (i.e. one per string of up to 16 human-driven vehicles) is necessary to stabilize traffic across all traffic conditions.

The development of sustainable transportation infrastructure for people and goods, using new technology and business models, can prove beneficial or detrimental for mobility, depending on its design and use. The focus of this paper is on the increasing impact new mobility services have on traffic patterns and transportation efficiency in general. Over the last decade, the rise of the mobile internet and the usage of mobile devices have enabled ubiquitous traffic information. With the increased adoption of specific smartphone applications, the number of users of routing applications has become large enough to disrupt traffic flow patterns in a significant manner. Similarly, but at a slightly slower pace, novel services for freight transportation and city logistics improve the efficiency of goods transportation and change the use of road infrastructure. This paper provides a general four-layer framework for modeling these new trends. The main motivation behind the development is to provide a unifying formal system description that can at the same time encompass system physics (flow and motion of vehicles) as well as coordination strategies under various information and cooperation structures. To showcase the framework, we apply it to the specific challenge of modeling and analyzing the integration of routing applications in today's transportation systems. In this framework, at the lowest layer (flow dynamics), we distinguish routed users from nonrouted users. A distributed parameter model based on a nonlocal partial differential equation is introduced and analyzed. The second layer incorporates connected services (e.g., routing) and other applications used to optimize the local performance of the system. As inputs to those applications, we propose a third layer introducing the incentive design and global objectives, which are typically varying over the day depending on road and weather conditions, external events, etc. The high-level planning is handled on the fourth layer taking social longterm objectives into account. We illustrate the framework by considering its ability to model at two different levels. Specific to vehicular traffic, numerical examples enable us to demonstrate the links between the traffic network layer and the routing decision layer. With a second example on optimized freight transport, we then discuss the links between the cooperative control layer and the lower layers. The congestion pricing in Stockholm is used to illustrate how also the social planning layer can be incorporated in future mobility services.

Sensing by proxy (SbP) is proposed in this paper as a sensing paradigm for occupancy detection, where the inference is based on “proxy” measurements such as temperature and CO2 concentrations. The effects of occupants on indoor environments are captured by constitutive models comprising a coupled partial differential equation-ordinary differential equation system that exploits the spatial and physical features. Sensor fusion of multiple environmental parameters is enabled in the proposed framework. We report on experiments conducted under simulated conditions and real-life circumstances, when the variation of occupancy follows a schedule as the ground truth. The inference of the number of occupants in the room based on CO2 concentration at the air return and air supply vents by our approach achieves an overall mean squared error of 0.6044 (fractional person), while the best alternative by Bayes net is 1.2061 (fractional person). Results from the projected ventilation analysis show that SbP can potentially save 55% of total ventilation compared with the traditional fixed schedule ventilation strategy, while at the same time maintain a reasonably comfort profile for the occupants.

The routing game models congestion in transportation networks, communication networks, and other cyber-physical systems in which agents compete for shared resources. We consider an online learning model of player dynamics: at each iteration, every player chooses a route (or a probability distribution over routes, which corresponds to a flow allocation over the physical network), then the joint decision of all players determines the costs of each path, which are then revealed to the players. We pose the following estimation problem: given a sequence of player decisions and the corresponding costs, we would like to estimate the parameters of the learning model. We consider, in particular, entropic mirror descent dynamics and reduce the problem to estimating the learning rates of each player. In order to demonstrate our methods, we developed a web application that allows players to participate in a distributed, online routing game, and we deployed the application on Amazon Mechanical Turk. When players log in, they are assigned an origin and destination on a shared network. They can choose, at each iteration, a distribution over their available routes, and each player seeks to minimize her own cost. We collect a dataset using this platform, then apply the proposed method to estimate the learning rates of each player. We observe, in particular, that after an exploration phase, the joint decision of the players remains within a small distance of the set of equilibria. We also use the estimated model parameters to predict the flow distribution over routes, and compare our predictions to the actual distributions, showing that the online learning model can be used as a predictive model over short horizons. Finally, we discuss some of the qualitative insights from the experiments, and give directions for future research.

This paper shows how the recent breakthroughs in reinforcement learning (RL) that have enabled robots to learn to play arcade video games, walk, or assemble colored bricks, can be used to perform other tasks that are currently at the core of engineering cyberphysical systems. We present the first use of RL for the control of systems modeled by discretized non-linear partial differential equations (PDEs) and devise a novel algorithm to use non-parametric control techniques for large multi-agent systems. Cyberphysical systems (e.g., hydraulic channels, transportation systems, the energy grid, and electromagnetic systems) are commonly modeled by PDEs, which historically have been a reliable way to enable engineering applications in these domains. However, it is known that the control of these PDE models is notoriously difficult. We show how neural network-based RL enables the control of discretized PDEs whose parameters are unknown, random, and time-varying. We introduce an algorithm of mutual weight regularization (MWR), which alleviates the curse of dimensionality of multi-agent control schemes by sharing experience between agents while giving each agent the opportunity to specialize its action policy so as to tailor it to the local parameters of the part of the system it is located in. A discretized PDE, such as the scalar Lighthill-Whitham-Richards PDE can indeed be considered as a macroscopic freeway traffic simulator and which presents the most salient challenges for learning to control large cyberphysical system with multiple agents. We consider two different discretization procedures and show the opportunities offered by applying deep reinforcement for continuous control on both. Using a neural RL PDE controller on a traffic flow simulation based on a Godunov discretization of the San Francisco Bay Bridge, we are able to achieve precise adaptive metering without model calibration thereby beating the state of the art in traffic metering. Furthermore, with the more accurate BeATS simulator, we manage to achieve a control performance on par with ALINEA, a state-of-the-art parametric control scheme, and show how using MWR improves the learning procedure.

Sampling at random timestamps, long range dependencies, and scale hamper standard meth- ods for multivariate time series analysis. In this paper we present a novel estimator for cross-covariance of randomly observed time series which unravels the dynamics of an unobserved stochastic process. We analyze the statistical properties of our estimator without needing the assumption that observation timestamps are independent from the process of interest and show that our solution is not hindered by the issues affecting standard estimators for cross-covariance. We implement and evaluate our statistically sound and scalable approach in the distributed setting using Apache Spark and demonstrate its ability to unravel causal dynamics on both simulations and high-frequency financial trading data.

This paper introduces a simple but practical approach that uses both loop detector data and probe travel times for computing the vehicle hours traveled (VHT), average delay, and level of service (LOS) for signalized intersections. The goal is to improve upon the state-of-the-practice method outlined in the highway capacity manual (HCM) by incorporating additional travel time measurements from probe vehicles or vehicle re-identification systems. The proposed methodology is designed to work under a variety of traffic conditions, including states of congestion in which the HCM methodology is not reliable. Our analysis is then tested using simulation of an arterial site in Arcadia, CA, USA. The results suggest that the proposed methodology performs better at the approach level than at the lane group level. Population size and probe penetration rate are two key parameters in the estimation. Either a large population size or a high penetration rate is required in order to produce reliable estimates of VHT, delay, and LOS. Results also show that the proposed methodology only requires 7% of the penetration rate to outperform the HCM methodology.

We study a general adversarial online learning problem, in which we are given a decision set X' in a reflexive Banach space X and a sequence of reward vectors in the dual space of X. At each iteration, we choose an action from X', based on the observed sequence of previous rewards. Our goal is to minimize regret, defined as the gap between the realized reward and the reward of the best fixed action in hindsight. Using results from infinite dimensional convex analysis, we generalize the method of Dual Averaging (or Follow the Regularized Leader) to our setting and obtain upper bounds on the worst-case regret that generalize many previous results. Under the assumption of uniformly continuous rewards, we obtain explicit regret bounds in a setting where the decision set is the set of probability distributions on a compact metric space S. Importantly, we make no convexity assumptions on either the set S or the reward functions. We also prove a general lower bound on the worst-case regret for any online algorithm. We then apply these results to the problem of learning in repeated two-player zero-sum games on compact metric spaces. In doing so, we first prove that if both players play a Hannan-consistent strategy, then with probability 1 the empirical distributions of play weakly converge to the set of Nash equilibria of the game. We then show that, under mild assumptions, Dual Averaging on the (infinite-dimensional) space of probability distributions indeed achieves Hannan-consistency.

We study accelerated descent dynamics for constrained convex optimization. This dynamics can be described naturally as a coupling of a dual variable accumulating gradients at a given rate $\eta(t)$, and a primal variable obtained as the weighted average of the mirrored dual trajectory, with weights $w(t)$. Using a Lyapunov argument, we give sufficient conditions on $\eta$ and $w$ to achieve a desired convergence rate. As an example, we show that the replicator dynamics (an example of mirror descent on the simplex) can be accelerated using a simple averaging scheme. We then propose an adaptive averaging heuristic which adaptively computes the weights to speed up the decrease of the Lyapunov function. We provide guarantees on adaptive averaging in continuous-time, prove that it preserves the quadratic convergence rate of accelerated first-order methods in discrete-time, and give numerical experiments to compare it with existing heuristics, such as adaptive restarting. The experiments indicate that adaptive averaging performs at least as well as adaptive restarting, with significant improvements in some cases.

The papers included in this special section were presented at the Sixth Annual ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS 2015) that was held on April 14-16, 2015 in Seattle, WA, USA, as part of the Eighth Annual Cyber-Physical Systems Week. ICCPS is the premier single-track conference for reporting advances in all aspects of cyber-physical systems, including theory, tools, applications, systems, testbeds, and field deployments. Its focus includes the core science and technology for developing fundamental principles that underpin the integration of cyber and physical elements, with application domains that include transportation, energy, water, agriculture, ecology, supply-chains, medical and assistive technology, sensor and social networks, and robotics.

Transportation networks constitute a critical infrastructure enabling the transfers of passengers and goods, with a significant impact on the economy at different scales. Transportation modes are coupled and interdependent. The frequent occurrence of perturbations on one or several modes disrupts passengers' entire journeys, directly and through ripple effects. Collaborative decision-making has shown significant benefits at the airport level, both in the U.S. and in Europe. This paper examines how it could be extended to the multimodal network level, discusses the supporting evidence, and provides recommendations for implementation. A case study on the disruption management following the Asiana Crash at San Francisco International Airport is presented. The crash led to a large number of flight diversions to many airports, such as Oakland, Los Angeles, but also Seattle for instance, disrupting the journeys of thousands of passengers. Passenger reaccommodation varied greatly from airline to airline and airport to airport. First, a passenger-centric reaccommodation scheme is developed to balance costs and delays, for each diversion airport. Second, assuming better information sharing and collaborative decision-making, we show that there was enough capacity at the neighboring airports, Oakland and San Jose, to accommodate most of the diverted flights and reoptimize the allocation of flight diversions to the Bay Area airports. Based on this case study, recommendations for the adoption of multimodal CDM are elaborated. This paper paves the way for further data-driven research for increased resilience of passenger door-to-door journeys.

Transportation networks constitute a critical infrastructure enabling the transfers of passengers and goods, with a significant impact on the economy at different scales. Transportation modes, whether air, road, or rail, are intrinsically coupled through passenger transfers and are interdependent. The frequent occurrence of perturbations on one or several modes disrupts passengers' entire journeys, directly and through ripple effects. This paper provides a case report of the Asiana crash in San Francisco International Airport (SFO) on July 6, 2013, and its repercussions on the multimodal transportation network. It studies the resulting propagation of disturbances on the transportation infrastructure in the USA, particularly on the U.S. air transport network and the ground transportation in the Bay Area. The perturbation takes different forms and varies in scale and time frame: cancelations and delays snowball in the airspace, with up to 86% of cancelations in the U.S. due to the SFO crash; highway traffic near the airport is impacted by congestion in previously not congested locations, with low speed and high delays on US 101; and transit passenger demand exhibits unusual traffic peaks in between airports in the Bay Area, with up to 180 passengers more per hour between SFO and Oakland International Airport Bay Area Rapid Transit stations. This paper also investigated the effect of the crash on the social media Twitter. This paper, through a case study, aims at stressing the importance of further data-driven research on interdependent infrastructure networks. The end goal is to form the basis for optimization models behind providing more reliable passenger door-to-door journeys and improved transport network resilience.

We consider an online optimization problem on a subset S of R^n (not necessarily convex), in which a decision maker chooses, at each iteration t, a probability distribution x^(t) over S, and seeks to minimize a cumulative expected loss, where each loss is a Lipschitz function revealed at the end of iteration t. Building on previous work, we propose a generalized Hedge algorithm and show a O(\sqrtt \log t) bound on the regret when the losses are uniformly Lipschitz and S is uniformly fat (a weaker condition than convexity). Finally, we propose a generalization to the dual averaging method on the set of Lebesgue-continuous distributions over S.

We study accelerated mirror descent dynamics in continuous and discrete time. Combining the original continuous-time motivation of mirror descent with a recent ODE interpretation of Nesterov's accelerated method, we propose a family of continuous-time descent dynamics for convex functions with Lipschitz gradients, such that the solution trajectories are guaranteed to converge to the optimum at a $O(1/t^2)$ rate. We then show that a large family of first-order accelerated methods can be obtained as a discretization of the ODE, and these methods converge at a $O(1/k^2)$ rate. This connection between accelerated mirror descent and the ODE provides an intuitive approach to the design and analysis of accelerated first-order algorithms.

Optimal control problems on dynamical systems are concerned with finding a control policy, which minimizes a desired objective, where the objective value depends on the future evolution of the system (the state of the system), which, in turn, depends on the control policy. For systems which contain subsystems that are disjoint across the state variables, distributed optimization techniques exist, which iteratively update subsystems concurrently and then exchange information between subsystems with shared control variables. This article presents a method, based on the asynchronous alternating directions method of multiplier algorithm, which extends these techniques to subsystems with shared control and state variables, while maintaining similar communication structure. The method is used as the basis for splitting network flow control problems into many subnetwork control problems with shared boundary conditions. The decentralized and parallel nature of the method permits high scalability with respect to the size of the network. For highly nonconvex applications, an efficient method, based on adjoint gradient computations, is presented for solving subproblems with shared state. The method is applied to decentralized, coordinated ramp metering and variable speed limit control on a realistic freeway network model using distributed model predictive control.

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 preprocessing and query algorithms for each technique, and also present an extension to the standard reach based preprocessing method that provides additional pruning. Finally, we explain the limitations of this approach due to the inefficiency of the preprocessing phase and present a fast heuristic preprocessing scheme. Numerical results for San Francisco, Luxembourg and a synthetic road network show up to an order of magnitude improvement in the query time for short queries, with even larger gains expected for longer queries.

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 estimates of the sensor measurement distributions, grouped by distance, between the tag and sensor. A grid of 24 sensors is deployed in an office environment, measuring Received Signal Strength (RSS) from the tags, and a multithreaded program is written to implement the method. We discuss the accuracy of the method using a verification data set collected during a field-operational test.

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, inspired from the continuous-time replicator dynamics. In particular, the discounted Hedge algorithm is proved to belong to this class, which guarantees its convergence.

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 recognition based on environmental measurements, which exploit location- and activity-specific characteristics and capture the trends resulted from the underlying physiological process. The features are statistically shown to have good separability and are also information-rich. Fusing environmental sensing together with acceleration is shown to achieve classification accuracy as high as 99.13%. For building applications, this study motivates a sensor fusion paradigm for learning individualized activity, location, and environmental preferences for energy management and user comfort.

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 observations. The framework is evaluated on a large San Francisco taxi data set and is shown to improve upon the current state of the art. This filter also provides insights about driving patterns of drivers. The PIF has been deployed at an industrial scale inside the Mobile Millennium traffic information system, and is used to map fleets of data in San Francisco and Sacramento, CA, USA; Stockholm, Sweden; and Porto, Portugal.

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.

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 motivates a new approach inspired from a well established technique for hybrid system estimation, namely the interactive multiple model (IMM). qThe performance of this new variant of the IMM is compared to the extended Kalman filter and the ensemble Kalman filter using the Mobile Millennium data set.

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. Our online EM algorithm can estimate traffic on a very large city network (the San Francisco Bay Area) by processing tens of thousands of observations per second, with a latency of a few seconds.

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 contribute more quantitatively significant data to earthquake research by automating the data collection and reporting mechanisms via the iShake mobile application. The devices act as distributed sensors that enable measurements to be taken and transmitted with a cellular network connection. Shaking table testing was used to assess the quality of the measurements obtained from the iPhones and iPods on a benchmark of 150 ground motions. Once triggered by a shaking event, the devices transmit sensor data to a backend server for further processing. After a seismic event is verified by high-fidelity stations, filtering algorithms are used to detect falling phones, as well as device-specific responses to the event. A method was developed to determine the absolute orientation of a device to estimate the direction of first motion of a seismic event. A “virtual earthquake” pilot test was conducted on the UC Berkeley campus to verify the operation of the iShake system. By designing and fully implementing a system architecture, developing signal processing techniques unique to mobile sensing, and conducting shaking table tests to confirm the validity of the sensing platform, the iShake project serves as foundational work for further studies in seismic sensing on mobile devices.

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 each road link, advanced convolution methods centered on the Fast Fourier Transform and the idea of zero-delay convolution, and localization techniques for determining an optimal order of policy computation. We describe the algorithms for each speedup technique and analyze their impact on computation time. We also analyze the behavior of the algorithms as a function of the network topology and present numerical results to demonstrate this. Finally, experimental results are provided for the San Francisco Bay Area arterial road network to show how the algorithms would work in an operational setting.

Estimating and predicting traffic conditions in arterial networks using probe data has proven to be a substantial challenge. Sparse probe data represent the vast majority of the data available on arterial roads. This paper proposes a probabilistic modeling framework for estimating and predicting arterial travel-time distributions using sparsely observed probe vehicles. We introduce a model based on hydrodynamic traffic theory to learn the density of vehicles on arterial road segments, illustrating the distribution of delay within a road segment. The characterization of this distribution is essentially to use probe vehicles for traffic estimation: Probe vehicles report their location at random locations, and the travel times between location reports must be properly scaled to match the map discretization. A dynamic Bayesian network represents the spatiotemporal dependence on the network and provides a flexible framework to learn traffic dynamics from historical data and to perform real-time estimation with streaming data. The model is evaluated using data from a fleet of 500 probe vehicles in San Francisco, CA, which send Global Positioning System (GPS) data to our server every minute. The numerical experiments analyze the learning and estimation capabilities on a subnetwork with more than 800 links. The sampling rate of the probe vehicles does not provide detailed information about the location where vehicles encountered delay or the reason for any delay (i.e., signal delay, congestion delay, etc.). The model provides an increase in estimation accuracy of 35% when compared with a baseline approach to process probe-vehicle data.

Traffic monitoring using probe vehicles with GPS receivers promises significant improvements in cost, coverage, and accuracy over dedicated infrastructure systems. Current approaches, however, raise privacy concerns because they require participants to reveal their positions to an external traffic monitoring server. To address this challenge, we describe a system based on virtual trip lines and an associated cloaking technique, followed by another system design in which we relax the privacy requirements to maximize the accuracy of real-time traffic estimation. We introduce virtual trip lines which are geographic markers that indicate where vehicles should provide speed updates. These markers are placed to avoid specific privacy sensitive locations. They also allow aggregating and cloaking several location updates based on trip line identifiers, without knowing the actual geographic locations of these trip lines. Thus, they facilitate the design of a distributed architecture, in which no single entity has a complete knowledge of probe identities and fine-grained location information. We have implemented the system with GPS smartphone clients and conducted a controlled experiment with 100 phone-equipped drivers circling a highway segment, which was later extended into a year-long public deployment.

We report on our experience scaling up the Mobile Millennium traffic information system using cloud computing and the Spark cluster computing framework. Mobile Millennium uses machine learning to infer traffic conditions for large metropolitan areas from crowdsourced data, and Spark was specifically designed to support such applications. Many studies of cloud computing frameworks have demonstrated scalability and performance improvements for simple machine learning algorithms. Our experience implementing a real-world machine learning-based application corroborates such benefits, but we also encountered several challenges that have not been widely reported. These include: managing large parameter vectors, using memory efficiently, and integrating with the application's existing storage infrastructure. This paper describes these challenges and the changes they required in both the Spark framework and the Mobile Millennium software. While we focus on a system for traffic estimation, we believe that the lessons learned are applicable to other machine learning-based applications.

Motorized floating sensors have distinct advantages over their non-actuated counterparts. A motorized unit can prevent the sensor from washing ashore or heading into dangerous areas, expanding the mission regions in which they can be feasibly operated. In this article, we present a control frame work and describe the physically realized system used to prove its effectiveness. The controller uses two minimum-time-to-reach (MTTR) functions-one giving the time to reach the center of the river and one giving the time to reach the shoreline. The MTTR functions are constructed from solutions to Hamilton Jacobi-Bellman-Isaacs (HJBI) Equations. Contours along these functions are used to define the state transition thresholds for an on-off controller. The first MTTR function is also used to construct the optimal bearing to travel back to the center of the river. We investigate the effectiveness of the controller using a software-in-the-loop (SIL) simulator. Using prototypes built at UC Berkeley, results from a field operational test in the Sacramento-San Joaquin River Delta are then presented to validate the simulation results.

The "iShake" system uses smartphones as seismic sensors to measure and deliver ground motion intensity parameters produced by earthquakes more rapidly and accurately than currently possible. Shaking table tests followed by field trial with approximately 30 iShake users were implemented to evaluate the reliability of the phones as seismic monitoring instruments and the functionality of the iShake system. In addition, user experiences were investigated with 59 iShake users, who provided feedback through a mobile questionnaire. Research included participative planning with a focus group to design and conceptualize how to improve iShake for future use. The shaking table tests demonstrated that cell phones may reliably measure the shaking produced by an earthquake. The performed user studies led to important guidelines for the future development and improvement of the iShake system. User studies also provided understanding of how iShake could best provide value to its users. The iShake system was shown to have great potential in providing critical information and added value for the public and emergency responders during earthquakes. Value creation for other users and first response through user-generated data was seen as a great source of motivation and commitment for active use of the system.

This article investigates the vulnerabilities of Supervisory Control and Data Acquisition (SCADA) systems which monitor and control the modern day irrigation canal systems.\nThis type of monitoring and control infrastructure is also common for many other water distribution systems. We present a linearized shallow water partial differential equation (PDE) system that can model water flow in a network of canal pools which are equipped with lateral offtakes for water withdrawal and are connected by automated gates. The knowledge of the system dynamics enables us to develop a deception attack scheme based on switching the PDE parameters and proportional (P) boundary control actions, to withdraw water from the pools through offtakes. We briefly discuss the limits on detectability of such attacks. We use a known formulation based on low frequency approximation of the PDE model and an associated proportional integral (PI) controller, to create a stealthy deception scheme capable of compromising the performance of the closed-loop system. We test the proposed attack scheme in simulation, using a shallow water solver; and show that the attack is indeed realizable in practice by implementing it on a physical canal in Southern France: the Gignac canal. A successful field experiment shows that the attack scheme enables us to steal water stealthily from the canal until the end of the attack.

Automotive traffic monitoring using probe vehicles with Global Positioning System receivers promises significant improvements in cost, coverage, and accuracy. Current approaches, however, raise privacy concerns because they require participants to reveal their positions to an external traffic monitoring server. To address this challenge, we propose a system based on virtual trip lines and an associated cloaking technique. Virtual trip lines are geographic markers that indicate where vehicles should provide location updates. These markers can be placed to avoid particularly privacy sensitive locations. They also allow aggregating and cloaking several location updates based on trip line identifiers, without knowing the actual geographic locations of these trip lines. Thus they facilitate the design of a distributed architecture, where no single entity has a complete knowledge of probe identities and fine-grained location information. We have implemented the system with GPS smartphone clients and conducted a controlled experiment with 20 phone-equipped drivers circling a highway segment. Results show that even with this low number of probe vehicles, travel time estimates can be provided with less than 15% error, and applying the cloaking techniques reduces travel time estimation accuracy by less than 5% compared to a standard periodic sampling approach.

The problem of regulating air traffic in the en route airspace of the National Airspace System is studied using a Eulerian network model to describe air traffic flow. The evolution of traffic on each edge of the network is modeled by a modified Lighthill-Whitham-Richards partial differential equation. The equation is transformed with a variable change, which makes it linear and enables us to use linear finite difference schemes to discretize the problem. We pose the problem of optimal traffic flow regulation as a continuous optimization program in which the partial differential equation appears in the constraints. We propose a discrete formulation of this problem, which makes all constraints (the discretized partial differential equations, boundary, and initial conditions) linear. Corresponding linear programming and quadratic programming based solutions to this convex optimization program yield globally optimal solutions to various air traffic management objectives. The proposed method is applied to the maximization of aircraft arrivals and minimization of delays in the arrival airspace due to exogenous capacity reductions. The corresponding linear and quadratic programs are solved numerically using CPLEX for a benchmark scenario in the Oakland Air Route Traffic Control Center. Several computational aspects of the method are assessed-in particular, accuracy of the numerical discretization, computational time, and storage space required by the method.

Hybrid system theory lies at the intersection of the fields of engineering control theory and computer science verification. It is defined as the modeling, analysis, and control of systems that involve the interaction of both discrete state systems, represented by finite automata, and continuous state dynamics, represented by differential equations. The embedded autopilot of a modern commercial jet is a prime example of a hybrid system: the autopilot modes correspond to the application of different control laws, and the logic of mode switching is determined by the continuous state dynamics of the aircraft, as well as through interaction with the pilot. To understand the behavior of hybrid systems, to simulate, and to control these systems, theoretical advances, analyses, and numerical tools are needed. In this paper, we first present a general model for a hybrid system along with an overview of methods for verifying continuous and hybrid systems. We describe a particular verification technique for hybrid systems, based on two-person zero-sum game theory for automata and continuous dynamical systems. We then outline a numerical implementation of this technique using level set methods, and we demonstrate its use in the design and analysis of aircraft collision avoidance protocols and in verification of autopilot logic.