A classic reachability problem for safety of dynamic systems is to compute the set of initial states from which the state trajectory is guaranteed to stay inside a given constraint set over a given time horizon. In this paper, we leverage existing theory of reachability analysis and risk measures to devise a risk-sensitive reachability approach for safety of stochastic dynamic systems under non-adversarial disturbances over a finite time horizon. Specifically, we first introduce the notion of a risk-sensitive safe set asa set of initial states from which the risk of large constraint violations can be reduced to a required level via a control policy, where risk is quantified using the Conditional Value-at-Risk(CVaR) measure. Second, we show how the computation of a risk-sensitive safe set can be reduced to the solution to a Markov Decision Process (MDP), where cost is assessed according to CVaR. Third, leveraging this reduction, we devise a tractable algorithm to approximate a risk-sensitive safe set and provide arguments about its correctness. Finally, we present a realistic example inspired from stormwater catchment design to demonstrate the utility of risk-sensitive reachability analysis. In particular, our approach allows a practitioner to tune the level of risk sensitivity from worst-case (which is typical for Hamilton-Jacobi reachability analysis) to risk-neutral (which is the case for stochastic reachability analysis).
more »
« less
Safety-Aware Optimal Control of Stochastic Systems Using Conditional Value-at-Risk
In this paper, we consider a multi-objective control problem for stochastic systems that seeks to minimize a cost of interest while ensuring safety. We introduce a novel measure of safety risk using the conditional value-at-risk and a set distance to formulate a safety risk-constrained optimal control problem. Our reformulation method using an extremal representation of the safety risk measure provides a computationally tractable dynamic programming solution. A useful byproduct of the proposed solution is the notion of a risk-constrained safe set, which is a new stochastic safety verification tool. We also establish useful connections between the risk-constrained safe sets and the popular probabilistic safe sets. The tradeoff between the risk tolerance and the mean performance of our controller is examined through an inventory control problem.
more »
« less
- Award ID(s):
- 1657100
- NSF-PAR ID:
- 10128747
- Date Published:
- Journal Name:
- 2018 Annual American Control Conference (ACC)
- Page Range / eLocation ID:
- 6285 to 6290
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A classic reachability problem for safety of dynamic systems is to compute the set of initial states from which the state trajectory is guaranteed to stay inside a given constraint set over a given time horizon. In this paper, we leverage existing theory of reachability analysis and risk measures to devise a risk-sensitive reachability approach for safety of stochastic dynamic systems under non-adversarial disturbances over a finite time horizon. Specifically, we first introduce the notion of a risk-sensitive safe set as a set of initial states from which the risk of large constraint violations can be reduced to a required level via a control policy, where risk is quantified using the Conditional Value-at-Risk (CVaR) measure. Second, we show how the computation of a risk-sensitive safe set can be reduced to the solution to a Markov Decision Process (MDP), where cost is assessed according to CVaR. Third, leveraging this reduction, we devise a tractable algorithm to approximate a risk-sensitive safe set, and provide theoretical arguments about its correctness. Finally, we present a realistic example inspired from stormwater catchment design to demonstrate the utility of risk-sensitive reachability analysis. In particular, our approach allows a practitioner to tune the level of risk sensitivity from worst-case (which is typical for Hamilton-Jacobi reachability analysis) to risk-neutral (which is the case for stochastic reachability analysis).more » « less
-
A classic reachability problem for safety of dynamic systems is to compute the set of initial states from which the state trajectory is guaranteed to stay inside a given constraint set over a given time horizon. In this paper, we leverage existing theory of reachability analysis and risk measures to devise a risk-sensitive reachability approach for safety of stochastic dynamic systems under non-adversarial disturbances over a finite time horizon. Specifically, we first introduce the notion of a risk-sensitive safe set as a set of initial states from which the risk of large constraint violations can be reduced to a required level via a control policy, where risk is quantified using the Conditional Value-at-Risk (CVaR) measure. Second, we show how the computation of a risk-sensitive safe set can be reduced to the solution to a Markov Decision Process (MDP), where cost is assessed according to CVaR. Third, leveraging this reduction, we devise a tractable algorithm to approximate a risk-sensitive safe set, and provide theoretical arguments about its correctness. Finally, we present a realistic example inspired from stormwater catchment design to demonstrate the utility of risk-sensitive reachability analysis. In particular, our approach allows a practitioner to tune the level of risk sensitivity from worst-case (which is typical for Hamilton-Jacobi reachability analysis) to risk-neutral (which is the case for stochastic reachability analysis).more » « less
-
d. Many of the infrastructure sectors that are considered to be crucial by the Department of Homeland Security include networked systems (physical and temporal) that function to move some commodity like electricity, people, or even communication from one location of importance to another. The costs associated with these flows make up the price of the network’s normal functionality. These networks have limited capacities, which cause the marginal cost of a unit of flow across an edge to increase as congestion builds. In order to limit the expense of a network’s normal demand we aim to increase the resilience of the system and specifically the resilience of the arc capacities. Divisions of critical infrastructure have faced difficulties in recent years as inadequate resources have been available for needed upgrades and repairs. Without being able to determine future factors that cause damage both minor and extreme to the networks, officials must decide how to best allocate the limited funds now so that these essential systems can withstand the heavy weight of society’s reliance. We model these resource allocation decisions using a two-stage stochastic program (SP) for the purpose of network protection. Starting with a general form for a basic two-stage SP, we enforce assumptions that specify characteristics key to this type of decision model. The second stage objective—which represents the price of the network’s routine functionality—is nonlinear, as it reflects the increasing marginal cost per unit of additional flow across an arc. After the model has been designed properly to reflect the network protection problem, we are left with a nonconvex, nonlinear, nonseparable risk-neutral program. This research focuses on key reformulation techniques that transform the problematic model into one that is convex, separable, and much more solvable. Our approach focuses on using perspective functions to convexify the feasibility set of the second stage and second order conic constraints to represent nonlinear constraints in a form that better allows the use of computational solvers. Once these methods have been applied to the risk-neutral model we introduce a risk measure into the first stage that allows us to control the balance between an efficient, solvable model and the need to hedge against extreme events. Using Benders cuts that exploit linear separability, we give a decomposition and solution algorithm for the general network model. The innovations included in this formulation are then implemented on a transportation network with given flow demandmore » « less
-
Motivated by connected and automated vehicle (CAV) technologies, this paper proposes a data-driven optimization-based Model Predictive Control (MPC) modeling framework for the Cooperative Adaptive Cruise Control (CACC) of a string of CAVs under uncertain traffic conditions. The proposed data-driven optimization-based MPC modeling framework aims to improve the stability, robustness, and safety of longitudinal cooperative automated driving involving a string of CAVs under uncertain traffic conditions using Vehicle-to-Vehicle (V2V) data. Based on an online learning-based driving dynamics prediction model, we predict the uncertain driving states of the vehicles preceding the controlled CAVs. With the predicted driving states of the preceding vehicles, we solve a constrained Finite-Horizon Optimal Control problem to predict the uncertain driving states of the controlled CAVs. To obtain the optimal acceleration or deceleration commands for the CAVs under uncertainties, we formulate a Distributionally Robust Stochastic Optimization (DRSO) model (i.e. a special case of data-driven optimization models under moment bounds) with a Distributionally Robust Chance Constraint (DRCC). The predicted uncertain driving states of the immediately preceding vehicles and the controlled CAVs will be utilized in the safety constraint and the reference driving states of the DRSO-DRCC model. To solve the minimax program of the DRSO-DRCC model, we reformulate the relaxed dual problem as a Semidefinite Program (SDP) of the original DRSO-DRCC model based on the strong duality theory and the Semidefinite Relaxation technique. In addition, we propose two methods for solving the relaxed SDP problem. We use Next Generation Simulation (NGSIM) data to demonstrate the proposed model in numerical experiments. The experimental results and analyses demonstrate that the proposed model can obtain string-stable, robust, and safe longitudinal cooperative automated driving control of CAVs by proper settings, including the driving-dynamics prediction model, prediction horizon lengths, and time headways. Computational analyses are conducted to validate the efficiency of the proposed methods for solving the DRSO-DRCC model for real-time automated driving applications within proper settings.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.23919/ACC.2018.8430957
