Technical Summary: Sampling-Based Control via Entropy-Regularized Optimal Transport

Problem Statement

Sampling-based Model Predictive Control (MPC) methods, such as Model Predictive Path Integral (MPPI) and the Cross-Entropy Method (CEM), are widely used for real-time control of nonlinear robotic systems, particularly where gradients are unavailable or dynamics are discontinuous. However, these methods rely on information-theoretic objectives (e.g., KL divergence) that are agnostic to the geometric structure of the control space.

This geometric agnosticism leads to two primary failure modes:

1. Mode-Averaging: MPPI aggregates samples via a weighted average. In complex, multimodal cost landscapes (e.g., navigating around an obstacle), this results in control commands that blend distinct local minima, often steering the robot directly into obstacles rather than choosing a valid path around them.
2. Mode-Seeking: CEM avoids averaging by selecting "elite" samples, but this aggressively commits to a single mode, limiting exploration and potentially causing the algorithm to miss viable solutions in favor of a local optimum.

Existing solutions often rely on post-hoc heuristics (e.g., annealing schedules, covariance adaptation) that do not fundamentally alter the variational objective. The paper argues that a foundational shift is required to incorporate spatial information into the optimization process.

Methodology: OT-MPC and Sinkhorn Coordinate Descent

The authors propose OT-MPC (Optimal Transport MPC), a sampling-based algorithm derived from an Entropy-Regularized Optimal Transport (EOT) formulation. Instead of minimizing information-theoretic divergence, OT-MPC minimizes the cost of transporting probability mass between candidate control sequences and low-cost proposals, explicitly incorporating geometric proximity.

Core Algorithm: Sinkhorn Coordinate Descent (SCD)

The optimization engine is Sinkhorn Coordinate Descent (SCD), a gradient-free algorithm that evolves a set of $N$ particles (candidate control sequences) toward a target distribution using $M$ proposals.

1. Formulation: The problem is framed as finding an optimal coupling $\Gamma$ between particles $z$ and proposals $y$ that minimizes a transport cost $c(z, y)$ regularized by entropy $H(\Gamma)$.
2. Alternating Optimization:
   • Coupling Update: Given fixed particles, the optimal coupling $\Gamma$ is computed efficiently using the Sinkhorn algorithm. This step factors in both the cost of the proposals and the geometric distance between particles and proposals.
   • Particle Update: Given the coupling, particles are updated. For quadratic costs, this update has a closed-form solution: each particle moves toward the weighted barycenter of its coupled proposals.
   • Relaxation: A step-size parameter $\eta$ is used to stabilize updates, particularly when proposals are resampled at every iteration.
3. Proposal Distribution: To balance exploration and exploitation, proposals are sampled from a mixture distribution: a fraction $\rho$ is drawn from a global distribution (e.g., uniform or broad Gaussian), while the remainder are local perturbations of existing particles.

Key Theoretical Properties

• Biconvexity: The objective function is biconvex in the particles and the coupling, ensuring unique solutions for subproblems.
• Monotone Descent: The algorithm guarantees a non-increasing sequence of objective values.
• Convergence: The iterates converge to a stationary point.
• Generalization: SCD generalizes MPPI; in the limit where the number of particles $N=1$ or the regularization $\epsilon \to \infty$, SCD recovers the standard MPPI importance-weighted average.

Key Contributions

1. Algorithmic Innovation: The proposal of SCD and its instantiation as OT-MPC. Unlike existing sampling methods, SCD updates particles based on both cost and geometric proximity, enabling local refinement while preserving diversity across modes.
2. Theoretical Guarantees: Establishment of theoretical properties for SCD, including monotone descent, convergence guarantees, and closed-form updates for quadratic costs (and other specific cost functions like circular distance and Log-Euclidean metrics).
3. Empirical Validation: Demonstration that OT-MPC achieves higher success rates than MPPI, CEM, and Stein Variational MPC (SV-MPC) across diverse robotics tasks, particularly those with multimodal cost landscapes.

Experimental Results

The authors evaluated OT-MPC on navigation, manipulation, and locomotion tasks, comparing it against MPPI, CEM, and SV-MPC.

• Car Obstacle Avoidance (Kinematic Bicycle): In dense obstacle fields ("Hard" setting), OT-MPC achieved a 93.5% success rate compared to 88.5% for MPPI. The performance gap widened in complex environments where MPPI suffered from mode-averaging.
• 2D Push-T (Contact-Rich Manipulation): OT-MPC achieved a 76% success rate, significantly outperforming MPPI (4%) and CEM (46%). SV-MPC failed entirely (0%) due to the lack of differentiable gradients in hybrid contact dynamics.
• Quadrotor Obstacle Avoidance (12-DOF): In medium and hard dense obstacle settings, OT-MPC achieved 100% and 92% success rates, respectively, compared to 60% and 19% for MPPI. MPPI frequently failed to find feasible paths, getting stuck in local minima.
• Cooperative Load Carrying (Two Quadrotors): In a task requiring precise coordination through a narrow wall opening, OT-MPC achieved 75% success in the "Hard" setting versus 10% for MPPI. The narrow bottleneck exacerbated MPPI's mode-averaging issues, disrupting coordination.
• Franka Push-T (3D Manipulation): OT-MPC achieved 66% success, comparable to a heavily tuned MPPI (64%), but required significantly less hyperparameter tuning effort.
• Quadruped Locomotion (Unitree Go2): OT-MPC demonstrated superior efficiency, requiring fewer average steps to reach goals in ramp climbing and box pushing tasks compared to MPPI.

Computational Overhead: While the Sinkhorn step adds computational cost ($O(NM)$ vs. $O(M)$ for MPPI), the authors report that OT-MPC often achieves comparable or faster wall-clock times. This is because the transport coupling extracts more information per sample, allowing the algorithm to use fewer proposals (rollouts) to achieve convergence.

Significance and Claims

The paper claims that OT-MPC addresses the fundamental limitations of information-theoretic sampling methods by replacing the KL divergence with an Optimal Transport objective. This shift allows the controller to:

• Preserve Modes: Avoid the "mode-averaging" that leads to collisions in multimodal environments.
• Coordinate Updates: Maintain ensemble diversity while refining candidates toward promising local regions.
• Operate Without Gradients: Remain compatible with black-box simulators and non-smooth dynamics, similar to MPPI.

The authors position OT-MPC not merely as a heuristic improvement but as a foundational change in how sampling-based control aggregates information, leveraging the geometric structure of the control space to achieve robust performance in complex, contact-rich, and high-dimensional robotic tasks. They acknowledge limitations, such as the dependency on proposal coverage for exploration and the need for careful tuning of the entropy regularization parameter $\epsilon$, but assert that the method offers a principled alternative to existing state-of-the-art sampling controllers.