PSK: A Matrix-Free Single-Loop Method for K-Level Physics-Based Control
Organizations: Meta Reality Labs.
Abstract
Physics-based control is central to robot learning, but differentiating through implicit physics steps typically requires Hessian or Karush--Kuhn--Tucker (KKT) linear solves; we ask whether gradient steps suffice. Each simulation step minimizes an energy under many contact and collision constraints. Without constraints, we view control over steps as -level optimization with strongly convex lower levels, recast as one min--max problem. Our Penalized Single-loop -level method (PSK) uses only gradients and a projection, updates all levels in parallel, and reaches an -stationary control in iterations, with a -independent exponent but a -dependent constant. Contact-rich constraints, however, typically violate a constraint qualification (CQ). We replace each constraint by a smooth wall that acts on a band of constant width. Under mild assumptions that need no CQ, every exact solution of the banded lower levels is then feasible and banded Fritz--John, and PSK keeps the complexity. Without a CQ that is uniform in the band width, however, a shrinking band loses the -independent exponent: with width and fixed , deterministic zero-respecting methods need calls on a hard instance whose control dimension grows with . We prove our assumptions for smoothed kinematic and dynamic multi-robot navigation among segment obstacles. In navigation experiments, PSK, tuned per case, reaches every goal with sixteen levels and, at equal time, reaches a lower loss than tuned unrolling in 17 of 18 cases, while implicit differentiation is lower in 10.
Figures & tables
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
| scene | model | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Corner swap | kinematic | 4 | 10 | 200 | 0.5 | 0.01 | 0.005 | 0.02 | 0.1 | 0.05 |
| 8 | 10 | 200 | 0.5 | 0.01 | 0.005 | 0.02 | 0.1 | 0.05 | ||
| 16 | 10 | 200 | 0.5 | 0.01 | 0.005 | 0.03 | 0.1 | 0.05 | ||
| dynamic | 4 | 10 | 793 | 0.1 | 0.005 | 0.00404 | 0.005 | 0.2 | 0.05 | |
| 8 | 5 | 400 | 0.1 | 0.005 | 0.008 | 0.0025 | 0.1 | 0.05 | ||
| 16 | 5 | 400 | 0.1 | 0.005 | 0.008 | 0.0025 | 0.1 | 0.05 |
| scene | model | goal err. | min slack | stop ( ) | |
|---|---|---|---|---|---|
| Corner swap | kinematic | 4 | 0.121 | 0.047 | 0.3 |
| 8 | 0.057 | 0.027 | 10 | ||
| 16 | 0.037 | 0.035 | 30 | ||
| dynamic | 4 | 0.125 | 0.037 | 3 | |
| 8 | 0.059 | 0.003 | 30 | ||
| 16 | 0.039 | 0.038 | 30 ∗ |
| exact chain loss at 90 s | ms / iteration | ||||||||
| scene | model | PSK | unroll (best ) | implicit | PSK | unroll | implicit | Newton/it. | |
| Corner swap | kinematic | 4 | 2.55 | 4.70 (5) | 2.53 | 6.2 | 20.1 | 257 | 3.6 |
| 8 | 1.63 | 2.26 (50) | 1.44 | 6.2 | 251.4 | 221 | 3.6 | ||
| 16 | 1.36 | 2.15 (5) | 3.52 | 6.4 | 83.4 | 271 | 5.8 | ||
| dynamic | 4 | 2.76 | 28.68 (5) | 2.70 | 7.2 | 24.0 | 177 | 0.0 | |
| 8 | 1.70 | 16.40 (20) | 1.50 | 6.2 | 146.4 | 263 | 11.2 | ||
| scene | model | goals reached | goal err. |
|---|---|---|---|
| Corner swap | kinematic | 4/4 | 0.04 0.00 |
| dynamic | 3/4 | 1.23 2.38 | |
| Eight-robot swap | kinematic | 4/4 | 0.03 0.00 |
| dynamic | 4/4 | 0.05 0.01 |
Robotic Control
Robotic control studies how machines use sensing and computation to produce reliable movement and interaction in changing environments.
See all 626 papers