{"data":{"kind":"file","path":"README.md","version_id":"y9ecsvqz9foqgcxzhersyyav","entry":{"name":"README.md","path":"README.md","is_directory":false,"size":8822,"modified_at":"2026-07-07T04:50:51.947000","content_hash":"18901cd582c972539dee1d87439add13fde375b035d914c07e1420690a9e6628"},"entries":[],"content":"# bimanual-chore-scheduling\n\nMinimum-makespan chore orchestration for a two-arm household robot — the\nsecond rung of a robotics vertical built with the same validation discipline\nas its siblings ([robot-cycle-time](https://github.com/JWilksBooth/robot-cycle-time),\n[economic-dispatch](https://github.com/JWilksBooth/economic-dispatch),\n[dcopf-grid-verifiers](https://github.com/JWilksBooth/dcopf-grid-verifiers),\n[multiperiod-dispatch](https://github.com/JWilksBooth/multiperiod-dispatch),\n[n1-contingency-dispatch](https://github.com/JWilksBooth/n1-contingency-dispatch),\n[nodal-pricing-lmp](https://github.com/JWilksBooth/nodal-pricing-lmp)).\nRung 1 asks *how fast can the arm move*; this rung asks *what should the\nrobot do next*. A bimanual robot (two arms with different end-effectors,\nhence different per-arm task times) faces a chore set — a laundry chain\nwhose washer/dryer cycles run unattended, batches of dishes contending for\nthe sink and dishwasher, filler chores, bimanual tasks needing both arms —\nunder precedence and exclusive stations, on an integer-minute grid, in\nminimum total time. **The mathematics is industrial machine tending** (arms\nserving long autonomous machine cycles, work packed into cycle windows)\nwearing a household skin; the isomorphism is documented, not hidden.\n\nThe naive answer this environment defeats is greedy longest-first list\nscheduling (LPT, the standard dispatching heuristic): it starves the short\nchain-head tasks that gate the machine cycles and takes long both-arm bait\nfirst. On a measured **100% of instances the greedy schedule is suboptimal**\n— a structural property of the task class (any root chore baits LPT away\nfrom a chain head; measured across a 14-config sweep and reported the same\nway the sibling reports its structural sync-failure rate) — by a\n**median 36.5% makespan premium** (N=200; the calibrated dial, see\n[CALIBRATION.md](CALIBRATION.md)).\n\n## Task\n\nGiven the task table (types: `arm` — choose an arm, per-arm durations;\n`bimanual` — both arms; `machine` — no arm, runs alone), station lists,\nprecedence, and the start cap: output\n`{\"schedule\": [[\"<task>\", \"<arm>\", <start>], ...]}` — every task exactly\nonce. Rewards: format (0.10), feasibility (0.40 — positive-proof check of\narm/station occupancy incl. one dual-station task, precedence at chosen-arm\ndurations, label/type consistency), and makespan (0.50 —\n`exp(−5·(M−M*)/M*)`, hard-gated on feasibility, fail-closed below M*).\n\n## Ground truth validation\n\nTwo independently implemented solvers in **different paradigms** must agree\non the minimum makespan M* for every dataset instance:\n\n- **Primary:** time-indexed MILP (scipy/HiGHS dual bounds closed to\n  optimality; decoded schedule re-graded by the reward function itself).\n- **Cross-check:** CP-SAT interval model (ortools; constraint propagation —\n  different vendor, different algorithm class, different encoding), written\n  from the spec text only, by an implementer who never read the primary.\n\n| Metric (200 instances, seeds 0–199) | Result |\n|---|---|\n| M* disagreements between paradigms | **0 / 200** |\n| M*−1 refutation certificates (both solvers, exact INFEASIBLE status) | 0 failures / 400 |\n| Anti-vacuity controls (M ≤ M* attained at exactly M*) | 0 failures / 400 |\n| Greedy schedule grader-feasible (validates horizon + grader semantics) | 200 / 200 |\n| Greedy suboptimal (premium rate) | **100% (structural)** |\n| Median premium | 36.5% |\n| Raw-draw rejection rate (survivor-bias indicator) | 0.0% |\n\n**Exact-certificate property:** scheduling on an integer-minute grid means\nthere are NO tolerances anywhere — the grader, both solvers, and the\ncertificates share exact integer semantics, so M*−1 is *proven infeasible\nunder the grader's own rules* and no numerical slack can buy a shorter\ncertified schedule. (The first cross-check implementation — a disjunctive\nbig-M MILP — agreed on every M* but needed up to 22 minutes per refutation\ncertificate; it was replaced by CP-SAT, ~50,000× faster on the worst case,\nand the dead end is documented with its measurements in\n[CALIBRATION.md](CALIBRATION.md).)\n\n## Anti-reward-hacking (18 regression-tested attack gates)\n\nSingle shared parse gate: format-invalid answers cascade to zero on all\nthree rewards (invariant asserted across the whole attack corpus). Gates\ncover: the greedy shortcut and blind serialization (honest partial credit,\nstrictly separated); NaN/Infinity literals, >4300-digit integers, bracket\nbombs, null bytes (all score 0 without crashing); duration-injection killed\nby fixed arity; duplicate/omitted/phantom tasks (multiset check on the raw\nlist); arm-swap compression (chosen-arm duration used in occupancy AND\nprecedence AND makespan); two-sided one-minute boundary probes at every\nresource type; dual-station occupancy; label/type mismatches (bimanual\nlabeled \"left\" frees no arm); sub-M* compression (fail-closed); Arrow\nround-trip identity on the real dataset rows; determinism. An adversarial\npass (100+ crafted payloads, 10,000-schedule parse fuzz, 60,000-schedule\nfeasibility fuzz vs an independent oracle) found zero reward exploits.\n\n## Usage\n\n```bash\npip install -e .\nN_INSTANCES=200 python tests/test_validation.py   # needs: pip install ortools==9.11.4210\npython calibration/measure.py --n 200             # difficulty sweep\n\n# give frontier models room to reason; -r 1 matches published baselines\nvf-eval bimanual-chore-scheduling -p anthropic -m <model> -n 50 -r 1 --max-tokens 16000\n```\n\nLower token budgets truncate reasoning mid-derivation and score as format\nfailures — published baselines use exactly the line above.\n\n```python\nimport verifiers as vf\nenv = vf.load_environment(\"bimanual-chore-scheduling\", num_examples=300)\n# disjoint train/eval: load_environment(1000) + load_environment(200, seed_offset=1000)\n```\n\nInstance generation: median 0.23 s per instance including the M* solve\n(mean 0.32 s, worst 1.41 s over 12 seeds). Fully deterministic per seed.\n\n## Baselines\n\n50 examples, 1 rollout each, `--max-tokens 16000` (reproduce with the\n`vf-eval` line above; `-m claude-haiku-4-5` / `-m claude-opus-4-8`):\n\n| Model | Mean reward | Format | Feasibility | On completed rollouts |\n|---|---|---|---|---|\n| Haiku 4.5 | 0.269 | 0.98 | 0.22 | fails on feasibility — cannot track the minute-grid packing |\n| Opus 4.8 | 0.820 | 0.82 | 0.82 | **41/41 non-truncated → exact optimum (reward 1.0)** |\n\nRead these honestly. The Haiku→Opus gap is large and real: Haiku parses the\ntask (format 0.98) but collapses on feasibility (0.22) — it writes schedules\nthat double-book an arm or violate a minute boundary. Opus, given the tokens,\n**saturates**: every one of its 41 non-truncated rollouts is a certified\noptimum, and its entire 0.180 gap from 1.0 is the 9/50 rollouts that\ntruncated at 16k tokens mid-derivation (mean output 5.8k tokens; the\nminute-by-minute reasoning is long), scoring 0.0 for want of a final JSON\nobject — not a single feasible-but-suboptimal answer among them. So at the\nshipped 12–26-task size this environment **discriminates sharply between\nHaiku-class and Opus-class reasoning but does not measure frontier headroom**\n(cf. the vertical's saturated control, economic-dispatch). Larger instances\n(more tasks, tighter horizons) are the lever for frontier discrimination —\ntracked as a v0.2 knob, not shipped unmeasured.\n\n## Instance generation\n\n12–26 tasks: the laundry chain (always), 2–4 dish batches (p=0.75), fillers\nand bimanual root tasks sized so greedy's failure is *measured, not\nassumed* — the difficulty distribution, the knobs that control it, and the\nconfig that shipped are in [CALIBRATION.md](CALIBRATION.md), along with the\nstylizations (compressed cycle times, two-arm task abstraction) stated\nplainly.\n\n## Roadmap\n\n- **v0.2 (frontier headroom): capacity-2 stations.** A structural analysis\n  plus an Opus 4.8 mini-probe (documented in [CALIBRATION.md](CALIBRATION.md))\n  established that at this instance size the optimum equals the closed-form\n  arithmetic lower bound on ~93% of instances, so a frontier model that isn't\n  truncated finds it exactly — no config knob moves M\\* more than +2 above the\n  bound, and the compact regime saturates the same way (7/7 exact on completed\n  rollouts). A shared resource that admits *two* concurrent occupants turns\n  station timing into genuine cumulative-resource packing that no closed-form\n  bound reads off, breaking the saturation while preserving the exact-MILP +\n  dual-certificate validation spine (a one-line capacity change, unlike\n  stochastic durations or preemption which would rewrite it).\n- v0.3: task durations imported from rung-1 (robot-cycle-time) motion\n  solutions — connecting the vertical's layers with real numbers; stochastic\n  durations; task preemption.\n","encoding":"utf-8","truncated":false,"total_bytes":8822},"status":null}