Showing 1–50 of 124 results for author: Tomlin, C

An Update to the Level Set Theorems in Hamilton-Jacobi Reachability Analysis

Authors: Dylan Hirsch, William McEneaney, Jaime Fisac, Claire Tomlin, Sylvia Herbert

Abstract: Hamilton-Jacobi Reachability (HJR) is an important framework for controlling safety-critical systems despite uncertainty. Its theoretical underpinnings are rooted in Hamilton-Jacobi Partial Differential Equations, which provide the value function used for controller synthesis. The Level Set Theorems of HJR allow one to interpret the value function in terms of satisfaction of a qualitative goal (e.… ▽ More Hamilton-Jacobi Reachability (HJR) is an important framework for controlling safety-critical systems despite uncertainty. Its theoretical underpinnings are rooted in Hamilton-Jacobi Partial Differential Equations, which provide the value function used for controller synthesis. The Level Set Theorems of HJR allow one to interpret the value function in terms of satisfaction of a qualitative goal (e.g. goal-reaching or obstacle-avoidance). We here provide a technical update regarding additional criteria needed for these theorems to hold. △ Less

Submitted 19 July, 2026; originally announced July 2026.

Robust Direct Data-Driven Hamiltonian for Safe Set Computation under Measurement Noise and Disturbances

Authors: Mohammad Bajelani, Christopher A. Strong, Claire J. Tomlin, Jason J. Choi, Klaske van Heusden

Abstract: Safe set computation is a fundamental challenge in safety-critical control systems, especially in direct data-driven settings where safety analysis is performed directly from noise-affected measurements, without explicit modeling. A recently proposed method, Data-Driven Hamiltonian (DDH), enables reachability analysis directly from measurements, without relying on prior knowledge of the underlying… ▽ More Safe set computation is a fundamental challenge in safety-critical control systems, especially in direct data-driven settings where safety analysis is performed directly from noise-affected measurements, without explicit modeling. A recently proposed method, Data-Driven Hamiltonian (DDH), enables reachability analysis directly from measurements, without relying on prior knowledge of the underlying system dynamics. This paper extends the DDH framework to a robust setting that accounts for measurement noise, exogenous disturbances, and sampling-induced state-velocity estimation error. A Robust Data-Driven Hamiltonian (R-DDH) is derived from noisy measurements and shown to yield a certified lower bound on the exact Hamiltonian. This results in a provable under-approximation of the value function and an inner approximation of the associated safe set. The gap between the data-driven and exact Hamiltonians is quantified, and it is shown to converge to zero with more data in a noise-free setting with additive disturbances. The effectiveness of the approach is shown through two case studies: a constrained double integrator and an aircraft taxiing system with a nonlinear closed-loop controller operating under perceptual uncertainty. △ Less

Submitted 15 June, 2026; originally announced June 2026.

Characterization and Analysis of Emergency Landing Flight Envelopes with Graded Safety Specifications

Authors: Chams Eddine Mballo, Bryce L. Ferguson, Inkyu Jang, Donggun Lee, Claire J. Tomlin

Abstract: Emergency landing flight envelope analysis traditionally adopts a binary notion of safety, whereby a trajectory is safe only if state constraints are satisfied pointwise in time. In practice, ensuring a successful landing requires recognizing that aircraft operation spans a continuum in the state space from the nominal to the critical regime. Between these regimes lies a degraded regime of states… ▽ More Emergency landing flight envelope analysis traditionally adopts a binary notion of safety, whereby a trajectory is safe only if state constraints are satisfied pointwise in time. In practice, ensuring a successful landing requires recognizing that aircraft operation spans a continuum in the state space from the nominal to the critical regime. Between these regimes lies a degraded regime of states outside nominal operation that may be visited only for limited durations. Safety is therefore inherently graded, in the sense that limited exposure to degraded states may be tolerated, and must be assessed using a trajectory-dependent criterion rather than a purely pointwise-in-time one. This paper develops a Hamilton-Jacobi reachability framework for analyzing emergency landing flight envelopes under this graded notion of safety. Safety is encoded through a soft constraint defined by a designer-specified continuous violation cost function that assigns zero cost in the nominal regime and larger cost to more safety-critical off-nominal states. We introduce a general class of state- and time-dependent violation cost functions and establish monotonicity and continuity properties that characterize how the flight envelope varies with the cost of off-nominal operation. These results provide a principled sensitivity analysis linking safety conservativeness to operational capability. Building on this analysis, we propose a synthesis algorithm for parameterized violation cost functions in this class. The algorithm provably converges to the least conservative parameter under which a prescribed off-nominal safety requirement is satisfied. Numerical results for a fixed-wing emergency landing scenario under propulsion failure demonstrate the sensitivity properties and validate the algorithm. △ Less

Submitted 3 June, 2026; originally announced June 2026.

Inverse Safety Filtering: Inferring Constraints from Safety Filters for Decentralized Coordination

Authors: Minh Nguyen, Jingqi Li, Gechen Qu, Claire J. Tomlin

Abstract: Safe multi-agent coordination in uncertain environments can benefit from learning constraints from other agents. Implicitly communicating safety constraints through actions is a promising approach, allowing agents to coordinate and maintain safety without expensive communication channels. This paper introduces an online method to infer constraints from observing the safety-filtered actions of othe… ▽ More Safe multi-agent coordination in uncertain environments can benefit from learning constraints from other agents. Implicitly communicating safety constraints through actions is a promising approach, allowing agents to coordinate and maintain safety without expensive communication channels. This paper introduces an online method to infer constraints from observing the safety-filtered actions of other agents. We approach the problem by using safety filters to ensure forward safety and exploit their structure to work backwards and infer constraints. We provide sufficient conditions under which we can infer these constraints and prove that our inference method converges. This constraint inference procedure is coupled with a decentralized planning method that ensures safety when the constraint activation distance is sufficiently large. We then empirically validate our method with Monte Carlo simulations and hardware experiments with quadruped robots. △ Less

Submitted 2 April, 2026; originally announced April 2026.

From Global to Local: Hierarchical Probabilistic Verification for Reachability Learning

Authors: Ebonye Smith, Sampada Deglurkar, Jingqi Li, Gechen Qu, Claire J. Tomlin

Abstract: Hamilton-Jacobi (HJ) reachability provides formal safety guarantees for nonlinear systems. However, it becomes computationally intractable in high-dimensional settings, motivating learning-based approximations that may introduce unsafe errors or overly optimistic safe sets. In this work, we propose a hierarchical probabilistic verification framework for reachability learning that bridges offline g… ▽ More Hamilton-Jacobi (HJ) reachability provides formal safety guarantees for nonlinear systems. However, it becomes computationally intractable in high-dimensional settings, motivating learning-based approximations that may introduce unsafe errors or overly optimistic safe sets. In this work, we propose a hierarchical probabilistic verification framework for reachability learning that bridges offline global certification and online local refinement. We first construct a coarse safe set using scenario optimization, providing an efficient global probabilistic certificate. We then introduce an online local refinement module that expands the certified safe set near its boundary by solving a sequence of convex programs, recovering regions excluded by the global verification. This refinement reduces conservatism while focusing computation on critical regions of the state space. We provide probabilistic safety guarantees for both the global and locally refined sets. Integrated with a switching mechanism between a learned reachability policy and a model-based controller, the proposed framework improves success rates in goal-reaching tasks with safety constraints, as demonstrated in simulation experiments of two drones racing to a goal with complex safety constraints. △ Less

Submitted 25 March, 2026; originally announced March 2026.

Comments: Submitted to the 65th IEEE Conference on Decision and Control (CDC 2026) and IEEE Control Systems Letters (L-CSS)

Active Calibration of Reachable Sets Using Approximate Pick-to-Learn

Authors: Sampada Deglurkar, Ebonye Smith, Jingqi Li, Claire J. Tomlin

Abstract: Reachability computations that rely on learned or estimated models require calibration in order to uphold confidence about their guarantees. Calibration generally involves sampling scenarios inside the reachable set. However, producing reasonable probabilistic guarantees may require many samples, which can be costly. To remedy this, we propose that calibration of reachable sets be performed using… ▽ More Reachability computations that rely on learned or estimated models require calibration in order to uphold confidence about their guarantees. Calibration generally involves sampling scenarios inside the reachable set. However, producing reasonable probabilistic guarantees may require many samples, which can be costly. To remedy this, we propose that calibration of reachable sets be performed using active learning strategies. In order to produce a probabilistic guarantee on the active learning, we adapt the Pick-to-Learn algorithm, which produces generalization bounds for standard supervised learning, to the active learning setting. Our method, Approximate Pick-to-Learn, treats the process of choosing data samples as maximizing an approximate error function. We can then use conformal prediction to ensure that the approximate error is close to the true model error. We demonstrate our technique for a simulated drone racing example in which learning is used to provide an initial guess of the reachable tube. Our method requires fewer samples to calibrate the model and provides more accurate sets than the baselines. We simultaneously provide tight generalization bounds. △ Less

Submitted 25 March, 2026; originally announced March 2026.

Comments: This paper has been submitted to the IEEE Control Systems Letters (L-CSS) jointly with the IEEE Conference on Decision and Control (CDC), with the addition of the crucial citation [3] and the code repo link

A Spectral Perspective on Stochastic Control Barrier Functions

Authors: Inkyu Jang, Chams E. Mballo, Claire J. Tomlin, H. Jin Kim

Abstract: Stochastic control barrier functions (SCBFs) provide a safety-critical control framework for systems subject to stochastic disturbances by bounding the probability of remaining within a safe set. However, synthesizing a valid SCBF that explicitly reflects the true safety probability of the system, which is the most natural measure of safety, remains a challenge. This paper addresses this issue by… ▽ More Stochastic control barrier functions (SCBFs) provide a safety-critical control framework for systems subject to stochastic disturbances by bounding the probability of remaining within a safe set. However, synthesizing a valid SCBF that explicitly reflects the true safety probability of the system, which is the most natural measure of safety, remains a challenge. This paper addresses this issue by adopting a spectral perspective, utilizing the linear operator that governs the evolution of the closed-loop system's safety probability. We find that the dominant eigenpair of this Koopman-like operator encodes fundamental safety information of the stochastic system. The dominant eigenfunction is a natural and valid SCBF, with values that explicitly quantify the relative long-term safety of the state, while the dominant eigenvalue indicates the global rate at which the safety probability decays. A practical synthesis algorithm is proposed, termed power-policy iteration, which jointly computes the dominant eigenpair and an optimized backup policy. The method is validated using simulation experiments on safety-critical dynamics models. △ Less

Submitted 20 March, 2026; originally announced March 2026.

Comments: 16 pages, 7 figures. This work has been submitted to the IEEE for possible publication

A Hamilton-Jacobi Reachability Framework with Soft Constraints for Safety-Critical Systems

Authors: Chams Eddine Mballo, Donggun Lee, Claire J. Tomlin

Abstract: Traditional reachability methods provide formal guarantees of safety under bounded disturbances. However, they strictly enforce state constraints as inviolable, which can result in overly conservative or infeasible solutions in complex operational scenarios. Many constraints encountered in practice, such as bounds on battery state of charge in electric vehicles, recommended speed envelopes, and co… ▽ More Traditional reachability methods provide formal guarantees of safety under bounded disturbances. However, they strictly enforce state constraints as inviolable, which can result in overly conservative or infeasible solutions in complex operational scenarios. Many constraints encountered in practice, such as bounds on battery state of charge in electric vehicles, recommended speed envelopes, and comfort constraints in passenger-carrying vehicles, are inherently soft. Soft constraints allow temporary violations within predefined safety margins to accommodate uncertainty and competing operational demands, albeit at a cost such as increased wear or higher operational expenses. This paper introduces a novel soft-constrained reachability framework that extends Hamilton-Jacobi reachability analysis for the formal verification of safety-critical systems subject to both hard and soft constraints. Specifically, the framework characterizes a subset of the state space, referred to as the soft-constrained reach-avoid set, from which the system is guaranteed to reach a desired set safely, under worst-case disturbances, while ensuring that cumulative soft-constraint violations remain within a user-specified budget. The framework comprises two principal components: (i) an augmented-state model with an auxiliary budget state that tracks soft-constraint violations, and (ii) a regularization-based approximation of the discontinuous Hamilton-Jacobi value function associated with the reach-avoid differential game studied herein. The effectiveness of the proposed framework is demonstrated through numerical examples involving the landing of a simple point-mass model and a fixed-wing aircraft executing an emergency descent, both under wind disturbances. The simulation results validate the framework's ability to simultaneously manage both hard and soft constraints in safety-critical settings △ Less

Submitted 28 October, 2025; originally announced October 2025.

Multi-Agent Guided Policy Search for Non-Cooperative Dynamic Games

Authors: Jingqi Li, Gechen Qu, Jason J. Choi, Somayeh Sojoudi, Claire Tomlin

Abstract: Multi-agent reinforcement learning (MARL) optimizes strategic interactions in non-cooperative dynamic games, where agents have misaligned objectives. However, data-driven methods such as multi-agent policy gradients (MA-PG) often suffer from instability and limit-cycle behaviors. Prior stabilization techniques typically rely on entropy-based exploration, which slows learning and increases variance… ▽ More Multi-agent reinforcement learning (MARL) optimizes strategic interactions in non-cooperative dynamic games, where agents have misaligned objectives. However, data-driven methods such as multi-agent policy gradients (MA-PG) often suffer from instability and limit-cycle behaviors. Prior stabilization techniques typically rely on entropy-based exploration, which slows learning and increases variance. We propose a model-based approach that incorporates approximate priors into the reward function as regularization. In linear quadratic (LQ) games, we prove that such priors stabilize policy gradients and guarantee local exponential convergence to an approximate Nash equilibrium. We then extend this idea to infinite-horizon nonlinear games by introducing Multi-agent Guided Policy Search (MA-GPS), which constructs short-horizon local LQ approximations from trajectories of current policies to guide training. Experiments on nonlinear vehicle platooning and a six-player strategic basketball formation show that MA-GPS achieves faster convergence and more stable learning than existing MARL methods. △ Less

Submitted 11 February, 2026; v1 submitted 28 September, 2025; originally announced September 2025.

Comments: This paper has been accepted for presentation at the IEEE American Control Conference (ACC) 2026. We sincerely appreciate the reviewers' valuable and constructive feedback. The latest version of the manuscript incorporates their suggestions, including additional clarifications of theoretical assumptions, convergence guarantees, and experimental details

EigenSafe: A Spectral Framework for Learning-Based Probabilistic Safety Assessment

Authors: Inkyu Jang, Jonghae Park, Sihyun Cho, Chams E. Mballo, Claire J. Tomlin, H. Jin Kim

Abstract: We present EigenSafe, an operator-theoretic framework for safety assessment of learning-enabled stochastic systems. In many robotic applications, the dynamics are inherently stochastic due to factors such as sensing noise and environmental disturbances, and it is challenging for conventional methods such as Hamilton-Jacobi reachability and control barrier functions to provide a well-calibrated saf… ▽ More We present EigenSafe, an operator-theoretic framework for safety assessment of learning-enabled stochastic systems. In many robotic applications, the dynamics are inherently stochastic due to factors such as sensing noise and environmental disturbances, and it is challenging for conventional methods such as Hamilton-Jacobi reachability and control barrier functions to provide a well-calibrated safety critic that is tied to the actual safety probability. We derive a linear operator that governs the dynamic programming principle for safety probability, and find that its dominant eigenpair provides critical safety information for both individual state-action pairs and the overall closed-loop system. The proposed framework learns this dominant eigenpair, which can be used to either inform or constrain policy updates. We demonstrate that the learned eigenpair effectively facilitates safe reinforcement learning. Further, we validate its applicability in enhancing the safety of learned policies from imitation learning through robot manipulation experiments using a UR3 robotic arm in a food preparation task. △ Less

Submitted 15 February, 2026; v1 submitted 22 September, 2025; originally announced September 2025.

Comments: Inkyu Jang and Jonghae Park contributed equally to this work. Project Webpage: https://eigen-safe.github.io/

When are safety filters safe? On minimum phase conditions of control barrier functions

Authors: Jason J. Choi, Claire J. Tomlin, Shankar Sastry, Koushil Sreenath

Abstract: In emerging control applications involving multiple and complex tasks, safety filters are gaining prominence as a modular approach to enforcing safety constraints. Among various methods, control barrier functions (CBFs) are widely used for designing safety filters due to their simplicity, imposing a single linear constraint on the control input at each state. In this work, we focus on the internal… ▽ More In emerging control applications involving multiple and complex tasks, safety filters are gaining prominence as a modular approach to enforcing safety constraints. Among various methods, control barrier functions (CBFs) are widely used for designing safety filters due to their simplicity, imposing a single linear constraint on the control input at each state. In this work, we focus on the internal dynamics of systems governed by CBF-constrained control laws. Our key observation is that, although CBFs guarantee safety by enforcing state constraints, they can inadvertently be "unsafe" by causing the internal state to diverge. We investigate the conditions under which the full system state, including the internal state, can remain bounded under a CBF-based safety filter. Drawing inspiration from the input-output linearization literature, where boundedness is ensured by minimum phase conditions, we propose a new set of CBF minimum phase conditions tailored to the structure imposed by the CBF constraint. A critical distinction from the original minimum phase conditions is that the internal dynamics in our setting is driven by a nonnegative virtual control input, which reflects the enforcement of the safety constraint. We include a range of numerical examples, including single-input, multi-input, linear, and nonlinear systems, validating both our analysis and the necessity of the proposed CBF minimum phase conditions. △ Less

Submitted 11 August, 2025; originally announced August 2025.

Comments: This work has been submitted to the IEEE for possible publication

Resolving Conflicting Constraints in Multi-Agent Reinforcement Learning with Layered Safety

Authors: Jason J. Choi, Jasmine Jerry Aloor, Jingqi Li, Maria G. Mendoza, Hamsa Balakrishnan, Claire J. Tomlin

Abstract: Preventing collisions in multi-robot navigation is crucial for deployment. This requirement hinders the use of learning-based approaches, such as multi-agent reinforcement learning (MARL), on their own due to their lack of safety guarantees. Traditional control methods, such as reachability and control barrier functions, can provide rigorous safety guarantees when interactions are limited only to… ▽ More Preventing collisions in multi-robot navigation is crucial for deployment. This requirement hinders the use of learning-based approaches, such as multi-agent reinforcement learning (MARL), on their own due to their lack of safety guarantees. Traditional control methods, such as reachability and control barrier functions, can provide rigorous safety guarantees when interactions are limited only to a small number of robots. However, conflicts between the constraints faced by different agents pose a challenge to safe multi-agent coordination. To overcome this challenge, we propose a method that integrates multiple layers of safety by combining MARL with safety filters. First, MARL is used to learn strategies that minimize multiple agent interactions, where multiple indicates more than two. Particularly, we focus on interactions likely to result in conflicting constraints within the engagement distance. Next, for agents that enter the engagement distance, we prioritize pairs requiring the most urgent corrective actions. Finally, a dedicated safety filter provides tactical corrective actions to resolve these conflicts. Crucially, the design decisions for all layers of this framework are grounded in reachability analysis and a control barrier-value function-based filtering mechanism. We validate our Layered Safe MARL framework in 1) hardware experiments using Crazyflie drones and 2) high-density advanced aerial mobility (AAM) operation scenarios, where agents navigate to designated waypoints while avoiding collisions. The results show that our method significantly reduces conflict while maintaining safety without sacrificing much efficiency (i.e., shorter travel time and distance) compared to baselines that do not incorporate layered safety. The project website is available at https://dinamo-mit.github.io/Layered-Safe-MARL/ △ Less

Submitted 4 May, 2025; originally announced May 2025.

Comments: Accepted for publication at the 2025 Robotics: Science and Systems Conference. 18 pages, 8 figures

Data-Driven Hamiltonian for Direct Construction of Safe Set from Trajectory Data

Authors: Jason J. Choi, Christopher A. Strong, Koushil Sreenath, Namhoon Cho, Claire J. Tomlin

Abstract: In continuous-time optimal control, evaluating the Hamiltonian requires solving a constrained optimization problem using the system's dynamics model. Hamilton-Jacobi reachability analysis for safety verification has demonstrated practical utility only when efficient evaluation of the Hamiltonian over a large state-time grid is possible. In this study, we introduce the concept of a data-driven Hami… ▽ More In continuous-time optimal control, evaluating the Hamiltonian requires solving a constrained optimization problem using the system's dynamics model. Hamilton-Jacobi reachability analysis for safety verification has demonstrated practical utility only when efficient evaluation of the Hamiltonian over a large state-time grid is possible. In this study, we introduce the concept of a data-driven Hamiltonian (DDH), which circumvents the need for an explicit dynamics model by relying only on mild prior knowledge (e.g., Lipschitz constants), thus enabling the construction of reachable sets directly from trajectory data. Recognizing that the Hamiltonian is the optimal inner product between a given costate and realizable state velocities, the DDH estimates the Hamiltonian using the worst-case realization of the velocity field based on the observed state trajectory data. This formulation ensures a conservative approximation of the true Hamiltonian for uncertain dynamics. The reachable set computed based on the DDH is also ensured to be a conservative approximation of the true reachable set. Next, we propose a data-efficient safe experiment framework for gradual expansion of safe sets using the DDH. This is achieved by iteratively conducting experiments within the computed data-driven safe set and updating the set using newly collected trajectory data. To demonstrate the capabilities of our approach, we showcase its effectiveness in safe flight envelope expansion for a tiltrotor vehicle transitioning from near-hover to forward flight. △ Less

Submitted 4 April, 2025; originally announced April 2025.

Comments: This is the extended version of the article submitted to IEEE CDC 2025. This work has been submitted to the IEEE for possible publication

System-Level Analysis of Module Uncertainty Quantification in the Autonomy Pipeline

Authors: Sampada Deglurkar, Haotian Shen, Anish Muthali, Marco Pavone, Dragos Margineantu, Peter Karkus, Boris Ivanovic, Claire J. Tomlin

Abstract: Modern autonomous systems with machine learning components often use uncertainty quantification to help produce assurances about system operation. However, there is a lack of consensus in the community on what uncertainty is and how to perform uncertainty quantification. In this work, we propose that uncertainty measures should be understood within the context of overall system design and operatio… ▽ More Modern autonomous systems with machine learning components often use uncertainty quantification to help produce assurances about system operation. However, there is a lack of consensus in the community on what uncertainty is and how to perform uncertainty quantification. In this work, we propose that uncertainty measures should be understood within the context of overall system design and operation. To this end, we present two novel analysis techniques. First, we produce a probabilistic specification on a module's uncertainty measure given a system specification. Second, we propose a method to measure a system's input-output robustness in order to compare system designs and quantify the impact of making a system uncertainty-aware. In addition to this theoretical work, we present the application of these analyses on two real-world autonomous systems: an autonomous driving system and an aircraft runway incursion detection system. We show that our analyses can determine desired relationships between module uncertainty and error, provide visualizations of how well an uncertainty measure is being used by a system, produce principled comparisons between different uncertainty measures and decision-making algorithm designs, and provide insights into system vulnerabilities and tradeoffs. △ Less

Submitted 25 January, 2026; v1 submitted 15 October, 2024; originally announced October 2024.

Comments: Previous version was a conference paper (Conference on Decision and Control, Dec 2024). This version is a journal submission (IEEE Transactions on Control Systems Technology). The title is the same but the text is entirely different and the content is significantly revised

Gait Switching and Enhanced Stabilization of Walking Robots with Deep Learning-based Reachability: A Case Study on Two-link Walker

Authors: Xingpeng Xia, Jason J. Choi, Ayush Agrawal, Koushil Sreenath, Claire J. Tomlin, Somil Bansal

Abstract: Learning-based approaches have recently shown notable success in legged locomotion. However, these approaches often lack accountability, necessitating empirical tests to determine their effectiveness. In this work, we are interested in designing a learning-based locomotion controller whose stability can be examined and guaranteed. This can be achieved by verifying regions of attraction (RoAs) of l… ▽ More Learning-based approaches have recently shown notable success in legged locomotion. However, these approaches often lack accountability, necessitating empirical tests to determine their effectiveness. In this work, we are interested in designing a learning-based locomotion controller whose stability can be examined and guaranteed. This can be achieved by verifying regions of attraction (RoAs) of legged robots to their stable walking gaits. This is a non-trivial problem for legged robots due to their hybrid dynamics. Although previous work has shown the utility of Hamilton-Jacobi (HJ) reachability to solve this problem, its practicality was limited by its poor scalability. The core contribution of our work is the employment of a deep learning-based HJ reachability solution to the hybrid legged robot dynamics, which overcomes the previous work's limitation. With the learned reachability solution, first, we can estimate a library of RoAs for various gaits. Second, we can design a one-step predictive controller that effectively stabilizes to an individual gait within the verified RoA. Finally, we can devise a strategy that switches gaits, in response to external perturbations, whose feasibility is guided by the RoA analysis. We demonstrate our method in a two-link walker simulation, whose mathematical model is well established. Our method achieves improved stability than previous model-based methods, while ensuring transparency that was not present in the existing learning-based approaches. △ Less

Submitted 10 September, 2024; originally announced September 2024.

Comments: The first two authors contributed equally. This work is supported in part by the NSF Grant CMMI-1944722, the NSF CAREER Program under award 2240163, the NASA ULI on Safe Aviation Autonomy, and the DARPA Assured Autonomy and Assured Neuro Symbolic Learning and Reasoning (ANSR) programs. The work of Jason J. Choi received the support of a fellowship from Kwanjeong Educational Foundation, Korea

Competency-Aware Planning for Probabilistically Safe Navigation Under Perception Uncertainty

Authors: Sara Pohland, Claire Tomlin

Abstract: 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… ▽ More 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 correctly 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 very valuable in enabling efficient navigation. △ Less

Submitted 26 July, 2025; v1 submitted 9 September, 2024; originally announced September 2024.

Journal ref: 2025 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

Certifiable Reachability Learning Using a New Lipschitz Continuous Value Function

Authors: Jingqi Li, Donggun Lee, Jaewon Lee, Kris Shengjun Dong, Somayeh Sojoudi, Claire Tomlin

Abstract: We propose a new reachability learning framework for high-dimensional nonlinear systems, focusing on reach-avoid problems. These problems require computing the reach-avoid set, which ensures that all its elements can safely reach a target set despite disturbances within pre-specified bounds. Our framework has two main parts: offline learning of a newly designed reachavoid value function, and post-… ▽ More We propose a new reachability learning framework for high-dimensional nonlinear systems, focusing on reach-avoid problems. These problems require computing the reach-avoid set, which ensures that all its elements can safely reach a target set despite disturbances within pre-specified bounds. Our framework has two main parts: offline learning of a newly designed reachavoid value function, and post-learning certification. Compared to prior work, our new value function is Lipschitz continuous and its associated Bellman operator is a contraction mapping, both of which improve the learning performance. To ensure deterministic guarantees of our learned reach-avoid set, we introduce two efficient post-learning certification methods. Both methods can be used online for real-time local certification or offline for comprehensive certification. We validate our framework in a 12-dimensional crazyflie drone racing hardware experiment and a simulated 10-dimensional highway take-over example. △ Less

Submitted 15 February, 2025; v1 submitted 14 August, 2024; originally announced August 2024.

Effects of dynamic power electronic load models on power systems analysis using ZIP-E loads

Authors: Gabriel E. Colon-Reyes, Reid Dye, Claire Tomlin, Duncan Callaway

Abstract: Power grids are seeing more devices connected at the load level in the form of power electronics: e.g., data centers, electric vehicle chargers, and battery storage facilities. Therefore it is necessary to perform power system analyses with load models that capture these loads' behavior, which has historically not been done. To this end, we propose ZIP-E loads, a composite load model that has a ZI… ▽ More Power grids are seeing more devices connected at the load level in the form of power electronics: e.g., data centers, electric vehicle chargers, and battery storage facilities. Therefore it is necessary to perform power system analyses with load models that capture these loads' behavior, which has historically not been done. To this end, we propose ZIP-E loads, a composite load model that has a ZIP load with a dynamic power electronic, or E, load model. We perform small signal and transient analysis of the IEEE WSCC 9 Bus test case with ZIP and ZIP-E load models. For small signals, we conclude that ZIP loads destabalize networks significantly faster than corresponding ZIP-E loads. In stable cases, transient results showed significantly larger oscillations for ZIP loads. Further, we find that a higher network loading condition is correlated with a higher sensitivity to load model choice. These results suggests that the constant power portion of the ZIP load has a large destabilizing effect and can generally overestimate instability, and that attention should be drawn to load model choice if operating near a stability boundary. △ Less

Submitted 17 July, 2024; originally announced July 2024.

Intent Demonstration in General-Sum Dynamic Games via Iterative Linear-Quadratic Approximations

Authors: Jingqi Li, Anand Siththaranjan, Somayeh Sojoudi, Claire Tomlin, Andrea Bajcsy

Abstract: Autonomous agents should coordinate effectively without prior knowledge of others' intents. While prior work has focused on intent inference, we address the inverse problem: how agents can strategically demonstrate their intents within general-sum dynamic games. We model this problem and propose an algorithm that balances intent demonstration with task performance. To handle nonlinear dynamic game… ▽ More Autonomous agents should coordinate effectively without prior knowledge of others' intents. While prior work has focused on intent inference, we address the inverse problem: how agents can strategically demonstrate their intents within general-sum dynamic games. We model this problem and propose an algorithm that balances intent demonstration with task performance. To handle nonlinear dynamic games with continuous state-action spaces, our method leverages iterative linear-quadratic game approximations and provides efficient intent-teaching guarantees: the uncertain agent's belief can be driven rapidly to the ground truth, while the demonstrating agent avoids expending effort on unnecessary belief alignment when it does not improve task performance. Theoretical analysis and hardware experiments confirm that our approach enables the demonstrating agent to reconcile task execution with belief alignment and strategically manage the information asymmetry among agents, even as its intent evolves during deployment. △ Less

Submitted 8 November, 2025; v1 submitted 15 February, 2024; originally announced February 2024.

The computation of approximate feedback Stackelberg equilibria in multi-player nonlinear constrained dynamic games

Authors: Jingqi Li, Somayeh Sojoudi, Claire Tomlin, David Fridovich-Keil

Abstract: Solving feedback Stackelberg games with nonlinear dynamics and coupled constraints, a common scenario in practice, presents significant challenges. This work introduces an efficient method for computing approximate local feedback Stackelberg equilibria in multi-player general-sum dynamic games, with continuous state and action spaces. Different from existing (approximate) dynamic programming solut… ▽ More Solving feedback Stackelberg games with nonlinear dynamics and coupled constraints, a common scenario in practice, presents significant challenges. This work introduces an efficient method for computing approximate local feedback Stackelberg equilibria in multi-player general-sum dynamic games, with continuous state and action spaces. Different from existing (approximate) dynamic programming solutions that are primarily designed for unconstrained problems, our approach involves reformulating a feedback Stackelberg dynamic game into a sequence of nested optimization problems, enabling the derivation of Karush-Kuhn-Tucker (KKT) conditions and the establishment of a second-order sufficient condition for local feedback Stackelberg equilibria. We propose a Newton-style primal-dual interior point method for solving constrained linear quadratic (LQ) feedback Stackelberg games, offering provable convergence guarantees. Our method is further extended to compute local feedback Stackelberg equilibria for more general nonlinear games by iteratively approximating them using LQ games, ensuring that their KKT conditions are locally aligned with those of the original nonlinear games. We prove the exponential convergence of our algorithm in constrained nonlinear games. In a feedback Stackelberg game with nonlinear dynamics and (nonconvex) coupled costs and constraints, our experimental results reveal the algorithm's ability to handle infeasible initial conditions and achieve exponential convergence towards an approximate local feedback Stackelberg equilibrium. △ Less

Submitted 2 April, 2025; v1 submitted 28 January, 2024; originally announced January 2024.

Comments: This manuscript has been accepted by SIAM Journal on Optimization. In this arxiv version, we fix a typo in equation (4.3), \ell_{T+1}(x_T) -> \ell_{T+1}(x_{T+1}), and a typo in equation (4.7), L_{T+1} -> L_T. All main results are unchanged

Hacking Predictors Means Hacking Cars: Using Sensitivity Analysis to Identify Trajectory Prediction Vulnerabilities for Autonomous Driving Security

Authors: Marsalis Gibson, David Babazadeh, Claire Tomlin, Shankar Sastry

Abstract: Adversarial attacks on learning-based multi-modal trajectory predictors have already been demonstrated. However, there are still open questions about the effects of perturbations on inputs other than state histories, and how these attacks impact downstream planning and control. In this paper, we conduct a sensitivity analysis on two trajectory prediction models, Trajectron++ and AgentFormer. The a… ▽ More Adversarial attacks on learning-based multi-modal trajectory predictors have already been demonstrated. However, there are still open questions about the effects of perturbations on inputs other than state histories, and how these attacks impact downstream planning and control. In this paper, we conduct a sensitivity analysis on two trajectory prediction models, Trajectron++ and AgentFormer. The analysis reveals that between all inputs, almost all of the perturbation sensitivities for both models lie only within the most recent position and velocity states. We additionally demonstrate that, despite dominant sensitivity on state history perturbations, an undetectable image map perturbation made with the Fast Gradient Sign Method can induce large prediction error increases in both models, revealing that these trajectory predictors are, in fact, susceptible to image-based attacks. Using an optimization-based planner and example perturbations crafted from sensitivity results, we show how these attacks can cause a vehicle to come to a sudden stop from moderate driving speeds. △ Less

Submitted 20 May, 2024; v1 submitted 18 January, 2024; originally announced January 2024.

Comments: 10 pages, 5 figures, 1 tables

Constraint-Guided Online Data Selection for Scalable Data-Driven Safety Filters in Uncertain Robotic Systems

Authors: Jason J. Choi, Fernando Castañeda, Wonsuhk Jung, Bike Zhang, Claire J. Tomlin, Koushil Sreenath

Abstract: 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… ▽ More 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. △ Less

Submitted 27 September, 2024; v1 submitted 23 November, 2023; originally announced November 2023.

Comments: The first three authors contributed equally to the work. This work has been submitted to the IEEE for possible publication

A Forward Reachability Perspective on Control Barrier Functions and Discount Factors in Reachability Analysis

Authors: Jason J. Choi, Donggun Lee, Boyang Li, Jonathan P. How, Koushil Sreenath, Sylvia L. Herbert, Claire J. Tomlin

Abstract: Control invariant sets are crucial for various methods that aim to design safe control policies for systems whose state constraints must be satisfied over an indefinite time horizon. In this article, we explore the connections among reachability, control invariance, and Control Barrier Functions (CBFs). Unlike prior formulations based on backward reachability concepts, we establish a strong link b… ▽ More Control invariant sets are crucial for various methods that aim to design safe control policies for systems whose state constraints must be satisfied over an indefinite time horizon. In this article, we explore the connections among reachability, control invariance, and Control Barrier Functions (CBFs). Unlike prior formulations based on backward reachability concepts, we establish a strong link between these three concepts by examining the inevitable Forward Reachable Tube (FRT), which is the set of states such that every trajectory reaching the FRT must have passed through a given initial set of states. First, our findings show that the inevitable FRT is a robust control invariant set if it has a continuously differentiable boundary. If the boundary is not differentiable, the FRT may lose invariance. We also show that any robust control invariant set including the initial set is a superset of the FRT if the boundary of the invariant set is differentiable. Next, we formulate a differential game between the control and disturbance, where the inevitable FRT is characterized by the zero-superlevel set of the value function. By incorporating a discount factor in the cost function of the game, the barrier constraint of the CBF naturally arises in the Hamilton-Jacobi (HJ) equation and determines the optimal policy. The resulting FRT value function serves as a CBF-like function, and conversely, any valid CBF is also a forward reachability value function. We further prove that any $C^1$ supersolution of the HJ equation for the FRT value functions is a valid CBF and characterizes a robust control invariant set that outer-approximates the FRT. Building on this property, finally, we devise a novel method that learns neural control barrier functions, which learn an control invariant superset of the FRT of a given initial set. △ Less

Submitted 15 March, 2026; v1 submitted 26 October, 2023; originally announced October 2023.

Comments: The first two authors contributed equally to this work

Safe Connectivity Maintenance of Underactuated Multi-Agent Networks in Dynamic Oceanic Environments

Authors: Nicolas Hoischen, Marius Wiggert, Claire J. Tomlin

Abstract: Autonomous multi-agent systems are increasingly being deployed in environments where winds and ocean currents have a significant influence. Recent work has developed control policies for single agents that leverage flows to achieve their objectives in dynamic environments. However, in multi-agent systems, these flows can cause agents to collide or drift apart and lose direct inter-agent communicat… ▽ More Autonomous multi-agent systems are increasingly being deployed in environments where winds and ocean currents have a significant influence. Recent work has developed control policies for single agents that leverage flows to achieve their objectives in dynamic environments. However, in multi-agent systems, these flows can cause agents to collide or drift apart and lose direct inter-agent communications, especially when agents have low propulsion capabilities. To address these challenges, we propose a hierarchical multi-agent control approach that allows arbitrary single-agent performance policies that are unaware of other agents to be used in multi-agent systems while ensuring safe operation. We first develop a safety controller using potential functions, solely dedicated to avoiding collisions and maintaining inter-agent communication. Next, we design a low-interference safe interaction (LISIC) policy that trades off the performance policy and the safety control to ensure safe and performant operation. Specifically, when the agents are at an appropriate distance, LISIC prioritizes the performance policy while smoothly increasing the safety controller when necessary. We prove that under mild assumptions on the flows experienced by the agents, our approach can guarantee safety. Additionally, we demonstrate the effectiveness of our method in realistic settings through an extensive empirical analysis with simulations of fleets of underactuated autonomous surface vehicles operating in dynamic ocean currents where these assumptions do not always hold. △ Less

Submitted 20 June, 2024; v1 submitted 4 July, 2023; originally announced July 2023.

Comments: 8 pages, Published at European Control Conference 2024 (ECC 2024) Nicolas Hoischen and Marius Wiggert contributed equally to this work

Stranding Risk for Underactuated Vessels in Complex Ocean Currents: Analysis and Controllers

Authors: Andreas Doering, Marius Wiggert, Hanna Krasowski, Manan Doshi, Pierre F. J. Lermusiaux, Claire J. Tomlin

Abstract: Low-propulsion vessels can take advantage of powerful ocean currents to navigate towards a destination. Recent results demonstrated that vessels can reach their destination with high probability despite forecast errors. However, these results do not consider the critical aspect of safety of such vessels: because of their low propulsion which is much smaller than the magnitude of currents, they mig… ▽ More Low-propulsion vessels can take advantage of powerful ocean currents to navigate towards a destination. Recent results demonstrated that vessels can reach their destination with high probability despite forecast errors. However, these results do not consider the critical aspect of safety of such vessels: because of their low propulsion which is much smaller than the magnitude of currents, they might end up in currents that inevitably push them into unsafe areas such as shallow areas, garbage patches, and shipping lanes. In this work, we first investigate the risk of stranding for free-floating vessels in the Northeast Pacific. We find that at least 5.04% would strand within 90 days. Next, we encode the unsafe sets as hard constraints into Hamilton-Jacobi Multi-Time Reachability (HJ-MTR) to synthesize a feedback policy that is equivalent to re-planning at each time step at low computational cost. While applying this policy closed-loop guarantees safe operation when the currents are known, in realistic situations only imperfect forecasts are available. We demonstrate the safety of our approach in such realistic situations empirically with large-scale simulations of a vessel navigating in high-risk regions in the Northeast Pacific. We find that applying our policy closed-loop with daily re-planning on new forecasts can ensure safety with high probability even under forecast errors that exceed the maximal propulsion. Our method significantly improves safety over the baselines and still achieves a timely arrival of the vessel at the destination. △ Less

Submitted 4 July, 2023; originally announced July 2023.

Comments: 6 pages, 3 figures, submitted to 2023 IEEE 62th Annual Conference on Decision and Control (CDC) Andreas Doering and Marius Wiggert contributed equally to this work

Maximizing Seaweed Growth on Autonomous Farms: A Dynamic Programming Approach for Underactuated Systems Navigating on Uncertain Ocean Currents

Authors: Matthias Killer, Marius Wiggert, Hanna Krasowski, Manan Doshi, Pierre F. J. Lermusiaux, Claire J. Tomlin

Abstract: Seaweed biomass presents a substantial opportunity for climate mitigation, yet to realize its potential, farming must be expanded to the vast open oceans. However, in the open ocean neither anchored farming nor floating farms with powerful engines are economically viable. Thus, a potential solution are farms that operate by going with the flow, utilizing minimal propulsion to strategically leverag… ▽ More Seaweed biomass presents a substantial opportunity for climate mitigation, yet to realize its potential, farming must be expanded to the vast open oceans. However, in the open ocean neither anchored farming nor floating farms with powerful engines are economically viable. Thus, a potential solution are farms that operate by going with the flow, utilizing minimal propulsion to strategically leverage beneficial ocean currents. In this work, we focus on low-power autonomous seaweed farms and design controllers that maximize seaweed growth by taking advantage of ocean currents. We first introduce a Dynamic Programming (DP) formulation to solve for the growth-optimal value function when the true currents are known. However, in reality only short-term imperfect forecasts with increasing uncertainty are available. Hence, we present three additional extensions. Firstly, we use frequent replanning to mitigate forecast errors. Second, to optimize for long-term growth, we extend the value function beyond the forecast horizon by estimating the expected future growth based on seasonal average currents. Lastly, we introduce a discounted finite-time DP formulation to account for the increasing uncertainty in future ocean current estimates. We empirically evaluate our approach with 30-day simulations of farms in realistic ocean conditions. Our method achieves 95.8\% of the best possible growth using only 5-day forecasts.This demonstrates that low-power propulsion is a promising method to operate autonomous seaweed farms in real-world conditions. △ Less

Submitted 4 June, 2025; v1 submitted 4 July, 2023; originally announced July 2023.

Comments: 8 pages, submitted to IEEE Robotics and Automation Letters (RA-L) Matthias Killer and Marius Wiggert contributed equally to this work

Scenario-Game ADMM: A Parallelized Scenario-Based Solver for Stochastic Noncooperative Games

Authors: Jingqi Li, Chih-Yuan Chiu, Lasse Peters, Fernando Palafox, Mustafa Karabag, Javier Alonso-Mora, Somayeh Sojoudi, Claire Tomlin, David Fridovich-Keil

Abstract: Decision-making in multi-player games can be extremely challenging, particularly under uncertainty. In this work, we propose a new sample-based approximation to a class of stochastic, general-sum, pure Nash games, where each player has an expected-value objective and a set of chance constraints. This new approximation scheme inherits the accuracy of objective approximation from the established sam… ▽ More Decision-making in multi-player games can be extremely challenging, particularly under uncertainty. In this work, we propose a new sample-based approximation to a class of stochastic, general-sum, pure Nash games, where each player has an expected-value objective and a set of chance constraints. This new approximation scheme inherits the accuracy of objective approximation from the established sample average approximation (SAA) method and enjoys a feasibility guarantee derived from the scenario optimization literature. We characterize the sample complexity of this new game-theoretic approximation scheme, and observe that high accuracy usually requires a large number of samples, which results in a large number of sampled constraints. To accommodate this, we decompose the approximated game into a set of smaller games with few constraints for each sampled scenario, and propose a decentralized, consensus-based ADMM algorithm to efficiently compute a generalized Nash equilibrium (GNE) of the approximated game. We prove the convergence of our algorithm to a GNE and empirically demonstrate superior performance relative to a recent baseline algorithm based on ADMM and interior point method. △ Less

Submitted 5 November, 2024; v1 submitted 4 April, 2023; originally announced April 2023.

Multi-Agent Reachability Calibration with Conformal Prediction

Authors: Anish Muthali, Haotian Shen, Sampada Deglurkar, Michael H. Lim, Rebecca Roelofs, Aleksandra Faust, Claire Tomlin

Abstract: We investigate methods to provide safety assurances for autonomous agents that incorporate predictions of other, uncontrolled agents' behavior into their own trajectory planning. Given a learning-based forecasting model that predicts agents' trajectories, we introduce a method for providing probabilistic assurances on the model's prediction error with calibrated confidence intervals. Through quant… ▽ More We investigate methods to provide safety assurances for autonomous agents that incorporate predictions of other, uncontrolled agents' behavior into their own trajectory planning. Given a learning-based forecasting model that predicts agents' trajectories, we introduce a method for providing probabilistic assurances on the model's prediction error with calibrated confidence intervals. Through quantile regression, conformal prediction, and reachability analysis, our method generates probabilistically safe and dynamically feasible prediction sets. We showcase their utility in certifying the safety of planning algorithms, both in simulations using actual autonomous driving data and in an experiment with Boeing vehicles. △ Less

Submitted 13 December, 2023; v1 submitted 1 April, 2023; originally announced April 2023.

Cost Inference for Feedback Dynamic Games from Noisy Partial State Observations and Incomplete Trajectories

Authors: Jingqi Li, Chih-Yuan Chiu, Lasse Peters, Somayeh Sojoudi, Claire Tomlin, David Fridovich-Keil

Abstract: In multi-agent dynamic games, the Nash equilibrium state trajectory of each agent is determined by its cost function and the information pattern of the game. However, the cost and trajectory of each agent may be unavailable to the other agents. Prior work on using partial observations to infer the costs in dynamic games assumes an open-loop information pattern. In this work, we demonstrate that th… ▽ More In multi-agent dynamic games, the Nash equilibrium state trajectory of each agent is determined by its cost function and the information pattern of the game. However, the cost and trajectory of each agent may be unavailable to the other agents. Prior work on using partial observations to infer the costs in dynamic games assumes an open-loop information pattern. In this work, we demonstrate that the feedback Nash equilibrium concept is more expressive and encodes more complex behavior. It is desirable to develop specific tools for inferring players' objectives in feedback games. Therefore, we consider the dynamic game cost inference problem under the feedback information pattern, using only partial state observations and incomplete trajectory data. To this end, we first propose an inverse feedback game loss function, whose minimizer yields a feedback Nash equilibrium state trajectory closest to the observation data. We characterize the landscape and differentiability of the loss function. Given the difficulty of obtaining the exact gradient, our main contribution is an efficient gradient approximator, which enables a novel inverse feedback game solver that minimizes the loss using first-order optimization. In thorough empirical evaluations, we demonstrate that our algorithm converges reliably and has better robustness and generalization performance than the open-loop baseline method when the observation data reflects a group of players acting in a feedback Nash game. △ Less

Submitted 3 January, 2023; originally announced January 2023.

Comments: Accepted by AAMAS 2023. This is a preprint version

Multi-Task Imitation Learning for Linear Dynamical Systems

Authors: Thomas T. Zhang, Katie Kang, Bruce D. Lee, Claire Tomlin, Sergey Levine, Stephen Tu, Nikolai Matni

Abstract: We study representation learning for efficient imitation learning over linear systems. In particular, we consider a setting where learning is split into two phases: (a) a pre-training step where a shared $k$-dimensional representation is learned from $H$ source policies, and (b) a target policy fine-tuning step where the learned representation is used to parameterize the policy class. We find that… ▽ More We study representation learning for efficient imitation learning over linear systems. In particular, we consider a setting where learning is split into two phases: (a) a pre-training step where a shared $k$-dimensional representation is learned from $H$ source policies, and (b) a target policy fine-tuning step where the learned representation is used to parameterize the policy class. We find that the imitation gap over trajectories generated by the learned target policy is bounded by $\tilde{O}\left( \frac{k n_x}{HN_{\mathrm{shared}}} + \frac{k n_u}{N_{\mathrm{target}}}\right)$, where $n_x > k$ is the state dimension, $n_u$ is the input dimension, $N_{\mathrm{shared}}$ denotes the total amount of data collected for each policy during representation learning, and $N_{\mathrm{target}}$ is the amount of target task data. This result formalizes the intuition that aggregating data across related tasks to learn a representation can significantly improve the sample efficiency of learning a target task. The trends suggested by this bound are corroborated in simulation. △ Less

Submitted 9 November, 2023; v1 submitted 30 November, 2022; originally announced December 2022.

Comments: Appeared in L4DC 2023. V3: corrected typo in assumptions

Optimality Guarantees for Particle Belief Approximation of POMDPs

Authors: Michael H. Lim, Tyler J. Becker, Mykel J. Kochenderfer, Claire J. Tomlin, Zachary N. Sunberg

Abstract: 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 w… ▽ More 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 $\mathcal{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. △ Less

Submitted 19 October, 2023; v1 submitted 10 October, 2022; originally announced October 2022.

Journal ref: Journal of Artificial Intelligence Research, 77, 1591-1636 (2023)

Recursively Feasible Probabilistic Safe Online Learning with Control Barrier Functions

Authors: Fernando Castañeda, Jason J. Choi, Wonsuhk Jung, Bike Zhang, Claire J. Tomlin, Koushil Sreenath

Abstract: Learning-based control has recently shown great efficacy in performing complex tasks for various applications. However, to deploy it in real systems, it is of vital importance to guarantee the system will stay safe. Control Barrier Functions (CBFs) offer mathematical tools for designing safety-preserving controllers for systems with known dynamics. In this article, we first introduce a model-uncer… ▽ More Learning-based control has recently shown great efficacy in performing complex tasks for various applications. However, to deploy it in real systems, it is of vital importance to guarantee the system will stay safe. Control Barrier Functions (CBFs) offer mathematical tools for designing safety-preserving controllers for systems with known dynamics. In this article, we first introduce a model-uncertainty-aware reformulation of CBF-based safety-critical controllers using Gaussian Process (GP) regression to close the gap between an approximate mathematical model and the real system, which results in a second-order cone program (SOCP)-based control design. We then present the pointwise feasibility conditions of the resulting safety controller, highlighting the level of richness that the available system information must meet to ensure safety. We use these conditions to devise an event-triggered online data collection strategy that ensures the recursive feasibility of the learned safety controller. Our method works by constantly reasoning about whether the current information is sufficient to ensure safety or if new measurements under active safe exploration are required to reduce the uncertainty. As a result, our proposed framework can guarantee the forward invariance of the safe set defined by the CBF with high probability, even if it contains a priori unexplored regions. We validate the proposed framework in two numerical simulation experiments. △ Less

Submitted 3 September, 2024; v1 submitted 23 August, 2022; originally announced August 2022.

Comments: Journal article. Includes the results of the 2021 CDC paper titled "Pointwise feasibility of gaussian process-based safety-critical control under model uncertainty" and proposes a recursively feasible safe online learning algorithm as new contribution

Lyapunov Density Models: Constraining Distribution Shift in Learning-Based Control

Authors: Katie Kang, Paula Gradu, Jason Choi, Michael Janner, Claire Tomlin, Sergey Levine

Abstract: 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 it was trained on. In co… ▽ More 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 it 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 work, 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 on an agent's ability to stay in-distribution over its entire trajectory. △ Less

Submitted 21 June, 2022; originally announced June 2022.

Navigation between initial and desired community states using shortcuts

Authors: Benjamin W. Blonder, Michael H. Lim, Zachary Sunberg, Claire Tomlin

Abstract: Ecological management problems often involve navigating from an initial to a desired community state. We ask whether navigation is possible without brute-force additions and deletions of species, using actions of varying costs: adding/deleting a small number of individuals of a species, changing the environment, and waiting. Navigation can yield direct paths (single sequence of actions) or shortcu… ▽ More Ecological management problems often involve navigating from an initial to a desired community state. We ask whether navigation is possible without brute-force additions and deletions of species, using actions of varying costs: adding/deleting a small number of individuals of a species, changing the environment, and waiting. Navigation can yield direct paths (single sequence of actions) or shortcut paths (multiple sequences of actions with lower cost than a direct path). We ask (1) when is non-brute-force navigation possible?; (2) do shortcuts exist and what are their properties?; and (3) what heuristics predict shortcut existence? Using several empirical datasets, we show that (1) non-brute-force navigation is only possible between some state pairs, (2) shortcuts exist between many state pairs; and (3) changes in abundance and richness are the strongest predictors of shortcut existence, independent of dataset and algorithm choices. State diagrams thus unveil hidden strategies for efficiently shifting between states. △ Less

Submitted 2 December, 2022; v1 submitted 15 April, 2022; originally announced April 2022.

Stability and Robustness of a Hybrid Control Law for the Half-bridge Inverter

Authors: Gabriel E. Colón-Reyes, Kaylene C. Stocking, Duncan S. Callaway, Claire J. Tomlin

Abstract: Hybrid systems combine both discrete and continuous state dynamics. Power electronic inverters are inherently hybrid systems: they are controlled via discrete-valued switching inputs which determine the evolution of the continuous-valued current and voltage state dynamics. Hybrid systems analysis could prove increasingly useful as large numbers of renewable energy sources are incorporated to the… ▽ More Hybrid systems combine both discrete and continuous state dynamics. Power electronic inverters are inherently hybrid systems: they are controlled via discrete-valued switching inputs which determine the evolution of the continuous-valued current and voltage state dynamics. Hybrid systems analysis could prove increasingly useful as large numbers of renewable energy sources are incorporated to the grid with inverters as their interface. In this work, we explore a hybrid systems approach for the stability analysis of power and power electronic systems. We provide an analytical proof showing that the use of a hybrid model for the half-bridge inverter allows the derivation of a control law that drives the system states to desired sinusoidal voltage and current references. We derive an analytical expression for a global Lyapunov function for the dynamical system in terms of the system parameters, which proves uniform, global, and asymptotic stability of the origin in error coordinates. Moreover, we demonstrate robustness to parameter changes through this Lyapunov function. We validate these results via simulation. Finally, we show empirically the incorporation of droop control with this hybrid systems approach. In the low-inertia grid community, the juxtaposition of droop control with the hybrid switching control can be considered a grid-forming control strategy using a switched inverter model. △ Less

Submitted 18 May, 2022; v1 submitted 15 April, 2022; originally announced April 2022.

On the Computational Consequences of Cost Function Design in Nonlinear Optimal Control

Authors: Tyler Westenbroek, Anand Siththaranjan, Mohsin Sarwari, Claire J. Tomlin, Shankar S. Sastry

Abstract: Optimal control is an essential tool for stabilizing complex nonlinear systems. However, despite the extensive impacts of methods such as receding horizon control, dynamic programming and reinforcement learning, the design of cost functions for a particular system often remains a heuristic-driven process of trial and error. In this paper we seek to gain insights into how the choice of cost functio… ▽ More Optimal control is an essential tool for stabilizing complex nonlinear systems. However, despite the extensive impacts of methods such as receding horizon control, dynamic programming and reinforcement learning, the design of cost functions for a particular system often remains a heuristic-driven process of trial and error. In this paper we seek to gain insights into how the choice of cost function interacts with the underlying structure of the control system and impacts the amount of computation required to obtain a stabilizing controller. We treat the cost design problem as a two-step process where the designer specifies outputs for the system that are to be penalized and then modulates the relative weighting of the inputs and the outputs in the cost. To characterize the computational burden associated to obtaining a stabilizing controller with a particular cost, we bound the prediction horizon required by receding horizon methods and the number of iterations required by dynamic programming methods to meet this requirement. Our theoretical results highlight a qualitative separation between what is possible, from a design perspective, when the chosen outputs induce either minimum-phase or non-minimum-phase behavior. Simulation studies indicate that this separation also holds for modern reinforcement learning methods. △ Less

Submitted 17 November, 2022; v1 submitted 5 April, 2022; originally announced April 2022.

Koopman-Based Neural Lyapunov Functions for General Attractors

Authors: Shankar A. Deka, Alonso M. Valle, Claire J. Tomlin

Abstract: Koopman spectral theory has grown in the past decade as a powerful tool for dynamical systems analysis and control. In this paper, we show how recent data-driven techniques for estimating Koopman-Invariant subspaces with neural networks can be leveraged to extract Lyapunov certificates for the underlying system. In our work, we specifically focus on systems with a limit-cycle, beyond just an isola… ▽ More Koopman spectral theory has grown in the past decade as a powerful tool for dynamical systems analysis and control. In this paper, we show how recent data-driven techniques for estimating Koopman-Invariant subspaces with neural networks can be leveraged to extract Lyapunov certificates for the underlying system. In our work, we specifically focus on systems with a limit-cycle, beyond just an isolated equilibrium point, and use Koopman eigenfunctions to efficiently parameterize candidate Lyapunov functions to construct forward-invariant sets under some (unknown) attractor dynamics. Additionally, when the dynamics are polynomial and when neural networks are replaced by polynomials as a choice of function approximators in our approach, one can further leverage Sum-of-Squares programs and/or nonlinear programs to yield provably correct Lyapunov certificates. In such a polynomial case, our Koopman-based approach for constructing Lyapunov functions uses significantly fewer decision variables compared to directly formulating and solving a Sum-of-Squares optimization problem. △ Less

Submitted 23 March, 2022; originally announced March 2022.

Comments: Submitted to CDC 2022

Infinite-Horizon Reach-Avoid Zero-Sum Games via Deep Reinforcement Learning

Authors: Jingqi Li, Donggun Lee, Somayeh Sojoudi, Claire J. Tomlin

Abstract: In this paper, we consider the infinite-horizon reach-avoid zero-sum game problem, where the goal is to find a set in the state space, referred to as the reach-avoid set, such that the system starting at a state therein could be controlled to reach a given target set without violating constraints under the worst-case disturbance. We address this problem by designing a new value function with a con… ▽ More In this paper, we consider the infinite-horizon reach-avoid zero-sum game problem, where the goal is to find a set in the state space, referred to as the reach-avoid set, such that the system starting at a state therein could be controlled to reach a given target set without violating constraints under the worst-case disturbance. We address this problem by designing a new value function with a contracting Bellman backup, where the super-zero level set, i.e., the set of states where the value function is evaluated to be non-negative, recovers the reach-avoid set. Building upon this, we prove that the proposed method can be adapted to compute the viability kernel, or the set of states which could be controlled to satisfy given constraints, and the backward reachable set, or the set of states that could be driven towards a given target set. Finally, we propose to alleviate the curse of dimensionality issue in high-dimensional problems by extending Conservative Q-Learning, a deep reinforcement learning technique, to learn a value function such that the super-zero level set of the learned value function serves as a (conservative) approximation to the reach-avoid set. Our theoretical and empirical results suggest that the proposed method could learn reliably the reach-avoid set and the optimal control policy even with neural network approximation. △ Less

Submitted 18 September, 2024; v1 submitted 18 March, 2022; originally announced March 2022.

Computation of Regions of Attraction for Hybrid Limit Cycles Using Reachability: An Application to Walking Robots

Authors: Jason J. Choi, Ayush Agrawal, Koushil Sreenath, Claire J. Tomlin, Somil Bansal

Abstract: Contact-rich robotic systems, such as legged robots and manipulators, are often represented as hybrid systems. However, the stability analysis and region-of-attraction computation for these systems are often challenging because of the discontinuous state changes upon contact (also referred to as state resets). In this work, we cast the computation of region-ofattraction as a Hamilton-Jacobi (HJ) r… ▽ More Contact-rich robotic systems, such as legged robots and manipulators, are often represented as hybrid systems. However, the stability analysis and region-of-attraction computation for these systems are often challenging because of the discontinuous state changes upon contact (also referred to as state resets). In this work, we cast the computation of region-ofattraction as a Hamilton-Jacobi (HJ) reachability problem. This enables us to leverage HJ reachability tools that are compatible with general nonlinear system dynamics, and can formally deal with state and input constraints as well as bounded disturbances. Our main contribution is the generalization of HJ reachability framework to account for the discontinuous state changes originating from state resets, which has remained a challenge until now. We apply our approach for computing region-of-attractions for several underactuated walking robots and demonstrate that the proposed approach can (a) recover a bigger region-of-attraction than state-of-the-art approaches, (b) handle state resets, nonlinear dynamics, external disturbances, and input constraints, and (c) also provides a stabilizing controller for the system that can leverage the state resets for enhancing system stability. △ Less

Submitted 8 February, 2022; v1 submitted 20 January, 2022; originally announced January 2022.

Comments: Accepted to IEEE RA-L & ICRA, 2022

Safety and Liveness Guarantees through Reach-Avoid Reinforcement Learning

Authors: Kai-Chieh Hsu, Vicenç Rubies-Royo, Claire J. Tomlin, Jaime F. Fisac

Abstract: Reach-avoid optimal control problems, in which the system must reach certain goal conditions while staying clear of unacceptable failure modes, are central to safety and liveness assurance for autonomous robotic systems, but their exact solutions are intractable for complex dynamics and environments. Recent successes in reinforcement learning methods to approximately solve optimal control problems… ▽ More Reach-avoid optimal control problems, in which the system must reach certain goal conditions while staying clear of unacceptable failure modes, are central to safety and liveness assurance for autonomous robotic systems, but their exact solutions are intractable for complex dynamics and environments. Recent successes in reinforcement learning methods to approximately solve optimal control problems with performance objectives make their application to certification problems attractive; however, the Lagrange-type objective used in reinforcement learning is not suitable to encode temporal logic requirements. Recent work has shown promise in extending the reinforcement learning machinery to safety-type problems, whose objective is not a sum, but a minimum (or maximum) over time. In this work, we generalize the reinforcement learning formulation to handle all optimal control problems in the reach-avoid category. We derive a time-discounted reach-avoid Bellman backup with contraction mapping properties and prove that the resulting reach-avoid Q-learning algorithm converges under analogous conditions to the traditional Lagrange-type problem, yielding an arbitrarily tight conservative approximation to the reach-avoid set. We further demonstrate the use of this formulation with deep reinforcement learning methods, retaining zero-violation guarantees by treating the approximate solutions as untrusted oracles in a model-predictive supervisory control framework. We evaluate our proposed framework on a range of nonlinear systems, validating the results against analytic and numerical solutions, and through Monte Carlo simulation in previously intractable problems. Our results open the door to a range of learning-based methods for safe-and-live autonomous behavior, with applications across robotics and automation. See https://github.com/SafeRoboticsLab/safety_rl for code and supplementary material. △ Less

Submitted 22 December, 2021; originally announced December 2021.

Comments: Accepted in Robotics: Science and Systems (RSS), 2021

Compositional Learning-based Planning for Vision POMDPs

Authors: Sampada Deglurkar, Michael H. Lim, Johnathan Tucker, Zachary N. Sunberg, Aleksandra Faust, Claire J. Tomlin

Abstract: The Partially Observable Markov Decision Process (POMDP) is a powerful framework for capturing decision-making problems that involve state and transition uncertainty. However, most current POMDP planners cannot effectively handle high-dimensional image observations prevalent in real world applications, and often require lengthy online training that requires interaction with the environment. In thi… ▽ More The Partially Observable Markov Decision Process (POMDP) is a powerful framework for capturing decision-making problems that involve state and transition uncertainty. However, most current POMDP planners cannot effectively handle high-dimensional image observations prevalent in real world applications, and often require lengthy online training that requires interaction with the environment. In this work, we propose Visual Tree Search (VTS), a compositional learning and planning procedure that combines generative models learned offline with online model-based POMDP planning. The deep generative observation models evaluate the likelihood of and predict future image observations in a Monte Carlo tree search planner. We show that VTS is robust to different types of image noises that were not present during training and can adapt to different reward structures without the need to re-train. This new approach significantly and stably outperforms several baseline state-of-the-art vision POMDP algorithms while using a fraction of the training time. △ Less

Submitted 2 December, 2022; v1 submitted 17 December, 2021; originally announced December 2021.

Incorporating Data Uncertainty in Object Tracking Algorithms

Authors: Anish Muthali, Forrest Laine, Claire Tomlin

Abstract: Methodologies for incorporating the uncertainties characteristic of data-driven object detectors into object tracking algorithms are explored. Object tracking methods rely on measurement error models, typically in the form of measurement noise, false positive rates, and missed detection rates. Each of these quantities, in general, can be dependent on object or measurement location. However, for de… ▽ More Methodologies for incorporating the uncertainties characteristic of data-driven object detectors into object tracking algorithms are explored. Object tracking methods rely on measurement error models, typically in the form of measurement noise, false positive rates, and missed detection rates. Each of these quantities, in general, can be dependent on object or measurement location. However, for detections generated from neural-network processed camera inputs, these measurement error statistics are not sufficient to represent the primary source of errors, namely a dissimilarity between run-time sensor input and the training data upon which the detector was trained. To this end, we investigate incorporating data uncertainty into object tracking methods such as to improve the ability to track objects, and particularly those which out-of-distribution w.r.t. training data. The proposed methodologies are validated on an object tracking benchmark as well on experiments with a real autonomous aircraft. △ Less

Submitted 2 November, 2021; v1 submitted 22 September, 2021; originally announced September 2021.

Comments: For associated video, see https://youtu.be/S21EvaAynRg

Towards cyber-physical systems robust to communication delays: A differential game approach

Authors: Shankar A. Deka, Donggun Lee, Claire J. Tomlin

Abstract: Collaboration between interconnected cyber-physical systems is becoming increasingly pervasive. Time-delays in communication channels between such systems are known to induce catastrophic failure modes, like high frequency oscillations in robotic manipulators in bilateral teleoperation or string instability in platoons of autonomous vehicles. This paper considers nonlinear time-delay systems repre… ▽ More Collaboration between interconnected cyber-physical systems is becoming increasingly pervasive. Time-delays in communication channels between such systems are known to induce catastrophic failure modes, like high frequency oscillations in robotic manipulators in bilateral teleoperation or string instability in platoons of autonomous vehicles. This paper considers nonlinear time-delay systems representing coupled robotic agents, and proposes controllers that are robust to time-varying communication delays. We introduce approximations that allow the delays to be considered as implicit control inputs themselves, and formulate the problem as a zero-sum differential game between the stabilizing controllers and the delays acting adversarially. The ensuing optimal control law is finally compared to known results from Lyapunov-Krasovskii based approaches via numerical experiments. △ Less

Submitted 21 September, 2021; originally announced September 2021.

Comments: 7 pages, 5 figures, Submitted to IEEE Control Systems Letters

MSC Class: 34K35; 49L12; 93D21

Multi-Task Learning with Sequence-Conditioned Transporter Networks

Authors: Michael H. Lim, Andy Zeng, Brian Ichter, Maryam Bandari, Erwin Coumans, Claire Tomlin, Stefan Schaal, Aleksandra Faust

Abstract: 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 be… ▽ More 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. △ Less

Submitted 15 September, 2021; originally announced September 2021.

Discretizing Dynamics for Maximum Likelihood Constraint Inference

Authors: Kaylene C. Stocking, David L. McPherson, Robert P. Matthew, Claire J. Tomlin

Abstract: Maximum likelihood constraint inference is a powerful technique for identifying unmodeled constraints that affect the behavior of a demonstrator acting under a known objective function. However, it was originally formulated only for discrete state-action spaces. Continuous dynamics are more useful for modeling many real-world systems of interest, including the movements of humans and robots. We pr… ▽ More Maximum likelihood constraint inference is a powerful technique for identifying unmodeled constraints that affect the behavior of a demonstrator acting under a known objective function. However, it was originally formulated only for discrete state-action spaces. Continuous dynamics are more useful for modeling many real-world systems of interest, including the movements of humans and robots. We present a method to generate a tabular state-action space that approximates continuous dynamics and can be used for constraint inference on demonstrations that obey the true system dynamics. We then demonstrate accurate constraint inference on nonlinear pendulum systems with 2- and 4-dimensional state spaces, and show that performance is robust to a range of hyperparameters. The demonstrations are not required to be fully optimal with respect to the objective, and the most likely constraints can be identified even when demonstrations cover only a small portion of the state space. For these reasons, the proposed approach may be especially useful for inferring constraints on human demonstrators, which has important applications in human-robot interaction and biomechanical medicine. △ Less

Submitted 10 September, 2021; originally announced September 2021.

Comments: 10 pages, 7 figures

Lax Formulae for Efficiently Solving Two Classes of State-Constrained Optimal Control Problems

Authors: Donggun Lee, Claire J. Tomlin

Abstract: This paper presents Lax formulae for solving the following optimal control problems: minimize the maximum (or the minimum) cost over a time horizon, while satisfying a state constraint. We present a viscosity theory, and by applying the theory to the Hamilton-Jacobi (HJ) equations, these Lax formulae are derived. A numerical algorithm for the Lax formulae is presented: under certain conditions, th… ▽ More This paper presents Lax formulae for solving the following optimal control problems: minimize the maximum (or the minimum) cost over a time horizon, while satisfying a state constraint. We present a viscosity theory, and by applying the theory to the Hamilton-Jacobi (HJ) equations, these Lax formulae are derived. A numerical algorithm for the Lax formulae is presented: under certain conditions, this algorithm's computational complexity is polynomial in the dimension of the state. For each class of optimal control problem, an example demonstrates the use and performance of the Lax formulae. △ Less

Submitted 31 August, 2021; originally announced September 2021.

Hamilton-Jacobi Equations for Two Classes of State-Constrained Zero-Sum Games

Authors: Donggun Lee, Claire J. Tomlin

Abstract: This paper presents Hamilton-Jacobi (HJ) formulations for two classes of two-player zero-sum games: one with a maximum cost value over time, and one with a minimum cost value over time. In the zero-sum game setting, player A minimizes the given cost while satisfying state constraints, and player B wants to prevent player A's success. For each class of problems, this paper presents two HJ equations… ▽ More This paper presents Hamilton-Jacobi (HJ) formulations for two classes of two-player zero-sum games: one with a maximum cost value over time, and one with a minimum cost value over time. In the zero-sum game setting, player A minimizes the given cost while satisfying state constraints, and player B wants to prevent player A's success. For each class of problems, this paper presents two HJ equations: one for time-varying dynamics, cost, and state constraint; the other for time-invariant dynamics, cost, and state constraint. Utilizing the HJ equations, the optimal control for each player is analyzed, and a numerical algorithm is presented to compute the solution to the HJ equations. A two-dimensional water system is introduced as an example to demonstrate the proposed HJ framework. △ Less

Submitted 28 June, 2021; originally announced June 2021.

A Computationally Efficient Hamilton-Jacobi-based Formula for State-Constrained Optimal Control Problems

Authors: Donggun Lee, Claire J. Tomlin

Abstract: This paper investigates a Hamilton-Jacobi (HJ) analysis to solve finite-horizon optimal control problems for high-dimensional systems. Although grid-based methods, such as the level-set method [1], numerically solve a general class of HJ partial differential equations, the computational complexity is exponential in the dimension of the continuous state. To manage this computational complexity, met… ▽ More This paper investigates a Hamilton-Jacobi (HJ) analysis to solve finite-horizon optimal control problems for high-dimensional systems. Although grid-based methods, such as the level-set method [1], numerically solve a general class of HJ partial differential equations, the computational complexity is exponential in the dimension of the continuous state. To manage this computational complexity, methods based on Lax-Hopf theory have been developed for the state-unconstrained optimal control problem under certain assumptions, such as affine dynamics and state-independent stage cost. Based on the Lax formula [2], this paper proposes an HJ formula for the state-constrained optimal control problem for nonlinear systems. We call this formula \textit{the generalized Lax formula} for the optimal control problem. The HJ formula provides both the optimal cost and an optimal control signal. We also provide an efficient computational method for a class of problems for which the dynamics is affine in the state, and for which the stage and terminal cost, as well as the state constraints, are convex in the state. This class of problems does not require affine dynamics and convex stage cost in the control. This paper also provides three practical examples. △ Less

Submitted 25 June, 2021; originally announced June 2021.

Pointwise Feasibility of Gaussian Process-based Safety-Critical Control under Model Uncertainty

Authors: Fernando Castañeda, Jason J. Choi, Bike Zhang, Claire J. Tomlin, Koushil Sreenath

Abstract: Control Barrier Functions (CBFs) and Control Lyapunov Functions (CLFs) are popular tools for enforcing safety and stability of a controlled system, respectively. They are commonly utilized to build constraints that can be incorporated in a min-norm quadratic program (CBF-CLF-QP) which solves for a safety-critical control input. However, since these constraints rely on a model of the system, when t… ▽ More Control Barrier Functions (CBFs) and Control Lyapunov Functions (CLFs) are popular tools for enforcing safety and stability of a controlled system, respectively. They are commonly utilized to build constraints that can be incorporated in a min-norm quadratic program (CBF-CLF-QP) which solves for a safety-critical control input. However, since these constraints rely on a model of the system, when this model is inaccurate the guarantees of safety and stability can be easily lost. In this paper, we present a Gaussian Process (GP)-based approach to tackle the problem of model uncertainty in safety-critical controllers that use CBFs and CLFs. The considered model uncertainty is affected by both state and control input. We derive probabilistic bounds on the effects that such model uncertainty has on the dynamics of the CBF and CLF. We then use these bounds to build safety and stability chance constraints that can be incorporated in a min-norm convex optimization-based controller, called GP-CBF-CLF-SOCP. As the main theoretical result of the paper, we present necessary and sufficient conditions for pointwise feasibility of the proposed optimization problem. We believe that these conditions could serve as a starting point towards understanding what are the minimal requirements on the distribution of data collected from the real system in order to guarantee safety. Finally, we validate the proposed framework with numerical simulations of an adaptive cruise controller for an automotive system. △ Less

Submitted 1 October, 2021; v1 submitted 13 June, 2021; originally announced June 2021.

Comments: The first two authors contributed equally. Accepted for publication in IEEE 60th Conference on Decision and Control (CDC 2021)

Robust Control Barrier-Value Functions for Safety-Critical Control

Authors: Jason J. Choi, Donggun Lee, Koushil Sreenath, Claire J. Tomlin, Sylvia L. Herbert

Abstract: This paper works towards unifying two popular approaches in the safety control community: Hamilton-Jacobi (HJ) reachability and Control Barrier Functions (CBFs). HJ Reachability has methods for direct construction of value functions that provide safety guarantees and safe controllers, however the online implementation can be overly conservative and/or rely on chattering bang-bang control. The CBF… ▽ More This paper works towards unifying two popular approaches in the safety control community: Hamilton-Jacobi (HJ) reachability and Control Barrier Functions (CBFs). HJ Reachability has methods for direct construction of value functions that provide safety guarantees and safe controllers, however the online implementation can be overly conservative and/or rely on chattering bang-bang control. The CBF community has methods for safe-guarding controllers in the form of point-wise optimization using quadratic programs (CBF-QP), where the CBF-based safety certificate is used as a constraint. However, finding a valid CBF for a general dynamical system is challenging. This paper unifies these two methods by introducing a new reachability formulation inspired by the structure of CBFs to construct a Control Barrier-Value Function (CBVF). We verify that CBVF is a viscosity solution to a novel Hamilton-Jacobi-Isaacs Variational Inequality and preserves the same safety guarantee as the original reachability formulation. Finally, inspired by the CBF-QP, we propose a QP-based online control synthesis for systems affine in control and disturbance, whose solution is always the CBVF's optimal control signal robust to bounded disturbance. We demonstrate the benefit of using the CBVFs for double-integrator and Dubins car systems by comparing it to previous methods. △ Less

Submitted 25 October, 2021; v1 submitted 6 April, 2021; originally announced April 2021.

Comments: IEEE CDC 2021