ren2022chance

Chance-Constrained Trajectory Planning under Gaussian Mixture Model Uncertainty

Authors: Ren, Ahn, Kamgarpour · Year: 2022 · Venue: IEEE Control Systems Letters (L-CSS) / likely ACC
Raw: md

Summary

The paper formulates a chance-constrained trajectory-planning problem where the uncertain obstacle position follows a Gaussian Mixture Model (GMM) rather than a unimodal Gaussian, motivated by the multimodal intents (e.g., go-straight vs. turn) produced by modern trajectory-prediction networks. It derives an exact deterministic second-order-cone reformulation of the per-mode chance constraint (and a conservative CVaR approximation), and—when the GMM moments are estimated from finite samples—a tight moment-concentration bound that robustifies the constraint with high confidence. The methods are validated on the real-world nuScenes autonomous-driving dataset using Trajectron++ predictions, where GMM modelling yields less conservative motion than unimodal Gaussian (which is infeasible) or scenario-based baselines.

Key Claims

• A GMM chance constraint decomposes into one per-mode Gaussian chance constraint per mode plus a risk-budget split ${\sum }_k{\pi }_k{ϵ}_k=ϵ$ (Eqs. 5–6).
• For a linear (affine) constraint ${\delta }^{\top }\tilde{x}\le 0$, both the per-mode chance constraint and its CVaR approximation reduce to the same SOC form ${\Gamma }_k\sqrt{{\tilde{x}}^{\top }{\Sigma }_k\tilde{x}}+{\mu }_k^{\top }\tilde{x}\le 0$, differing only in ${\Gamma }_k$: ${\Gamma }_k={\Psi }^{-1}(1-{ϵ}_k)$ for chance, ${\Gamma }_k=\varphi ({\Psi }^{-1}(1-{ϵ}_k))/{ϵ}_k$ for CVaR (Lemma 1).
• A new 1-D mean-concentration bound (Eq. 11) that exploits the scalar linear-constraint structure is provably tighter than the n-D bound of Lefkopoulos et al. (Eq. 16); the n-D bound rendered the planners infeasible on nuScenes while the 1-D bound admitted feasible solutions.
• With sample-estimated moments, the robustified SOC constraint guarantees per-mode feasibility with probability $\ge 1-2\beta$ (Theorem 1) and joint feasibility of the full plan with probability $\ge 1-2\beta TJ$ over $TJ$ obstacle-time constraints (Theorem 2).
• The full planner is a mixed-integer SOCP (Big-M for the disjunctive “outside at least one face” obstacle constraint), tractable via CPLEX; runtimes 1.5 s (MTA/MRA/CVaR) to 4.25 s (CVaRR) on a 4 s horizon.
• Empirically the CVaR-robust (CVaRR) planner minimizes expected violation amount while keeping violation rate below $ϵ=0.05$; unimodal Gaussian modelling is infeasible across all planners.

Method

Regime: Ground autonomous vehicles, not a space manipulator — no free-flying or free-floating regime is present. The “ego vehicle” is a generic linear discrete-time system $x_{t+1}=A_t{x}_t+B_t{u}_t$ (Eq. 12, a double-integrator in experiments). Relevance to a free-flying space manipulator is purely at the risk/uncertainty layer, not the dynamics.

Constraint setup (Assumption 1): the violation function is the affine product $C(x,\delta )={\delta }^{\top }\tilde{x}$ with $\tilde{x}=[x^{\top }1{]}^{\top }$; $\delta$ encodes an obstacle edge. The chance constraint is
${\mathbb{P}}_{\delta \sim p_{\ast }}(C(x,\delta )\le 0)\ge 1-ϵ,ϵ\in (0,0.5).$
GMM: $p_{\ast }(z)={\sum }_{k=1}^K{\pi }_k\mathcal{N}({\mu }_k,{\Sigma }_k)$, ${\sum }_k{\pi }_k=1$. Note the affine constraint pushes $C(x,\delta )$ to a 1-D Gaussian per mode, $C\sim \mathcal{N}({\mu }_k^{\top }\tilde{x},{\tilde{x}}^{\top }{\Sigma }_k\tilde{x})$, which is what makes the scalar concentration bound (Eq. 11) tighter than the vector bound (Eq. 16).

CVaR per mode (Eq. 8): ${\mathrm{CVaR}}_{{ϵ}_k}({\delta }^{\top }\tilde{x})={\inf }_{\alpha >0}\{\frac{1}{{ϵ}_k}\mathbb{E}[({\delta }^{\top }\tilde{x}+\alpha {)}_{+}]-\alpha \}\le 0$, a conservative inner approximation of the chance constraint.

Multi-obstacle/multi-face planning: the disjunction “be outside at least one of $I_j$ faces” is handled with Big-M binaries $z_{ij}^t$ and Boole’s-inequality risk splitting ${ϵ}_{ij}^t=ϵ/(TJ)$ (uniform risk allocation), giving a mixed-integer SOCP (Theorem 2). An optional optimal risk allocation via Branch-and-Bound is noted to give negligible improvement over uniform.

Notation clash flag: the markdown renders the inverse standard-normal CDF as \Psi^{-1} (textPsi) and the standard-normal PDF as \Phi. This is the reverse of the conventional $\Phi$ (CDF) / $\varphi$ (PDF) usage; readers must not assume $\Phi$ here is the CDF. I transcribe the paper’s symbols verbatim but rendered CVaR’s ${\Gamma }_k$ as $\varphi ({\Psi }^{-1}(\cdot ))/{ϵ}_k$ in plain terms (PDF of the $(1-{ϵ}_k)$-quantile divided by ${ϵ}_k$). Also Eq. 11 has a likely typo: $r_{1,k}$ is written with $\hat{\Sigma }$ (no subscript $k$) under the root.

Relevance to thesis

The dynamics are irrelevant to a free-flying space manipulator, but the risk layer is directly transferable. The key reusable ingredients: (1) exact SOC reformulation of per-mode Gaussian chance/CVaR constraints; (2) the unification that, under an affine constraint, chance and CVaR share one SOC form differing only by the tightening constant ${\Gamma }_k$; (3) finite-sample moment-robustification with explicit confidence accounting ($1-2\beta TJ$ over a horizon). For risk-aware inspection or proximity operations where obstacle/target pose is predicted with multimodal uncertainty (multiple plausible tumble modes), the GMM-chance-constraint machinery and the scalar concentration bound port directly once the manipulator’s collision constraint is linearized to affine form ${\delta }^{\top }\tilde{x}\le 0$.

Connections

Topics: chance_constraints · conditional_value_at_risk · gaussian_mixture_model · moment_concentration_bound

Key Equations / Quotes

GMM chance-constraint decomposition (Eqs. 5–6):
${\mathbb{P}}_{\delta \sim p_k}({\delta }^{\top }\tilde{x}\le 0)\ge 1-{ϵ}_k\forall k,{\sum }_{k=1}^K{\pi }_k{ϵ}_k=ϵ.$

Deterministic SOC reformulation, known moments (Lemma 1, Eq. 7):
${\Gamma }_k\sqrt{{\tilde{x}}^{\top }{\Sigma }_k\tilde{x}}+{\mu }_k^{\top }\tilde{x}\le 0,\forall k\in {\mathbb{Z}}_{1:K},$
with ${\Gamma }_k={\Psi }^{-1}(1-{ϵ}_k)$ (chance) or ${\Gamma }_k=\Phi ({\Psi }^{-1}(1-{ϵ}_k))/{ϵ}_k$ (CVaR), in the paper’s notation.

Sample-robustified constraint (Theorem 1, Eq. 9):
${\Gamma }_k\sqrt{(1+r_{2,k}){\tilde{x}}^{\top }{\hat{\Sigma }}_k\tilde{x}}+r_{1,k}(x)+{\hat{\mu }}_k^{\top }\tilde{x}\le 0,$
$r_{1,k}(x)=\sqrt{\frac{T_{1,N_k-1}^2(1-\beta )}{N_k}}\sqrt{{\tilde{x}}^{\top }\hat{\Sigma }\tilde{x}},r_{2,k}=\max \left\{\right|1-\frac{N_k-1}{{\chi }_{N_k-1,1-\beta /2}^2}|,|1-\frac{N_k-1}{{\chi }_{N_k-1,\beta /2}^2}\left|\right\}.$

“modelling the uncertain parameter’s distribution with GMM induces less conservative motion than unimodal Gaussian modelling. The CVaR-constrained planner limits the constraint violation amount while ensuring safety with high probability.” (Introduction, contributions)

“the robustified chance and CVaR-constrained planners yield infeasible solutions with the bound [n-D], while the new bound [1-D] enables feasible solutions.” (Sec. II-C)

Open Questions

• Assumption 2/3 require the sample-to-mode assignment and mode weights ${\pi }_k$ to be known a priori (from the predictor’s latent variables); relaxing this (joint clustering + planning) is left as future work.
• The guarantee is open-loop over a fixed horizon; the authors note closed-loop (receding-horizon) extension as ongoing work, where the per-step confidence budget $1-2\beta TJ$ may compound.
• The CVaRR planner’s 4.25 s runtime is too slow for online use; reducing it is flagged as future work.
• Whether the $1-2\beta TJ$ union bound (vs. the multiplicative $(1-2\beta {)}^{TJ}$) is tight enough to avoid excessive conservatism as $TJ$ grows is not analyzed.