Modern large language models (LLMs) excel at fitting finetuning data, but often struggle on unseen examples. In order to teach models genuine reasoning abilities rather than superficial pattern matching, our work aims to better understand how the learning dynamics of LLM finetuning shapes downstream generalization. Our analysis focuses on reasoning tasks, whose problem structure allows us to distinguish between memorization (the exact replication of reasoning steps from the training data) and performance (the correctness of the final solution). We find that a model’s performance on test prompts can be effectively characterized by a training metric we call pre-memorization train accuracy: the accuracy of model samples on training queries before they begin to copy the exact reasoning steps from the training set. On the dataset level, this metric is able to almost perfectly predict test accuracy, achieving $R^2$ of $\geq 0.9$ across various models (Llama3 8B, Gemma2 9B), datasets (GSM8k, MATH), and training configurations. On a per-example level, this metric is also indicative of whether individual model predictions are robust to perturbations in the training query. By connecting a model’s learning dynamics to test performance, pre-memorization train accuracy can inform training decisions, such as the makeup of the training data. Our experiments on data curation show that prioritizing examples with low pre-memorization accuracy leads to 1.5-2x improvements in data efficiency compared to i.i.d. data scaling and other data scaling techniques.

Perception-based navigation systems are useful for unmanned ground vehicle (UGV) navigation in complex terrains, where traditional depth-based navigation schemes are insufficient. However, these data-driven methods are highly dependent on their training data and can fail in surprising and dramatic ways with little warning. To ensure the safety of the vehicle and the surrounding environment, it is imperative that the navigation system is able to recognize the predictive uncertainty of the perception model and respond safely and effectively in the face of uncertainty. In an effort to enable safe navigation under perception uncertainty, we develop a probabilistic and reconstruction-based competency estimation (PaRCE) method to estimate the model’s level of familiarity with an input image as a whole and with specific regions in the image. We find that the overall competency score can accurately predict correctly classified, misclassified, and out-of-distribution (OOD) samples. We also confirm that the regional competency maps can accurately distinguish between familiar and unfamiliar regions across images. We then use this competency information to develop a planning and control scheme that enables effective navigation while maintaining a low probability of error. We find that the competency-aware scheme greatly reduces the number of collisions with unfamiliar obstacles, compared to a baseline controller with no competency awareness. Furthermore, the regional competency information is particularly valuable in enabling efficient navigation.

Katie Kang, Eric Wallace, Claire Tomlin, Aviral Kumar, Sergey Levine. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

As the use of autonomous robots expands in tasks that are complex and challenging to model, the demand for robust data-driven control methods that can certify safety and stability in uncertain conditions is increasing. However, the practical implementation of these methods often faces scalability issues due to the growing amount of data points with system complexity, and a significant reliance on high-quality training data. In response to these challenges, this study presents a scalable data-driven controller that efficiently identifies and infers from the most informative data points for implementing data-driven safety filters. Our approach is grounded in the integration of a model-based certificate function-based method and Gaussian Process (GP) regression, reinforced by a novel online data selection algorithm that reduces time complexity from quadratic to linear relative to dataset size. Empirical evidence, gathered from successful real-world cart-pole swing-up experiments and simulated locomotion of a five-link bipedal robot, demonstrates the efficacy of our approach. Our findings reveal that our efficient online data selection algorithm, which strategically selects key data points, enhances the practicality and efficiency of data-driven certifying filters in complex robotic systems, significantly mitigating scalability concerns inherent in nonparametric learning-based control methods.

Conventional wisdom suggests that neural network predictions tend to be unpredictable and overconfident when faced with out-of-distribution (OOD) inputs. Our work reassesses this assumption for neural networks with high-dimensional inputs. Rather than extrapolating in arbitrary ways, we observe that neural network predictions often tend towards a constant value as input data becomes increasingly OOD. Moreover, we find that this value often closely approximates the optimal constant solution (OCS), i.e., the prediction that minimizes the average loss over the training data without observing the input. We present results showing this phenomenon across 8 datasets with different distributional shifts (including CIFAR10-C and ImageNet-R, S), different loss functions (cross entropy, MSE, and Gaussian NLL), and different architectures (CNNs and transformers). Furthermore, we present an explanation for this behavior, which we first validate empirically and then study theoretically in a simplified setting involving deep homogeneous networks with ReLU activations. Finally, we show how one can leverage our insights in practice to enable risk-sensitive decision-making in the presence of OOD inputs.

Reinforcement learning (RL) methods for social robot navigation show great success navigating robots through large crowds of people, but the performance of these learning-based methods tends to degrade in particularly challenging or unfamiliar situations due to the models’ dependency on representative training data. To ensure human safety and comfort, it is critical that these algorithms handle uncommon cases appropriately, but the low frequency and wide diversity of such situations present a significant challenge for these data-driven methods. To overcome this challenge, we propose modifications to the learning process that encourage these RL policies to maintain additional caution in unfamiliar situations. Specifically, we improve the Socially Attentive Reinforcement Learning (SARL) policy by (1) modifying the training process to systematically introduce deviations into a pedestrian model, (2) updating the value network to estimate and utilize pedestrian-unpredictability features, and (3) implementing a reward function to learn an effective response to pedestrian unpredictability. Compared to the original SARL policy, our modified policy maintains similar navigation times and path lengths, while reducing the number of collisions by 82% and reducing the proportion of time spent in the pedestrians’ personal space by up to 19 percentage points for the most difficult cases. We also describe how to apply these modifications to other RL policies and demonstrate that some key high-level behaviors of our approach transfer to a physical robot.

Typical robotic systems rely on models for planning. Therefore, the quality of the robot's behavior is heavily dependent on how accurately the model can predict the outcome of the robot's actions in the environment. A challenge, however, is that no model is perfect; moreover, we often do not know where discrepancies between the model's prediction and the actual outcome occur prior to observing executions in the real-world. One way to address this is to bias the planner away from these discrepancies by inflating the cost of states and actions where we previously observed the model to be inaccurate. Making such decisions about where and how to bias purely at the planning-level, however, neglects valuable information from the control-level, which gives a more fine-grained understanding of where and how the model went wrong during execution. Based on this observation, our key idea is to first infer a statistical model over discrepancies in the control-level's model. Then, we translate this model to the planning-level, where we use it to more informatively bias the planner away from states and actions where the model's predicted outcome is likely to be inaccurate. We demonstrate that our framework enables a robot to complete tasks, despite an inaccurate planning model, with greater efficiency than existing approaches. We do so through an experimental evaluation in simulation and real-robot experiments on NASA's Astrobee free-flyer.

Partially observable Markov decision processes (POMDPs) provide a flexible representation for real-world decision and control problems. However, POMDPs are notoriously difficult to solve, especially when the state and observation spaces are continuous or hybrid, which is often the case for physical systems. While recent online sampling-based POMDP algorithms that plan with observation likelihood weighting have shown practical effectiveness, a general theory characterizing the approximation error of the particle filtering techniques that these algorithms use has not previously been proposed. Our main contribution is bounding the error between any POMDP and its corresponding finite sample particle belief MDP (PB-MDP) approximation. This fundamental bridge between PB-MDPs and POMDPs allows us to adapt any sampling-based MDP algorithm to a POMDP by solving the corresponding particle belief MDP, thereby extending the convergence guarantees of the MDP algorithm to the POMDP. Practically, this is implemented by using the particle filter belief transition model as the generative model for the MDP solver. While this requires access to the observation density model from the POMDP, it only increases the transition sampling complexity of the MDP solver by a factor of O(C), where C is the number of particles. Thus, when combined with sparse sampling MDP algorithms, this approach can yield algorithms for POMDPs that have no direct theoretical dependence on the size of the state and observation spaces. In addition to our theoretical contribution, we perform five numerical experiments on benchmark POMDPs to demonstrate that a simple MDP algorithm adapted using PB-MDP approximation, Sparse-PFT, achieves performance competitive with other leading continuous observation POMDP solvers.

Safety guarantee prior to the deployment of robots can be difficult due to unexpected disturbances in runtime. This article presents a real-time receding-horizon robust trajectory planning algorithm for nonlinear closed-loop systems, which guarantees the safety of the system under unknown but bounded disturbances. We characterize the forward reachable sets (FRSs) of the system based on the Hamilton–Jacobi reachability analysis as a means for safety verification. For the online computation of the FRSs, we approximate nonlinear systems as LTV systems with linearization errors and compute ellipsoids that encompass the FRSs in continuous time. Using the proposed ellipsoidal approximation of the FRSs, we formulate a computationally tractable robust planning problem that can be solved online. Consequently, the proposed method enables real-time replanning of a reference trajectory with safety guarantees even when the system encounters unexpected disturbances in runtime. The flight experiment of obstacle avoidance in a windy environment validates the proposed robust planning algorithm.

Learned models and policies can generalize effectively when evaluated within the distribution of the training data, but can produce unpredictable and erroneous outputs on out-of-distribution inputs. In order to avoid distribution shift when deploying learning-based control algorithms, we seek a mechanism to constrain the agent to states and actions that resemble those that the method was trained on. In control theory, Lyapunov stability and control-invariant sets allow us to make guarantees about controllers that stabilize the system around specific states, while in machine learning, density models allow us to estimate the training data distribution. Can we combine these two concepts, producing learning-based control algorithms that constrain the system to in-distribution states using only in-distribution actions? In this paper, we propose to do this by combining concepts from Lyapunov stability and density estimation, introducing Lyapunov density models: a generalization of control Lyapunov functions and density models that provides guarantees about an agent’s ability to stay in-distribution over its entire trajectory.

Enabling robots to solve multiple manipulation tasks has a wide range of industrial applications. While learning-based approaches enjoy flexibility and generalizability, scaling these approaches to solve such compositional tasks remains a challenge. In this work, we aim to solve multi-task learning through the lens of sequence-conditioning and weighted sampling. First, we propose a new suite of benchmark specifically aimed at compositional tasks, MultiRavens, which allows defining custom task combinations through task modules that are inspired by industrial tasks and exemplify the difficulties in vision-based learning and planning methods. Second, we propose a vision-based end-to-end system architecture, Sequence-Conditioned Transporter Networks, which augments Goal-Conditioned Transporter Networks with sequence-conditioning and weighted sampling and can efficiently learn to solve multi-task long horizon problems. Our analysis suggests that not only the new framework significantly improves pick-and-place performance on novel 10 multi-task benchmark problems, but also the multi-task learning with weighted sampling can vastly improve learning and agent performances on individual tasks.

When a robot observes another agent unexpectedly modifying their behavior, inferring the most likely cause is a valuable tool for maintaining safety and reacting appropriately. In this work, we present a novel method for inferring constraints that works on continuous, possibly sub-optimal demonstrations. We first learn a representation of the continuous-state maximum entropy trajectory distribution using deep reinforcement learning. We then use Monte Carlo sampling from this distribution to generate expected constraint violation probabilities and perform constraint inference. When the demonstrator's dynamics and objective function are known in advance, this process can be performed offline, allowing for real-time constraint inference at the moment demonstrations are observed. We evaluate our approach on two continuous dynamical systems: a 2-dimensional inverted pendulum model, and a 4-dimensional unicycle model that was successfully used for fast constraint inference on a 1/10 scale car remote-controlled by a human.

When a person is not satisfied with how a robot performs a task, they can intervene to correct it. Reward learning methods enable the robot to adapt its reward function online based on such human input, but they rely on handcrafted features. When the correction cannot be explained by these features, recent work in deep Inverse Reinforcement Learning (IRL) suggests that the robot could ask for task demonstrations and recover a reward defined over the raw state space. Our insight is that rather than implicitly learning about the missing feature(s) from demonstrations, the robot should instead ask for data that explicitly teaches it about what it is missing. We introduce a new type of human input in which the person guides the robot from states where the feature being taught is highly expressed to states where it is not. We propose an algorithm for learning the feature from the raw state space and integrating it into the reward function. By focusing the human input on the missing feature, our method decreases sample complexity and improves generalization of the learned reward over the above deep IRL baseline. We show this in experiments with a physical 7DOF robot manipulator, as well as in a user study conducted in a simulated environment.

Predictive human models often need to adapt their parameters online from human data. This raises previously ignored safety-related questions for robots relying on these models such as what the model could learn online and how quickly could it learn it. For instance, when will the robot have a confident estimate in a nearby human’s goal? Or, what parameter initializations guarantee that the robot can learn the human’s preferences in a finite number of observations? To answer such analysis questions, our key idea is to model the robot’s learning algorithm as a dynamical system where the state is the current model parameter estimate and the control is the human data the robot observes. This enables us to leverage tools from reachability analysis and optimal control to compute the set of hypotheses the robot could learn in finite time, as well as the worst and best-case time it takes to learn them. We demonstrate the utility of our analysis tool in four human-robot domains, including autonomous driving and indoor navigation.

Hamilton-Jacobi (HJ) reachability analysis is an important formal verification method for guaranteeing performance and safety properties of dynamical control systems. Its advantages include compatibility with general nonlinear system dynamics, formal treatment of bounded disturbances, and the ability to deal with state and input constraints. However, it involves solving a PDE, whose computational and memory complexity scales exponentially with respect to the number of state variables, limiting its direct use to small-scale systems. We propose DeepReach, a method that leverages new developments in sinusoidal networks to develop a neural PDE solver for high-dimensional reachability problems. The computational requirements of DeepReach do not scale directly with the state dimension, but rather with the complexity of the underlying reachable tube. DeepReach achieves comparable results to the state-of-the-art reachability methods, does not require any explicit supervision for the PDE solution, can easily handle external disturbances, adversarial inputs, and system constraints, and also provides a safety controller for the system. We demonstrate DeepReach on a 9D multi-vehicle collision problem, and a 10D narrow passage problem, motivated by autonomous driving applications.

Robots deployed in real-world environments should operate safely in a robust manner. In scenarios where an "ego" agent navigates in an environment with multiple other "non-ego" agents, two modes of safety are commonly proposed—adversarial robustness and probabilistic constraint satisfaction. However, while the former is generally computationally intractable and leads to overconservative solutions, the latter typically relies on strong distributional assumptions and ignores strategic coupling between agents.To avoid these drawbacks, we present a novel formulation of robustness within the framework of general-sum dynamic game theory, modeled on defensive driving. More precisely, we prepend an adversarial phase to the ego agent’s cost function. That is, we prepend a time interval during which other agents are assumed to be temporarily distracted, in order to render the ego agent’s equilibrium trajectory robust against other agents’ potentially dangerous behavior during this time. We demonstrate the effectiveness of our new formulation in encoding safety via multiple traffic scenarios.

In this paper, we present a method for finding approximate Nash equilibria in a broad class of reachability games. These games are often used to formulate both collision avoidance and goal satisfaction. Our method is computationally efficient, running in real-time for scenarios involving multiple players and more than ten state dimensions. The proposed approach forms a family of increasingly exact approximations to the original game. Our results characterize the quality of these approximations and show operation in a receding horizon, minimally-invasive control context. Additionally, as a special case, our method reduces to local gradient-based optimization in the single-player (optimal control) setting, for which a wide variety of efficient algorithms exist.

Autonomous systems like aircraft and assistive robots often operate in scenarios where guaranteeing safety is critical. Methods like Hamilton-Jacobi reachability can provide guaranteed safe sets and controllers for such systems. However, often these same scenarios have unknown or uncertain environments, system dynamics, or predictions of other agents. As the system is operating, it may learn new knowledge about these uncertainties and should therefore update its safety analysis accordingly. However, work to learn and update safety analysis is limited to small systems of about two dimensions due to the computational complexity of the analysis. In this paper we synthesize several techniques to speed up computation: decomposition, warm-starting, and adaptive grids. Using this new framework we can update safe sets by one or more orders of magnitude faster than prior work, making this technique practical for many realistic systems. We demonstrate our results on simulated 2D and 10D near-hover quadcopters operating in a windy environment.

We present a novel method for handling uncertainty about the intentions of non-ego players in trajectory games, with application to motion planning for autonomous vehicles. Our method models the uncertainty about the intention of other agents by constructing multiple hypotheses about the objectives and constraints of other agents in the scene. For each candidate hypothesis, we associate a Bernoulli random variable representing the probability of that hypothesis, which may or may not be independent of the probability of other hypotheses. We leverage constraint asymmetries and feedback information patterns to incorporate the probabilities of hypotheses in a natural way. Specifically, increasing the probability associated with a given hypothesis from 0 to 1 shifts the responsibility of collision avoidance from the hypothesized agent to the ego agent. This method allows the generation of interactive trajectories for the ego agent, where the level of assertiveness or caution that the ego exhibits is directly related to the easy-to-model uncertainty it maintains about the scene.

In many applications of autonomy in robotics, guarantees that constraints are satisfied throughout the learning process are paramount. We present a controller synthesis technique based on the computation of reachable sets, using optimal control and game theory. Then, we present methods for combining reachability with learning-based methods, to enable performance improvement while maintaining safety and to move towards safe robot control with learned models of the dynamics and the environment. We will illustrate these "safe learning" methods on robotic platforms at Berkeley, including demonstrations of motion planning around people, and navigating in a priori unknown environments.

In this article, we study an adaptive source seeking problem, in which a mobile robot must identify the strongest emitter(s) of a signal in an environment with background emissions. Background signals may be highly heterogeneous and can mislead algorithms that are based on receding horizon control. We propose AdaSearch, a general algorithm for adaptive source seeking in the face of heterogeneous background noise. AdaSearch combines global trajectory planning with principled confidence intervals in order to concentrate measurements in promising regions while guaranteeing sufficient coverage of the entire area. Theoretical analysis shows that AdaSearch confers gains over a uniform sampling strategy when the distribution of background signals is highly variable. Simulation experiments demonstrate that when applied to the problem of radioactive source-seeking, AdaSearch outperforms both uniform sampling and a receding time horizon informationmaximization approach based on the current literature. We also demonstrate AdaSearch in hardware, providing further evidence of its potential for real-time implementation.

Real-world autonomous systems often employ probabilistic predictive models of human behavior during planning to reason about their future motion. Since accurately modeling human behavior a priori is challenging, such models are often parameterized, enabling the robot to adapt predictions based on observations by maintaining a distribution over the model parameters. Although this enables data and priors to improve the human model, observation models are difficult to specify and priors may be incorrect, leading to erroneous state predictions that can degrade the safety of the robot motion plan. In this work, we seek to design a predictor which is more robust to misspecified models and priors, but can still leverage human behavioral data online to reduce conservatism in a safe way. To do this, we cast human motion prediction as a Hamilton-Jacobi reachability problem in the joint state space of the human and the belief over the model parameters. We construct a new continuous-time dynamical system, where the inputs are the observations of human behavior, and the dynamics include how the belief over the model parameters change. The results of this reachability computation enable us to both analyze the effect of incorrect priors on future predictions in continuous state and time, as well as to make predictions of the human state in the future. We compare our approach to the worst-case forward reachable set and a stochastic predictor which uses Bayesian inference and produces full future state distributions. Our comparisons in simulation and in hardware demonstrate how our framework can enable robust planning while not being overly conservative, even when the human model is inaccurate. Videos of our experiments can be found at the project website1.

Many problems in robotics involve multiple decision making agents. To operate efficiently in such settings, a robot must reason about the impact of its decisions on the behavior of other agents. Differential games offer an expressive theoretical framework for formulating these types of multi-agent problems. Unfortunately, most numerical solution techniques scale poorly with state dimension and are rarely used in real-time applications. For this reason, it is common to predict the future decisions of other agents and solve the resulting decoupled, i.e., single-agent, optimal control problem. This decoupling neglects the underlying interactive nature of the problem; however, efficient solution techniques do exist for broad classes of optimal control problems. We take inspiration from one such technique, the iterative linear-quadratic regulator (ILQR), which solves repeated approximations with linear dynamics and quadratic costs. Similarly, our proposed algorithm solves repeated linear-quadratic games. We experimentally benchmark our algorithm in several examples with a variety of initial conditions and show that the resulting strategies exhibit complex interactive behavior. Our results indicate that our algorithm converges reliably and runs in real-time. In a three-player, 14-state simulated intersection problem, our algorithm initially converges in <; 0.25 s. Receding horizon invocations converge in <; 50 ms in a hardware collision-avoidance test.

Iterative linear-quadratic (ILQ) methods are widely used in the nonlinear optimal control community. Recent work has applied similar methodology in the setting of multi-player general-sum differential games. Here, ILQ methods are capable of finding local equilibria in interactive motion planning problems in real-time. As in most iterative procedures, however, this approach can be sensitive to initial conditions and hyperparameter choices, which can result in poor computational performance or even unsafe trajectories. In this paper, we focus our attention on a broad class of dynamical systems which are feedback linearizable, and exploit this structure to improve both algorithmic reliability and runtime. We showcase our new algorithm in three distinct traffic scenarios, and observe that in practice our method converges significantly more often and more quickly than was possible without exploiting the feedback linearizable structure.

We present a novel approach to control design for nonlinear systems which leverages model-free policy optimization techniques to learn a linearizing controller for a physical plant with unknown dynamics. Feedback linearization is a technique from nonlinear control which renders the input-output dynamics of a nonlinear plant linear under application of an appropriate feedback controller. Once a linearizing controller has been constructed, desired output trajectories for the nonlinear plant can be tracked using a variety of linear control techniques. However, the calculation of a linearizing controller requires a precise dynamics model for the system. As a result, model-based approaches for learning exact linearizing controllers generally require a simple, highly structured model of the system with easily identifiable parameters. In contrast, the model-free approach presented in this paper is able to approximate the linearizing controller for the plant using general function approximation architectures. Specifically, we formulate a continuous-time optimization problem over the parameters of a learned linearizing controller whose optima are the set of parameters which best linearize the plant. We derive conditions under which the learning problem is (strongly) convex and provide guarantees which ensure the true linearizing controller for the plant is recovered. We then discuss how model-free policy optimization algorithms can be used to solve a discrete-time approximation to the problem using data collected from the real-world plant. The utility of the framework is demonstrated in simulation and on a real-world robotic platform.

Partially observable Markov decision processes (POMDPs) with continuous state and observation spaces have powerful flexibility for representing real-world decision and control problems but are notoriously difficult to solve. Recent online sampling-based algorithms that use observation likelihood weighting have shown unprecedented effectiveness in domains with continuous observation spaces. However there has been no formal theoretical justification for this technique. This work offers such a justification, proving that a simplified algorithm, partially observable weighted sparse sampling (POWSS), will estimate Q-values accurately with high probability and can be made to perform arbitrarily near the optimal solution by increasing computational power.

We propose a novel technique for improving the stochastic gradient descent (SGD) method to train deep networks, which we term pbSGD. The proposed pbSGD method simply raises the stochastic gradient to a certain power elementwise during iterations and introduces only one additional parameter, namely, the power exponent (when it equals to 1, pbSGD reduces to SGD). We further propose pbSGD with momentum, which we term pbSGDM. The main results of this paper present comprehensive experiments on popular deep learning models and benchmark datasets. Empirical results show that the proposed pbSGD and pbSGDM obtain faster initial training speed than adaptive gradient methods, comparable generalization ability with SGD, and improved robustness to hyper-parameter selection and vanishing gradients. pbSGD is essentially a gradient modifier via a nonlinear transformation. As such, it is orthogonal and complementary to other techniques for accelerating gradient-based optimization such as learning rate schedules. Finally, we show convergence rate analysis for both pbSGD and pbSGDM methods. The theoretical rates of convergence match the best known theoretical rates of convergence for SGD and SGDM methods on nonconvex functions.

We consider the problem of extracting safe environments and controllers for reach-avoid objectives for systems with known state and control spaces, but unknown dynamics. In a given environment, a common approach is to synthesize a controller from an abstraction or a model of the system (potentially learned from data). However, in many situations, the relationship between the dynamics of the model and the actual system is not known; and hence it is difficult to provide safety guarantees for the system. In such cases, the Standard Simulation Metric (SSM), defined as the worst-case norm distance between the model and the system output trajectories, can be used to modify a reach-avoid specification for the system into a more stringent specification for the abstraction. Nevertheless, the obtained distance, and hence the modified specification, can be quite conservative. This limits the set of environments for which a safe controller can be obtained. We propose SPEC, a specification-centric simulation metric, which overcomes these limitations by computing the distance using only the trajectories that violate the specification for the system. We show that modifying a reach-avoid specification with SPEC allows us to synthesize a safe controller for a larger set of environments compared to SSM. We also propose a probabilistic method to compute SPEC for a general class of systems. Case studies using simulators for quadrotors and autonomous cars illustrate the advantages of the proposed metric for determining safe environment sets and controllers.

Robust motion planning is a well-studied problem in the robotics literature, yet current algorithms struggle to operate scalably and safely in the presence of other moving agents, such as humans. This paper introduces a novel framework for robot navigation that accounts for high-order system dynamics and maintains safety in the presence of external disturbances, other robots, and humans. Our approach precomputes a tracking error margin for each robot, generates confidence-aware human motion predictions, and coordinates multiple robots with a sequential priority ordering, effectively enabling scalable safe trajectory planning and execution. We demonstrate our approach in hardware with two robots and two humans, and showcase scalability in a larger simulation.

Safety analysis is a necessary component in the design and deployment of autonomous robotic systems. Techniques from robust optimal control theory, such as Hamilton-Jacobi reachability analysis, allow a rigorous formalization of safety as guaranteed constraint satisfaction. Unfortunately, the computational complexity of these tools for general dynamical systems scales poorly with state dimension, making existing tools impractical beyond small problems. Modern reinforcement learning methods have shown promising ability to find approximate yet proficient solutions to optimal control problems in complex and high-dimensional systems, however their application has in practice been restricted to problems with an additive payoff over time, unsuitable for reasoning about safety. In recent work, we introduced a time-discounted modification of the problem of maximizing the minimum payoff over time, central to safety analysis, through a modified dynamic programming equation that induces a contraction mapping. Here, we show how a similar contraction mapping can render reinforcement learning techniques amenable to quantitative safety analysis as tools to approximate the safe set and optimal safety policy. This opens a new avenue of research connecting control-theoretic safety analysis and the reinforcement learning domain. We validate the correctness of our formulation by comparing safety results computed through Q-learning to analytic and numerical solutions, and demonstrate its scalability by learning safe sets and control policies for simulated systems of up to 18 state dimensions using value learning and policy gradient techniques.

We present a new framework for motion planning that wraps around existing kinodynamic planners and guarantees recursive feasibility when operating in a priori unknown, static environments. Our approach makes strong guarantees about overall safety and collision avoidance by utilizing a robust controller derived from reachability analysis. We ensure that motion plans never exit the safe backward reachable set of the initial state, while safely exploring the space. This preserves the safety of the initial state, and guarantees that that we will eventually find the goal if it is possible to do so while exploring safely. We implement our framework in the Robot Operating System (ROS) software environment and demonstrate it in a real-time simulation.

A method is presented for solving the discrete-time finite-horizon Linear Quadratic Regulator (LQR) problem subject to auxiliary linear equality constraints, such as fixed end-point constraints. The method explicitly determines an affine relationship between the control and state variables, as in standard Riccati recursion, giving rise to feedback control policies that account for constraints. Since the linearly-constrained LQR problem arises commonly in robotic trajectory optimization, having a method that can efficiently compute these solutions is important. We demonstrate some of the useful properties and interpretations of said control policies, and we compare the computation time and complexity of our method against existing methods.

Hamilton-Jacobi (HJ) reachability provides a flexible framework for the verification of safety in robotic systems: it accounts for nonlinear system dynamics and provides safety-preserving controllers. However, computational scalability limits its direct application to systems of less than five continuous state dimensions. To alleviate this computational burden, system decomposition methods have been proposed; however, safety guarantees are lost in situations involving “leaking corners which arise when there are conflicting controls between subsystems. In this paper, a coupled HJ formulation is presented, which addresses leaking corners and guarantees safety, while incorporating dimensionality reduction. We demonstrate our method in two examples, one of which is a vehicle obstacle avoidance problem with a 5D car model, whose HJ computation was previously considered to be intractable.

Hamilton-Jacobi (HJ) reachability analysis has been developed over the past decades into a widely-applicable tool for determining goal satisfaction and safety verification in nonlinear systems. While HJ reachability can be formulated very generally, computational complexity can be a serious impediment for many systems of practical interest. Much prior work has been devoted to computing approximate solutions to large reachability problems, yet many of these methods may only apply to very restrictive problem classes, do not generate controllers, and/or can be extremely conservative. In this paper, we present a new method for approximating the optimal controller of the HJ reachability problem for control-affine systems. While also a specific problem class, many dynamical systems of interest are, or can be well approximated, by control-affine models. We explicitly avoid storing a representation of the reachability value function, and instead learn a controller as a sequence of simple binary classifiers. We compare our approach to existing grid-based methodologies in HJ reachability and demonstrate its utility on several examples, including a physical quadrotor navigation task.

Ensuring safety in trajectory planning of multirotor systems is an essential element for risk-free operation. Even if the generated trajectory is known to be safe in the planning phase, unknown disturbance during an actual operation can lead to a dangerous situation. This paper proposes safety-guaranteed receding horizon planning against unknown, but bounded, disturbances. We first characterize forward reachable set (FRS) of the system, the set of states after a certain duration considering all possible disturbances, using Hamilton-Jacobi (HJ) reachability analysis. To compute the FRSs in real-time, we conservatively approximate the true FRS and perform ellipsoidal parameterization on the FRSs. Using the FRSs, we can plan a robust trajectory that avoids risky regions and rapidly re-plan the trajectory when the system encounters sudden disturbance. The proposed method is validated through an experiment of avoiding obstacles in a wind.

A global asymptotic stability condition for Long Short-Term Memory neural networks is presented in this paper. A linear matrix inequality optimization problem is used to describe this global stability condition. The linear matrix inequality formulation can be viewed as a way for stabilization of Long Short-Term Memory neural networks since the networks' weight matrices and biases can be essentially treated as control variables. The condition and how to compute numerical values for the weight matrices and biases are illustrated by some examples.

Drug resistance in breast cancer cell populations has been shown to arise through phenotypic transition of cancer cells to a drug-tolerant state, for example through epithelial-to-mesenchymal transition or transition to a cancer stem cell state. However, many breast tumors are a heterogeneous mixture of cell types with numerous epigenetic states in addition to stem-like and mesenchymal phenotypes, and the dynamic behavior of this heterogeneous mixture in response to drug treatment is not well-understood. Recently, we showed that plasticity between differentiation states, as identified with intracellular markers such as cytokeratins, is linked to resistance to specific targeted therapeutics. Understanding the dynamics of differentiation-state transitions in this context could facilitate the development of more effective treatments for cancers that exhibit phenotypic heterogeneity and plasticity. In this work, we develop computational models of a drug-treated, phenotypically heterogeneous triple-negative breast cancer (TNBC) cell line to elucidate the feasibility of differentiation-state transition as a mechanism for therapeutic escape in this tumor subtype. Specifically, we use modeling to predict the changes in differentiation-state transitions that underlie specific therapy-induced changes in differentiation-state marker expression that we recently observed in the HCC1143 cell line. We report several statistically significant therapy-induced changes in transition rates between basal, luminal, mesenchymal, and non-basal/non-luminal/non-mesenchymal differentiation states in HCC1143 cell populations. Moreover, we validate model predictions on cell division and cell death empirically, and we test our models on an independent data set. Overall, we demonstrate that changes in differentiation-state transition rates induced by targeted therapy can provoke distinct differentiation-state aggregations of drug-resistant cells, which may be fundamental to the design of improved therapeutic regimens for cancers with phenotypic heterogeneity.

[This corrects the article DOI: 10.1371/journal.pcbi.1006840.].

We study the multi-armed bandit problem with multiple plays and a budget constraint for both the stochastic and the adversarial setting. At each round, exactly K out of N possible arms have to be played (with 1 ≤ K <= N). In addition to observing the individual rewards for each arm played, the player also learns a vector of costs which has to be covered with an a-priori defined budget B. The game ends when the sum of current costs associated with the played arms exceeds the remaining budget. Firstly, we analyze this setting for the stochastic case, for which we assume each arm to have an underlying cost and reward distribution with support [cmin, 1] and [0, 1], respectively. We derive an Upper Confidence Bound (UCB) algorithm which achieves O(NK4 log B) regret. Secondly, for the adversarial case in which the entire sequence of rewards and costs is fixed in advance, we derive an upper bound on the regret of order O(√NB log(N/K)) utilizing an extension of the well-known Exp3 algorithm. We also provide upper bounds that hold with high probability and a lower bound of order Ω((1 – K/N) √NB/K).

Motion planning is an extremely well-studied problem in the robotics community, yet existing work largely falls into one of two categories: computationally efficient but with few if any safety guarantees, or able to give stronger guarantees but at high computational cost. This work builds on a recent development called FaSTrack in which a slow offline computation provides a modular safety guarantee for a faster online planner. We introduce the notion of “meta-planning” in which a refined offline computation enables safe switching between different online planners. This provides autonomous systems with the ability to adapt motion plans to a priori unknown environments in real-time as sensor measurements detect new obstacles, and the flexibility to maneuver differently in the presence of obstacles than they would in free space, all while maintaining a strict safety guarantee. We demonstrate the meta-planning algorithm both in simulation and in hardware using a small Crazyflie 2.0 quadrotor.

We present a 70mg, 3cm wing-span, flapping wing aerial vehicle capable of generating up to 60mg of lift using an electromagnetic actuator with low-voltage input (≈5.5V). Its design is novel, with the actuation and transmission integrated into a single resonant mechanism, thus not requiring any small-linear-displacement amplifying stages seen in other works. It can produce ±45° wing strokes and ±45° wing plane rotations at 98Hz operation mimicking relevant insects at this size scale. With required input power of only 250mW, it is, to the best of our knowledge, the most energy efficient electromagnetic design at the sub-100mg scale reported to date, and an order of magnitude more efficient than all other electromagnetic works.

In this paper some local stability results for an autonomous Long Short-Term Memory neural network model with respect to the origin are provided. In particular, it is shown through linearization that the local asymptotic stability conditions with respect to the origin only depend on one of the weight matrices. Simulations indicate that these local stability conditions greatly influence the behavior of the autonomous four-dimensional neural network in the region where each variable's values vary between minus one and one. Finally, some sufficient stability conditions for the nonlinear model are formulated as a convex program involving linear matrix inequalities.

In assistive teleoperation, an autonomous agent uses a prediction about a human user's intent to attempt to align the behavior of a controlled system with the human's goal, even if the human's own inputs are not perfectly aligned to that goal. Haptic Assistance achieves this effect by influencing the human through forces/torques applied to the human's control interface. In this work, we describe our method for creating such haptic assistance via Inverse Reinforcement Learning applied to successful task demonstrations. We then use our assistance method to examine the role that haptic feedback plays in assistive teleoperation. Through our user study, we find that when the assistance incorrectly predicts a user's intent, aiding the user via haptic feedback on their control interface, rather than directly modifying their input signal, is preferable and provides the user with a significantly greater sense of control over the system.

Hamilton-Jacobi (HJ) reachability is a method that provides rigorous analyses of the safety properties of dynamical systems. These guarantees can be provided by the computation of a backward reachable set (BRS), which represents the set of states from which the system may be driven into violating safety properties despite the system's best effort to remain safe. Unfortunately, the complexity of the BRS computation scales exponentially with the number of state dimensions. Although numerous approximation techniques are able to tractably provide conservative estimates of the BRS, they often require restrictive assumptions about system dynamics without providing an exact solution. In this paper we propose a general method for decomposing dynamical systems. Even when the resulting subsystems are coupled, relatively high-dimensional BRSs that were previously intractable or expensive to compute can now be quickly and exactly computed in lower-dimensional subspaces. As a result, the curse of dimensionality is alleviated to a large degree without sacrificing optimality. We demonstrate our theoretical results through a 3D Dubins Car model and a 6D Acrobatic Quadrotor model.

Learning cooperative policies for multi-agent systems is often challenged by partial observability and a lack of coordination. In some settings, the structure of a problem allows a distributed solution with limited communication. Here, we consider a scenario where no communication is available, and instead we learn local policies for all agents that collectively mimic the solution to a centralized multi-agent static optimization problem. Our main contribution is an information theoretic framework based on rate distortion theory which facilitates analysis of how well the resulting fully decentralized policies are able to reconstruct the optimal solution. Moreover, this framework provides a natural extension that addresses which nodes an agent should communicate with to improve the performance of its individual policy.

We consider a model of game-theoretic learning based on online mirror descent (OMD) with asynchronous and delayed feedback information. Instead of focusing on specific games, we consider a broad class of continuous games defined by the general equilibrium stability notion, which we call λ-variational stability. Our first contribution is that, in this class of games, the actual sequence of play induced by OMD-based learning converges to Nash equilibria provided that the feedback delays faced by the players are synchronous and bounded. Subsequently, to tackle fully decentralized, asynchronous environments with (possibly) unbounded delays between actions and feedback, we propose a variant of OMD which we call delayed mirror descent (DMD), and which relies on the repeated leveraging of past information. With this modification, the algorithm converges to Nash equilibria with no feedback synchronicity assumptions and even when the delays grow superlinearly relative to the horizon of play.

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.

The papers in this special section are devoted to the topic of human-centered automation. The central theme of these papers are the tools and methods for the design and analysis of human-centered automation systems including: the design and validation of computational models of systems that integrate models of the human with models of autonomous and semi-autonomous systems; the design of systems that ease the transfer of information between humans and autonomous systems; the analysis and prediction of potential conflicts between the human and the automation in semi-autonomous systems; the design of autonomy to accommodate varying levels of human experience, training, and acuity; the analysis of information asymmetry in collaborative, semi-autonomous systems; the design of autonomy for off-nominal conditions, such as multiple sensor failures, human error, or other cascading events; and the design of autonomy to support systems with multiple humans; the design of autonomous systems which are “self-aware,” so that humans are prompted to intervene when necessary.

With the growth of high-throughput proteomic data, in particular time series gene expression data from various perturbations, a general question that has arisen is how to organize inherently heterogenous data into meaningful structures. Since biological systems such as breast cancer tumors respond differently to various treatments, little is known about exactly how these gene regulatory networks (GRNs) operate under different stimuli. Challenges due to the lack of knowledge not only occur in modeling the dynamics of a GRN but also cause bias or uncertainties in identifying parameters or inferring the GRN structure. This paper describes a new algorithm which enables us to estimate bias error due to the effect of perturbations and correctly identify the common graph structure among biased inferred graph structures. To do this, we retrieve common dynamics of the GRN subject to various perturbations. We refer to the task as "repairing" inspired by "image repairing" in computer vision. The method can automatically correctly repair the common graph structure across perturbed GRNs, even without precise information about the effect of the perturbations. We evaluate the method on synthetic data sets and demonstrate an application to the DREAM data sets and discuss its implications to experiment design.

Hamilton-Jacobi-Isaacs (HJI) reachability analysis has been employed to guarantee constraint satisfaction (safety) in a number of applications including robotics, air traffic control, and control of HVAC systems. However, the current standard for these methods can result in overly-conservative controllers that can degrade system performance with respect to lower priority objectives. There has been interest in incorporating online machine learning techniques to reduce the conservativeness of this approach. However, recent efforts have resulted in methods that are computationally inefficient and scale poorly with the dimension of the state space. We explore a novel online reachability update algorithm based on temporal-difference learning that is computationally more efficient than current methods. Our algorithm is demonstrated on a simulation of a quadrotor learning to track a trajectory in a confined space and a reach-avoid/pursuit-evader game.

We consider a reach-avoid differential game, in which one of the players aims to steer the system into a target set without violating a set of state constraints, while the other player tries to prevent the first from succeeding; the system dynamics, target set, and state constraints may all be time-varying. The analysis of this problem plays an important role in collision avoidance, motion planning and aircraft control, among other applications. Previous methods for computing the guaranteed winning initial conditions and strategies for each player have either required augmenting the state vector to include time, or have been limited to problems with either no state constraints or entirely static targets, constraints and dynamics. To incorporate time-varying dynamics, targets and constraints without the need for state augmentation, we propose a modified Hamilton-Jacobi-Isaacs equation in the form of a double-obstacle variational inequality, and prove that the zero sublevel set of its viscosity solution characterizes the capture basin for the target under the state constraints. Through this formulation, our method can compute the capture basin and winning strategies for time-varying games at virtually no additional computational cost relative to the time-invariant case. We provide an implementation of this method based on well-known numerical schemes and show its convergence through a simple example; we include a second example in which our method substantially outperforms the state augmentation approach.

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.

Automatic dependent surveillance-broadcast (ADS-B) is one of the fundamental surveillance technologies to improve the safety, capacity, and efficiency of the national airspace system. ADS-B shares its frequency band with current radar systems that use the same 1,090 MHz band. The coexistence of radar systems and ADS-B systems is a key issue to detect and resolve conflicts in the next generation air transportation system (NextGen). This paper focuses on the performance evaluation of ADS-B with existing radar systems and performance optimization of ADS-B systems to improve the safety and efficiency of conflict detection and resolution in NextGen. We have developed a simulation environment which models the complex interplay among the air traffic load, the radar systems, the ADS-B systems, and the wireless channel. A simple model is used to derive an analytical expression for a performance metric of ADS-B. This model is then used to design an adaptive ADS-B protocol for maximizing the information coverage while guaranteeing reliable and timely communication in air traffic surveillance networks. Simulation results show that the effect of ADS-B interference on the current radar system is negligible. The operational ability of ADS-B meets the performance requirements of conflict detection and resolution in air traffic control. However, upgrades are required in the current radar system for operation within an ADS-B environment since the current radars can significantly degrade the ADS-B performance. Numerical results indicate that the proposed adaptive protocol has the potential to improve the performance of conflict detection and resolution in air traffic control.

Proving that systems satisfy hard input and state constraints is frequently desirable when designing cyber-physical systems. One method for doing so is to compute the viability kernel, the subset of the state space for which a control signal exists that is guaranteed to keep the system within the constraints over some time horizon. In this paper we present a novel method for approximating the viability kernel for linear sampled-data systems using a sampling-based algorithm, which by its construction offers a direct trade-off between scalability and accuracy. We also prove that the algorithm is correct, that its convergence properties are optimal, and demonstrate it on a simple example. We conclude by briefly describing additional results which are omitted due to space constraints.

We consider a single-pursuer-multiple-evader pursuit-evasion game in which a team of evaders aims to delay the capture by a faster pursuer. We extend our previous open-loop formulation (and its solution) of the game to incorporate more realistic settings: a pursuer with uncertain position and evaders with limited turning rates. The formulation provides a guaranteed lower bound on the team survival time. The survival time performance of the proposed approach is evaluated through extensive simulations and compared to that of the existing approaches. It is shown to be highly effective even when the evaders can not detect the pursuer. A noticeable trend of potentially practical importance is that larger teams benefit more from an increase in turning rates than smaller teams.

We describe a practical collision avoidance algorithm that synthesizes provably safe piecewise constant control laws (compatible with the sampled-data nature of the system), and demonstrate the results on an experimental platform, the Pioneer ground robots. Our application is formulated in a pursuer-evader framework in which an automated unmanned vehicle navigates its environment while avoiding a moving obstacle that acts as a malicious agent. Offline, we employ reachability analysis to characterize the evolution of trajectories so as to determine what control inputs can preserve safety over every sampling interval. The moving obstacle is considered unpredictable with nearly no restrictions on its control policies (although we do take into account the physical constraints due to limited dynamical and actuation capacities of both robots). Online, the controller executes computationally inexpensive operations based only on an easy-to-store lookup table. The results of the experiment as well as the proposed algorithm are presented and discussed in detail.

BACKGROUND: We consider the problem of reconstructing a gene regulatory network structure from limited time series gene expression data, without any a priori knowledge of connectivity. We assume that the network is sparse, meaning the connectivity among genes is much less than full connectivity. We develop a method for network reconstruction based on compressive sensing, which takes advantage of the network's sparseness. RESULTS: For the case in which all genes are accessible for measurement, and there is no measurement noise, we show that our method can be used to exactly reconstruct the network. For the more general problem, in which hidden genes exist and all measurements are contaminated by noise, we show that our method leads to reliable reconstruction. In both cases, coherence of the model is used to assess the ability to reconstruct the network and to design new experiments. We demonstrate that it is possible to use the coherence distribution to guide biological experiment design effectively. By collecting a more informative dataset, the proposed method helps reduce the cost of experiments. For each problem, a set of numerical examples is presented. CONCLUSIONS: The method provides a guarantee on how well the inferred graph structure represents the underlying system, reveals deficiencies in the data and model, and suggests experimental directions to remedy the deficiencies.

Capacity constraints imposed by current air traffic management technologies and protocols could severely limit the performance of the Next Generation Air Transportation System (NextGen). A fundamental design decision in the development of this system is the level of decentralization that balances system safety and efficiency. A new surveillance technology called automatic dependent surveillance-broadcast (ADS-B) can be potentially used to shift air traffic control to a more distributed architecture; however, channel variations and interference with existing secondary radar replies can affect ADS-B systems. This paper presents a framework for managing arrivals at an airport by using a hybrid centralized/distributed algorithm for communication and control. The algorithm combines the centralized control that is used in congested regions with the distributed control that is used in lower traffic density regions. The hybrid algorithm is evaluated through realistic simulations of operations around a major airport. The proposed strategy is shown to significantly improve air traffic control performance under various operating conditions by adapting to the underlying communication, navigation, and surveillance systems. The performance of the proposed strategy is found to be comparable to fully centralized strategies, despite requiring significantly less ground infrastructure.

We present a numerical method for computing backward reachable sets in differential games. A backward reachable set for time t is captured by the t sublevel set of the lower value function of the game, which coincides with the viscosity solution of a stationary Hamilton-Jacobi-Isaacs (HJI) equation. We solve the stationary HJI equation in a computationally efficient way that does not involve any numerical integration over time, which would otherwise be required for time-dependent HJI equations. Backward reachable sets for all time points can simultaneously be extracted from the solution. The performance of the method is demonstrated by investigating the growth of multicellular structures of non-malignant and malignant breast cells as a proof of principle.

This talk will present reachability analysis as a tool for model checking and controller synthesis for dynamic systems. We will consider the problem of guaranteeing reachability to a given desired subset of the state space while satisfying a safety property defined in terms of state constraints. We allow for nonlinear and hybrid dynamics, and possibly nonconvex state constraints. We use these results to synthesize controllers that ensure safety and reachability properties under bounded model disturbances that vary continuously.

In this paper, we present details of the real time implementation onboard a quadrotor helicopter of learning-based model predictive control (LBMPC). LBMPC rigorously combines statistical learning with control engineering, while providing levels of guarantees about safety, robustness, and convergence. Experimental results show that LBMPC can learn physically based updates to an initial model, and how as a result LBMPC improves transient response performance. We demonstrate robustness to mis-learning. Finally, we show the use of LBMPC in an integrated robotic task demonstration-The quadrotor is used to catch a ball thrown with an a priori unknown trajectory.

While machine learning techniques have become popular tools in the design of autonomous systems, the asymptotic nature of their performance guarantees means that they should not be used in scenarios in which safety and robustness are critical for success. By pairing machine learning algorithms with rigorous safety analyses, such as Hamilton-Jacobi-Isaacs (HJI) reachability, this limitation can be overcome. Guaranteed Safe Online Learning via Reachability (GSOLR) is a framework which combines HJI reachability with general machine learning techniques, allowing for the design of robotic systems which demonstrate both high performance and guaranteed safety. In this paper we show how the GSOLR framework can be applied to a target tracking problem, in which an observing quadrotor helicopter must keep a target ground vehicle with unknown (but bounded) dynamics inside its field of view at all times, while simultaneously attempting to build a motion model of the target. The resulting algorithm was implemented on board the Stanford Testbed of Autonomous Rotorcraft for Multi-Agent Control, and was compared to a naive safety-only algorithm and a learning-only algorithm. Experimental results illustrate the success of the GSOLR algorithm, even under scenarios in which the machine learning algorithm performed poorly (and would otherwise lead to unsafe actions), thus demonstrating the power of this technique.

We present an efficient algorithm which computes, for a kinematic point mass moving in the plane, a time-optimal path that visits a sequence of target sets while conservatively avoiding collision with moving obstacles, also modelled as kinematic point masses, but whose trajectories are unknown. The problem is formulated as a pursuit-evasion differential game, and the underlying construction is based on optimal control. The algorithm, which is a variant of the fast marching method for shortest path problems, can handle general dynamical constraints on the players and arbitrary domain geometry (e.g. obstacles, non-polygonal boundaries). Applications to a two-stage game, capture-the-flag, is presented.

This paper considers the problem of stochastic motion planning in uncertain environments, and extends existing chance constrained optimal control solutions. Due to the imperfect knowledge of the system state caused by motion uncertainty, sensor noise and environment uncertainty, the system constraints cannot be guaranteed to be satisfied and consequently must be considered probabilistically. To account for the uncertainty, the constraints are formulated as convex constraints on a random variable, known as chance constraints, with the violation probability of all the constraints guaranteed to be below a threshold. Standard chance constrained stochastic motion planning methods do not incorporate environmental sensing which typically leads to overly-conservative solutions. To address this, a novel hierarchical framework is proposed that consists of two main steps: an expected shortest path problem on an uncertain graph and a chance constrained motion planning problem. The first successful, real-time experimental demonstration of chance constrained control with uncertain constraint parameters and variables is also presented for a quadrotor equipped with a Kinect sensor navigating through an uncertain, cluttered 3D environment.

Heating, ventilation, and air conditioning (HVAC) systems are an important target for efficiency improvements through new equipment and retrofitting because of their large energy footprint. One type of equipment that is common in homes and some offices is an electrical, single-stage heat pump air conditioner (AC). To study this setup, we have built the Berkeley Retrofitted and Inexpensive HVAC Testbed for Energy Efficiency (BRITE) platform. This platform allows us to actuate an AC unit that controls the room temperature of a computer laboratory on the Berkeley campus that is actively used by students, while sensors record room temperature and AC energy consumption. We build a mathematical model of the temperature dynamics of the room, and combining this model with statistical methods allows us to compute the heating load due to occupants and equipment using only a single temperature sensor. Next, we implement a control strategy that uses learning-based model-predictive control (MPC) to learn and compensate for the amount of heating due to occupancy as it varies throughout the day and year. Experiments on BRITE show that our techniques result in a 30%-70% reduction in energy consumption as compared to two-position control, while still maintaining a comfortable room temperature. The energy savings are due to our control scheme compensating for varying occupancy, while considering the transient and steady state electrical consumption of the AC. Our techniques can likely be generalized to other HVAC systems while still maintaining these energy saving features.

The continuous growth of air traffic demand, skyrocketing fuel price, and increasing concerns on safety and environmental impact of air transportation necessitate the modernization of the air traffic management (ATM) system in the United States. The design of such a large-scale networked system that involves complex interactions among automation and human operators poses new challenges for many engineering fields. This paper investigates several important facets of the future ATM system from a systems-level point of view. In particular, we develop a hierarchical decentralized decision architecture that can design 4-D (space +time) path plans for a large number of flights while satisfying weather and capacity constraints of the overall system. The proposed planning framework respects preferences of individual flights and encourages information sharing among different decision makers in the system, and thus has a great potential to reduce traffic delays and weather risks while maintaining safety standards. The framework is validated through a large-scale simulation based on real traffic data over the entire airspace of the contiguous United States. We envision that the hierarchical decentralization approach developed in this paper would also provide useful insights into the design of decision and information hierarchies for other large-scale infrastructure systems.

Epithelia are sheets of connected cells that are essential across the animal kingdom. Experimental observations suggest that the dynamical behavior of many single-layered epithelial tissues has strong analogies with that of specific mechanical systems, namely large networks consisting of point masses connected through spring-damper elements and undergoing the influence of active and dissipating forces. Based on this analogy, this work develops a modeling framework to enable the study of the mechanical properties and of the dynamic behavior of large epithelial cellular networks. The model is built first by creating a network topology that is extracted from the actual cellular geometry as obtained from experiments, then by associating a mechanical structure and dynamics to the network via spring-damper elements. This scalable approach enables running simulations of large network dynamics: the derived modeling framework in particular is predisposed to be tailored to study general dynamics (for example, morphogenesis) of various classes of single-layered epithelial cellular networks. In this contribution, we test the model on a case study of the dorsal epithelium of the Drosophila melanogaster embryo during early dorsal closure (and, less conspicuously, germband retraction).

We present a dynamic programming based solution to a stochastic reachability problem for a controlled discrete-time stochastic hybrid system. A sum-multiplicative cost function is introduced along with a corresponding dynamic recursion which quantifies the probability of hitting a target set at some point during a finite time horizon, while avoiding an obstacle set during each time step preceding the target hitting time. In contrast with earlier works which consider the reach and avoid sets as both deterministic and time invariant, we consider the avoid set to be both time-varying and probabilistic. Optimal reach-avoid control policies are derived as the solution to an optimal control problem via dynamic programming. A computational example motivated by aircraft motion planning is provided.

The task of planning and controlling robot motion in practical applications is often complicated by the effects of model uncertainties and environment disturbances. We present in this paper a systematic approach for generating robust motion control strategies to satisfy high level specifications of safety, target attainability, and invariance, under unknown but bounded, continuous disturbances. The motion planning task is decomposed into the two sub-problems of finite horizon reach with avoid and infinite horizon invariance. The set of states for which each of the sub-problems is robustly feasible is computed via iterative reachability calculations under a differential game framework. We discuss how the results of this computation can be used to inform selections of control inputs based upon state measurements at run-time and provide an algorithm for implementing the corresponding feedback control policies. Finally, we demonstrate an experimental application of this method to the control of an autonomous helicopter in tracking a moving ground vehicle.

Capture-the-flag is a complex, challenging game that is a useful proxy for many problems in robotics and other application areas. The game is adversarial, with multiple, potentially competing, objectives. This interplay between different factors makes the problem complex, even in the case of only two players. To make analysis tractable, previous approaches often make various limiting assumptions upon player actions. In this paper, we present a framework for analyzing and solving a two-player capture-the-flag game as a zero-sum differential game. Our problem formulation allows each player to make decisions rationally based upon the current player positions, assuming only an upper bound on the movement speeds. Using Hamilton-Jacobi reachability analysis, we compute winning regions for each player as subsets of the joint configuration space and derive the corresponding winning strategies. Simulation results are presented along with implications of the work as a tool for automation-aided decision-making for humans and mixed human-robot teams.

This paper considers the problem of motion planning for linear, Gaussian systems, and extends existing chance constrained optimal control solutions [1], [2] by incorporating the closed-loop uncertainty of the system and by reducing the conservativeness in the constraints. Due to the imperfect knowledge of the system state caused by motion uncertainty and sensor noise, the constraints cannot be guaranteed to be satisfied and consequently must be considered probabilistically. In this work, they are formulated as convex constraints on a univariate Gaussian random variable, with the violation probability of all the constraints guaranteed to be below a threshold. This threshold is a tuning parameter which trades off the performance of the system and the conservativeness of the solution. In contrast to similar methods, the proposed work considers the specific estimator and controller used in the closed-loop system in order to directly characterize the a priori distribution of the closed-loop system state. Using this distribution, a convex optimization program is formulated to solve for the optimal solution for the closed-loop system. The performance of the algorithm is demonstrated through several examples.

For some time now machine learning methods have been widely used in perception for autonomous robots. While there have been many results describing the performance of machine learning techniques with regards to their accuracy or convergence rates, relatively little work has been done on developing theoretical performance guarantees about their stability and robustness. As a result, many machine learning techniques are still limited to being used in situations where safety and robustness are not critical for success. One way to overcome this difficulty is by using reachability analysis, which can be used to compute regions of the state space, known as reachable sets, from which the system can be guaranteed to remain safe over some time horizon regardless of the disturbances. In this paper we show how reachability analysis can be combined with machine learning in a scenario in which an aerial robot is attempting to learn the dynamics of a ground vehicle using a camera with a limited field of view. The resulting simulation data shows that by combining these two paradigms, one can create robotic systems that feature the best qualities of each, namely high performance and guaranteed safety.

One of the oldest problems in the study of dynamical systems is the calculation of an optimal control. Though the determination of a numerical solution for the general non-convex optimal control problem for hybrid systems has been pursued relentlessly to date, it has proven difficult, since it demands nominal mode scheduling. In this paper, we calculate a numerical solution to the optimal control problem for a constrained switched nonlinear dynamical system with a running and final cost. The control parameter has a discrete component, the sequence of modes, and two continuous components, the duration of each mode and the continuous input while in each mode. To overcome the complexity posed by the discrete optimization problem, we propose a bi-level hierarchical optimization algorithm: at the higher level, the algorithm updates the mode sequence by using a single-mode variation technique, and at the lower level, the algorithm considers a fixed mode sequence and minimizes the cost functional over the continuous components. Numerical examples detail the potential of our proposed methodology.

For many applications, the control of a complex nonlinear system can be made easier by modeling the system as a collection of simplified hybrid modes, each representing a particular operating regime. An example of this is the decomposition of complex aerobatic flights into sequences of discrete maneuvers, an approach that has proven very successful for both human piloted and autonomously controlled aircraft. However, a critical step when designing such control systems is to ensure the safety and feasibility of transitions between these maneuvers. This work presents a hybrid dynamics framework for the design of guaranteed safe switching regions and is applied to a quadrotor helicopter performing an autonomous backflip. The regions are constructed using reachable sets calculated via a Hamilton-Jacobi differential game formulation, and experimental results are presented from flight tests on the STARMAC quadrotor platform.

BACKGROUND: The correlation between the expression levels of transcription factors and their target genes can be used to infer interactions within animal regulatory networks, but current methods are limited in their ability to make correct predictions. RESULTS: Here we describe a novel approach which uses nonparametric statistics to generate ordinary differential equation (ODE) models from expression data. Compared to other dynamical methods, our approach requires minimal information about the mathematical structure of the ODE; it does not use qualitative descriptions of interactions within the network; and it employs new statistics to protect against over-fitting. It generates spatio-temporal maps of factor activity, highlighting the times and spatial locations at which different regulators might affect target gene expression levels. We identify an ODE model for eve mRNA pattern formation in the Drosophila melanogaster blastoderm and show that this reproduces the experimental patterns well. Compared to a non-dynamic, spatial-correlation model, our ODE gives 59% better agreement to the experimentally measured pattern. Our model suggests that protein factors frequently have the potential to behave as both an activator and inhibitor for the same cis-regulatory module depending on the factors' concentration, and implies different modes of activation and repression. CONCLUSIONS: Our method provides an objective quantification of the regulatory potential of transcription factors in a network, is suitable for both low- and moderate-dimensional gene expression datasets, and includes improvements over existing dynamic and static models.

Local linearization techniques are an important class of nonparametric system identification. Identifying local linearizations in practice involves solving a linear regression problem that is ill-posed. The problem can be ill-posed either if the dynamics of the system lie on a manifold of lower dimension than the ambient space or if there are not enough measurements of all the modes of the dynamics of the system. We describe a set of linear regression estimators that can handle data lying on a lower-dimension manifold. These estimators differ from previous estimators, because these estimators are able to improve estimator performance by exploiting the sparsity of the system - the existence of direct interconnections between only some of the states - and can work in the ldquolarge p, small nrdquo setting in which the number of states is comparable to the number of data points. We describe our system identification procedure, which consists of a pre smoothing step and a regression step, and then we apply this procedure to data taken from a quadrotor helicopter. We use this data set to compare our procedure with existing procedures.

Quadrotor helicopters have become increasingly important in recent years as platforms for both research and commercial unmanned aerial vehicle applications. This paper extends previous work on several important aerodynamic effects impacting quadrotor flight in regimes beyond nominal hover conditions. The implications of these effects on quadrotor performance are investigated and control techniques are presented that compensate for them accordingly. The analysis and control systems are validated on the Stanford Testbed of Autonomous Rotorcraft for Multi-Agent Control quadrotor helicopter testbed by performing the quadrotor equivalent of the stall turn aerobatic maneuver. Flight results demonstrate the accuracy of the aerodynamic models and improved control performance with the proposed control schemes.

The Stanford Testbed of Autonomous Rotorcraft for Multi-Agent Control, a fleet of quadrotor helicopters, has been developed as a testbed for novel algorithms that enable autonomous operation of aerial vehicles. The testbed has been used to validate multiple algorithms such as reactive collision avoidance, collision avoidance through Nash Bargaining, path planning, cooperative search and aggressive maneuvering. This article briefly describes the algorithms presented and provides references for a more in-depth formulation, and the accompanying movie shows the demonstration of the algorithms on the testbed.

Air traffic flow control during adverse weather conditions is managed by the Federal Aviation Administration in today's air traffic system, although it is the individual airlines that are in the best position to assess the costs of disruptions to scheduled operations. To improve the efficiency of resource allocation, a market mechanism is proposed that enables airlines to participate directly in the flow control decision-making process. Since airlines can be expected to behave strategically, a lump-sum market mechanism is used for which existence of a Nash equilibrium and a bound on the worst case efficiency loss have been shown for agents that anticipate the effects of their own bids on resource prices. The convergence properties of this mechanism are studied for a two-player game with linear utilities, which reveals that restricting the airline bid update step-size can result in a wider range of stable bidding processes. The mechanism is then applied to an air traffic flow control scenario for multiple airports in the northeastern United States, which demonstrates the feasibility of performing market-based resource allocation within the time horizon for reliable weather predictions.

The Stanford Testbed of Autonomous Rotorcraft for Multi-Agent Control (STARMAC) is a multi-vehicle testbed currently comprised of two quadrotors, also called X4-flyers, with capacity for eight. This paper presents a comparison of control design techniques, specifically for outdoor altitude control, in and above ground effect, that accommodate the unique dynamics of the aircraft. Due to the complex airflow induced by the four interacting rotors, classical linear techniques failed to provide sufficient stability. Integral sliding mode and reinforcement learning control are presented as two design techniques for accommodating the nonlinear disturbances. The methods both result in greatly improved performance over classical control techniques.

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.

We address the problem of generating provably-safe conflict resolution maneuvers for aircraft in uncertain environments. We assume that a maneuver is composed of a sequence of flight modes, which are segments of constant heading, of constant bank angle, or of constant airspeed. Each of these flight modes has associated to it the kinematics of the aircraft, and hence the maneuver is a hybrid system. While the flight modes are defined ahead of time, their sequencing and parameter values do not necessarily have to be. We present an algorithm for generating provably safe maneuvers, which is based on a general procedure for designing controllers for hybrid systems. The result is a maneuver, proven to be safe within the limits of the models used, which is a familiar sequence of commands easily executable by the flight management systems. The maneuvers may be viewed as protocols, or "rules of the road", and are well-defined for each conflict scenario. We present results for two example maneuvers.

We present a method to design controllers for safety specifications in hybrid systems. The hybrid system combines discrete event dynamics with nonlinear continuous dynamics: the discrete event dynamics model linguistic and qualitative information and naturally accommodate mode switching logic, and the continuous dynamics model the physical processes themselves, such as the continuous response of an aircraft to the forces of aileron and throttle. Input variables model both continuous and discrete control and disturbance parameters. We translate safety specifications into restrictions on the system's reachable sets of states. Then, using analysis based on optimal control and game theory for automata and continuous dynamical systems, we derive Hamilton-Jacobi equations whose solutions describe the boundaries of reachable sets. These equations are the heart of our general controller synthesis technique for hybrid systems, in which we calculate feedback control laws for the continuous and discrete variables, which guarantee that the hybrid system remains in the "safe subset" of the reachable set. We discuss issues related to computing solutions to Hamilton-Jacobi equations. Throughout, we demonstrate out techniques on examples of hybrid automata modeling aircraft conflict resolution, autopilot flight mode switching, and vehicle collision avoidance.

We explore the use of distributed online motion planning algorithms for multiple mobile agents, in air traffic management systems (ATMS). The work is motivated by current trends in ATMS to move towards decentralized air traffic management, in which the aircraft operate in "free flight" mode instead of following prespecified "sky freeways". Conflict resolution strategies are an integral part of the free flight setting. The purpose of this paper is to obtain a set of manoeuvres to cover all possible conflict scenarios involving multiple agents. A distributed motion planning algorithm based on potential and vortex fields is used. While the algorithm is not always guaranteed to generate flyable trajectories, the obtained trajectories can serve as qualitative prototypes for coordination manoeuvres between multiple aircraft. The actual manoeuvres are generated by approximating these prototypes with trajectories made zip of straight lines and are further verified using hybrid verification techniques.