Technical Summary: Feedback Motion Planning for Stochastic Nonlinear Systems with Signal Temporal Logic Specifications

Problem Formulation

This paper addresses the challenge of feedback motion planning for continuous-time stochastic nonlinear systems subject to Signal Temporal Logic (STL) specifications. Unlike classical safe-set constraints that only encode spatial boundaries, STL allows for the specification of complex spatio-temporal requirements, such as sequencing ("visit A before B"), deadlines, and persistence.

The core difficulty lies in the presence of unmodeled dynamics and external perturbations, which are modeled as unbounded stochastic noise (e.g., sensor or actuator noise). In such settings, worst-case robust control methods become overly conservative. Conversely, existing probabilistic approaches often fail to scale to continuous-time nonlinear systems or lack rigorous guarantees. The specific problem is formulated as a chance-constrained STL trajectory optimization: finding a control policy $u$ that minimizes a cost function while ensuring the stochastic trajectory $X_t$ satisfies an STL formula $\phi$ with a high probability (e.g., $1-\delta \geq 99.99\%$).

The primary challenge is the intractability of enforcing a trajectory-level chance constraint over uncountably many time instants while simultaneously satisfying the logical and temporal structure of STL.

Methodology

The authors propose a systematic framework that transforms the intractable stochastic problem into a deterministic STL trajectory optimization (STLTO) problem with tightened constraints. The methodology consists of three main components:

1. Predicate Erosion Strategy

The core idea is to decouple randomness from logic. The authors introduce a predicate erosion strategy where the original STL predicates are "eroded" (tightened) to create a deterministic surrogate problem.

• Mechanism: A Probabilistic Reachable Tube (PRT) is constructed to bound the deviation between a stochastic trajectory $X_t$ and an associated nominal deterministic trajectory $x_t$.
• Transformation: If the nominal trajectory satisfies a "eroded" STL formula $\tilde{\phi}$ (where every predicate set $C$ is replaced by $C \ominus E_t$, with $E_t$ being the tube cross-section), then the stochastic trajectory is guaranteed to satisfy the original formula $\phi$ with probability at least $1-\delta$.
• Result: This converts the chance-constrained problem into a standard deterministic optimization problem (8), solvable with existing numerical tools.

2. Contraction-Based PRT Construction

To ensure the PRT is tight (avoiding excessive conservatism), the authors leverage contraction theory.

• Feedback Design: A feedback tracking controller is designed to render the closed-loop system strongly contracting. This ensures that the stochastic deviation from the nominal trajectory does not diverge.
• Tight Bounds: Using a novel Affine Martingale (AM) and the Averaged Moment Generating Function (AMGF), the authors derive a trajectory-level bound $r_{\delta,t}$ for the PRT.
• Key Insight: The derived bound scales as $O(\sqrt{\log(T/\delta)})$, which is the tightest possible dependence for Itô stochastic systems. This is significantly less conservative than methods relying on union bounds, which often scale linearly with time or discretization steps.

3. Feedback Motion Planning Pipeline

The framework operates in a two-stage synthesis process:

1. Offline Planning: Solve the deterministic surrogate problem (8) to obtain a nominal trajectory $(x^*, u^*)$ and a feedforward control.
2. Online Execution: Apply a composite control law $u_t = u^*_t + K_t(X_t; x^*_t, u^*_t)$, where $K_t$ is a tracking controller (e.g., Time-Varying LQR or Time-Varying Control Contraction Metric) that stabilizes the stochastic system around the nominal plan.

• Coupling: The paper addresses the coupling between the planning horizon (which depends on the tube size) and the controller synthesis (which determines the tube size) via an iterative algorithm or a decoupled design using trajectory-independent TVCCM synthesis.

Key Contributions

The paper makes the following specific contributions:

1. Continuous-Time STL Erosion: A systematic strategy that transforms chance-constrained STL trajectory optimization problems into deterministic ones by eroding predicates based on a PRT, applicable to general continuous-time nonlinear systems.
2. Rigorous Probabilistic Guarantees: A complete pipeline for feedback control synthesis that provides rigorous probabilistic guarantees (e.g., $\geq 99.99\%$ satisfaction) for stochastic systems, overcoming limitations of existing discrete-time or linear-only methods.
3. Tight PRT Bounds: The development of a tight, trajectory-level PRT bound using contraction theory and martingale-based analysis, which avoids the conservativeness of union bounds in continuous time.
4. Empirical Validation: Demonstration of the framework's scalability and effectiveness through extensive simulations on four robotic benchmarks (Double Integrator, Dubins Car, PVTOL, Quadrotor) and real-world experiments on a quadrupedal robot.

Results

The proposed framework was evaluated on four simulated benchmarks and a real-world quadrupedal robot (Unitree Go1).

• Simulation Performance:

  • The method achieved 100% STL specification satisfaction across 10,000 stochastic rollouts for all four benchmarks (Double Integrator, Dubins Car, PVTOL, and 3D Quadrotor).
  • Baselines: Competing methods, including "Non-Robust" deterministic planning and "Shrinking-Horizon MPC" (SHMPC), showed significantly lower satisfaction rates (ranging from 0.2% to 77.6%), demonstrating that deterministic planning alone is insufficient for stochastic systems.
  • Conservatism: Comparisons with discrete-time baselines (DPRT and STLCD) showed that the proposed continuous-time method is less conservative. Specifically, the erosion radius in the proposed method is independent of the discretization step size $N$ and scales more mildly with the risk level $\delta$ (as $\sqrt{\log(1/\delta)}$) compared to the linear scaling of discrete-time union bounds.

• Real-World Experiment:

  • The framework was deployed on a Unitree Go1 quadruped using a high-level unicycle abstraction.
  • In 50 hardware executions for two distinct navigation tasks (reach-avoid and pass-before), the robot successfully completed the tasks in all trials, satisfying the STL specifications despite state estimation noise, actuation noise, and model mismatch.

Significance and Claims

The authors claim that this work bridges a critical gap in robotic autonomy by enabling reliable, high-level temporal logic planning under uncertainty for continuous-time nonlinear systems.

• Overcoming Conservatism: The paper argues that existing probabilistic methods are either too conservative (due to union bounds) or lack formal guarantees (due to approximations). The proposed PRT-based erosion strategy offers a rigorous yet less conservative alternative.
• Scalability: By reducing the stochastic problem to a deterministic one, the method leverages existing numerical optimization solvers (e.g., SNOPT, MOSEK), making it scalable to complex nonlinear dynamics.
• Practical Applicability: The successful deployment on a real quadrupedal robot demonstrates that the theoretical framework is robust enough to handle real-world uncertainties, including hybrid dynamics and impact events, without requiring perfect system models.

The work concludes that explicit handling of chance constraints through predicate erosion and feedback control is necessary for reliable STL satisfaction in stochastic settings, offering a systematic path toward dependable autonomy in uncertain environments.