Skip to main content
$$ % Define your custom commands here \newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}} \newcommand{\E}{\mathbb{E}} \newcommand{\P}{\mathbb{P}} \newcommand{\S}{\mathbb{S}} \newcommand{\R}{\mathbb{R}} \newcommand{\S}{\mathbb{S}} \newcommand{\norm}[2]{\|{#1}\|_{{}_{#2}}} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\pdd}[2]{\frac{\partial^2 #1}{\partial #2^2}} \newcommand{\vectornorm}[1]{\left|\left|#1\right|\right|} \newcommand{\abs}[1]{\left|{#1}\right|} \newcommand{\mbf}[1]{\mathbf{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\bm}[1]{\boldsymbol{#1}} \newcommand{\nicefrac}[2]{{}^{#1}\!/_{\!#2}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\dd}{\operatorname{d}\!} $$

Certified funnels

Each edge of the contact-formation graph becomes a certified transition: every state of its entry set, for every disk friction in the band, reaches the next edge’s entry set. Chained, the edges certify a plan as executed, including motions that use momentum.

The idea

The hold gate and the box certificate certify that the box can be held at every pose along a plan. A funnel certifies the motion itself:

  • Entry set. A box of states the edge may start from: pose, velocity, contact offsets, and μdisk ∈ [0.3, 0.5].
  • Law and tube. A feedback law and a tube around its nominal motion.
  • Certificate. For every state in the entry set and every friction in the band, the motion stays in the tube, the contact forces stay inside their cones and above a derived floor, the motor stays in its box, and the edge ends inside the next edge’s entry set.
  • Check. The certified edge is executed in MJX from measured states, and the measured coverage is reported at 95/95.

Edges whose sets compose this way form a chain that is certified end to end. The box no longer has to be held at every instant, so rolls, landings in motion and coasting become plannable edges.

Track C: a chain with a landing in motion

The chain tips the box, pivots it on the step corner, breaks and remakes contact, rolls it over the corner, pushes it so that it lands on the platform in motion, and transports it to the goal.

Piece Certified MJX from real entry states
Tip (held departure) yes —
Pivot to 59.00° (law switch at 23°) yes 932 / 932
Stop at 59.00° yes, with the derived force floor 768 / 768
Gentle break, then make(mz) pressing along the inward normal yes 300 / 300
Break(gv) delivering the box to the roll yes 687 / 687
Roll over the corner being re-certified from the 62° junction pending
Push and landing in motion follows the roll pending
Transport to the goal follows the landing pending

The roll is re-searched because the junction at 62° failed: a jump from the break’s 1°/s to the roll’s 8°/s violates the sticking cone at the hand-off. The re-search includes ramped speed profiles. The best certified candidates so far keep 1°/s through the junction.

The landing impact is measured, not certified

Every piece above is certified by interval arithmetic. Each quantity is carried as a range guaranteed to contain its true value, the state box is pushed through the dynamics step by step, and each condition is checked over the whole box at once.

That fails over the few steps around the landing impact. The reason is the wrapping effect. Intervals store only axis-aligned boxes. Each step shears and rotates the set, and re-wrapping it in a box adds empty corners that compound.

A line segment rotated by 45° shows it. The smallest box around the rotated segment is a square, so the width grows by √2. After 8 such rotations the box is 16 times wider, while the true set is still a segment. At impact the velocities flip and couple strongly to where the box hit. The box grows until nothing can be proved, and splitting it would need about 1010 pieces.

The impact window is therefore stated by measurement: every MJX landing ends at rest in the target formation, reported at 95/95.

A set-based route: zonotopes

Background: zonotope propagation derives the operations below, with proofs, and maps each funnel check onto them.

The remedy is to certify a set shape that a step maps without re-wrapping. A zonotope is

c + G · [−1, 1]k,

a centre plus a linear image of a cube.

  • A linear step maps it exactly. It just multiplies G. A nonlinear step is linearized, its Jacobian multiplies G, and only the small remainder is boxed. In validated integration this is Lohner’s method, the first-order Taylor form.
  • Checks stay cheap. The minimum of a linear quantity a·x over the zonotope is a·c − Σ|a·G|. Force floors and friction cones cost about what they cost on boxes.
  • General polytopes don’t scale. Their face and vertex counts grow exponentially with the dimension, and a nonlinear map does not map a polytope to a polytope.
  • The hard part is the contact switch. At impact, part of the set is already in contact and part is not. The set has to be split along the contact guard and each part followed in its own mode. A hybrid zonotope, a union of constrained zonotopes indexed by binary factors, represents exactly such a mode-branched set (Bird, Pangborn, Jain and Koeln, Automatica 2023; for nonlinear steps, Siefert et al., ACC 2023).

First test. One impact branch and one small entry sub-box, with the first-order form (a chain-rule Jacobian with an interval remainder) intersected with the interval box at each step. The decision test was the size of the entry boxes on which every rocking class after the impact is excluded. Those boxes grew from 2−4 to 2−2 per coordinate, 212 in volume over the window’s six coordinates, against a bar of 210 set beforehand.

Step by step the picture is mixed:

  • The make step encloses the reached set 29–213 times tighter in volume.
  • The steps before impact gain almost nothing.
  • The tail step alone is looser than the interval box, which is why the two are intersected.

The other branches and the rest of the landing set are untested.

NoteIf the zonotope route works

If zonotopes certify the impact window over the whole landing set, the landing becomes a certified link, and set-based certificates for contact-rich funnels deserve to be pursued well beyond this chain.

Justin Koeln and Justin Ruths at UT Dallas work on exactly these set representations: hybrid zonotopes for reachability of mixed logical dynamical systems, and the zonoLAB toolbox (arXiv 2310.15426). That line would be a natural collaboration.

Where this goes next: the Roadmap.

Back to the overview