Background: techniques that made the chain certify
Six problems we hit while certifying the indirect lift edge by edge, the fix for each, and why each fix is sound.
Before this page: interval arithmetic, zonotopes, intervals and zonotopes together and certified funnels and composition. Each section below follows the same pattern: the problem, a tiny example, the fix, why the fix is sound, and where it showed up.
1. Index the tube by progress, not by time
Problem. A tube indexed by time asks where every state is at time \(t\). In an unstable phase, such as a box tipping over a corner, small differences in timing grow, so at a fixed time the set spreads over a wide range of tilts, and every condition must hold over that whole range.
Tiny example. Let the tilt grow as \(\theta(t)=\theta_0e^{1.2t}\) with \(\theta_0\in[0.08,0.12]\). At \(t=1.6\) the set spans tilts \(0.55\) to \(0.82\), and it keeps widening. At the tilt \(0.5\), the same motions differ only in when they arrive (times \(1.19\) to \(1.53\)), and their state there is the same tilt.
scripts/bg_certification_figures.py.Fix. Index the tube by a progress variable that the motion advances monotonically (the tilt, or the box’s position on a transport), cut it into bands, and certify that each step carries every state of a band into a later band. Timing drops out; only the transverse deviation (rate error, contact places) is carried.
Why it is sound. The certificate also proves that progress per step is at least one band, so every state leaves each band forward, and the bands cover the whole range without gaps.
In our chain. A zonotope tube for the push, indexed by time, was refused at step 14: the set spread in progress along the divergent tipping and the mean-value remainder blew up. The band tube for the same push holds (utilization 0.484).
2. Split the entry set, keep one law
Problem. A certificate over a large entry set can fail because a single box is too coarse (see bisection), not because the law is wrong.
Tiny example. On \([0.5,1]^2\) the interval lower bound of \(x\cdot y\) is \(0.25\); on the right half \([0.75,1]\times[0.5,1]\) it is \(0.375\). The same property, split, certifies where it holds.
scripts/bg_certification_figures.py.Fix. Split the entry set into sub-boxes and certify each one, with the same law on every piece. The union of the certified pieces is a certified entry set for that law.
Why it is sound. Each sub-box’s certificate holds for every state in it; the union of the sub-boxes covers the entry set; one law means the executed controller does not depend on which piece the state is in.
In our chain.
- The push after the roll: a single tube over the roll’s whole certified exit set is refused at every push magnitude (progress per step falls below one band); on a \(2\times8\) partition, 16 of 16 sub-boxes certify with one push of 0.1116 N (utilization 0.686).
- The floor-corner lift’s departure: over its whole start box the departure condition’s margin is \(-0.085\) (refused), and on \(8\times8\) pieces every piece certifies. The whole-box margin is itself the result of keeping a correlation: carrying the step-corner place as a function of the box pose (a mean-value form on the pose generators, remainder 0.5 µm) narrows it from \([60.484,61.005]\) mm to \([60.615,60.873]\) mm and raises the whole-box margin from \(-0.470\) to \(-0.085\) (same hull, different set).
3. Choose the pivot in interval elimination
Problem. Solving a linear system whose coefficients are intervals by Gaussian elimination divides by the pivots. If a pivot’s interval contains or nearly contains zero, the quotient blows up, and every later quantity inherits the blow-up.
Tiny example. Solve \(\begin{bmatrix}\varepsilon&1\\1&1\end{bmatrix}x=b\) with \(\varepsilon\in[-0.01,0.01]\). Pivoting on \(\varepsilon\) divides by an interval containing \(0\): no bound at all. Swapping the rows and pivoting on \(1\) gives the next pivot \(1-\varepsilon\in[0.99,1.01]\): perfectly tame.
Fix. Order the rows by pivoting on the coefficients’ midpoints [1]; fix that order for the evaluation; and still check that every pivot’s interval excludes zero.
Why it is sound. Any row order gives the same solution set; the interval elimination is sound for whichever order is used, provided no pivot interval contains zero, and that is checked.
In our chain. In the landing’s impact window, the make class with both the step corner and the platform’s far support sticking used a fixed order whose first pivot was near zero. Pivoting on the midpoints cut the census of the cover from \(1.7\times10^7\) to \(4.7\times10^4\) pieces. Two soundness audits checked certified cells against sampled trajectories and exact arithmetic: on the earlier landing set, 1000 cells, 906,497 step checks and 176,540 exact rational solves of that system; on the current landing set’s preview roots, 463 cells, 221,192 step checks and 76,830 exact solves. In all, 1,127,689 step checks (0 states outside the propagated zonotopes, 0 excluded classes taken) and 253,370 exact solves (0 outside the enclosure, 0 pivot enclosures containing zero).
4. A kink inside one formation: the support-switch band
Problem. Inside a single contact formation the force model can change: on the platform transport, the flush contact’s left support moves from the step corner to the box’s own corner as the box slides past half its width. The margins are smooth on either side but have a kink at the switch, and a band that straddles the switch cannot use either model alone.
Tiny example. Model A’s margin is \(0.30-0.25x\), model B’s is \(0.1625+0.30(x-0.55)\), and the true margin follows A before \(x=0.55\) and B after it. On a band \([0.43,0.67]\) across the switch, the bound \(\min(A,B)\) is valid wherever the state actually is.
scripts/bg_certification_figures.py.Fix. Near the switch, the band’s step image is the hull of both models’ enclosures, each condition’s bound is the minimum over both, and the two support conditions only define which piece each state is on. A term that is implied by a piece’s own support condition may be dropped only on that model’s piece.
Why it is sound. At every state in the band the true dynamics is one of the two models, so the true next state lies in one of the two enclosures (hence in their hull) and every true margin is at least the smaller bound.
In our chain. With the switch band, the goal transport ends at a section past the switch, where the rest at the goal certifies with both supports on the box’s corners, instead of a 32 µm window before it.
5. One contact definition, three readers
Problem. The recognizer (which contacts are on), the certifier’s reduction (which constraints a formation imposes) and the planner’s gate must agree on what a contact is. If one reader sees a contact that is not there, the others certify the wrong thing.
Tiny example. Two edges that are parallel and within the tolerance of each other, but meet only at a single point that another closed contact already holds, look “flush” to a distance test. Under Xiao and Ji’s rule a contact counts only if it is not contained in a larger one, so that pair is not a separate contact.
Fix. Apply Xiao–Ji containment [2] on the actual contact region, with no new constant, in all three readers. The certifier’s version must be a sound sufficient form of the recognizer’s: whenever the certifier says “contained (open)”, the recognizer must too; the two are cross-tested.
Why it is sound. A sufficient form can only refuse more, never certify a contact reading the recognizer would not produce.
In our chain. The recognizer read the box’s bottom face flush with the riser for box positions \(x_B\in[61.5,63.5]\) mm, although the two edges meet only at the step corner, already in the platform contact. That phantom contact stopped a certified transport short of the lift goal. Under the containment rule (issue #53) it is gone, and the 200 held-out and 34 test searches are re-run under it.
6. Keep the speed continuous at a junction
Problem. If one funnel ends at one speed and the next funnel’s law demands a much higher speed at once, the step after the junction needs a large acceleration, and the forces that produce it can leave their friction cones.
Tiny example. Raising a tilt rate from 1°/s to 8°/s within one \(10\) ms step is an angular acceleration of about \(12\) rad/s², far more than the slow, held motion before the junction ever needed.
Fix. Keep the incoming speed: certify the next funnel with a law that starts at the previous funnel’s speed, from the previous funnel’s certified exit.
Why it is sound. The junction is then an ordinary certified containment (composition): the next funnel is verified with its entry equal to the previous certified exit.
In our chain. The floor-corner lift ends at 1°/s. The roll at 8°/s could not be certified from the lift’s exit: the junction failed on the step corner’s friction cone and on the exclusion of other contact classes. The roll at 1°/s, verified from the lift’s certified exit, holds (utilization 0.2435), and its own certificate to the 88.16° hand-off holds at 0.376 with 765 of 765 held-out rollouts inside.
What to remember
- Index tubes by progress, not time, wherever the motion is unstable.
- Split the entry set, keep one law; the union of certified pieces is certified.
- Pivot on midpoints and check every pivot excludes zero; the order changes the bound, not the soundness.
- At a kink inside a formation, take the hull of both models and the minimum of both bounds.
- One contact definition for every reader; the certifier’s form is a sound sufficient version of the recognizer’s.
- Keep speeds continuous at junctions, and compose from certified exits.
Further reading
- Neumaier [1]: interval Gaussian elimination, pivoting and the conditions under which it is sound.
- Jaulin et al. [3]: subpavings, splitting a set into certified pieces.
- Xiao and Ji [2]: principal contacts and the containment rule behind one contact definition for every reader.
- Mason [4]: friction cones, quasi-static pushing and the mechanics behind the force models and their switches.
- Stewart and Trinkle [5]: time-stepping with contact and Coulomb friction, the kind of step map our certificates bound.
- Burridge, Rizzi and Koditschek [6]: why a junction must be a containment of certified sets.