Node identity
When does the search treat two states as the same node? Formation, the disk’s connected region, and the box’s pose, merged only when the gate agrees.
The search builds a tree of simulated states. It reaches the same physical situation by different routes all the time, and it has to recognize that, or it calls the expensive local solver Λ again and again on what is really one situation. This page explains the rule it uses to decide that two states are “the same node”, why the rule looks the way it does, and what it costs.
What a node is
A search node is a full simulator state: the box’s pose (x, z, θ), the disk’s position, and their velocities. Two states are practically never equal, so “the same node” has to mean something coarser. Whatever we choose is the node’s key: two states with the same key are duplicates, and the search keeps only the more promising one (the duplicate rule is below).
The key matters twice. In practice it decides how many Λ calls the search spends on repeats. In theory, the call bound of the paper (Orseau and Lelis’s bound for policy-guided search) holds only if states with the same key really behave alike: from either one, the same edits should succeed.
Three answers, and why we use the third
1. Round the pose to a grid. Put each coordinate in a cell (1 mm in position, 0.01 rad in angle) and key the node by its formation and its cell. This was the original search’s key. It’s simple, but the cells are arbitrary: two states 0.2 mm apart can straddle a cell boundary and become different nodes, and the grid treats every move of the disk as a new node even when nothing about the contacts changed.
2. Xiao and Ji’s contact state. Xiao and Ji (2001, Def. 6) define a contact state as a formation together with one connected region of the poses that realize it. Within that region, any pose can be reached from any other without changing contacts, so the pose inside it doesn’t matter. No grid, no resolution parameter. This is the principled object, and the construction we adopted (Decision 9).
3. Our key: collapse what we drive, keep what we don’t. Xiao and Ji assume the object is driven: in their assembly setting a robot holds it and moves it anywhere in the region. Our box is not held. It moves only when the disk pushes it. Take “box flat on the floor, disk touching nothing”: the box 10 cm from the step and the box 40 cm from the step are one Xiao–Ji contact state (the box could slide between them without changing contacts), but nothing can slide it there without the disk touching it, which is a different formation. Merging the two would let the search throw away the box near the step, which is the one the pivot needs. The disk is different: we drive it, so where it hovers inside its free region really doesn’t matter, because the next edit’s Λ call can move it anywhere there first.
So two states are the same node when they have
- the same formation σ (the recognized contacts),
- the same goal bit (whether the state is in the goal region),
- the disk in the same connected region of its in-σ positions, given the box’s pose (Xiao and Ji’s contact state over the disk’s coordinates), and
- the box’s poses within 10 mm of each other, and the hold gate giving both states the same verdict on every edit (merge by evaluation, below).
Nothing is rounded or snapped: every node keeps its real simulated state, and Λ always starts from where the previous motion actually ended.
The four examples, computed
The examples below are computed with the search’s real key code (NodeKey and the merge rule of SearchState in cmg/search, with the search’s own gate) and the old grid key, by scripts/04_node_identity.py. In all four the formation is the same: the box’s bottom face on the floor, {B:zn–E:L}.
| Pair of states | Grid (1 mm cells) | Xiao–Ji contact state | Our key, per-pose gate | Our key, relaxed gate (default) |
|---|---|---|---|---|
| disk in two places, box fixed | different | same | different | same |
| box 0.2 mm apart, across a cell boundary | different | same | same | same |
| box 5 mm apart | different | same | same | same |
| box 30 cm apart | different | same | different | different |
The grid splits the first three rows into several nodes, which only costs repeated calls. The Xiao–Ji contact state merges the last row, situations with different futures, which can lose the solution. Our key with the relaxed gate, now the default, gets all four right. (The per-pose column comes from the script; the relaxed column’s row 1 is checked by the test test_relaxed_verdicts_and_keys_ignore_the_disk_position and by the search benchmark below.)
Row 1 was a gap between the decision and the code. The decision collapses the disk’s position, but the code currently evaluates the gate at each node’s own disk position, and a different disk position can change a verdict (for example, which contacts are near enough to make). So the merge test kept the two states apart.
The fix (Decision 21, now the default): ask the gate the right question. A node’s verdict should be “is there some disk position in its region from which the box can be held through this edit?” That’s computed as a relaxation in the same hold LP: the disk’s contact becomes a contact that may slide along the reachable stretch of the face it will touch (a sliding contact on a straight face can push like either of the stretch’s two endpoints), so it’s one LP of the same size. It never rejects an edit some disk position could realize, which is the gate’s guarantee, and Λ decides where the disk actually goes. A sampled version (the gate at six disk spots) also closes the gap and was measured: 39% more accepted calls, admitted edits realized just as often, but twice the time and not guaranteed. The relaxed version’s theory is done: on a single straight stretch the two endpoint contacts are exact, not just a relaxation (their forces add up to one force at their centre of pressure), and around a corner they are exact unless the arc is very wide; the gate’s guarantee carries over, and its verdicts depend on the node’s identity alone. The suggested disk position is re-checked with the exact gate before Λ uses it.
Measured, and adopted. In short searches from the chain’s starts:
| Per-pose gate | Sampled (6 disk spots) | Relaxed (default) | |
|---|---|---|---|
| Seconds per gate evaluation | 3.45 | 21.1 | 4.40 |
| Λ’s acceptance per call | 0.27 | 0.26 | 0.36 |
| Merged nodes | 9 | 13 | 18 |
| Strict successes over 370 spread-out start–edit pairs | 45 | 60 | 119 |
With the relaxed gate, 72 of the disk-free pairs succeed (24 sampled, 9 per-pose) and 47 with the disk on the box (36). On 214 nodes it admits every edit the other two admit, with one exception that turned out to be their bug: on one formation they admit making disk contact with the disk inside the platform, because their sweep never checks the disk’s clearance from the environment (fixed Nov 8, f975f2e). The exact re-check at the suggested disk position fails on 1 of 246 admitted edits. Two implementation details differ from the theory note: the sweep still moves the disk along its contact, and the reachable stretch is computed once at the starting pose.
Merging by evaluation
How close must two box poses be to count as one node? The first plan was a radius derived from the gate’s margins: close enough that the gate provably gives the same verdict on every edit. The theory note certified the constants that radius needs, and they came out 20–40 times larger than the measured rates of change (the disk’s motor limits alone add a lot at the 30° pivot start). The certified radius on the step scene is 0.34–0.84 mm, and usually zero: rigorously, almost nothing could merge.
So the search checks instead of bounding. A new state joins an existing node’s key only if its box pose is within 10 mm of that node’s and its own gate verdicts equal the node’s for every edit. The 10 mm is only a test radius (the recognizer’s tolerance zones are 1–10 mm wide); the verdict check is what makes the merge sound, and the call bound’s proof needs nothing more. The price is one gate evaluation per would-be duplicate.
“Within 10 mm” is not transitive, so a new state is compared only with nodes the search actually made, never with ones it dropped, and joins the key of the earliest made node that passes. A dropped state can never pull a later one into its key.
Measured on searches from the chain’s starts: about half of the accepted Λ calls (18 of 37) produced duplicate candidates, 8 of which merged; the merge checks cost about 8% of the search time. Caching the gate per key cut the gate’s share of search time from 71% to 21% (1,170 → 414 s).
When a duplicate is dropped
A new child whose key is already taken is dropped only if a node already made with that key has a path probability π at least as large (Decision 13, the “safe” rule). Otherwise it is made as a new node. Dropping by first arrival instead breaks the call bound by an unbounded factor (it approaches d when the dropped node is d calls deep); re-parenting the old node to the new, more probable path breaks it too.
What changed in the search because of this
- Children are labeled by what was reached. A Λ call counts only if it succeeds and the recognizer returns exactly the requested formation; the child gets the recognized formation (before, the search stored the formation it had asked for).
- Moving within a node is part of an edit. Under these keys, a pure repositioning step always lands on its parent’s key and would always be dropped. So the disk’s motion to the edit’s transition pose is the first part of the edit’s own Λ call, not a separate search step.
- The gate is evaluated per key and cached (Decision 18), with the local sweep as a refinement at the node’s actual pose: 71% → 21% of search time.
What the measurements show
- Connected regions. Of the 328 formations (after the graph changes of Decision 19), 305 are one connected region and 23 split, 3 of them stably; none of the formations without a disk–box contact splits, and each of the chain’s eight formations is one region.
- The box is not carried across its region. When the disk pushes the box within a formation, it reached the target in 0 of 6, 0 of 6 and 2 of 6 trials on the chain’s three disk-contact formations. This is the evidence for keeping the box’s pose in the key.
- Moving the disk first helps where the disk is free. Each edit’s Λ call now begins by moving the disk within its region to where the edit starts, with the box fixed and the contacts held. Over 370 start–edit pairs spread across the chain’s formations, strict successes (exactly the target formation, the contacts held throughout) rose from 45 to 60. With the disk free, the gate admits 119 pairs instead of 51 and 24 succeed instead of 9; with the disk on the box nothing changes (36 successes), because those starts would need the box moved, which only pushing does. So the call bound’s main hypothesis, that the next edit works from every state of a node, holds only in part.
Check yourself
- Why is the disk’s position collapsed but the box’s pose is not, even though both can lie anywhere in a connected region of poses that realize σ?
- In the formation “box flush against the riser, disk away”, what does the 10 mm test do, and why doesn’t it matter? (Hint: can the box move at all without changing σ?)
- Three box poses A, B, C on a line at 0, 6 and 12 mm, same formation and disk region, the same gate verdicts everywhere, and a 10 mm test radius; each later arrival has a lower π than A, so it is dropped if its key is taken. Arrivals in the order A, C, B: which keys do C and B get? And in the order A, B, C? (Hint: is a dropped state ever compared against?)
- Why does dropping a duplicate by first arrival break the call bound, while the safe rule does not?