Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints

1. Problem Statement

The paper addresses Stochastic Motion Planning for discrete-time linear systems subject to uncertainty (process noise and initial state distribution). The goal is to find an optimal control policy that minimizes a quadratic cost function while satisfying Chance Constraints (CCs) with a specified probability level ($1-\epsilon$).

Key challenges in existing approaches include:

• Non-convexity: Formulating chance constraints on states and controls often leads to non-convex optimization problems, requiring linearization or successive convexification which can be conservative or computationally expensive.
• Decoupling limitations: Many methods decouple mean and covariance optimization, which fails to capture the trade-off between risk and performance (e.g., navigating narrow corridors requires tighter feedback laws).
• Conservatism: Existing approximations for quadratic chance constraints (e.g., using Markov's inequality) are often overly conservative, leading to infeasibility under moderate noise levels.

The specific problem (Problem 1) involves a linear time-varying system:
$$x_{k+1} = A_k x_k + B_k u_k + D_k w_k$$
subject to:

• Linear Chance Constraints (LCC): Probabilistic bounds on linear combinations of states and controls over single or multiple time steps.
• Quadratic Chance Constraints (QCC): Probabilistic bounds on the deviation of the state from its mean (ellipsoidal constraints).
• Terminal Covariance Constraints: Bounds on the final state covariance.

2. Methodology: Lifted Representation

The core contribution is a lifted representation method that explicitly encodes moment information (mean and covariance) into the decision variables, transforming the stochastic problem into a deterministic convex one.

A. Stochastic Basis and State/Control Representation

Instead of propagating covariances separately, the authors represent the random variables (states $x_k$ and controls $u_k$) as affine functions of a stochastic basis $e(k)$.

• Basis Construction: The basis $e(k)$ is a vector of independent standard Gaussian variables constructed recursively from the initial state noise and process noise up to time $k$.
• Lifted Variables:
  • State: $x_k = \mu_k + \Psi_k e(k)$, where $\mu_k$ is the mean and $\Psi_k$ encodes the covariance structure ($\text{var}(x_k) = \Psi_k \Psi_k^\top$).
  • Control: $u_k = \nu_k + V_k e(k)$, where $\nu_k$ is the mean control and $V_k$ encodes the feedback structure relative to the noise basis.
• This formulation assumes causal affine policies, where the control at time $k$ depends linearly on the history of noise realizations up to $k$.

B. Reformulation of Constraints

Using the lifted variables ($\mu, \nu, \psi, v$), the authors derive exact or conservative convex reformulations:

1. Linear Chance Constraints (Exact Reformulation):

   • For a linear constraint $P(a^\top x + \alpha^\top u \le b) \ge 1-\epsilon$, the random variable is a linear combination of Gaussians, hence Gaussian.
   • The constraint is exactly reformulated as a Second-Order Cone (SOC) constraint:
     $$\text{Mean} + \Phi^{-1}_N(1-\epsilon) \cdot \|\text{StdDev}\|_2 \le b$$
   • This holds without conservatism for $0 \le \epsilon < 0.5$.

2. Terminal Covariance Constraint (Exact Reformulation):

   • The constraint $\text{var}(x_N) \preceq \Sigma_f$ is reformulated using the Schur complement as a Linear Matrix Inequality (LMI) involving $\Psi_N$.

3. Quadratic Chance Constraints (Approximate Reformulation):

   • The paper proposes two conservative approximations for $P((x-\mu)^\top Q^{-1}_{CC} (x-\mu) \le 1) \ge 1-\epsilon$:
     • LMI Approximation: Uses set inclusion properties of ellipsoids to derive an LMI constraint. This is tighter when the eigenvalues of the covariance matrix are similar.
     • Quadratic Approximation: Uses a bound on the trace of the covariance matrix derived from concentration inequalities. This is tighter when the eigenvalues are highly spread (anisotropic noise).
   • Both are provably less conservative than existing methods (e.g., Markov's inequality).

C. The Resulting Optimization Problem

The original stochastic problem is transformed into Problem 2, a deterministic convex optimization problem with decision variables $\{\mu_k, \nu_k, \psi_k, v_k\}$.

• Objective: A quadratic cost function that includes terms for both the mean trajectory and the "spread" (covariance) of the trajectory.
• Constraints: Affine dynamics (in lifted space), SOC constraints (for LCCs), and LMIs/Quadratic constraints (for QCCs).

3. Key Contributions

1. Exact Convex Reformulation: Demonstrated that linear chance constraints on states and controls (including multi-step and mixed constraints) can be exactly represented as SOC constraints under Gaussian assumptions, eliminating the need for linearization or successive convexification.
2. Improved Quadratic Approximations: Derived two new convex approximations for quadratic chance constraints (LMI and Quadratic forms) that are provably less conservative than standard methods like Markov's inequality.
3. Unified Framework: Provided a single framework that handles mean optimization, covariance shaping, and chance constraints simultaneously, avoiding the decoupling of risk and performance.
4. Theoretical Guarantees: Proved that the feasible set of the lifted problem is equivalent to the set of feasible affine causal policies in the original stochastic problem.

4. Experimental Results

The authors validated the framework on minimum-snap trajectory generation for a quadrotor in a 2D plane under stochastic perturbations. They compared their method against two baselines:

• [7]: A method using feedback gains (Riccati equation) and exact linear constraints.
• [11]: A method using iterative covariance estimation and approximate linear constraints.

Key Findings:

• Feasibility: The proposed method remained feasible at noise levels an order of magnitude higher than the baselines.
  • Circle Arena: Feasible up to noise $\sigma = 0.85$, while baselines failed at $\sigma \approx 0.06$.
  • Funnel Corridor: Feasible up to $\sigma = 0.60$, while baselines failed at $\sigma \approx 0.06$.
• Optimality (Cost Reduction):
  • In the Circle Arena, the proposed method achieved up to 35% cost reduction compared to [7].
  • In the Funnel Corridor, it achieved up to 43% cost reduction under moderate noise.
• Quadratic Constraints: The LMI approximation (22) performed best for isotropic noise, while the Quadratic approximation (24) was superior for highly anisotropic noise. Both significantly outperformed Markov's bound.

5. Significance

This work bridges the gap between theoretical stochastic optimal control and practical implementation. By providing an exact convex reformulation for linear chance constraints, it removes the conservatism inherent in linearization-based approaches. This allows autonomous systems (like UAVs) to operate safely in much noisier environments and navigate tighter corridors than previously possible, while simultaneously optimizing for both trajectory accuracy and uncertainty management. The ability to shape the covariance directly within the optimization loop enables more aggressive and efficient motion planning in uncertain environments.