GENESIS

Learning to select search algorithms under a joint compute + physical budget.

GENESIS studies a resource-rational question: when a controller is given a portfolio of complete search algorithms (A*, Dijkstra, greedy best-first) and a finite energy budget, does reinforcement learning teach it to pick the right algorithm for each map — cheap search when a rough answer suffices, expensive optimal search only when it pays off? It's the orchestration problem behind a routing engine ("which planner do I run for this query?"), studied in a fast, fully-controllable 2D grid world.

A PPO controller (it orchestrates search; it does not navigate) chooses among:

action	effect	cost
Plan-A* / Plan-Dijkstra / Plan-Greedy	run that algorithm over the known map (budget-capped) → store a route	energy = nodes expanded × PLAN_UNIT
Follow	walk the stored route on the true grid; re-plan on a wall/terrain surprise	energy per step
Sense	reveal a disc of the map (under fog)	flat
Idle	wait	small "life-support" energy

Maps are 128×128, procedurally generated (random / rooms / maze / trap "comb" families), with weighted terrain (rough patches cost more to walk) and an optional fog of war. Because the energy budget can't afford a full optimal search on every map, the algorithm choice matters — that is the whole experiment.

This is v2. The original design (13 sub-algorithmic atoms + a PAIRED adversarial curriculum) is preserved in the codebase and history but was superseded — see CLAUDE.md for the full arc and the reasons for the redesign.

Key finding (honest, and it is a negative)

The central bet — that a controller under a compute+physical budget learns which search algorithm to deploy per map — was measured on 2026-08-18 and does not hold. The interesting part is that we can now say precisely why:

• The agent does not select, and it is right not to. On the fog-off run the pre-registered test |corr(map roughness, Plan-A* usage)| > 0.3 comes back at +0.109. A* (3.1%) and greedy (3.8%) are used equally and both are marginal.
• There is almost nothing to select. Deploying each algorithm alone under identical energy accounting, the per-map oracle (Virtual Best Solver) beats the single best algorithm by only a few percent. Dijkstra wins 0% of maps — with an admissible Manhattan heuristic and terrain costs

  = 1, A* provably never expands more, so it is a dominated action. And the trained agent already sits ~3 points below the ceiling of its own toolkit. The controller is not underperforming; the instrument is blunt.

• Turning fog off was the mistake. It bought +10 points of raw success and destroyed every interesting behaviour. Under fog the same system buys information adaptively (Sense 6.5% on open maps vs 27.6% on cluttered, corr +0.281) and re-plans continuously (10.4 plans/episode, 92% of episodes); with fog off it collapses to plan-once-then-idle (Idle 53.9%, Sense 0%). We optimised raw success and it walked us out of the regime worth studying.

So the project's own measurements now point somewhere sharper than algorithm selection — which is one-shot, full-information, and solved since SATzilla (2008). The live question is embodied metareasoning: when thinking and moving draw on one budget under partial observability, the right amount of compute changes mid-episode as sensing reveals structure. No fixed algorithm and no one-shot selector can do that, and two of the three required behaviours already emerged on their own.

Everything above is reproducible from checkpoints via genesis/experiments/ (see docs/RESUME.md and docs/Audit_and_Tier1_Plan_2026-08.md).

Stack

JAX (jax[cuda12]), Equinox, Optax, Distrax, chex — no PyTorch/TF in the core loop. Everything is JAX-native (jit + vmap, fixed-shape lax.scan), so the environment and the search algorithms batch across hundreds of parallel worlds on one GPU. Native Python 3.12 in a WSL2 (Ubuntu-24.04) venv.

Quick start

source .venv/bin/activate                       # deps pinned in requirements.lock.txt
JAX_PLATFORMS=cpu python -m pytest -q            # 125 tests (env, search kernel, portfolio, training)

# train the v2 portfolio controller at 128x128 (fog off = the selection-learnable regime)
GENESIS_SIZE=128 GENESIS_ENVS=32 GENESIS_UPD=2000 GENESIS_FOG=0 \
XLA_PYTHON_CLIENT_PREALLOCATE=false python -m genesis.train_v2

# watch it live in a browser (episode replays + per-algorithm usage; nothing saved to disk)
python -m genesis.watch runs/v2_128_nofog/ckpt --fog       # -> http://localhost:8000

Run knobs are environment variables: GENESIS_SIZE, GENESIS_ENVS, GENESIS_UPD, GENESIS_FOG (0 = off), GENESIS_WARM=<ckpt> (carry a trained agent into a changed environment), GENESIS_TAG. Training checkpoints every eval and resumes the same command after a crash; changing the environment config auto-starts fresh (a fingerprint guard).

Repository layout

genesis/
  config.py         EnvConfig — the static world definition (size, budget, terrain, fog, topologies)
  generate.py       solvable-by-construction map generation (BFS flood-fill) + topology families
  portfolio.py      the generic budget-capped best-first kernel (A*/Dijkstra/greedy, one scan)
  portfolio_env.py  v2 environment: PortfolioState + Plan/Follow/Sense/Idle action space
  train_v2.py       PPO training driver (resume, warm-start, metrics logging)
  watch.py          live browser dashboard (episode replays + algorithm-usage analytics)
  network/ppo/…     Equinox actor-critic, clipped PPO, GAE, running obs-normalizer, instrumentation
  primitives.py, env.py, paired.py, …   the v1 system (13 atoms + PAIRED), kept for reference/ablation
tests/              125 tests — solvability, search optimality vs BFS, budget accounting, training smokes
docs/               RESUME.md (handoff), the design proposals, and the research roadmap

Where to go next

• docs/RESUME.md — one-page state + prioritized next actions (baselines & VBS, multi-seed, the correlation measurement). Start here to continue the work.
• CLAUDE.md — the full design brief, locked decisions, and the complete development history.
• docs/Portfolio_Redesign_Proposal_2026-07.md — the v2 design rationale and how "beats all algorithms" is measured (Virtual Best Solver).

Status

Environment, all v2 primitives, the search portfolio, PPO training (with resume/warm-start/live dashboard), and the v1 system are implemented and tested (125 tests green). The open scientific work is the measurement layer — per-algorithm baselines, the Virtual Best Solver oracle, and multi-seed headline runs — and confirming the fog-off selection result. See docs/RESUME.md.