arah2/.planning/quick/261026-d95-alt-direction-split-isolated-research-si/261026-d95-PLAN.md

gsd_plan_version, mode, task, quick_id, slug, date, branch, base_commit, autonomous

gsd_plan_version	mode	task	quick_id	slug	date	branch	base_commit	autonomous
1.0	quick	Prove and measure isolated asymmetric directional ALT bidirectional search	261026-d95	alt-direction-split-isolated-research-si	2026-10-26	research/alt-direction-split	ceb71c2	true

Quick task 261026-d95: Isolated direction-split ALT research

Objective

Establish whether a sound asymmetric, direction-split ALT bidirectional search exists for this directed ARG2 graph with sentinel fringes, and whether it actually improves the fixed-seed KL workload. This is a research sidequest on research/alt-direction-split only: never edit the shipped routing/src/astar.ts, routing/src/index.ts, baseline fixture, bot/web integrations, or the separate /home/C-Fu/araharah checkout; never merge into main or claim the Worker budget is met without a measured passing gate. Reference docs/ALT-DIRECTION-SPLIT.md, routing/src/{astar,graph,landmark}.ts, and the existing routing scripts/tests. No ROADMAP update.

Must-haves

• A written, checkable derivation before experimental code separates P-1 (each directional heuristic's edge consistency) from P-2 (a valid bidirectional meeting invariant and stopping bound), including directed edges, stale heap entries, signed potentials, unreachable pairs, and 0xffff transitions. A counterexample or impossibility result is an honest outcome; do not implement a search with an unproved stop rule.
• Isolated experiments (only if both proofs succeed) compare seconds and reachability with Dijkstra on synthetic directed/sentinel cases and a fixed seeded real-graph sample. The shipped A1/625 test, D-03 frozen record, and original routeAstar remain the controls, never altered to make an experiment pass.
• Same-pair, warmed, host-relative expansion and CPU measurements against shipped haversine fallback are reported, including p95 and the 8 ms gate status, with missing binary/runtime and inconclusive results explicitly marked NOT MEASURED rather than PASS. Final verdict states proof status, counterexamples, optimality violations, expansion ratio, and budget verdict; experimental code stays on this branch.

Tasks

task 1: Derive P-1 and P-2, including sentinel boundary docs/ALT-DIRECTION-SPLIT-EXPERIMENT.md First confirm branch/HEAD and clean status in this checkout; read the handoff and existing BH reductions/meet probes. Define table-indexing and quantized lower bounds without treating `0xffff` as numeric distance. For **every traversable directed edge** `u→v`, prove the forward `h_f(u) ≤ c(u,v)+h_f(v)` and backward (reverse-search) `h_b(v) ≤ c(u,v)+h_b(u)` independently; do NOT infer P-2 from these inequalities. Account for max-with-haversine, search-scoped landmark selection, and actual edges across finite↔sentinel cells; a per-node family skip is not automatically consistent. Explicitly examine whether graph-wide clean-column selection on this 0/24-clean binary makes ALT inert; propose a different rigorously proved frontier/domain mechanism only if required and possible. Derive the precise keys, bridge-meeting costs, v-independent offsets (or a conservative stopping lower bound), treatment of stale keys/reopenings, and termination when one frontier empties; algebraically show why the criterion implies no undiscovered cheaper path. Test proof claims on hand-calculated oneway ring/bridge/island counterexamples. If no correct nontrivial sentinel policy or meet rule is established, record a NO-GO counterexample/unresolved obligation and stop before coding the search. test -s docs/ALT-DIRECTION-SPLIT-EXPERIMENT.md && grep -q 'P-1' docs/ALT-DIRECTION-SPLIT-EXPERIMENT.md && grep -q 'P-2' docs/ALT-DIRECTION-SPLIT-EXPERIMENT.md && grep -q '0xffff' docs/ALT-DIRECTION-SPLIT-EXPERIMENT.md Document contains independently checkable inequalities and stop-rule proof or an explicit NO-GO with counterexample, including finite/sentinel cross-edge and disconnected-component cases, before any search code. task 2: Implement branch-only experimental runner and adversarial oracle checks, conditional on proof routing/scripts/experiment-alt-direction-split.mjs, routing/test/alt-direction-split-experiment.test.mjs Only after task 1 establishes P-1 **and** P-2 with an executable sentinel rule: add a separate maintainer-time experiment script exporting a testable `routeDirectionSplit` and counters; do not import it from production, change shipped ASTAR, or change existing A11's ban on `landmarkFrom` in `astar.ts`. Match ARG2 semantics (row `[l*n+v]`, floor-quantized edge costs, bit0 forbidden in both traversal directions) and validate/reconstruct paths with exact traversable edge seconds. Implement exactly the proven potential pair, reduced costs, meeting updates and stop criterion; assert reduced-cost non-negativity on test graphs, fail loud for violated proof assumptions rather than substituting an unproved shortcut. Write new tests using `encodeGraph`/`decodeGraph` + `landmarkTables`: exhaustive directed ring + flagged mirrors + incoming spur, one-way bridge in BOTH travel directions, isolated anchored/unanchored components, origin/goal and interior sentinel cells, mixed clean/dirty columns, equal-cost alternatives and unreachable nulls; check every pair against independent Dijkstra, including paths' legal edges and symmetric seconds delta. Use a targeted adversarial edge where a per-node sentinel mask would violate consistency. If task 1 is NO-GO, do not create this runner/tests; document the blocked verification in the experiment record instead. if grep -q '^Verdict: NO-GO' docs/ALT-DIRECTION-SPLIT-EXPERIMENT.md; then test ! -e routing/scripts/experiment-alt-direction-split.mjs; else test -s routing/scripts/experiment-alt-direction-split.mjs && npm run routing:test && npm run routing:typecheck; fi Proof-qualified branch-only experiment passes adversarial oracle tests and preserves full existing suite; or NO-GO prevents unsupported code. If Node/npm unavailable, report tests NOT RUN (never green). task 3: Measure fixed-seed oracle and paired CPU/expansions; record honest verdict routing/scripts/experiment-alt-direction-split.mjs, docs/ALT-DIRECTION-SPLIT-EXPERIMENT.md For a proof-qualified candidate, run the experiment against the **same** compared 200 seeded cross-metro pairs as `measure-astar-oracle-sweep.mjs` (seed `0x08f1`, oversample 3x, 12 km floor, snap misses reported), with independent Dijkstra and symmetric ±1e-6 s verdict/class checks; additionally run A1 full suite and the existing D-03 frozen-record gate unchanged. Use the seeded `0x08a1` 100-pair extended workload for paired experimental-versus-shipped searches: same snapped endpoints, warm-up printed separately, count settled expansions per direction, report misses outside routed p95, median/mean/p95 CPU, expansion ratio and host/Node/version/graph SHA-256; alternate run order or repeated rounds to reduce JIT/thermal order bias. Shipped `routeAstar` with 0/24 clean columns is the **haversine-only control** for the present binary; instrument it only via an isolated copy/runner if needed and verify bit-identical costs before comparison. The original `measure-route-cpu.mjs --extended` budget gate is a separate shipped-control run and a FAIL exit is a measurement, not an instruction to weaken the gate. The gitignored ARG2 graph is available read-only at `/home/C-Fu/araharah/routing/data/kl-roadgraph.v1.bin`: if missing locally, link into this checkout's gitignored `routing/data/` only after verifying no existing path and binary ARG2; never write the target or any file in the other checkout. If unavailable/undecodable or Node/npm missing, record NOT MEASURED; never claim a speedup or PASS from synthetic data or 0 active landmarks. Report proof+oracle+expansion+p95 outcomes with a GO/NO-GO verdict and next-step recommendation confined to a later separately approved phase. Do not merge/integrate. test -s docs/ALT-DIRECTION-SPLIT-EXPERIMENT.md && test -z "$(git diff --name-only ceb71c2 -- routing/src/astar.ts routing/src/index.ts routing/test/fixtures/alt-baseline.json .planning/ROADMAP.md)" && test "$(git branch --show-current)" = research/alt-direction-split Document prints the oracle and paired workload results with provenance and explicit gate statuses, or explains exactly why a proof or measurement blocked execution; no production/baseline/main-checkout changes.

Verification and guardrails

At execution, ensure Node/npm are actually available (this planning shell currently reports node: command not found; do not pass an absent-runtime gate). Use npm run routing:test, npm run routing:typecheck, node routing/scripts/measure-optimality-gate.mjs, and node routing/scripts/measure-route-cpu.mjs --extended where available; record expected budget-gate FAIL honestly. Existing measure-astar-oracle-sweep.mjs measures shipped search, not the experiment: inject the candidate into the exported sweepOracle core or reproduce its exact seeded pair-selection/oracle contract in the isolated runner, labeling each separately. A missing real graph must never be counted as a 0/200 success (the shipped sweep's SKIP exits 0). Verify scope at end with git status --short, git branch --show-current, and git diff --name-only ceb71c2; inspect any untracked experiment files separately. No production deployment, no main merge.

Outcome

Completion means either a proved and measured branch-only search with 0 optimality violations and transparent steering/cost numbers, or a precise NO-GO identifying the failed proof/benchmark. The 8 ms Worker gate remains FAIL unless directly measured to pass on a representative free-plan host; a local CPU win alone cannot retire the budget concern.