This paper presents a technique, named STLCG, to compute the quantitative semantics of Signal Temporal Logic (STL) formulas using computation graphs. STLCG provides a platform which enables the incorporation of logical specifications into robotics problems that benefit from gradient-based solutions. Specifically, STL is a powerful and expressive formal language that can specify spatial and temporal properties of signals generated by both continuous and hybrid systems. The quantitative semantics of STL provide a robustness metric, i.e., how much a signal satisfies or violates an STL specification. In this work, we devise a systematic methodology for translating STL robustness formulas into computation graphs. With this representation, and by leveraging off-the-shelf automatic differentiation tools, we are able to efficiently backpropagate through STL robustness formulas and hence enable a natural and easy-to-use integration of STL specifications with many gradient-based approaches used in robotics. Through a number of examples stemming from various robotics applications, we demonstrate that STLCG is versatile, computationally efficient, and capable of incorporating human-domain knowledge into the problem formulation.
Towards the Unification and Data-Driven Synthesis of Autonomous Vehicle Safety Concepts
As safety-critical autonomous vehicles (AVs) will soon become pervasive in our society, a number of safety concepts for trusted AV deployment have been recently proposed throughout industry and academia. Yet, agreeing upon an "appropriate" safety concept is still an elusive task. In this paper, we advocate for the use of Hamilton Jacobi (HJ) reachability as a unifying mathematical framework for comparing existing safety concepts, and propose ways to expand its modeling premises in a data-driven fashion. Specifically, we show that (i) existing predominant safety concepts can be embedded in the HJ reachability framework, thereby enabling a common language for comparing and contrasting modeling assumptions, and (ii) HJ reachability can serve as an inductive bias to effectively reason, in a data-driven context, about two critical, yet often overlooked aspects of safety: responsibility and context-dependency.
2021
Multimodal Deep Generative Models for Trajectory Prediction: A Conditional Variational Autoencoder Approach
Human behavior prediction models enable robots to anticipate how humans may react to their actions, and hence are instrumental to devising safe and proactive robot planning algorithms. However, modeling complex interaction dynamics and capturing the possibility of many possible outcomes in such interactive settings is very challenging, which has recently prompted the study of several different approaches. In this work, we provide a self-contained tutorial on a conditional variational autoencoder (CVAE) approach to human behavior prediction which, at its core, can produce a multimodal probability distribution over future human trajectories conditioned on past interactions and candidate robot future actions. Specifically, the goals of this tutorial paper are to review and build a taxonomy of state-of-the-art methods in human behavior prediction, from physics-based to purely data-driven methods, provide a rigorous yet easily accessible description of a data-driven, CVAE-based approach, highlight important design characteristics that make this an attractive model to use in the context of model-based planning for human-robot interactions, and provide important design considerations when using this class of models.
@article{IvanovicLeungEtAl2020,bibtex_show={true},author={Ivanovic, B.* and Leung, K.* and Schmerling, E. and Pavone, M.},title={Multimodal Deep Generative Models for Trajectory Prediction: A Conditional Variational Autoencoder Approach},journal={{IEEE Robotics and Automation Letters}},volume={6},number={2},pages={295--302},year={2021},note={In Press},arxiv={2008.03880},keywords={Journal},img={IvanovicLeungEtAl2020.jpg},selected={true}}
Leveraging Neural Network Gradients within Trajectory Optimization for Proactive Human-Robot Interactions
To achieve seamless human-robot interactions, robots need to intimately reason about complex interaction dynamics and future human behaviors within their motion planning process. However, there is a disconnect between state-of-the-art neural network-based human behavior models and robot motion planners—either the behavior models are limited in their consideration of downstream planning or a simplified behavior model is used to ensure tractability of the planning problem. In this work, we present a framework that fuses together the interpretability and flexibility of trajectory optimization (TO) with the predictive power of state-of-the-art human trajectory prediction models. In particular, we leverage gradient information from data-driven prediction models to explicitly reason about human-robot interaction dynamics within a gradient-based TO problem. We demonstrate the efficacy of our approach in a multi-agent scenario whereby a robot is required to safely and efficiently navigate through a crowd of up to ten pedestrians. We compare against a variety of planning methods, and show that by explicitly accounting for interaction dynamics within the planner, our method offers safer and more efficient behaviors, even yielding proactive and nuanced behaviors such as waiting for a pedestrian to pass before moving.
@inproceedings{SchaeferLeungEtAl2021,bibtex_show={true},author={Schaefer, S. and Leung, K. and Ivanovic, B. and Pavone, M.},title={Leveraging Neural Network Gradients within Trajectory Optimization for Proactive Human-Robot Interactions},booktitle={{Proc.\ IEEE Conf.\ on Robotics and Automation}},year={2021},arxiv={2012.01027},keywords={Conference},img={SchaeferLeungEtAl2021.jpeg}}
2020
On Infusing Reachability-Based Safety Assurance within Planning Frameworks for Human-Robot Vehicle Interactions
Action anticipation, intent prediction, and proactive behavior are all desirable characteristics for autonomous driving policies in interactive scenarios. Paramount, however, is ensuring safety on the road—a key challenge in doing so is accounting for uncertainty in human driver actions without unduly impacting planner performance. This paper introduces a minimally-interventional safety controller operating within an autonomous vehicle control stack with the role of ensuring collision-free interaction with an externally controlled (e.g., human-driven) counterpart while respecting static obstacles such as a road boundary wall. We leverage reachability analysis to construct a real-time (100Hz) controller that serves the dual role of (1) tracking an input trajectory from a higher-level planning algorithm using model predictive control, and (2) assuring safety through maintaining the availability of a collision-free escape maneuver as a persistent constraint regardless of whatever future actions the other car takes. A full-scale steer-by-wire platform is used to conduct traffic weaving experiments wherein two cars, initially side-by-side, must swap lanes in a limited amount of time and distance, emulating cars merging onto/off of a highway. We demonstrate that, with our control stack, the autonomous vehicle is able to avoid collision even when the other car defies the planner’s expectations and takes dangerous actions, either carelessly or with the intent to collide, and otherwise deviates minimally from the planned trajectory to the extent required to maintain safety.
@article{LeungSchmerlingEtAl2020,bibtex_show={true},author={Leung, K. and Schmerling, E. and Zhang, M. and Chen, M. and Talbot, J. and Gerdes, J. C. and Pavone, M.},title={On Infusing Reachability-Based Safety Assurance within Planning Frameworks for Human-Robot Vehicle Interactions},journal={{Int.\ Journal of Robotics Research}},year={2020},volume={39},issue={10--11},pages={1326--1345},arxiv={2012.03390},keywords={Journal},img={LeungSchmerlingEtAl2020.png},selected={true}}
Infusing Reachability-Based Safety into Planning and Control for Multi-agent Interactions
Within a robot autonomy stack, the planner and controller are typically designed separately, and serve different purposes. As such, there is often a diffusion of responsibilities when it comes to ensuring safety for the robot. We propose that a planner and controller should share the same interpretation of safety but apply this knowledge in a different yet complementary way. To achieve this, we use Hamilton-Jacobi (HJ) reachability theory at the planning level to provide the robot planner with the foresight to avoid entering regions with possible inevitable collision. However, this alone does not guarantee safety. In conjunction with this HJ reachability-infused planner, we propose a minimally-interventional multi-agent safety-preserving controller also derived via HJ-reachability theory. The safety controller maintains safety for the robot without unduly impacting planner performance. We demonstrate the benefits of our proposed approach in a multi-agent highway scenario where a robot car is rewarded to navigate through traffic as fast as possible, and we show that our approach provides strong safety assurances yet achieves the highest performance compared to other safety controllers.
@inproceedings{WangLeungEtAl2020,bibtex_show={true},author={Wang, X.* and Leung, K.* and Pavone, M.},title={Infusing Reachability-Based Safety into Planning and Control for Multi-agent Interactions},booktitle={{IEEE/RSJ Int.\ Conf.\ on Intelligent Robots \& Systems}},year={2020},url={https://arxiv.org/pdf/2008.00067.pdf},arxiv={2008.00067},keywords={Conference},img={WangLeungEtAl2020.png}}
Back-propagation through signal temporal logic specifications: Infusing logical structure into gradient-based methods
This paper presents a technique, named stlcg, to compute the quantitative semantics of Signal Temporal Logic (STL) formulas using computation graphs. This provides a platform which enables the incorporation of logic-based specifications into robotics problems that benefit from gradient-based solutions. Specifically, STL is a powerful and expressive formal language that can specify spatial and temporal properties of signals generated by both continuous and hybrid systems. The quantitative semantics of STL provide a robustness metric, i.e., how much a signal satisfies or violates an STL specification. In this work we devise a systematic methodology for translating STL robustness formulas into computation graphs. With this representation, and by leveraging off-the-shelf auto-differentiation tools, we are able to back-propagate through STL robustness formulas and hence enable a natural and easy-to-use integration with many gradient-based approaches used in robotics. We demonstrate, through examples stemming from various robotics applications, that the technique is versatile, computationally efficient, and capable of injecting human-domain knowledge into the problem formulation.
@inproceedings{LeungArechigaEtAl2020,bibtex_show={true},author={Leung, K. and Ar\'{e}chiga, N. and Pavone, M.},title={Back-propagation through signal temporal logic specifications: Infusing logical structure into gradient-based methods},booktitle={{Workshop on Algorithmic Foundations of Robotics}},year={2020},url={2008.00097},keywords={Conference},img={LeungArechigaEtAl2020.png},selected={true}}
Interpretable Policies from Formally-Specified Temporal Properties
We present an approach for interpreting parameterized policies based on a formally-specified abstract description of the importance of certain behaviors or observed outcomes of a policy. The standard way to deploy data-driven policies usually involves sampling from the set of outcomes produced by the policy. Our approach leverages parametric signal temporal logic (pSTL) formulas to construct an interpretable view on the modeling parameters via a sequence of variational inference problems; one to solve for the pSTL parameters and another to construct a new parameterization satisfying the specification. We perform clustering using a finite set of examples, either real or simulated, and combine computational graph learning and normalizing flows to form a relationship between these parameters and pSTL formulas either derived by hand or inferred from data. We illustrate the utility of our approach to model selection for validation of the safety properties of an autonomous driving system, using a learned generative model of the surrounding agents.
@inproceedings{DeCastroLeungEtAl2020,bibtex_show={true},author={DeCastro, J. and Leung, K. and Ar\'{e}chiga, N. and Pavone, M.},title={Interpretable Policies from Formally-Specified Temporal Properties},booktitle={{Proc.\ IEEE Int.\ Conf.\ on Intelligent Transportation Systems}},year={2020},pdf={papers/DeCastro.Leung.ea.ITSC20.pdf},keywords={Conference},img={DeCastroLeungEtAl2020.png}}
Signal Temporal Logic (STL) is an expressive language used to describe logical and temporal properties of signals, both continuous and discrete. Inferring STL formulas from behavior traces can provide powerful insights into complex systems. These insights can help system designers better understand and improve the systems they develop (e.g., long-term behaviors of time series data), yet this is a very challenging and often intractable problem. This work presents a method for evaluating STL formulas using computation graphs, hence bridging a connection between STL and many modern machine learning frameworks that depend on computation graphs, such as deep learning. We show that this approach is particularly effective for solving parameteric STL (pSTL) problems, the problem of parameter fitting for a given signal. We provide a relaxation technique that makes this method more tractable when solving general pSTL formulas. By using computation graphs, we can leverage the benefits and the computational prowess of modern day machine learning tools. Motivated by the problem of learning explanatory factors and safety assurance for complex cyber-physical systems, we demonstrate our proposed method on an autonomous driving case study.
@inproceedings{LeungArechigaEtAl2019,bibtex_show={true},author={Leung, K. and Ar\'{e}chiga, N. and Pavone, M.},title={Backpropagation for Parametric {STL}},booktitle={{IEEE Intelligent Vehicles Symposium: Workshop on Unsupervised Learning for Automated Driving}},year={2019},pdf={papers/Leung.Arechiga.ea.ULAD19.pdf},keywords={Workshop},img={LeungArechigaEtAl2019.png}}
2018
Multimodal Probabilistic Model-Based Planning for Human-Robot Interaction
This paper presents a method for constructing human-robot interaction policies in settings where multimodality, i.e., the possibility of multiple highly distinct futures, plays a critical role in decision making. We are motivated in this work by the example of traffic weaving, e.g., at highway onramps/offramps, where entering and exiting cars must swap lanes in a short distance — a challenging negotiation even for experienced drivers due to the inherent multimodal uncertainty of who will pass whom. Our approach is to learn multimodal probability distributions over future human actions from a dataset of human-human exemplars and perform real-time robot policy construction in the resulting environment model through massively parallel sampling of human responses to candidate robot action sequences. Direct learning of these distributions is made possible by recent advances in the theory of conditional variational autoencoders (CVAEs), whereby we learn action distributions simultaneously conditioned on the present interaction history, as well as candidate future robot actions in order to take into account response dynamics. We demonstrate the efficacy of this approach with a human-in-the-loop simulation of a traffic weaving scenario.
@inproceedings{SchmerlingLeungEtAl2018,bibtex_show={true},author={Schmerling, E. and Leung, K. and Vollprecht, W. and Pavone, M.},title={Multimodal Probabilistic Model-Based Planning for Human-Robot Interaction},booktitle={{Proc.\ IEEE Conf.\ on Robotics and Automation}},year={2018},arxiv={1710.09483},keywords={Conference},img={SchmerlingLeungEtAl2018.png}}
Generative Modeling of Multimodal Multi-Human Behavior
This work presents a methodology for modeling and predicting human behavior in settings with N humans interacting in highly multimodal scenarios (i.e. where there are many possible highly-distinct futures). A motivating example includes robots interacting with humans in crowded environments, such as self-driving cars operating alongside human-driven vehicles or human-robot collaborative bin packing in a warehouse. Our approach to model human behavior in such uncertain environments is to model humans in the scene as nodes in a graphical model, with edges encoding relationships between them. For each human, we learn a multimodal probability distribution over future actions from a dataset of multi-human interactions. Learning such distributions is made possible by recent advances in the theory of conditional variational autoencoders and deep learning approximations of probabilistic graphical models. Specifically, we learn action distributions conditioned on interaction history, neighboring human behavior, and candidate future agent behavior in order to take into account response dynamics. We demonstrate the performance of such a modeling approach in modeling basketball player trajectories, a highly multimodal, multi-human scenario which serves as a proxy for many robotic applications.
@inproceedings{IvanovicSchmerlingEtAl2018,bibtex_show={true},author={Ivanovic, B. and Schmerling, E. and Leung, K. and Pavone, M.},title={Generative Modeling of Multimodal Multi-Human Behavior},booktitle={{IEEE/RSJ Int.\ Conf.\ on Intelligent Robots \& Systems}},year={2018},arxiv={1803.02015},keywords={Conference},img={IvanovicSchmerlingEtAl2018.png}}
On Infusing Reachability-Based Safety Assurance within Probabilistic Planning Frameworks for Human-Robot Vehicle Interactions
Action anticipation, intent prediction, and proactive behavior are all desirable characteristics for autonomous driving policies in interactive scenarios. Paramount, however, is ensuring safety on the road — a key challenge in doing so is accounting for uncertainty in human driver actions without unduly impacting planner performance. This paper introduces a minimally-interventional safety controller operating within an autonomous vehicle control stack with the role of ensuring collision-free interaction with an externally controlled (e.g., human-driven) counterpart. We leverage reachability analysis to construct a real-time (100Hz) controller that serves the dual role of (1) tracking an input trajectory from a higher-level planning algorithm using model predictive control, and (2) assuring safety through maintaining the availability of a collision-free escape maneuver as a persistent constraint regardless of whatever future actions the other car takes. A full-scale steer-by-wire platform is used to conduct traffic weaving experiments wherein the two cars, initially side-by-side, must swap lanes in a limited amount of time and distance, emulating cars merging onto/off of a highway. We demonstrate that, with our control stack, the autonomous vehicle is able to avoid collision even when the other car defies the planner’s expectations and takes dangerous actions, either carelessly or with the intent to collide, and otherwise deviates minimally from the planned trajectory to the extent required to maintain safety.
@inproceedings{LeungSchmerlingEtAl2018,bibtex_show={true},author={Leung, K.* and Schmerling, E.* and Chen, M. and Talbot, J. and Gerdes, J. C. and Pavone, M.},title={On Infusing Reachability-Based Safety Assurance within Probabilistic Planning Frameworks for Human-Robot Vehicle Interactions},booktitle={{Int.\ Symp.\ on Experimental Robotics}},year={2018},arxiv={1812.11315},keywords={Conference},img={LeungSchmerlingEtAl2018.png}}
2017
Nonlinear Stabilization via Control Contraction Metrics: A Pseudospectral Approach for Computing Geodesics
Real-time nonlinear stabilization techniques are often limited by inefficient or intractable online and/or offline computations, or a lack guarantee for global stability. In this paper, we explore the use of Control Contraction Metrics (CCM) for nonlinear stabilization because it offers tractable offline computations that give formal guarantees for global stability. We provide a method to solve the associated online computation for a CCM controller - a pseudospectral method to find a geodesic. Through a case study of a stiff nonlinear system, we highlight two key benefits: (i) using CCM for nonlinear stabilization and (ii) rapid online computations amenable to real-time implementation. We compare the performance of a CCM controller with other popular feedback control techniques, namely the Linear Quadratic Regulator (LQR) and Nonlinear Model Predictive Control (NMPC). We show that a CCM controller using a pseudospectral approach for online computations is a middle ground between the simplicity of LQR and stability guarantees for NMPC.
@inproceedings{LeungManchester2017,bibtex_show={true},author={Leung, K. and Manchester, I. R.},title={Nonlinear Stabilization via Control Contraction Metrics: A Pseudospectral Approach for Computing Geodesics},booktitle={{American Control Conference}},year={2017},arxiv={1607.04340},keywords={Conference},img={LeungManchester2017.png}}
2016
The Diver with a Rotor
Leung, K.,
Bharadwaj, S.,
Duignan, N.,
Tong, W.,
and Dullin, H.
We present and analyse a simple model for the twisting somersault. The model is a rigid body with a rotor attached which can be switched on and off. This makes it simple enough to devise explicit analytical formulas whilst still maintaining sufficient complexity to preserve the shape-changing dynamics essential for twisting somersaults in springboard and platform diving. With ‘rotor on’ and with ‘rotor off’ the corresponding Euler-type equations can be solved, and the essential quantities characterising the dynamics, such as the periods and rotation numbers, can be computed in terms of complete elliptic integrals. Thus we arrive at explicit formulas for how to achieve a dive with m somersaults and n twists in a given total time. This can be thought of as a special case of a geometric phase formula due to Cabrera 2007.
@article{LeungDullinEtAl2016,bibtex_show={true},author={Leung, K. and Bharadwaj, S. and Duignan, N. and Tong, W. and Dullin, H.},title={The Diver with a Rotor},journal={{Indagationes Mathematicae}},volume={27},number={5},pages={1147--1161},year={2016},arxiv={1510.02978},keywords={Journal},img={LeungDullinEtAl2016.png}}
Backpropagation through signal temporal logic specifications: Infusing logical structure into gradient-based methods(Submitted)
