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}\!} $$

Edits

How one contact state leads to the next: make, break, transfer, the rare compound edge, and the step chain.

The menu of edits

An edit changes a formation σ into a neighbor σ′. It is built from elementary changes:

Change What it does Example on the step
make(c) adds a contact make(s): push the box against the riser
break(c) removes a contact break(gv): lift the box’s corner off the floor
transfer(c → d) replaces a contact by one it contains, or the reverse g → gv: the box starts to tip onto its corner; sv → t: it lands on the platform
transport changes no contact; moves the pose toward the goal slide the box along the floor

Containment is Xiao and Ji’s (Def. 8): d is contained in c when d’s features are c’s or boundary elements of them. A transfer uses one-sided containment (their cases 2–3): one feature stays, and the other is an edge and one of its own end vertices. The box edge flat on the floor (g) shrinks to its corner on the floor (gv); the box side on the platform (t) shrinks to the box side on the step corner (sv). On the step there are 56 such pairs among the 40 templates.

Break and transfer to a contained contact relax; make and transfer to a containing contact constrain. Transport is offered only when the current formation holds the box.

When several contacts change at once

A set of elementary changes on different templates is an edge when:

  • they all relax or all constrain (Xiao and Ji’s containment between formations, Def. 9);
  • the result is valid;
  • every smaller nonempty subset of the changes gives an invalid formation.

A single valid change is always an edge. A compound edge is a set of changes that cannot be made one at a time. Moving the disk from −xB to −zB is not one edge: breaking mx first leaves a valid formation. The disk goes round the box corner in two transfers, through its contact with the vertex.

On the step every compound edge is the pivot or its reverse:

{mx, g, s} ⇒ {mx, gv, sv}.

Tipping the box on its corner lifts its side off the riser at the same instant. Both one-at-a-time intermediates, {mx, gv, s} and {mx, g, sv}, are excluded. The pivot appears in 64 contexts (the other contacts of the formation), so there are 128 compound edges, some of them in contexts no pose realizes, because the validity stand-in is only pairwise (Issues). The implementation enumerates compound edges of up to three changes; a search up to four finds no others on the step.

The marking graph

The marking graph has the valid formations as vertices and the edits as edges: 37,203 vertices on the step. Checked exhaustively in the test suite:

  • every edge lands on a valid formation and has its reverse;
  • the graph is connected;
  • with at most k changes per edge, the graph distance between σ and σ′ lies between |σ △ σ′|/(2k) and |σ △ σ′| (the symmetric difference);
  • a brute force over sets of two or three single steps finds exactly the implemented compound edges.

The step chain

With the disk free at the start, a plan for the step is the walk

{g} → {mx, g} → {mx, g, s} ⇒ {mx, gv, sv} → {mx, sv} → {mx, t} → {t} → {mz, t} → transport,

that is: make mx, make s, the pivot, break gv, transfer sv → t, break mx, make mz, and transport.

The box near the step corner, labeled by the recognizer. Left: resting on the corner alone, {sv}. Middle: landed with +xB on the platform and overhanging the corner. vS is the end of the platform edge the box rests on, so the box’s contact with vS is not principal, and the formation is {t}. Right: clear of the corner, still {t}.

The box near the step corner, labeled by the recognizer. Left: resting on the corner alone, {sv}. Middle: landed with +xB on the platform and overhanging the corner. vS is the end of the platform edge the box rests on, so the box’s contact with vS is not principal, and the formation is {t}. Right: clear of the corner, still {t}.

Landing is a transfer. Once +xB lies on the platform, vS is a boundary element of the touching platform edge, so the landed box realizes {t}, and sliding it clear of the corner changes no contact. Support is unaffected: t’s contact set ends at the corner, so the landed box is held exactly when its center of mass is over the platform.

Cand, the candidate generator, offers every step of the chain from a pose in its formation, provided the hold gate passes. Breaking gv needs the box tilted well past 30° with the disk low on its face (the hold gate).

Reproduce

cd ~/repos/research/c-gnn && git switch phase1/planar && git pull && cd cmg
JAX_PLATFORMS=cpu PYTHONPATH=tests .venv314/bin/python -m pytest -q tests/test_planar_step2.py
JAX_PLATFORMS=cpu .venv314/bin/python <website>/research/nonprehensile/planar-build/scripts/03_xiao_ji.py <out dir>

03_xiao_ji.py prints the counts on this page (templates, containment pairs, valid formations, compound edges).

← Contact states · The hold gate →