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

6. Candidate edits

From a node with formation σ at pose χ, Cand.legal_ops lists the edits the search may hand to the solver. There are 24 makes (set one bit), 24 breaks (clear one bit), and one transport (keep σ and move). An edit to σ′ is legal when

Transport is always legal. All 48 make/break checks run in one vmap.

python walkthrough/06_candidates.py
The script, 06_candidates.py (download) 
"""Step 6: candidate edits (Cand.legal_ops).

From a node's formation, every single-bit make and break is a candidate,
plus one transport (no change). A make or break is legal when it changes
the formation, the persisting contacts pass Supported (Hold), and every
added template is within phi_gate (Near). Print the legal edits at three
fixtures.
"""
import time

import jax
import jax.numpy as jnp
import numpy as np

from cmg.marking.candidate import Cand

from _common import fixtures, load_spec, on, template_names

spec = load_spec()
cand = Cand.from_spec(spec)
names = template_names(spec, cand.catalog)
n = len(names)
legal_ops = jax.jit(lambda q: cand.legal_ops(config=q))

for fixture in ("flat", "flat_stable_close", "toppled30_close"):
    qpos = jnp.array(fixtures()[fixture])
    start = time.perf_counter()
    ops, types = legal_ops(qpos)
    ops = np.asarray(ops)
    elapsed = time.perf_counter() - start
    formation = cand.catalog.band(config=qpos)
    print(f"== {fixture}  ({elapsed:.1f} s)")
    print("  formation:", on(formation, names))
    print("  make: ", on(ops[:n], names))
    print("  break:", on(ops[n:2 * n], names))
    print("  transport:", bool(ops[2 * n]))

Output

== flat  (22.6 s)
  formation: {B:xp-L:boundary, B:xn-L:boundary, B:yp-L:boundary, B:yn-L:boundary, B:zn-L:boundary}
  make:  {M:boundary-B:xn, M:boundary-B:yp, M:boundary-B:yn, M:boundary-B:zp, M:boundary-B:zn, B:zp-L:boundary, B:xp-S:boundary, B:yp-S:boundary, B:yn-S:boundary, B:zp-S:boundary, B:zn-S:boundary, B:xp-P:boundary, B:yp-P:boundary, B:yn-P:boundary, B:zp-P:boundary, B:zn-P:boundary}
  break: {B:xn-L:boundary, B:yn-L:boundary, B:zn-L:boundary}
  transport: True
== flat_stable_close  (0.0 s)
  formation: {M:boundary-B:xn, B:xp-L:boundary, B:xn-L:boundary, B:yp-L:boundary, B:yn-L:boundary, B:zn-L:boundary, B:xp-S:boundary, B:yp-S:boundary, B:yn-S:boundary, B:zn-S:boundary, B:xp-P:boundary, B:yp-P:boundary, B:yn-P:boundary}
  make:  {M:boundary-B:yp, M:boundary-B:yn, M:boundary-B:zp, M:boundary-B:zn, B:zp-L:boundary, B:xn-S:boundary, B:zp-S:boundary, B:xn-P:boundary, B:zp-P:boundary, B:zn-P:boundary}
  break: {M:boundary-B:xn, B:xn-L:boundary, B:yn-L:boundary, B:zn-L:boundary, B:xp-S:boundary, B:yp-S:boundary, B:yn-S:boundary, B:zn-S:boundary, B:xp-P:boundary, B:yp-P:boundary, B:yn-P:boundary}
  transport: True
== toppled30_close  (0.0 s)
  formation: {M:boundary-B:xn, B:xp-L:boundary, B:yp-L:boundary, B:yn-L:boundary, B:zn-L:boundary, B:xp-S:boundary, B:yp-S:boundary, B:yn-S:boundary, B:xp-P:boundary, B:yp-P:boundary, B:yn-P:boundary}
  make:  {M:boundary-B:yp, M:boundary-B:yn, M:boundary-B:zp, M:boundary-B:zn, B:xn-L:boundary, B:zp-L:boundary, B:xn-S:boundary, B:zp-S:boundary, B:zn-S:boundary, B:xn-P:boundary, B:zp-P:boundary, B:zn-P:boundary}
  break: {B:xp-L:boundary, B:yn-L:boundary, B:zn-L:boundary, B:xp-S:boundary, B:yp-S:boundary, B:yn-S:boundary, B:xp-P:boundary, B:yp-P:boundary, B:yn-P:boundary}
  transport: True

The first call compiles (about 22 s); later calls are fast.

What to notice

  • Makes are cheap to admit. A make keeps every current contact, so its hold test is just “is the current formation supported”, and Near is a distance threshold. At flat 16 of the 19 unset bits pass.
  • Near admits geometric nonsense. B:zp-L (the box’s top face onto the floor) is legal at flat: its gap, 0.125, is just under phi_gate (the kernels subtract about 1e−6). So are the disk on the box’s ±y faces, which the disk cannot reach because it never moves in y. The solver must reject each of them, one expensive call at a time (steps 7 and 8).
  • Breaks are where Hold bites. At flat only 3 of the 5 floor bits may be cleared; see exercise 6.2.
  • No exclusion is checked, because Cand never consults the contact graph (step 4).
  • The formation is recomputed from the band when none is supplied, as here. Inside the search, a node’s stored formation is used instead.

Code to read

src/cmg/marking/candidate.py: Cand.legal_ops, Cand.near, Cand.hold (the keep-set is new_formation & old_formation, which is the persistent-contact rule of Decision 7, bit for bit), Cand._hold_and_new (the σ′ ≠ σ check), and Cand.apply_op (how an operation index becomes a formation).

Exercises

6.1 Why is making M:boundary-B:xp illegal at flat?

Near fails: its gap is 0.14687 (step 2), above phi_gate = 0.125. The disk would have to travel around the box to reach its front face.

6.2 At flat, why are exactly B:xn-L, B:yn-L and B:zn-L breakable, and not B:xp-L or B:yp-L?

Use the midpoints from exercise 5.1. B:xn-L, B:yn-L and B:zn-L all sit at the same corner (−0.1625, −0.0625), so clearing any one of them leaves the same three distinct support points, and the box stays (marginally) supported. B:xp-L is the only contact at (−0.0375, −0.0625), and B:yp-L the only one at (−0.1625, 0.0625). Clearing either leaves two support points, and the box cannot be balanced on them. Which bits may be dropped is decided by which corner the closest-point routine happens to pick, not by the physics.

6.3 At toppled30_close, why is breaking M:boundary-B:xn illegal, and why is making B:xn-L legal?

The break would leave only environment contacts, and those fail EnvStable there (step 5): the box would fall back. The make keeps every current contact, which is supported, and the box’s −x face is within 0.125 of the floor because the box is tilted only 30°. Hold says nothing about whether the make can be realized; that is the solver’s job.

← 5. The hold LP · Next: 7. One solver call →