Methods
1. Representation
All geometry lives in integer decimetres (1 unit = 0.1 m). A plan is:
- a boundary: a rectilinear polygon stored as disjoint axis-aligned cells (rectangle, L, U);
- rooms: one axis-aligned rectangle per programme room, with a type;
- doors: segments on shared walls (or, for the entrance, on an exterior wall), width 0.9 m (1.0 m entrance);
- windows: segments on exterior walls of rooms that want daylight or exterior contact;
- circulation: explicit rooms of circulation type (hall, corridor, entrance, reception) — never implied by leftover space.
Integer coordinates make overlap, containment, shared-wall length and exterior-wall length exact set operations. Containment against an L or U boundary is tested as "sum of intersections with the disjoint cells equals the rectangle's area"; exterior walls are found by clipping a 1-unit strip outside each room edge against the cells. Unassigned floor area is allowed and counted against area efficiency; rooms are not required to tile the boundary.
2. Programme
A programme (src/core/types.ts: Program) fixes the boundary, the room list with [minArea, maxArea] and minDim, daylight and exterior preferences in [0, 1], required and preferred adjacencies, no-door and no-adjacency separations, the entrance room, an accessibility flag, and a trip list for the circulation objective. validateProgram rejects impossible programmes with necessary-condition checks: area sum vs. boundary area; every room's minimum rectangle fits some cell; adjacency/separation contradictions; adjacency degree vs. maximum achievable perimeter (d × 11 dm ≤ 2(minDim + maxArea/minDim)); references and ranges. Passing these does not guarantee feasibility — that is exactly what the benchmark measures.
3. Door and window policy (deterministic)
Doors are a pure function of the room rectangles (src/core/doors.ts):
- every required adjacency with ≥ 11 dm of shared wall gets a door;
- every preferred adjacency with ≥ 11 dm of shared wall gets a door unless a separation forbids it;
- a Prim-style spanning tree from the entrance adds the fewest extra doors needed for connectivity, preferring walls that touch circulation rooms, then longer walls;
- the entrance room gets an exterior door on its longest exterior segment (≥ 12 dm).
No other doors exist. Windows: each exterior segment ≥ 0.6 m of a room with daylight or exterior preference gets a centred window covering 40 % of the segment. Because doors and windows are derived, every method competes on room geometry only, and the door graph — which drives circulation, privacy and connectivity — is identical for identical rectangles regardless of who produced them.
4. Validity (hard constraints)
validatePlan returns a list of violations; a plan is valid iff the list is empty. Codes: MISSING_ROOM, EXTRA_ROOM, OVERLAP (positive-area intersection), OUT_OF_BOUNDS (any area outside the cells), MIN_DIM, AREA_MIN, AREA_MAX, REQUIRED_ADJACENCY (shared wall < 11 dm), SEPARATION (shared wall for no-adjacency; a door for no-door), DOOR_INVALID (not on a shared wall of its two rooms / not on an exterior wall / too narrow), NO_ENTRANCE_DOOR, DISCONNECTED (unreachable from the entrance through doors), ACCESSIBILITY (when the programme demands it: circulation ≥ 1.2 m wide, bathrooms/WCs ≥ 1.5 m clear square), NON_INTEGER. Every violation carries a continuous magnitude (dm, dm² or count) so search can descend a penalty; magnitude never affects validity.
Nothing invalid enters a result: the evaluator only computes objectives for valid plans; the archive stores only valid plans; the report re-validates every stored front plan and aborts if any fails.
5. Objectives (raw, explicit)
| Key | Direction | Definition |
|---|---|---|
| efficiency | max | (Σ area of non-circulation rooms) / boundary area |
| adjacency | max | fraction of preferred adjacencies with ≥ 11 dm shared wall (required ones are hard) |
| circulation | min | trip-weighted mean of shortest paths (m) through the door graph: nodes are room centroids and door points, edges are straight lines inside a room (always visible in a rectangle), Dijkstra |
| compactness | max | mean over non-circulation rooms of clip(1 − (aspect − 1.5)/2.5, 0, 1); circulation rooms count 1 |
| daylight | max | Σ_r daylight_r · daylit(r) / Σ_r daylight_r, where daylit(r) is the exact fraction of the room's area within 6 m of one of its windows (each window projects a strip inward, widened sideways by the same depth, clipped to the room; the union area is computed by coordinate compression). 6 m ≈ 2.5 × a 2.4 m window head — the standard daylit-zone rule of thumb. It is a proxy, not a daylight simulation |
| privacy | max | mean over private rooms (bedroom, bathroom, WC, study) of ½·[all its doors open onto circulation or private rooms] + ½·clip((door-depth from entrance − 1)/2, 0, 1); wet rooms opening into a public space lose a further 0.25 |
| exposure | max | Σ_r exterior_r · [room r has ≥ 1 m of exterior wall] / Σ_r exterior_r |
| accessibility | max | mean of [circulation width ≥ 1.2 m], [bathroom clear square ≥ 1.5 m], [entrance door ≥ 1.0 m], graded linearly below the threshold |
| carbon | min | partition length × 2.7 m × 25 + boundary perimeter × 2.7 m × 90 + area × 60 kgCO2e (see CARBON.md) |
Five headline objectives (efficiency, circulation, daylight, privacy, carbon) define dominance, the archive and hypervolume. All nine are stored raw with every plan. Normalisation to a minimisation vector in [0, 1] uses task-level references (circulation: 2 × boundary diagonal; carbon: envelope + slab floor to a worst-case partition upper bound), so hypervolume is comparable within a task only.
6. Methods
All methods share the evaluator, the door policy, the validator and the 0.5 m snapping grid.
| Id | Class | Summary |
|---|---|---|
| random | baseline | Sequential random non-overlapping placement: each room draws uniformly random feasible-size rectangles until one is disjoint from those placed (≤ 50 draws). Everything else is left to chance. |
| greedy | constructive heuristic | Constraint-ordered placement (entrance, then BFS over required adjacencies by degree and area, then the rest). Candidates are every grid offset flush against a host room's sides (required-adjacency anchors when placed, else all placed rooms) or, for the first room, against a boundary edge. Partial feasibility (containment, overlap, separations, required adjacency, entrance exterior wall, connectivity invariant) filters candidates; a local score (exterior wall when wanted, shared wall, aspect, mid-range area, perimeter for hub rooms) ranks them; a GRASP restricted candidate list (α = 0.25) picks one at random; depth-first backtracking (≤ 4 alternatives per room, ≤ 800 nodes) recovers from dead ends. Random restarts until budget. |
| sa | metaheuristic | Simulated annealing on rectangles with a feasibility-first energy: valid plans score 100 × weighted normalised objectives, invalid ones 100 + penalty. Moves: shift, resize, swap, abut (flush against a — preferably required — neighbour), align (edge to neighbour edge), slide (gravity until contact), relocate. Geometric cooling from a calibrated T₀ to T₀/1000 with restarts from the incumbent after 400 rejections. The budget is split evenly across six scalarisation weight vectors (uniform + each headline objective emphasised); the union of the runs' valid plans is the front. |
| sa-seeded | hybrid | Same SA, but each weight run starts from a greedy construction (whose candidate checks are charged) and from a 20 × cooler T₀. |
| nsga2 | multi-objective EA | NSGA-II with constraint-domination (any valid beats any invalid; invalid ordered by penalty), population 60, binary tournament on (rank, crowding), the SA move set as mutation (p = 1/n per room). Crossover is off by default: uniform per-room crossover at p = 0.9 and 0.3 produced 0 valid plans on medium-001 at 20k evaluations versus 1 519 at p = 0; recombining rectangles from two parents almost always reintroduces overlaps. |
| cp | constraint search | Depth-first assignment of (w, h, x, y) per room over the finite grid domain with the same corner-point candidate generator and partial-feasibility filter as greedy, an area-sum forward check, randomised value ordering, bounded branching (24 per node), size sub-sampling (6 shapes per room per node) and restarts every 4 000 nodes. Every complete assignment satisfies containment, overlap, separations, required adjacency and accessibility by construction; connectivity and no-door separations are checked by the evaluator. Purpose-built; not an industrial CP-SAT engine. |
| gradient | analytic placement | Continuous boxes (cx, cy, w, h) minimised with Adam (250 steps, lr 1.5) on a hand-differentiated energy: pairwise overlap (ramped 1→10), notch obstacles, log-area target, min-side and aspect hinges, required-adjacency attraction, no-adjacency repulsion, exterior attraction for daylight rooms. Snapped to the grid, sizes rounded to the nearest feasible shape, legalised by a ring search that moves each room to the nearest non-overlapping in-bounds position. Included because it is the floor-plan analogue of global placement + legalisation in VLSI, i.e. a classical differentiable method; it makes no learning claim. |
| llm | experimental | An OpenAI-compatible chat model proposes room rectangles as JSON; the proposal is snapped, doors are derived and the validator's messages are fed back for up to two repair rounds. Runs only with FPB_LLM_BASE_URL / _API_KEY / _MODEL set. It is not a geometry algorithm and is reported separately. |
7. Budget accounting
Every run gets 50 000 evaluation-equivalents. A full evaluation (doors + validation + objectives) is one unit. Partial work is charged at measured rates on this machine (src/bench/timing.ts):
| Work unit | Measured cost vs. a full evaluation | Charged |
|---|---|---|
| candidate rectangle check (greedy, cp): containment + overlaps + shared walls against placed rooms | 0.006–0.015 | 0.01 |
| gradient step (all rooms, O(n²)) | 0.34–1.2 | 0.5 |
| cache hit on an identical layout | free | 0 |
Consequently greedy and CP spend most of their budget on candidate checks and produce few, always-valid, full evaluations; SA/NSGA-II spend it on full evaluations of mostly-invalid neighbours. Wall-clock time is recorded as elapsedMs; the convergence trace samples a cheap 4 000-sample Monte-Carlo hypervolume estimate every 500 budget units (not the exact value used for the reported hypervolume), so it no longer dominates wall-clock the way an exact hypervolume of a 200-point archive did in an earlier version of the harness. The evaluator also exposes a computeMs/overheadMs split (elapsed time minus instrumentation) for future runs; the canonical run reported here predates the reporting code that reads it, so runtime in this report is plain elapsedMs.
8. Metrics
- Solved: share of (task × seed) runs with ≥ 1 valid plan. Valid plans per run, valid share of evaluations, budget to first valid plan (from the trace).
- Hypervolume: exact WFG recursion on the 5 headline objectives, reference point 1.0001⁵; Monte-Carlo (20 000 fixed-seed samples) on all 9.
- Front size, diversity (mean pairwise Euclidean distance of the normalised front).
- Union front per task across all methods and seeds, with per-method share of points and exclusive hypervolume contribution.
- Paired comparisons: per-task medians over seeds, two-sided Wilcoxon signed-rank over tasks (normal approximation, tie and continuity corrections), Holm-adjusted; percentile-bootstrap CIs for mean differences; wins/losses/ties.
- Weight sensitivity: 300 Dirichlet(1) weightings of the headline objectives; per (weight, task) the method whose per-seed fronts hold the best scalarised plan (median over seeds) wins; Kendall τ between the algorithm ranking under uniform weights and under each random weighting.
- Complexity scaling: all of the above against rooms, constraint count, boundary kind, fill ratio and accessibility.
9. Reproducibility
pnpm bench:canonical regenerates programmes, runs every (task, method, seed) that is not already on disk for the current core hash, and rebuilds the summary, fronts and gallery. The core hash is per algorithm: it covers everything under src/core except the other methods' generator files, so editing one method (as happened during development — a constraint-search restart-cadence bug and a missing compaction step in analytic placement were fixed) invalidates only that method's cached runs, not the whole 1 960-run set. Each run record stores programme id, method, seed, parameters, budget, grid, git SHA, that hash, timestamps, evaluations, validity counts, the front (objectives, normalised vectors, geometry), the convergence trace, the violation histogram and machine info. Records with a stale hash for their algorithm are ignored by the report. PRNG: xoshiro128** seeded by splitmix32 — identical streams in Node and the browser.