dixit2023risk

Risk-averse Receding Horizon Motion Planning for Obstacle Avoidance using Coherent Risk Measures

Authors: Dixit, Ahmadi, Burdick · Year: 2023 · Venue: Artificial Intelligence (Elsevier) / arXiv
Raw: md

Summary

The paper develops a risk-averse model predictive control (MPC) framework for dynamic obstacle avoidance of a discrete-time linear system subject to both additive process noise and measurement noise (uncertain obstacle rotation/translation). Constraints and cost are posed as bounds on a general coherent risk measure (CVaR, EVaR, total-variation distance, and other f-divergence / g-entropic measures), exploiting the dual “worst-case expectation over a risk envelope” representation. The non-convex risk-constrained problem is reformulated, via convex conjugacy and a Big-M disjunctive encoding of the non-convex safe set, into a convex mixed-integer program with constraint-tightening that removes the exponential-in-horizon blow-up. The authors prove risk-sensitive recursive feasibility and finite-time task completion (each in probability/confidence) and validate on 2D numerical examples.

Key Claims

• Any coherent risk constraint satisfying the dual representation (Assumption 4) admits an exact reformulation (Lemma 2) as a finite convex program in dual variables $({\mathbf{\lambda }}_1,{\lambda }_2,\nu ,h_{l,k})$ using the convex conjugate $g^{\ast }$ of the risk-envelope describing function $g$.
• Constraint tightening (Lemma 1) makes state/control/terminal risk constraints depend only on $\rho (|\delta |)$, which is disturbance-policy-independent and computable offline, avoiding online evaluation that would cost $O((J_{\delta }{)}^N)$ constraints.
• Introducing the auxiliary worst-case variable ${\delta }_{\max ,k}$ with $\mathbb{P}({\delta }_{\max ,k}\le x)=\mathbb{P}(|{\delta }_1|\le x{)}^k$ gives a conservative inner approximation that reduces the obstacle-constraint sample cardinality from $J=(J_{\delta }{)}^k{J}_o$ to $J=J_{\delta }{J}_o$, so constraint count no longer grows exponentially with horizon. The approximation is exact at $k=1$.
• Recursive feasibility (Prop. 1): if feasible at $t$ it is feasible at $t+1$ with confidence $\alpha$; the infeasibility probability is bounded via Cantelli’s inequality and the union bound, $\mathbb{P}\{\text{infeasible}\}\le 1-\alpha$ after Bonferroni risk-allocation $1-{\alpha }^{\prime }=(1-\alpha )/(L+1)$.
• Finite-time task completion (Prop. 2): the cost decreases by at least 1 per step (via a binary task-completion state $\psi$), so waypoint ${\mathbf{w}}_K$ is reached in at most $\lceil J_t^{\ast }\rceil$ steps per leg, with overall confidence ${\alpha }^{J_0^{K-1}}$.
• Empirically (2D system, 50 Monte Carlo runs): ordering $\mathrm{VaR}\le \mathrm{CVaR}\le \mathrm{EVaR}$ and $\mathrm{CVaR}\le \mathrm{TVD}$ holds; higher $\alpha$ (more conservative) lowers infeasibility (e.g. CVaR 5.3%→2.7%, EVaR→0%, TVD 0% at $\alpha =0.9$); exact CVaR cost prioritizes task completion but is ~13× slower (83.68 s vs 6.32 s/iteration).

Method

Linear discrete-time plant (Eq. eq:sys):
$\mathbf{x}(t+1)=A\mathbf{x}(t)+B\mathbf{u}(t)+D\mathbf{\delta }(t),\mathbf{y}(t)=C\mathbf{x}(t).$
Process noise $\mathbf{\delta }$ is i.i.d. from a discrete pmf $p_{\delta }$ (Assumption 2); full-state measurement and full-rank $D$ (Assumption 1). Each obstacle ${\bar{\mathcal{O}}}_l$ is a convex polytope subject to random rotation $R_l$ and translation ${\mathbf{w}}_l$ drawn from a discrete joint pmf $p_l$ (Assumption 3). The safety constraint bounds the coherent risk of the distance-to-safe-set, ${\rho }_{1-\alpha }[\zeta (\mathbf{y}(t),{\mathcal{S}}_l(t))]\le {ϵ}_l$.

Control is a simplified affine disturbance feedback (SADF) policy, $u_k={\sum }_{m=0}^{k-1}{K}_{k-m}{\delta }_m+{\eta }_k$, with decision variables $\{{\mathbf{K}}_N,{\mathbf{\eta }}_N\}$; this is less conservative than open-loop MPC (a special case with $K_i=0$) and is linear in the optimization variables (unlike affine state feedback). Coherent risk measures (Definition 1: monotonicity, translation invariance, positive homogeneity, subadditivity) are used in dual form (Definition 2 / Assumption 4):
$\rho (X)={\sup }_{Q\in \mathcal{Q}}{\mathbb{E}}_Q(X),\mathcal{Q}\subset \{Q\ll P\}\text{convex, closed (risk envelope)}.$
Specific envelopes are given for CVaR (Radon–Nikodym bound $dQ/dP\le 1/(1-\alpha )$), EVaR (KL-divergence epigraph, exponential cone), and TVD (total-variation ball). The non-convex safe set is handled with a Big-M disjunctive reformulation introducing binaries ${\gamma }_i^j\in \{0,1\}$, yielding a convex MIP whose local optima still satisfy the original risk constraints.

Regime: This is a generic linear-system MPC obstacle-avoidance paper; it is neither free-flying nor free-floating — it carries no manipulator dynamics, no base-arm dynamic coupling, and no reaction/momentum bookkeeping. The illustrative platform is a planar drone. Relevance to a free-flying space manipulator is purely at the risk/planning layer, not the dynamics model.

Relevance to thesis

This is a template for the risk layer sitting atop nominal guidance/control of the free-flying manipulator. Three transferable ideas: (i) the general coherent-risk dual reformulation lets us swap CVaR/EVaR/TVD without re-deriving the optimizer — useful for trading conservatism against feasibility on collision-risk constraints during inspection; (ii) the offline constraint-tightening on $\rho (|\delta |)$ and the ${\delta }_{\max ,k}$ trick are practical tools to keep a receding-horizon problem tractable under disturbance growth; (iii) the recursive-feasibility / finite-time-completion proofs (Cantelli bound + Bonferroni risk allocation) give a probabilistic safety certificate structure we could adapt. Caveat: the linear-plant assumption is restrictive — a 6-DOF free-flying base plus arm is strongly nonlinear and coupled, so the dynamics would need linearization or a different propagation of risk through the manipulator Jacobian before these results apply.

Connections

Topics: conditional_value_at_risk, coherent_risk_measures, chance_constraints, model_predictive_control

Key Equations / Quotes

“Coherent risk measures can be expressed as a distributionally-robust expectation, i.e, the risk is equivalently expressed as the worst-case expectation over a convex, closed set of distributions.” (Introduction)

CVaR (Eq. eq:cvar_def):
${\mathrm{CVaR}}_{1-\alpha }(X):={\inf }_{z\in \mathbb{R}}\mathbb{E}[z+\frac{(X-z{)}^{+}}{1-\alpha }].$

EVaR (Eq. eq:evar):
${\mathrm{EVaR}}_{1-\alpha }(X):={\inf }_{z>0}\left[z^{-1}\ln \frac{\mathbb{E}[e^{Xz}]}{1-\alpha }\right],{\lim }_{\alpha \to 1}{\mathrm{EVaR}}_{1-\alpha }(X)=\mathrm{esssup}(X).$

Conjugate-form safety reformulation (Lemma 2 / Eq. eq:conjugate):
${\min }_{{\mathbf{\lambda }}_1,{\lambda }_2,\nu }{\lambda }_2{g}^{\ast }\left({\lambda }_2^{-1}\right(\mathbf{p}(h_{l,k}^{\ast }+\nu )+{\mathbf{\lambda }}_1\left)\right)-\nu ,{\mathbf{\lambda }}_1⪰0,{\lambda }_2\ge 0.$

Tightened state constraint (Lemma 1, Eq. eq:state_tighten):
$f_{x,n}^{\top }(A^k{x}_0+{\mathbf{B}}_k{\mathbf{\eta }}_k)+\Vert f_{x,n}^{\top }({\mathbf{B}}_k{\mathbf{K}}_k+{\mathbf{D}}_k){\Vert }_1\rho (|\delta |)\le {ϵ}_x+g_{x,n}.$

Risk allocation (Remark 1): $1-{\alpha }^{\prime }=(1-\alpha )/(L+1)$.

Open Questions

• $N$-step reachability of the waypoints from the higher-level (A*/RRT) planner is assumed, not analyzed; the authors flag it as future work. How would this interact with a nonholonomic-free attitude path for a 6-DOF base?
• Extension beyond linear, time-invariant plants: the footnote notes that LTV systems break the SADF equivalence and require the non-simplified disturbance-feedback policy — what is the cost/feasibility penalty?
• The recursive-feasibility bound (Cantelli) is admittedly loose; the paper reports actual infeasibility far below the bound but the tightness is “unknown.” Can a sharper certificate be obtained for specific risk measures?
• All uncertainty is modeled as finite discrete pmfs; scaling to high-cardinality or continuous disturbance distributions (relevant to real sensor/actuator noise on a spacecraft) is not addressed.