Sleiman Safaoui, Lars Lindemann, Iman Shames, Tyler H Summers, ACC 2022.

Keywords: Risk-based control, stochastic systems, Temporal Logic

Overview

In a previous work, we studied the problem of designing discrete-time risk-bounded controls for linear systems with temporal logic specifications.

• Temporal logic specifications define spatial and temporal constraints to be enforced.
  • Examples of spatial constraints: avoid sets (collision regions), goal regions, …
  • Examples of temporal constraints: setting a time limit on reaching a region (reach the goal in at most 10 time-steps) or specifying an order for visiting regions.
• Risk-bounded controls are controls that result in the system satisfying the constraints with a certain probability guarantee.
  • Instead of simply assuming a Gaussian distribution, we consider a set of distributions that includes all distributions that have certain features (also called an ambiguity set).
  • The ambiguity set we consider is the moment-based ambiguity set: the set of all distributions with specific mean and covariance (or first two moments).

In this work, we consider the continuous-time analog of our previous work; i.e. we are interested in generating control commands that would render a continuous-time systems safe and enable it of satisfying its spatial and temporal requirements. Similarly, we consider stochastic linear systems affected by additive noise whose distribution belongs to the moment-based ambiguity set.

The continuous-time problem is more difficult.

• Instead of having discrete control values to optimize over, we have to deal with stochastic integrals. But, stochastic integrals are mostly studied in the case of Gaussian noise. Thus, handling non-Gaussian cases is to some extent novel.
• Finding an open-loop control over a horizon requires solving a constrained continuous-time optimization problem. Continuous-time optimal control is difficult itself (requires using Pontryagin’s maximum principle or solving the Hamilton-Jacobi-Bellman equation). In our problem we also have time-varying constraints.

In our work, we provide a sufficient solution to the problem that consists of:

1. using timed-signal transducers to divide the environment into adjacent convex regions
2. reformulating the dynamics to obtain deterministic risk-tightened dynamics
3. formulating a timed-transition continuous-time constrained problem and solving it by discretizing it while tightening our constraints to retain continuous-time guarantees
4. and finally stringing together solutions to the sequence of timed-transition problems.

Check out our paper on IEEE Xplore or arXiv!

Sleiman Safaoui*, Benjamin Gravell*, Venkatraman Renganathan*, Tyler H Summers, IEEE/RSJ IROS 2020, submitted.

Keywords: Risk-based planning, stochastic systems, nonlinear systems, RRT

Summary

We propose a two-phase risk-averse architecture for controlling stochastic nonlinear robotic systems. RRT* is a high-level sampling-based planning algorithm that is appealing thanks to its asymptotic guarantees of completeness (if a solution exists, it will be found as the number of samples goes to infinity) and optimal (the solution will converge to the optimal value as the number of samples goes to infinity). However, such planners generally do not account for uncertainties while planning resulting in optimistic plans that are prone to failure under uncertainties. Notice how the figure on the left shows an RRT* tree that plans the robot trajectory from the triangle in the upper right corner to the green dashed rectangle passing through the narrow gap to the right of the obstacle. In pursuit of optimality, the plan gets dangerously close to the obstacles (black rectangles). To counter that, we present RANS-RRT*: Risk-Averse Nonlinear Steering RRT*, as an RRT* variant designed for nonlinear dynamics (solves a nonlinear program to steer between nodes) that accounts for risk by approximating the state distribution and applying a distributionally robust collision check to promote safe planning. The figure on the right depicts safety ellipses (yellow circles) at each node that must not collide with the obstacles. Notice how the plan thus avoids the aforementioned gap since it is deemed risky and instead approaches the goal region from the left side.

Having generated a risk-averse plan, the robot uses a low-level controller to track it. We compare three feedback controllers: linear quadratic regulator (LQR), LQR with robustness-promoting multiplicative noise terms (LQRm), and nonlinear model predictive control (NMPC) and the open-loop controller demonstrating the effectiveness of the the feedback controllers, and specifically the chosen NMPC tracker, under heavy-tailed Laplace process noise.

We vary the size of the noise covariance from 0.0000005 to 0.1 and count the number of failures due to collisions out the 1000 Monte Carlo trials for each noise level. The results reveal NMPC’s superiority in tracking the trajectory more safely.

• 

• 

Read on arXiv.

Sleiman Safaoui, Lars Lindemann, Dimos V Dimarogonas, Iman Shames, Tyler H Summers, IEEE L-CSS/CDC 2020

Keywords: Signal temporal logic, stochastic systems, constraint control, optimization

Summary

We present a framework for risk semantics on Signal Temporal Logic (STL) specifications for discrete-time linear dynamical systems with additive stochastic noise. Under our recursive risk semantics, risk constraints on STL formulas can be expressed in terms of risk constraints on atomic predicates which can be tightened into deterministic STL constraints on a related deterministic system. For affine predicates and the Distributionally Robust Value at Risk measure (DR-VaR), we show how the STL risk constraint is reformulated into a deterministic STL constraint. We demonstrate the framework using a Model Predictive Control (MPC) design.

Get paper on IEEE Xplore or arXiv.

Overview

Signal Temporal Logic (STL) has been a focus of recent control and robotics research because it provides expressive tools to formulate and reason about spatial and temporal system properties. A large fraction of this control synthesis under STL specifications literature primarily focuses on deterministic systems or stochastic systems with specific distributions (e.g. normal, bounded support, …) or incoherent risk metrics (e.g. chance constraint). However, practical systems are inherently stochastic and the disturbance may not always be know. Furthermore, it is compelling to use coherent risk metrics for robotics (where risk assessment follows four important risk axioms: monotonicity, translation invariance, positive homogeneity, and subadditivity). The need for frameworks that directly incorporate risk into the STL control synthesis problem is the primary motivation for our work.

Risk-Based STL

We use the STL grammar given by:

This grammar is know as the negation normal form (or positive normal form) and only includes negations at the atomic predicate level. The grammar builds formulas from the true boolean, an atomic predicate, the negation of an atomic predicate, the conjunction of two formulas, the disjunction of two formulas, the until temporal operator (satisfy the formula until the second is true), and the release operator. The atomic predicate is true if the system state applied to a predicate function is greater than zero and false if the latter is less than zero.

Since the system is stochastic, the system states form a stochastic process (rather than a deterministic run). This also make the predicate function with a stochastic state a random variable. We thus consider the risk of violating an STL formula and define the STL risk semantics.

STL Formula Tightening

We first leverage the STL risk semantics to rewrite the STL risk constraint as a set of risk constraints on atomic predicates.

We can then reformulate the discrete-time stochastic system, assuming affine predicates, to find affine risk-tightened predicates. This uses the fact that any random variable can be divided into the sum of its mean and a 0-mean random variable. This also gives us a nominal system which is the expectation of the stochastic system.

Reformulation for DR-VaR Risk Metric

Using the DR-VaR (distributionally robust value at risk) risk metric, Theorem 3.1 from “On distributionally robust chance-constrained linear programs” by Calafiore and El Ghaoui allows us to rewrite the risk-tightened constraints as deterministic affine inequalities.

Here, the overlined x term is the nominal state given by the expectation of the stochastic state, the Delta term in front of the norm is a constant that depends on the chosen risk-bound, the Sigma term is the covariance of the stochastic disturbance, the L term is a matrix based on the system dynamics (system A matrix), and the a,b terms come from the affine predicates.

Numerical Experiments

The experiment formula above, with appropriate predicates, encodes the following problem:

• two agents ag1 and ag2 must always avoid a square obstacle centered at (0,0) with side length 1 over the time interval I1 = [0,3]
• ag1 must eventually, over the time interval I2 = [2,3], reach a square goal region centered at (2,0)
• ag1 and ag2 must maintain a maximum distance of 1 from each other over the time interval I3 = [1,3].

The simulation of 100 experiments yields the following results.

The left figure does not explicitly account for risk and thus collides with the obstacle with 84/100 runs failing to reach the goal because of the disturbance.

The right figure includes our proposed risk analysis with the tightened predicates. This keeps the trajectories sufficiently far from the obstacle and results in 98/100 runs reaching their goal safely.

Get paper on IEEE Xplore or arXiv.