More Like this

1. Guaranteed Safe Path and Trajectory Tracking via Reachability Analysis Using Differential Inequalities

   Yang, Xuejiao; Mu, Bowen; Robertson, Dillard; Scott, Joseph K. (January 2023, Journal of intelligent robotic systems)

   In many automated motion planning systems, vehicles are tasked with tracking a reference path or trajectory that is safe by design. However, due to various uncertainties, real vehicles may deviate from such references, potentially leading to collisions. This paper presents rigorous reachable set bounding methods for rapidly enclosing the set of possible deviations under uncertainty, which is critical information for online safety verification. The proposed approach applies recent advances in the theory of differential inequalities that exploit redundant model equations to achieve sharp bounds using only simple interval calculations. These methods have been shown to produce very sharp bounds at low cost for nonlinear systems in other application domains, but they rely on problem-specific insights to identify appropriate redundant equations, which makes them difficult to generalize and automate. Here, we demonstrate the application of these methods to tracking problems for the first time using three representative case studies. We find that defining redundant equations in terms of Lyapunov-like functions is particularly effective. The results show that this technique can produce effective bounds with computational times that are orders of magnitude less than the planned time horizon, making this a promising approach for online safety verification. This performance, however, comes at the cost of low generalizability, specifically due to the need for problem-specific insights and advantageous problem structure, such as the existence of appropriate Lyapunov-like functions. 

   more » « less
2. Model Predictive Real-Time Monitoring of Linear Systems

   https://doi.org/10.1109/RTSS.2017.00035  

   Chen, Xin; Sankaranarayanan, Sriram (December 2017, 2017 IEEE Real-Time Systems Symposium (RTSS))

   The predictive monitoring problem asks whether a deployed system is likely to fail over the next T seconds under some environmental conditions. This problem is of the utmost importance for cyber-physical systems, and has inspired real-time architectures capable of adapting to such failures upon forewarning. In this paper, we present a linear model-predictive scheme for the real-time monitoring of linear systems governed by time-triggered controllers and time-varying disturbances. The scheme uses a combination of offline (advance) and online computations to decide if a given plant model has entered a state from which no matter what control is applied, the disturbance has a strategy to drive the system to an unsafe region. Our approach is independent of the control strategy used: this allows us to deal with plants that are controlled using model-predictive control techniques or even opaque machine-learning based control algorithms that are hard to reason with using existing reachable set estimation algorithms. Our online computation reuses the symbolic reachable sets computed offline. The real-time monitor instantiates the reachable set with a concrete state estimate, and repeatedly performs emptiness checks with respect to a safety property. We classify the various alarms raised by our approach in terms of what they imply about the system as a whole. We implement our real-time monitoring approach over numerous linear system benchmarks and show that the computation can be performed rapidly in practice. Furthermore, we also examine the alarms reported by our approach and show how some of the alarms can be used to improve the controller. 

   more » « less
3. A new vertically integrated MOno-Layer Higher-Order (MOLHO) ice flow model

   https://doi.org/10.5194/tc-16-179-2022  

   Dias dos Santos, Thiago; Morlighem, Mathieu; Brinkerhoff, Douglas (January 2022, The Cryosphere)

   Abstract. Numerical simulations of ice sheets rely on the momentum balance to determine how ice velocities change as the geometry of the system evolves. Ice is generally assumed to follow a Stokes flow with a nonlinear viscosity. Several approximations have been proposed in order to lower the computational cost of a full-Stokes stress balance. A popular option is the Blatter–Pattyn or higher-order model (HO), which consists of a three-dimensional set of equations that solves the horizontal velocities only. However, it still remains computationally expensive for long transient simulations. Here we present a depth-integrated formulation of the HO model, which can be solved on a two-dimensional mesh in the horizontal plane. We employ a specific polynomial function to describe the vertical variation in the velocity, which allows us to integrate the vertical dimension using a semi-analytic integration. We assess the performance of this MOno-Layer Higher-Order (MOLHO) model to compute ice velocities and simulate grounding line dynamics on standard benchmarks (ISMIP-HOM and MISMIP3D). We compare MOLHO results to the ones obtained with the original three-dimensional HO model. We also compare the time performance of both models in time-dependent runs. Our results show that the ice velocities and grounding line positions obtained with MOLHO are in very good agreement with the ones from HO. In terms of computing time, MOLHO requires less than 10 % of the computational time of a typical HO model, for the same simulations. These results suggest that the MOno-Layer Higher-Order formulation provides improved computational time performance and a comparable accuracy compared to the HO formulation, which opens the door to higher-order paleo simulations. 

   more » « less
4. A Neural Network Approach for Stochastic Optimal Control

   Li, Xingjian; Verma, Deepanshu; Ruthotto, Lars (June 2024, SIAM journal on scientific computing)

   We present a neural network approach for approximating the value function of high- dimensional stochastic control problems. Our training process simultaneously updates our value function estimate and identifies the part of the state space likely to be visited by optimal trajectories. Our approach leverages insights from optimal control theory and the fundamental relation between semi-linear parabolic partial differential equations and forward-backward stochastic differential equations. To focus the sampling on relevant states during neural network training, we use the stochastic Pontryagin maximum principle (PMP) to obtain the optimal controls for the current value function estimate. By design, our approach coincides with the method of characteristics for the non-viscous Hamilton-Jacobi-Bellman equation arising in deterministic control problems. Our training loss consists of a weighted sum of the objective functional of the control problem and penalty terms that enforce the HJB equations along the sampled trajectories. Importantly, training is unsupervised in that it does not require solutions of the control problem. Our numerical experiments highlight our scheme’s ability to identify the relevant parts of the state space and produce meaningful value estimates. Using a two-dimensional model problem, we demonstrate the importance of the stochastic PMP to inform the sampling and compare to a finite element approach. With a nonlinear control affine quadcopter example, we illustrate that our approach can handle complicated dynamics. For a 100-dimensional benchmark problem, we demonstrate that our approach improves accuracy and time-to-solution and, via a modification, we show the wider applicability of our scheme. 

   more » « less
5. Using SOS and Sublevel Set Volume Minimization for Estimation of Forward Reachable Sets

   Jones, M.; Peet, M. (January 2019, IFAC proceedings series)

   In this paper we propose a convex Sum-of-Squares optimization problem for finding outer approximations of forward reachable sets for nonlinear uncertain Ordinary Differential Equations (ODE’s) with either (or both) L2 or point-wise bounded input disturbances. To make our approximations tight we seek to minimize the volume of our approximation set. Our approach to volume minimization is based on the use of a convex determinant-like objective function.We provide several numerical examples including the Lorenz system and the Van der Pol oscillator. 

   more » « less