Sleiman Safaoui, Tyler H Summers

Keywords: Computational methods, uncertain systems, optimization, code generation, risk-based optimization

Overview

Optimization modeling tools and parser solvers, such as CVXPY, make solving deterministic optimization problems a lot easier: they allow users to encode optimization problems in high-level mathematical expressions thereby reducing the need for tedious reformulations or fitting problems into canonical forms.

Many optimization problems often include uncertain terms which are modeled as random variables. Examples of such random variables include stock returns, sensor readings, or the state of a system (e.g. localization of a robot which is uncertain). This gives rise to Risk-Based Optimization problems.

Risk-based optimization problems can be hard to code and they may require tedious reformulations or digging up equivalent forms to eventually encode the problem as an equivalent deterministic risk-tightened optimization problems. To encourage risk-based optimization problems and help speed up the development cycle, we created cvxRiskOpt: a risk-based optimization tool built on top of CVXPY.

There are a few tools for encoding risk-based optimization problems, such as Pyomo, RSOME, and PICOS. While they may support a wider range of stochastic, robust, and distributionally robust optimization problems than our cvxRiskOpt, they have their limitations. Some require complex reformulations of uncertainty sets, some have limited support for problem instances, and all are limited to solving the problem without being able to generate embeddable code for the risk-based optimization problem, a nice feature for embedded system applications or to speed up solve times.

On the other hand, our cvxRiskOpt package builds on CVXPY and provides users with tools to automatically generate risk-based optimization problems and risk-based constraints (e.g. worst case expectation with a Wasserstein-based ambiguity set, chance constraint with a moment-based ambiguity set, etc). Furthermore, because cvxRiskOpt integrates with CVXPY directly and results in CVXPY Problems and constraints, users can utilize CVXPYgen to automatically generate C-code which can be used on embedded systems or utilized with the python-wrapper to speed up solving the optimization problems.

cvxRiskOpt is on PyPI and GitHub.

For more details about cvxRiskOpt and how to use it, please check out the package documentation!

Sleiman Safaoui, Tyler H Summers, ICRA 2024.

Keywords: Risk-based planning, Wasserstein-based ambiguity set, DR-CVaR, Uncertain environments

Overview

Planning a trajectory for an autonomous robot in the presence of dynamics obstacles is a challenging problem. It involves having to predict how the obstacles will move and choosing a collision-free path.

Modern motion planning solutions (e.g. ones based on machine learning) can, to some extent, capture the intention of the dynamic obstacles when generating a motion plan. However, these motion plans generally do not provide hard safety guarantees.

To address this issue, we propose the usage of a safety filter before passing down the reference trajectory from the motion planner to the controller, as shown in the figure below. The safety filter is an optimization-based module that makes corrections to the reference trajectory to enforce the satisfaction of safety requirements.

We assume that the safety filter has access to a motion prediction module that generates sample trajectories for the obstacle vehicles. These sample trajectories capture some of the uncertainty in the obstacles’ motion. However, since these trajectories are only samples and do not capture the true distribution of the uncertainty, we rely on tools from distributionally robust optimization (DRO) to account for that.

In particular, we formulate an empirical distribution from the samples and consider a Wasserstein-based ambiguity set around the empirical distribution. This ambiguity set consists of all distributions that are within some epsilon distance of the empirical distribution where the distance is measured using the Wasserstein metric.

The notion of safety we use in this work is the CVaR risk metric: the conditional value-at-risk. CVaR is a metric that measures the average of the worst cases. Thus, CVaR not only limits the probability of unsafe events, but also puts a bound on the level of danger or risk in the worst cases.

By computing the CVaR with respect to the ambiguity set, we get a DR-CVaR safety constraint that ensures that the corrected trajectory is safe even when the distribution is unknown.

Through numerical simulations, we show that the proposed safety filtering solution can run in real time and ensure the safety of the ego vehicle even in edge cases. An example of that is shown in the figure below where the ego vehicle (in blue) navigates around the other three obstacles and safely reaches its goal on the right side.

For more details, check out our paper on arXiv! (the ICRA24 version will soon be on IEEE Xplore as well.)

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.