"use strict"; (() => { const __modules = Object.create(null); __modules["src/domain/planning-policy.js"] = (() => { const SEARCH_CONTRACT_VERSION = "mapf-search/1.0"; const COMPARISON_CONTRACT_VERSION = "solved-only-canonical/3.0"; const searches = Object.freeze({ priorityFirst:Object.freeze({id:"customPriority",label:"Custom Priority Heuristic",description:"Binnode priority-inheritance and yield heuristic. No joint cost optimality claim."}), spacetime:Object.freeze({id:"prioritizedReservation",label:"Prioritized Reservations",description:"Agents are planned sequentially against earlier reservations; no joint cost optimality claim."}), cbs:Object.freeze({id:"sumOfCosts",label:"Sum of Costs",description:"CBS orders conflicts by summed final arrival ticks. Unit move/wait costs; final-goal occupancy persists. Search is bounded; optimality is not certified."}) }); function searchContractFor(strategy) { const spec = searches[strategy]; return spec ? {contractVersion:SEARCH_CONTRACT_VERSION,objective:spec.id,label:spec.label,description:spec.description, goalBehavior:"stay-at-final-goal",timeUnit:"logical-tick",optimality:"not-certified",comparisonControlsSearch:false} : null; } function compareObjectiveLabel(profile) { return ({balanced:"Balanced",throughput:"Completion First",makespan:"Makespan First",lowWait:"Low Wait"})[profile] || profile; } function comparisonContractFor(profile) { const order = {balanced:["weightedScore:desc"],throughput:["validatedCompletionOnly"], makespan:["makespan:asc","waitTicks:asc","sumOfCosts:asc"],lowWait:["waitTicks:asc","makespan:asc","sumOfCosts:asc"]}; return {contractVersion:COMPARISON_CONTRACT_VERSION,objective:profile,label:compareObjectiveLabel(profile), eligibleResults:"validated-solved-only",ties:"all-equal-comparison-keys",scope:"cached-candidates-not-global-optimality", method:profile === "balanced" ? "weighted-score" : profile === "throughput" ? "completion-only" : "lexicographic", orderedBy:order[profile] || [],scalarScoreAvailable:["balanced","throughput"].includes(profile), runtimeBreaksTies:false,reference:"deterministic-display-only; no unique winner implied", changesSearch:false,legacyProfileId:profile === "throughput" ? "throughput" : null}; } return { SEARCH_CONTRACT_VERSION, COMPARISON_CONTRACT_VERSION, searchContractFor, compareObjectiveLabel, comparisonContractFor }; })(); __modules["src/domain/comparison-policy.js"] = (() => { const { comparisonContractFor } = __modules["src/domain/planning-policy.js"]; const profiles = new Set(["balanced","throughput","makespan","lowWait"]); function eligibleForComparison(row) { return !!row && row.status === "SOLVED" && row.valid === true && row.costsAvailable === true && !row.pending && !row.runtimeFailure && !row.unavailable && [row.makespan,row.waitTicks,row.sumOfCosts,row.completed,row.totalAgents,row.validationConflicts].every(value => Number.isSafeInteger(value) && value >= 0) && row.totalAgents > 0 && row.completed === row.totalAgents && row.validationConflicts === 0; } function objectiveScore(row, profile = "balanced") { if (!profiles.has(profile) || !eligibleForComparison(row)) return null; if (profile === "throughput") return 1; if (profile !== "balanced") return null; return 1e12 + 4e10 + row.completed * 1e7 - row.makespan * 1000 - row.waitTicks * 50 - row.validationConflicts * 100000; } function comparisonKey(row, profile = "balanced") { if (!profiles.has(profile) || !eligibleForComparison(row)) return null; if (profile === "makespan") return [row.makespan,row.waitTicks,row.sumOfCosts]; if (profile === "lowWait") return [row.waitTicks,row.makespan,row.sumOfCosts]; if (profile === "throughput") return [0]; return [-objectiveScore(row,profile)]; } function compareKeys(a, b) { for (let index = 0; index < a.length; index++) { if (a[index] < b[index]) return -1; if (a[index] > b[index]) return 1; } return 0; } function compareSummaries(a, b, profile = "balanced") { const left = comparisonKey(a,profile), right = comparisonKey(b,profile); if (!left || !right) return left ? -1 : right ? 1 : 0; return compareKeys(left,right); } function reweightSummary(row, profile) { return {...row, compareObjective:profile, comparison:comparisonContractFor(profile), comparisonModel:comparisonContractFor(profile).contractVersion, rankKey:comparisonKey(row,profile), score:objectiveScore(row,profile)}; } function rankComparisons(results, profile) { const rows = Array.isArray(results) ? results : []; const objective = profile ?? rows.find(row => row && row.compareObjective)?.compareObjective ?? "balanced"; const candidates = rows.filter(row => comparisonKey(row,objective) !== null); if (!candidates.length) return {reference:null,leaders:[],tied:false,solved:false,objective}; const best = candidates.reduce((a,b) => compareSummaries(b,a,objective) < 0 ? b : a); const leaders = candidates.filter(row => compareSummaries(row,best,objective) === 0); const order = ["priorityFirst","spacetime","cbs"]; const ordered = [...leaders].sort((a,b) => { const ai = order.indexOf(a.strategy), bi = order.indexOf(b.strategy); if (ai >= 0 || bi >= 0) return (ai < 0 ? order.length : ai) - (bi < 0 ? order.length : bi); const ak = String(a.strategy || a.name || ""), bk = String(b.strategy || b.name || ""); return ak < bk ? -1 : ak > bk ? 1 : 0; }); return {reference:ordered[0],leaders,tied:leaders.length > 1,solved:true,objective}; } return { eligibleForComparison, objectiveScore, comparisonKey, compareSummaries, reweightSummary, rankComparisons }; })(); __modules["src/validation/input-validator.js"] = (() => { const INPUT_LIMITS = Object.freeze({snapshotBytes:1048576, maxWidth:52, maxHeight:34, maxAgents:24, maxPlanTicks:10000, maxPlanPositions:250000, maxIssues:200}); const SOLVER_IDS = Object.freeze(["priorityFirst", "spacetime", "cbs"]); const OBJECTIVES = Object.freeze(["balanced", "throughput", "makespan", "lowWait"]); const TRAFFIC_SCENARIOS = Object.freeze(["cross", "random", "corridor"]); const GOAL_RULES = Object.freeze(["endpoint", "randomGoal"]); function isRecord(value) { return value !== null && typeof value === "object" && !Array.isArray(value); } function isCell(value, grid) { return isRecord(value) && Number.isInteger(value.x) && Number.isInteger(value.y) && value.x >= 0 && value.y >= 0 && value.x < grid.w && value.y < grid.h; } function inputIssue(code, field, message) { return {code, field, message}; } function validateScenario(scenario) { const issues = []; const add = (code, field, message) => { if (issues.length < INPUT_LIMITS.maxIssues) issues.push(inputIssue(code, field, message)); }; if (!isRecord(scenario)) return {ok:false, issues:[inputIssue("INVALID_SCENARIO", "scenario", "Scenario must be an object.")]}; const {grid, robots} = scenario; if (!isRecord(grid) || !Number.isInteger(grid.w) || !Number.isInteger(grid.h) || grid.w < 2 || grid.h < 2 || grid.w > INPUT_LIMITS.maxWidth || grid.h > INPUT_LIMITS.maxHeight) { return {ok:false, issues:[inputIssue("GRID_LIMIT", "grid", "Grid dimensions must be integers from 2 x 2 through 52 x 34.")]}; } if (!Array.isArray(grid.cells) || grid.cells.length !== grid.h) return {ok:false, issues:[inputIssue("GRID_SHAPE", "grid.cells", "Grid row count does not match its height.")]}; for (let y = 0; y < grid.h; y++) { const row = grid.cells[y]; if (!Array.isArray(row) || row.length !== grid.w) add("GRID_SHAPE", "grid.cells[" + y + "]", "Grid column count does not match its width."); else for (let x = 0; x < grid.w; x++) if (row[x] !== 0 && row[x] !== 1) add("INVALID_CELL_VALUE", "grid.cells[" + y + "][" + x + "]", "Cells must be 0 (free) or 1 (blocked)."); } if (issues.length) return {ok:false, issues}; if (!Array.isArray(robots) || robots.length < 1 || robots.length > INPUT_LIMITS.maxAgents) return {ok:false, issues:[inputIssue("AGENT_LIMIT", "robots", "Scenario must contain 1 through 24 agents.")]}; const starts = new Set(); const goals = new Set(); for (let i = 0; i < robots.length; i++) { const robot = robots[i]; if (!isRecord(robot)) { add("INVALID_AGENT", "robots[" + i + "]", "Agent must be an object."); continue; } if (robot.id !== undefined && robot.id !== i) add("INVALID_AGENT_ID", "robots[" + i + "].id", "Agent IDs must match their zero-based array index."); for (const role of ["start", "goal"]) { const p = robot[role]; if (!isCell(p, grid)) { add("INVALID_COORDINATE", "robots[" + i + "]." + role, "Agent coordinates must be in-bounds integers."); continue; } if (grid.cells[p.y][p.x] !== 0) add("BLOCKED_ENDPOINT", "robots[" + i + "]." + role, "Agent start and goal cells must be free."); const used = role === "start" ? starts : goals; const k = p.x + "," + p.y; if (used.has(k)) add("DUPLICATE_ENDPOINT", "robots[" + i + "]." + role, "Duplicate " + role + " cell."); used.add(k); } } for (const field of ["bufferCells","endpointCells"]) { if (scenario[field] !== undefined && (!Array.isArray(scenario[field]) || scenario[field].length > grid.w * grid.h || scenario[field].some(p => !isCell(p,grid) || grid.cells[p.y][p.x] !== 0))) add("INVALID_MARKERS", field, "Scenario markers must be free in-bounds cells."); } return {ok:issues.length === 0, issues}; } function validateGeneratorConfig(config) { const issues = []; if (!isRecord(config)) return {ok:false, issues:[inputIssue("INVALID_CONFIG", "config", "Scenario configuration must be an object.")]}; const bounds = {width:[12,52], height:[10,34], agents:[2,24], density:[0,38], seed:[1,999999]}; for (const [field, [min,max]] of Object.entries(bounds)) if (!Number.isInteger(config[field]) || config[field] < min || config[field] > max) issues.push(inputIssue("CONFIG_RANGE", field, field + " must be an integer from " + min + " to " + max + ".")); if (!TRAFFIC_SCENARIOS.includes(config.trafficScenario)) issues.push(inputIssue("UNKNOWN_SCENARIO", "trafficScenario", "Unknown traffic scenario.")); if (!GOAL_RULES.includes(config.goalMode)) issues.push(inputIssue("UNKNOWN_GOAL_RULE", "goalMode", "Unknown goal rule.")); return {ok:issues.length === 0, issues}; } function validateSolverOptions(options) { if (!isRecord(options)) return {ok:false, issues:[inputIssue("INVALID_OPTIONS", "options", "Solver options must be an object.")]}; const issues = []; if (!SOLVER_IDS.includes(options.strategy)) issues.push(inputIssue("UNKNOWN_SOLVER", "strategy", "Unknown solver ID. No fallback was executed.")); for (const field of ["objectiveProfile","compareObjective"]) { if (options[field] !== undefined && !OBJECTIVES.includes(options[field])) issues.push(inputIssue("UNKNOWN_OBJECTIVE", field, "Unknown comparison objective.")); } if (options.objectiveProfile !== undefined && options.compareObjective !== undefined && options.objectiveProfile !== options.compareObjective) issues.push(inputIssue("OBJECTIVE_MISMATCH", "compareObjective", "Compare objective and its legacy alias must agree.")); if (options.searchObjective !== undefined && (options.strategy !== "cbs" || options.searchObjective !== "sumOfCosts")) issues.push(inputIssue("UNSUPPORTED_SEARCH_OBJECTIVE", "searchObjective", "Only CBS exposes a fixed Sum of Costs search objective in this build.")); for (const name of Object.keys(options)) if (!["strategy", "objectiveProfile", "compareObjective", "searchObjective"].includes(name)) issues.push(inputIssue("UNKNOWN_OPTION", name, "Unsupported solver option: " + name + ".")); return {ok:issues.length === 0, issues}; } function normalizeSolverOptions(options) { const profile = options.compareObjective || options.objectiveProfile || "balanced"; return {strategy:options.strategy,objectiveProfile:profile,compareObjective:profile,...(options.strategy === "cbs" ? {searchObjective:"sumOfCosts"} : {})}; } return { INPUT_LIMITS, SOLVER_IDS, OBJECTIVES, TRAFFIC_SCENARIOS, GOAL_RULES, isRecord, isCell, inputIssue, validateScenario, validateGeneratorConfig, validateSolverOptions, normalizeSolverOptions }; })(); __modules["src/core/grid-search.js"] = (() => { function rng(seed) { let a = seed >>> 0; return function() { a += 0x6D2B79F5; let t = a; t = Math.imul(t ^ t >>> 15, t | 1); t ^= t + Math.imul(t ^ t >>> 7, t | 61); return ((t ^ t >>> 14) >>> 0) / 4294967296; }; } function clamp(v, lo, hi) { return Math.max(lo, Math.min(hi, v)); } function key(p) { return p.x + "," + p.y; } function same(a, b) { return a.x === b.x && a.y === b.y; } function manhattan(a, b) { return Math.abs(a.x - b.x) + Math.abs(a.y - b.y); } function inBounds(x, y, w, h) { return x >= 0 && y >= 0 && x < w && y < h; } function isFree(grid, x, y) { return inBounds(x, y, grid.w, grid.h) && grid.cells[y][x] === 0; } function neighbors(grid, p, includeWait) { const dirs = [[1,0],[-1,0],[0,1],[0,-1]]; const out = []; for (const d of dirs) { const x = p.x + d[0]; const y = p.y + d[1]; if (isFree(grid, x, y)) out.push({x, y}); } if (includeWait) out.push({x:p.x, y:p.y}); return out; } function astar(grid, start, goal) { if (!isFree(grid, start.x, start.y) || !isFree(grid, goal.x, goal.y)) return null; const open = [{p:start, g:0, f:manhattan(start, goal), parent:null}]; const best = new Map([[key(start), 0]]); let guard = 0; while (open.length && guard++ < 20000) { open.sort((a, b) => a.f - b.f || a.g - b.g); const cur = open.shift(); if (same(cur.p, goal)) return unwind(cur); for (const np of neighbors(grid, cur.p, false)) { const g = cur.g + 1; const k = key(np); if (!best.has(k) || g < best.get(k)) { best.set(k, g); open.push({p:np, g, f:g + manhattan(np, goal), parent:cur}); } } } return null; } function unwind(node) { const path = []; let n = node; while (n) { path.push({x:n.p.x, y:n.p.y}); n = n.parent; } path.reverse(); return path; } function pathAt(path, index) { return path[Math.min(index, path.length - 1)]; } function stateKey(p, t) { return p.x + "," + p.y + "," + t; } function edgeKey(a, b, t) { return a.x + "," + a.y + ">" + b.x + "," + b.y + "," + t; } function unwindTimed(node) { const path = []; let n = node; while (n) { path.push({x:n.p.x, y:n.p.y}); n = n.parent; } path.reverse(); return path; } return { rng, clamp, key, same, manhattan, inBounds, isFree, neighbors, astar, unwind, pathAt, stateKey, edgeKey, unwindTimed }; })(); __modules["src/domain/trajectory-costs.js"] = (() => { const { same, pathAt } = __modules["src/core/grid-search.js"]; function trajectoryCosts(path, goal, observedHorizon) { const last = path[path.length - 1]; let goalSuffixStartTick = null; if (same(last, goal)) { goalSuffixStartTick = path.length - 1; while (goalSuffixStartTick > 0 && same(path[goalSuffixStartTick - 1], goal)) goalSuffixStartTick--; } const costEnd = goalSuffixStartTick === null ? observedHorizon : goalSuffixStartTick; let travelSteps = 0; let waitTicks = 0; const travelPrefix = [0]; const waitPrefix = [0]; for (let t = 1; t <= observedHorizon; t++) { const stationary = same(pathAt(path, t - 1), pathAt(path, t)); if (!stationary) travelSteps++; else if (t <= costEnd) waitTicks++; travelPrefix.push(travelSteps); waitPrefix.push(waitTicks); } return {goalSuffixStartTick, travelSteps, waitTicks, travelPrefix, waitPrefix}; } return { trajectoryCosts }; })(); __modules["src/validation/plan-validator.js"] = (() => { const { INPUT_LIMITS, isRecord, isCell, validateScenario } = __modules["src/validation/input-validator.js"]; const { same, manhattan, pathAt } = __modules["src/core/grid-search.js"]; const { trajectoryCosts } = __modules["src/domain/trajectory-costs.js"]; function validatePlanResult(scenario, result) { const issues = []; const counts = {}; let issueCount = 0; let errorCount = 0; let vertexConflicts = 0; let edgeConflicts = 0; let completed = 0; let replaySafe = false; const checked = {structure:false, coordinates:false, timeline:false, movement:false, conflicts:false, goals:false, complete:false}; const scenarioCheck = validateScenario(scenario); const totalAgents = scenarioCheck.ok ? scenario.robots.length : 0; const add = (type, severity, tick, agents, cell, from, to, message, extra = {}) => { issueCount++; counts[type] = (counts[type] || 0) + 1; if (severity === "ERROR") errorCount++; if (issues.length >= INPUT_LIMITS.maxIssues) return; issues.push({id:"V" + String(issueCount).padStart(3,"0"), type, severity, tick:Number.isInteger(tick) ? tick : 0, agents, cell:cell ? {...cell} : null, from:from ? {...from} : null, to:to ? {...to} : null, message, ...extra}); }; const finish = () => { const solverStatus = isRecord(result) ? result.solverStatus : "INVALID"; let status = "PARTIAL"; if (errorCount || !checked.complete) status = "INVALID"; else if (solverStatus === "UNSUPPORTED") status = "UNSUPPORTED"; else if (solverStatus === "TIMEOUT") status = "TIMEOUT"; else if (solverStatus === "INVALID") status = "INVALID"; else if (solverStatus === "PARTIAL") status = "PARTIAL"; else if (completed === totalAgents) status = "SOLVED"; return {valid:status === "SOLVED", structurallyValid:checked.complete && errorCount === 0, status, issues, issueCount, issuesTruncated:issueCount > issues.length, errorCount, counts, errors:issues.filter(i => i.severity === "ERROR").map(i => i.message), vertexConflicts, edgeConflicts, completed, totalAgents, replaySafe, checked, solverReason:isRecord(result) && typeof result.solverReason === "string" ? result.solverReason.slice(0,2048) : "", contractVersion:"mapf-validation/1.2"}; }; if (!scenarioCheck.ok) { for (const item of scenarioCheck.issues) add("INVALID_SCENARIO", "ERROR", 0, [], null, null, null, item.message, {field:item.field}); return finish(); } if (!isRecord(result)) { add("INVALID_RESULT", "ERROR", 0, [], null, null, null, "Plan result must be an object."); return finish(); } if (result.solverStatus !== undefined && !["SOLVED","PARTIAL","TIMEOUT","INVALID","UNSUPPORTED"].includes(result.solverStatus)) { add("UNKNOWN_RESULT_STATUS","ERROR",0,[],null,null,null,"Unsupported solver result status."); return finish(); } const paths = result.paths; if (!Array.isArray(paths) || paths.length !== totalAgents) { add("PATH_COUNT_MISMATCH", "ERROR", 0, [], null, null, null, "Path count does not match the agent count."); return finish(); } let totalPositions = 0; for (let i = 0; i < totalAgents; i++) { if (!Array.isArray(paths[i]) || paths[i].length < 1) add("NO_PATH", "ERROR", 0, [i], scenario.robots[i].start, null, null, "Agent " + (i+1) + " has no path."); else { totalPositions += paths[i].length; if (paths[i].length > INPUT_LIMITS.maxPlanTicks + 1) add("PLAN_LIMIT", "ERROR", 0, [i], null, null, null, "Path exceeds the supported time horizon."); } } if (totalPositions > INPUT_LIMITS.maxPlanPositions) add("PLAN_LIMIT", "ERROR", 0, [], null, null, null, "Plan exceeds the position budget."); if (errorCount) return finish(); const pathMaxLen = Math.max(...paths.map(path => path.length)); const canonical = result.canonicalVersion !== undefined; if (canonical && (result.canonicalVersion !== "final-goal-trimmed/1.0" || !Number.isInteger(result.observedHorizon) || result.observedHorizon < pathMaxLen - 1 || result.observedHorizon > INPUT_LIMITS.maxPlanTicks || (result.observedHorizon + 1) * totalAgents > INPUT_LIMITS.maxPlanPositions)) { add("INVALID_CANONICAL_HORIZON", "ERROR", 0, [], null, null, null, "Canonical horizon must cover every path within the replay budget."); return finish(); } const maxLen = canonical ? result.observedHorizon + 1 : pathMaxLen; const hasTimeline = result.timeline !== undefined; if (hasTimeline) { if (!Array.isArray(result.timeline) || result.timeline.length !== maxLen) add("TIMELINE_MISMATCH", "ERROR", 0, [], null, null, null, "Timeline length differs from the padded paths horizon."); else for (let t = 0; t < maxLen; t++) if (!Array.isArray(result.timeline[t]) || result.timeline[t].length !== totalAgents) add("TIMELINE_SHAPE", "ERROR", t, [], null, null, null, "Timeline frame must contain every agent exactly once."); } if (result.events !== undefined) { if (!Array.isArray(result.events) || result.events.length !== maxLen) add("EVENT_SHAPE", "ERROR", 0, [], null, null, null, "Event count must match the plan horizon."); else for (let t = 0; t < maxLen; t++) { const e = result.events[t]; if (!isRecord(e) || ["waits","conflicts","completed"].some(k => !Number.isFinite(e[k]) || !Number.isInteger(e[k]) || e[k] < 0) || e.completed > totalAgents || e.waits > totalAgents) add("INVALID_EVENT", "ERROR", t, [], null, null, null, "Malformed plan event."); else { if (e.reportedWaits !== undefined && (!Number.isInteger(e.reportedWaits) || e.reportedWaits < 0 || e.reportedWaits > totalAgents)) add("INVALID_EVENT", "ERROR", t, [], null, null, null, "Invalid planner-reported waits."); for (const role of ["inheritedIds","yieldIds"]) if (e[role] !== undefined && (!Array.isArray(e[role]) || e[role].length > totalAgents || e[role].some(v => !Number.isInteger(v) || v < 0 || v >= totalAgents))) add("INVALID_EVENT", "ERROR", t, [], null, null, null, "Invalid event agent IDs."); if (e.yieldTargets !== undefined && (!Array.isArray(e.yieldTargets) || e.yieldTargets.length !== totalAgents || e.yieldTargets.some(p => p !== null && !isCell(p,scenario.grid)))) add("INVALID_EVENT", "ERROR", t, [], null, null, null, "Invalid yield target coordinates."); } } } if (errorCount) return finish(); checked.structure = true; for (let i = 0; i < totalAgents; i++) for (let t = 0; t < paths[i].length; t++) if (!isCell(paths[i][t],scenario.grid)) add("INVALID_COORDINATE", "ERROR", t, [i], null, null, null, "Path coordinates must be in-bounds integers."); if (hasTimeline) for (let t = 0; t < maxLen; t++) for (let i = 0; i < totalAgents; i++) if (!isCell(result.timeline[t][i],scenario.grid)) add("INVALID_COORDINATE", "ERROR", t, [i], null, null, null, "Timeline coordinates must be in-bounds integers."); if (errorCount) return finish(); checked.coordinates = true; if (hasTimeline) { for (let t = 0; t < maxLen; t++) for (let i = 0; i < totalAgents; i++) { if (!same(result.timeline[t][i],pathAt(paths[i],t))) add("TIMELINE_MISMATCH", "ERROR", t, [i], result.timeline[t][i], pathAt(paths[i],t), result.timeline[t][i], "Path / Timeline mismatch for Agent " + (i+1) + " at tick " + t + "."); } checked.timeline = !counts.TIMELINE_MISMATCH; } if (canonical && result.events && checked.timeline) { const costs = paths.map((path,i) => trajectoryCosts(path,scenario.robots[i].goal,maxLen-1)); for (let t = 0; t < maxLen; t++) { const expectedWaits = costs.reduce((sum,c) => sum+c.waitPrefix[t]-(t ? c.waitPrefix[t-1] : 0),0); const expectedAtGoal = paths.filter((path,i) => same(pathAt(path,t),scenario.robots[i].goal)).length; if (result.events[t].waits !== expectedWaits || result.events[t].completed !== expectedAtGoal) add("CANONICAL_EVENT_MISMATCH","ERROR",t,[],null,null,null,"Canonical wait/occupancy counters disagree with trajectories."); } } replaySafe = checked.timeline; for (let i = 0; i < totalAgents; i++) { const path = paths[i]; if (!same(path[0],scenario.robots[i].start)) add("START_MISMATCH", "ERROR", 0, [i], path[0], scenario.robots[i].start, path[0], "Agent " + (i+1) + " starts at the wrong cell."); for (let t = 0; t < path.length; t++) { const p = path[t]; if (scenario.grid.cells[p.y][p.x] !== 0) add("BLOCKED_CELL", "ERROR", t, [i], p, t ? path[t-1] : null, p, "Agent " + (i+1) + " enters a blocked cell."); if (t && manhattan(path[t-1],p) > 1) add("INVALID_MOVE", "ERROR", t, [i], p, path[t-1],p, "Agent " + (i+1) + " makes a discontinuous move."); } } checked.movement = true; for (let t = 0; t < maxLen; t++) for (let a = 0; a < totalAgents; a++) for (let b = a+1; b < totalAgents; b++) { const pa = pathAt(paths[a],t), pb = pathAt(paths[b],t); if (same(pa,pb)) { vertexConflicts++; add("VERTEX_CONFLICT", "ERROR", t, [a,b],pa,null,null,"Vertex conflict between Agent " + (a+1) + " and Agent " + (b+1) + "."); } if (t) { const a0 = pathAt(paths[a],t-1), b0 = pathAt(paths[b],t-1); if (same(a0,pb) && same(b0,pa)) { edgeConflicts++; add("EDGE_SWAP_CONFLICT", "ERROR", t, [a,b],pa,a0,pa,"Edge-swap conflict between Agent " + (a+1) + " and Agent " + (b+1) + ".",{otherFrom:{...b0},otherTo:{...pb}}); } } } checked.conflicts = true; for (let i = 0; i < totalAgents; i++) { const last = paths[i][paths[i].length-1]; if (same(last,scenario.robots[i].goal)) completed++; else add("GOAL_NOT_REACHED", "WARNING",maxLen-1,[i],scenario.robots[i].goal,last,scenario.robots[i].goal,"Agent " + (i+1) + " did not reach its goal."); } if (result.solverStatus === "TIMEOUT") { const type = ({CBS_NODE_LIMIT:"PLANNER_NODE_LIMIT",LOW_LEVEL_EXPANSION_LIMIT:"PLANNER_EXPANSION_LIMIT"})[result.terminationReason] || "PLANNER_TIMEOUT"; add(type,"WARNING",maxLen-1,Number.isInteger(result.searchOutcome?.agent) ? [result.searchOutcome.agent] : [],null,null,null,result.solverReason || "Planner reached its limit.",{terminationReason:result.terminationReason || "UNKNOWN_LIMIT",phase:result.searchOutcome?.phase || null}); } if (result.solverStatus === "PARTIAL" && ["NO_PATH_WITHIN_HORIZON","NO_SOLUTION_WITHIN_HORIZON"].includes(result.terminationReason)) add("SEARCH_HORIZON_EXHAUSTED","WARNING",maxLen-1,Number.isInteger(result.searchOutcome?.agent) ? [result.searchOutcome.agent] : [],null,null,null,result.solverReason,{terminationReason:result.terminationReason,horizon:result.searchOutcome?.horizon}); if (result.solverStatus === "PARTIAL" && ["ST_DISCONNECTED","ST_HORIZON_REACHED","NO_RESERVED_PATH_WITHIN_HORIZON"].includes(result.terminationReason)) { const outcome = result.searchOutcome || {}; const type = ({ST_DISCONNECTED:"STATIC_DISCONNECTED",ST_HORIZON_REACHED:"SEARCH_HORIZON_REACHED",NO_RESERVED_PATH_WITHIN_HORIZON:"RESERVED_PATH_NOT_FOUND"})[result.terminationReason]; const index = Number.isInteger(outcome.agent) && outcome.agent >= 0 && outcome.agent < totalAgents ? outcome.agent : null; add(type,"WARNING",0,index === null ? [] : [index],index === null ? null : scenario.robots[index].start,null,null,result.solverReason || "Prioritized search did not find a path.", {terminationReason:result.terminationReason,horizon:outcome.horizon,priorityOrder:outcome.priorityOrder,horizonReached:outcome.horizonReached,phase:outcome.phase,diagnosticReplay:"stationary-fallback"}); } if (result.solverStatus === "UNSUPPORTED") add("PLANNER_UNSUPPORTED", "WARNING", 0,[],null,null,null,result.solverReason || "Unsupported solver request."); if (result.solverStatus === "INVALID") add("PLANNER_INVALID", "ERROR",0,[],null,null,null,result.solverReason || "Planner rejected the request."); checked.goals = true; checked.complete = true; return finish(); } return { validatePlanResult }; })(); __modules["src/domain/execution-limits.js"] = (() => { const { isRecord, inputIssue } = __modules["src/validation/input-validator.js"]; function resolveExecutionLimits(scenario, requested = {}) { const cells = scenario.grid.w * scenario.grid.h; const value = {maxTicks:Math.max(160, cells * 4), horizon:Math.max(80, cells * 2), cbsAgents:12, cbsTimeMs:1400, cbsNodes:1600, spaceTimeExpansions:50000, cbsLowLevelExpansions:90000}; if (!isRecord(requested)) return {ok:false, issues:[inputIssue("INVALID_LIMITS", "limits", "Limits must be an object.")]}; const bounds = {maxTicks:10000, horizon:10000, cbsAgents:12, cbsTimeMs:60000, cbsNodes:20000, spaceTimeExpansions:200000, cbsLowLevelExpansions:200000}; const issues = []; for (const [key, limit] of Object.entries(requested)) { if (!Object.hasOwn(bounds, key) || !Number.isInteger(limit) || limit < 1 || limit > bounds[key]) issues.push(inputIssue("INVALID_LIMIT", "limits." + key, "Invalid or unsupported limit: " + key + ".")); else value[key] = limit; } return {ok:issues.length === 0, issues, value:Object.freeze(value)}; } return { resolveExecutionLimits }; })(); __modules["src/domain/palette.js"] = (() => { const colors = ["#2bcf78", "#4cb3c9", "#9b86d9", "#d97b88", "#d7bd42", "#62c982", "#d77b32", "#c979c3", "#669bd1", "#d878a8", "#39b98b", "#9f76c8", "#d6a83d", "#42a9b2", "#7fd19a", "#d99196", "#86a7cf", "#d5c87d", "#b29acb", "#66b4b0", "#a4bf5b", "#d59a67", "#a99bc8", "#7bc4aa"]; return { colors }; })(); __modules["src/domain/scenario.js"] = (() => { const { colors } = __modules["src/domain/palette.js"]; function deepFreeze(value) { if (value && typeof value === "object" && !Object.isFrozen(value)) { for (const item of Object.values(value)) deepFreeze(item); Object.freeze(value); } return value; } function copyScenario(scenario) { return { grid:{w:scenario.grid.w, h:scenario.grid.h, cells:scenario.grid.cells.map(row => row.slice())}, robots:scenario.robots.map((r, id) => ({id, start:{x:r.start.x,y:r.start.y}, goal:{x:r.goal.x,y:r.goal.y}, color:colors[id]})), endpointCells:(scenario.endpointCells || scenario.robots.map(r => r.goal)).map(p => ({x:p.x,y:p.y})), bufferCells:(scenario.bufferCells || []).map(p => ({x:p.x,y:p.y})), config:scenario.config ? {...scenario.config} : null, generator:scenario.generator ? {...scenario.generator} : null, ...(scenario.source?.kind === "manual" ? {source:{kind:"manual",name:scenario.source.name,origin:scenario.source.origin ? {scenarioId:scenario.source.origin.scenarioId} : null}} : {}) }; } return { deepFreeze, copyScenario }; })(); __modules["src/core/scenario-generator.js"] = (() => { const { rng, clamp, key, manhattan, neighbors, astar, isFree } = __modules["src/core/grid-search.js"]; const { colors } = __modules["src/domain/palette.js"]; const { validateGeneratorConfig } = __modules["src/validation/input-validator.js"]; function createGrid(w, h, density, random, layout) { const cells = Array.from({length:h}, () => Array(w).fill(0)); const d = density / 100; for (let y = 0; y < h; y++) { for (let x = 0; x < w; x++) { if (x === 0 || y === 0 || x === w - 1 || y === h - 1) continue; if (random() < d) cells[y][x] = 1; } } if (layout === "corridor") { const cy = Math.floor(h / 2); for (let y = 2; y < h - 2; y++) { if (Math.abs(y - cy) <= 1) continue; for (let x = Math.floor(w * 0.42); x <= Math.floor(w * 0.58); x++) cells[y][x] = 1; } for (let x = 2; x < w - 2; x++) cells[cy][x] = 0; if (cy - 1 > 0) for (let x = 2; x < w - 2; x++) if (x % 7 !== 0) cells[cy - 1][x] = 0; if (cy + 1 < h - 1) for (let x = 2; x < w - 2; x++) if (x % 7 !== 0) cells[cy + 1][x] = 0; } return {w, h, cells}; } function pickCell(grid, random, used, side) { const tries = 240; for (let i = 0; i < tries; i++) { let x = 1; let y = 1; if (side === 0) { x = 1 + Math.floor(random() * Math.max(1, Math.floor(grid.w * 0.18))); y = 1 + Math.floor(random() * (grid.h - 2)); } if (side === 1) { x = grid.w - 2 - Math.floor(random() * Math.max(1, Math.floor(grid.w * 0.18))); y = 1 + Math.floor(random() * (grid.h - 2)); } if (side === 2) { x = 1 + Math.floor(random() * (grid.w - 2)); y = 1 + Math.floor(random() * Math.max(1, Math.floor(grid.h * 0.18))); } if (side === 3) { x = 1 + Math.floor(random() * (grid.w - 2)); y = grid.h - 2 - Math.floor(random() * Math.max(1, Math.floor(grid.h * 0.18))); } const k = x + "," + y; if (isFree(grid, x, y) && !used.has(k)) { used.add(k); return {x, y}; } } return null; } function cellDegree(grid, cell) { return neighbors(grid, cell, false).length; } function sideMatch(grid, cell, side) { if (side === 0) return cell.x <= Math.max(2, Math.floor(grid.w * 0.22)); if (side === 1) return cell.x >= grid.w - 1 - Math.max(2, Math.floor(grid.w * 0.22)); if (side === 2) return cell.y <= Math.max(2, Math.floor(grid.h * 0.22)); if (side === 3) return cell.y >= grid.h - 1 - Math.max(2, Math.floor(grid.h * 0.22)); return true; } function pickGoalCell(grid, random, used, side, mode) { if (mode === "randomGoal") return pickCell(grid, random, used, side); const candidates = []; for (let y = 1; y < grid.h - 1; y++) { for (let x = 1; x < grid.w - 1; x++) { const c = {x, y}; const k = key(c); if (!isFree(grid, x, y) || used.has(k) || !sideMatch(grid, c, side)) continue; const degree = cellDegree(grid, c); if (degree <= 2) candidates.push({cell:c, score:degree * 10 + manhattan(c, {x:grid.w / 2, y:grid.h / 2}) * 0.04 + random()}); } } candidates.sort((a, b) => a.score - b.score); if (candidates.length) { const chosen = candidates[Math.floor(random() * Math.min(8, candidates.length))].cell; used.add(key(chosen)); return chosen; } return pickCell(grid, random, used, side); } function classifyMapNodes(grid, robots) { const occupied = new Set(); for (const r of robots) { occupied.add(key(r.start)); occupied.add(key(r.goal)); } const buffers = []; const endpoints = robots.map(r => ({...r.goal})); for (let y = 1; y < grid.h - 1; y++) { for (let x = 1; x < grid.w - 1; x++) { const c = {x, y}; if (!isFree(grid, x, y) || occupied.has(key(c))) continue; const degree = cellDegree(grid, c); const borderPocket = x <= 2 || y <= 2 || x >= grid.w - 3 || y >= grid.h - 3; if (degree <= 2 || borderPocket) buffers.push({x, y, degree}); } } buffers.sort((a, b) => a.degree - b.degree || a.y - b.y || a.x - b.x); return {endpoints, buffers:buffers.slice(0, 160).map(c => ({x:c.x, y:c.y}))}; } function generateScenario(config) { const input = validateGeneratorConfig(config); if (!input.ok) return {ok:false, status:"INVALID", issues:input.issues}; config = {...config}; const w = config.width; const h = config.height; const count = config.agents; const density = config.density; const baseSeed = config.seed; const layout = config.trafficScenario; for (let attempt = 0; attempt < 80; attempt++) { const random = rng(baseSeed + attempt * 7919); const grid = createGrid(w, h, density, random, layout); const used = new Set(); const robots = []; let ok = true; for (let i = 0; i < count; i++) { let startSide = i % 4; let goalSide = (startSide + 1) % 4; if (layout === "cross") goalSide = startSide === 0 ? 1 : startSide === 1 ? 0 : startSide === 2 ? 3 : 2; if (layout === "random") { startSide = Math.floor(random() * 4); goalSide = (startSide + 2 + Math.floor(random() * 2)) % 4; } const start = pickCell(grid, random, used, startSide); const goal = pickGoalCell(grid, random, used, goalSide, config.goalMode); if (!start || !goal) { ok = false; break; } const p = astar(grid, start, goal); if (!p) { ok = false; break; } robots.push({id:i, start, goal, color:colors[i % colors.length]}); } if (ok) { const markers = classifyMapNodes(grid, robots); return {ok:true, scenario:{grid, robots, endpointCells:markers.endpoints, bufferCells:markers.buffers, config:{...config}, generator:{version:"v1_38-preserved", attempt, effectiveSeed:baseSeed + attempt * 7919}}}; } } return {ok:false, status:"SCENARIO_INVALID", issues:[{code:"GENERATION_FAILED", field:"scenario", message:"Could not generate connected start/goal pairs after 80 attempts."}]}; } return { generateScenario, classifyMapNodes }; })(); __modules["src/domain/plan-contract.js"] = (() => { const { same, pathAt } = __modules["src/core/grid-search.js"]; const CONTRACT_VERSION = "mapf-plan/2.1"; const METRIC_MODEL = "final-settlement-unit-tick/1.0"; const CANONICAL_VERSION = "final-goal-trimmed/1.0"; const COST_POLICY = Object.freeze({ id:METRIC_MODEL, moveCost:1, waitCost:1, timeUnit:"logical-tick", goalBehavior:"stay-at-final-goal", transientGoalWaits:"included", finalGoalPadding:"excluded-from-cost-not-occupancy", incompleteCosts:"null", optimality:"not-claimed" }); function buildResultFromPaths(scenario, paths, meta = {}) { const normalized = paths.map((path, i) => path && path.length ? path.map(p => ({x:p.x, y:p.y})) : [{...scenario.robots[i].start}]); const maxLen = Math.max(1, ...normalized.map(path => path.length)); const timeline = []; const events = []; for (let t = 0; t < maxLen; t++) { const frame = normalized.map(path => ({...pathAt(path, t)})); timeline.push(frame); const waits = t === 0 ? 0 : frame.reduce((sum, p, i) => sum + (same(p, pathAt(normalized[i], t - 1)) && !same(p, scenario.robots[i].goal) ? 1 : 0), 0); events.push({waits, conflicts:0, completed:frame.filter((p, i) => same(p, scenario.robots[i].goal)).length}); } return {timeline, events, paths:normalized, ...meta}; } function stationaryPlanResult(scenario, status, reason) { const paths = scenario.robots.map(r => [{...r.start}]); return buildResultFromPaths(scenario, paths, {solverStatus:status, solverReason:reason || ""}); } return { buildResultFromPaths, stationaryPlanResult, CONTRACT_VERSION, METRIC_MODEL, CANONICAL_VERSION, COST_POLICY }; })(); __modules["src/domain/canonical-plan.js"] = (() => { const { pathAt } = __modules["src/core/grid-search.js"]; const { deepFreeze } = __modules["src/domain/scenario.js"]; const { CONTRACT_VERSION, METRIC_MODEL, CANONICAL_VERSION, COST_POLICY } = __modules["src/domain/plan-contract.js"]; const { trajectoryCosts } = __modules["src/domain/trajectory-costs.js"]; const { validatePlanResult } = __modules["src/validation/plan-validator.js"]; function normalizePlan(scenario, result) { const inputValidation = validatePlanResult(scenario, result); if (!inputValidation.replaySafe || inputValidation.counts.CANONICAL_EVENT_MISMATCH) return {ok:false, validation:inputValidation}; const observedHorizon = result.timeline.length - 1; const costs = result.paths.map((path, i) => trajectoryCosts(path, scenario.robots[i].goal, observedHorizon)); const paths = result.paths.map((path, i) => { const arrival = costs[i].goalSuffixStartTick; const length = arrival === null ? path.length : arrival + 1; return path.slice(0, length).map(p => ({x:p.x, y:p.y})); }); const timeline = Array.from({length:observedHorizon + 1}, (_, t) => paths.map(path => ({...pathAt(path, t)}))); const reported = Array.isArray(result.events) ? result.events : []; const events = timeline.map((frame, t) => { const previous = reported[t] || {conflicts:0, waits:0}; return {...previous, waits:costs.reduce((sum, c) => sum + c.waitPrefix[t] - (t ? c.waitPrefix[t - 1] : 0), 0), reportedWaits:previous.reportedWaits === undefined ? previous.waits : previous.reportedWaits, conflicts:previous.conflicts, completed:frame.filter((p, i) => p.x === scenario.robots[i].goal.x && p.y === scenario.robots[i].goal.y).length }; }); const value = {...result, paths, timeline, events, observedHorizon, canonicalVersion:CANONICAL_VERSION, contractVersion:CONTRACT_VERSION, metricModel:METRIC_MODEL, costPolicy:COST_POLICY}; delete value.validation; delete value.metrics; const validation = validatePlanResult(scenario, value); value.validation = validation; value.status = validation.status; return {ok:true, value:deepFreeze(structuredClone(value)), validation}; } return { normalizePlan }; })(); __modules["src/solvers/priority-first.js"] = (() => { const { same, key, astar, neighbors, manhattan } = __modules["src/core/grid-search.js"]; function solvePriorityFirst(scenario, options, limits) { const context = {grid:scenario.grid, robots:scenario.robots, bufferCells:scenario.bufferCells, activeTargets:null}; function robotTarget(i) { if (context && context.activeTargets && context.activeTargets[i]) return context.activeTargets[i]; return context.robots[i].goal; } function setActiveTargets(targets) { context.activeTargets = targets.map(t => ({...t})); } function clearActiveTargets() { if (context) context.activeTargets = null; } function stepYieldHolds(yieldHolds) { for (let i = 0; i < yieldHolds.length; i++) if (yieldHolds[i] > 0) yieldHolds[i]--; } function snapshotYieldTargets(yieldTargets) { return yieldTargets.map(target => target ? {x:target.x, y:target.y} : null); } function goalBlocksFuturePath(i, positions, targets) { const cell = context.robots[i].goal; if (!same(positions[i], cell)) return false; for (let j = 0; j < positions.length; j++) { if (i === j) continue; if (same(positions[j], targets[j])) continue; const p = astar(context.grid, positions[j], targets[j]); if (!p || p.length < 2) continue; const limit = Math.min(p.length - 1, 14); for (let k = 1; k <= limit; k++) { if (same(p[k], cell)) return true; } } return false; } function findNearestBufferCell(i, positions) { const occupied = new Set(); const goals = new Set(); for (let r = 0; r < context.robots.length; r++) { if (r !== i) occupied.add(key(positions[r])); goals.add(key(context.robots[r].goal)); } const preferred = new Set((context.bufferCells || []).map(key)); const start = positions[i]; const queue = [{...start}]; const visited = new Set([key(start)]); let fallback = null; while (queue.length) { const cur = queue.shift(); for (const n of neighbors(context.grid, cur, false)) { const k = key(n); if (visited.has(k)) continue; visited.add(k); if (!occupied.has(k) && !goals.has(k)) { if (!fallback) fallback = {...n}; if (preferred.has(k)) return {...n}; } queue.push(n); } } return fallback; } function refreshYieldTargets(positions, yieldTargets, yieldHolds) { for (let i = 0; i < yieldTargets.length; i++) { if (yieldTargets[i] && same(positions[i], yieldTargets[i])) { yieldTargets[i] = null; yieldHolds[i] = Math.max(yieldHolds[i], 5); } } const targets = context.robots.map((r, i) => { if (yieldTargets[i]) return yieldTargets[i]; if (yieldHolds[i] > 0) return positions[i]; return r.goal; }); setActiveTargets(targets); const yielded = []; for (let i = 0; i < positions.length; i++) { if (yieldTargets[i] || yieldHolds[i] > 0) continue; if (!same(positions[i], context.robots[i].goal)) continue; if (!goalBlocksFuturePath(i, positions, targets)) continue; const buffer = findNearestBufferCell(i, positions); if (!buffer) continue; yieldTargets[i] = buffer; targets[i] = buffer; yielded.push(i); } setActiveTargets(targets); return yielded; } function occupiedIndex(positions, cell) { for (let i = 0; i < positions.length; i++) if (same(positions[i], cell)) return i; return -1; } function countNeighborRobots(positions, cell) { let c = 0; for (const p of positions) if (manhattan(p, cell) === 1) c++; return c; } function priorityPlusCandidates(i, positions, desired, forcedLeave) { const r = context.robots[i]; const target = robotTarget(i); const list = []; const current = positions[i]; const direct = astar(context.grid, current, target); if (direct && direct.length > 1) list.push({cell:direct[1], kind:0}); for (const n of neighbors(context.grid, current, false)) list.push({cell:n, kind:1}); if (!forcedLeave) list.push({cell:current, kind:2}); const seen = new Set(); const unique = []; for (const item of list) { const k = key(item.cell); if (!seen.has(k)) { seen.add(k); unique.push(item); } } unique.sort((a, b) => { const da = manhattan(a.cell, target); const db = manhattan(b.cell, target); const ca = countNeighborRobots(positions, a.cell); const cb = countNeighborRobots(positions, b.cell); const pa = same(a.cell, desired[i]) ? -8 : 0; const pb = same(b.cell, desired[i]) ? -8 : 0; const wa = same(a.cell, current) ? 18 : 0; const wb = same(b.cell, current) ? 18 : 0; return (da + ca * 1.5 + a.kind * 1.2 + pa + wa) - (db + cb * 1.5 + b.kind * 1.2 + pb + wb); }); return unique.map(v => v.cell); } function simulatePriorityPlus() { const n = context.robots.length; const positions = context.robots.map(r => ({...r.start})); const waitTurns = Array(n).fill(0); const yieldTargets = Array(n).fill(null); const yieldHolds = Array(n).fill(0); const timeline = [positions.map(p => ({...p}))]; const events = [{waits:0, conflicts:0, completed:0, inheritedIds:[], recovery:false, leaderId:-1, moved:0, yieldIds:[], yieldTargets:Array(n).fill(null)}]; const trails = context.robots.map(r => [{...r.start}]); const max = limits.maxTicks; let stuckTurns = 0; let recoveryTicks = 0; let recoveryLeader = -1; for (let t = 1; t <= max; t++) { const yielded = refreshYieldTargets(positions, yieldTargets, yieldHolds); const desired = []; for (let i = 0; i < n; i++) { const target = robotTarget(i); if (same(positions[i], target)) desired.push(positions[i]); else { const p = astar(context.grid, positions[i], target); desired.push(p && p.length > 1 ? p[1] : positions[i]); } } if (stuckTurns >= 3 && recoveryTicks <= 0) { let best = -1; let bestScore = -Infinity; for (let i = 0; i < n; i++) { if (same(positions[i], robotTarget(i))) continue; const score = waitTurns[i] * 10 + manhattan(positions[i], robotTarget(i)); if (score > bestScore) { bestScore = score; best = i; } } recoveryLeader = best; recoveryTicks = best >= 0 ? 8 : 0; } const priority = []; for (let i = 0; i < n; i++) { let v = (n - i) + waitTurns[i] * 4 - manhattan(positions[i], robotTarget(i)) * 0.04; if (yieldTargets[i]) v += 360; if (recoveryTicks > 0 && i === recoveryLeader) v += 1000; priority.push(v); } const next = positions.map(p => ({...p})); const planned = Array(n).fill(false); const reserved = new Set(); const transitions = []; const inherited = new Set(); let conflicts = 0; function hasSwap(i, cell) { for (const tr of transitions) { if (same(cell, tr.from) && same(positions[i], tr.to)) return true; } return false; } function canEnterOldCell(i, j, cell) { if (!planned[j]) return false; if (same(next[j], positions[j])) return false; if (same(next[j], positions[i])) return false; if (hasSwap(i, cell)) return false; return true; } function planMove(i, chain, forcedLeave) { if (planned[i]) return !forcedLeave || !same(next[i], positions[i]); const target = robotTarget(i); if (same(positions[i], target) && !forcedLeave) { planned[i] = true; next[i] = positions[i]; reserved.add(key(next[i])); return true; } const candidates = priorityPlusCandidates(i, positions, desired, forcedLeave); for (const cell of candidates) { const k = key(cell); if (reserved.has(k)) continue; if (hasSwap(i, cell)) continue; const occ = occupiedIndex(positions, cell); if (occ >= 0 && occ !== i) { if (canEnterOldCell(i, occ, cell)) { next[i] = cell; planned[i] = true; reserved.add(k); if (!same(cell, positions[i])) transitions.push({from:{...positions[i]}, to:{...cell}}); return true; } if (chain.includes(occ)) continue; if (priority[i] + 0.01 >= priority[occ] || recoveryTicks > 0 || yieldTargets[occ]) { inherited.add(occ); priority[occ] = Math.max(priority[occ], priority[i] + 0.5); if (planMove(occ, chain.concat([i]), true)) { if (!reserved.has(k) && !hasSwap(i, cell)) { next[i] = cell; planned[i] = true; reserved.add(k); if (!same(cell, positions[i])) transitions.push({from:{...positions[i]}, to:{...cell}}); conflicts++; return true; } } } continue; } next[i] = cell; planned[i] = true; reserved.add(k); if (!same(cell, positions[i])) transitions.push({from:{...positions[i]}, to:{...cell}}); return true; } if (!forcedLeave && !reserved.has(key(positions[i]))) { next[i] = positions[i]; planned[i] = true; reserved.add(key(next[i])); return true; } return false; } const order = Array.from({length:n}, (_, i) => i).sort((a, b) => priority[b] - priority[a] || a - b); for (const i of order) planMove(i, [], false); for (let i = 0; i < n; i++) { if (!planned[i]) { next[i] = positions[i]; if (!reserved.has(key(next[i]))) reserved.add(key(next[i])); } } let moved = 0; let waits = 0; for (let i = 0; i < n; i++) { if (!same(next[i], positions[i])) moved++; if (same(next[i], positions[i]) && !same(positions[i], robotTarget(i))) { waits++; waitTurns[i]++; } else { waitTurns[i] = 0; } positions[i] = next[i]; trails[i].push({...positions[i]}); } stepYieldHolds(yieldHolds); if (moved === 0 && positions.some((p, i) => !same(p, robotTarget(i)))) stuckTurns++; else stuckTurns = 0; const recovery = recoveryTicks > 0; if (recoveryTicks > 0) recoveryTicks--; timeline.push(positions.map(p => ({...p}))); events.push({waits, conflicts, completed:positions.filter((p, i) => same(p, context.robots[i].goal)).length, inheritedIds:Array.from(inherited), recovery, leaderId:recovery ? recoveryLeader : -1, moved, yieldIds:yielded, yieldTargets:snapshotYieldTargets(yieldTargets)}); if (positions.every((p, i) => same(p, context.robots[i].goal)) && yieldTargets.every(v => !v) && yieldHolds.every(v => v <= 0)) break; } clearActiveTargets(); return {timeline, events, paths:trails, terminationReason:positions.every((p, i) => same(p, context.robots[i].goal)) ? "COMPLETED" : "TICK_LIMIT", counters:{ticks:timeline.length - 1}}; } return simulatePriorityPlus(); } return { solvePriorityFirst }; })(); __modules["src/solvers/prioritized-space-time.js"] = (() => { const { same, key, manhattan, neighbors, stateKey, edgeKey, unwindTimed } = __modules["src/core/grid-search.js"]; const { buildResultFromPaths, stationaryPlanResult } = __modules["src/domain/plan-contract.js"]; function spaceTimeAstar(grid, start, goal, reservations, edgeReservations, maxT, goalSafetyCheck, expansionLimit = 50000) { const open = [{p:start, t:0, g:0, f:manhattan(start, goal), parent:null}]; const best = new Map([[stateKey(start, 0), 0]]); const counters = {expanded:0,generated:1,reservationRejects:0,edgeReservationRejects:0,horizonPruned:0,maxTimeVisited:0}; const finish = (status, path = null) => ({status,path,counters:{...counters},expansionLimit,horizon:maxT, horizonReached:counters.horizonPruned > 0,frontierRemaining:open.length}); while (open.length && counters.expanded < expansionLimit) { open.sort((a, b) => a.f - b.f || a.t - b.t); const cur = open.shift(); counters.expanded++; counters.maxTimeVisited = Math.max(counters.maxTimeVisited,cur.t); if (same(cur.p, goal) && (!goalSafetyCheck || goalSafetyCheck(goal, cur.t, reservations, maxT))) return finish("FOUND",unwindTimed(cur)); if (cur.t >= maxT) { counters.horizonPruned++; continue; } for (const np of neighbors(grid, cur.p, true)) { const nt = cur.t + 1; if (reservations.has(stateKey(np, nt))) { counters.reservationRejects++; continue; } if (edgeReservations.has(edgeKey(np, cur.p, nt))) { counters.edgeReservationRejects++; continue; } const g = cur.g + 1 + (same(np, cur.p) ? 0.18 : 0); const sk = stateKey(np, nt); if (!best.has(sk) || g < best.get(sk)) { best.set(sk, g); open.push({p:np, t:nt, g, f:g + manhattan(np, goal), parent:cur}); counters.generated++; } } } return finish(open.length ? "EXPANSION_LIMIT" : "SEARCH_EXHAUSTED"); } function staticConnection(grid, start, goal) { const queue = [{...start,distance:0}]; const visited = new Set([key(start)]); let index = 0; while (index < queue.length) { const cell = queue[index++]; if (same(cell,goal)) return {connected:true,distance:cell.distance,checkedCells:index}; for (const next of neighbors(grid,cell,false)) { const k = key(next); if (!visited.has(k)) { visited.add(k); queue.push({...next,distance:cell.distance+1}); } } } return {connected:false,distance:null,checkedCells:index}; } function reservationGoalSafe(goal, startTime, reservations, maxT) { for (let t = startTime; t <= maxT; t++) if (reservations.has(stateKey(goal, t))) return false; return true; } function solveSpaceTime(scenario, options, limits) { const maxT = limits.horizon; const reservations = new Set(); const edgeReservations = new Set(); const paths = []; const searches = []; for (let i = 0; i < scenario.robots.length; i++) { const r = scenario.robots[i]; const search = spaceTimeAstar(scenario.grid, r.start, r.goal, reservations, edgeReservations, maxT, reservationGoalSafe, limits.spaceTimeExpansions); const {path,...trace} = search; searches.push({agent:i,agentId:r.id,priorityOrder:i+1,...trace}); if (!search.path) { const connection = staticConnection(scenario.grid,r.start,r.goal); const reason = !connection.connected ? "ST_DISCONNECTED" : search.status === "EXPANSION_LIMIT" ? "LOW_LEVEL_EXPANSION_LIMIT" : search.horizonReached ? "ST_HORIZON_REACHED" : "NO_RESERVED_PATH_WITHIN_HORIZON"; const messages = { ST_DISCONNECTED:"Start and Goal are disconnected by obstacles. Check the map.", LOW_LEVEL_EXPANSION_LIMIT:"The A* expansion budget was exhausted. A path may still exist.", ST_HORIZON_REACHED:"Search was truncated at the time horizon. No path was found under this priority order within that horizon.", NO_RESERVED_PATH_WITHIN_HORIZON:"No path was found under the current reservations, priority order and horizon. Other orders or solvers may succeed." }; const result = stationaryPlanResult(scenario,reason === "LOW_LEVEL_EXPANSION_LIMIT" ? "TIMEOUT" : "PARTIAL","Agent " + (i+1) + ": " + messages[reason]); result.terminationReason = reason; result.searchOutcome = {contractVersion:"prioritized-search-diagnostics/1.0",phase:"prioritized-agent",agent:i,agentId:r.id, priorityOrder:i+1,totalAgents:scenario.robots.length,plannedAgents:paths.length,horizon:maxT,expansionLimit:limits.spaceTimeExpansions, lowLevelStatus:search.status,horizonReached:search.horizonReached,frontierRemaining:search.frontierRemaining, staticConnection:connection,start:{...r.start},goal:{...r.goal},counters:search.counters, lowLevelSearches:searches,reason,diagnosticReplay:"stationary-fallback-not-search-progress",optimality:"not-certified"}; result.counters = {ticks:0,lowLevelSearches:searches.length,expanded:searches.reduce((sum,item) => sum+item.counters.expanded,0),diagnosticCells:connection.checkedCells}; return result; } const p = search.path; paths.push(p); for (let t = 0; t < Math.min(maxT, p.length); t++) reservations.add(stateKey(p[t], t)); for (let t = 1; t < Math.min(maxT, p.length); t++) edgeReservations.add(edgeKey(p[t - 1], p[t], t)); const last = p[p.length - 1]; for (let t = p.length; t <= maxT; t++) reservations.add(stateKey(last, t)); } return buildResultFromPaths(scenario, paths, {solverStatus:"SOLVED",terminationReason:"COMPLETED", searchOutcome:{contractVersion:"prioritized-search-diagnostics/1.0",phase:"complete",agent:null,horizon:maxT, expansionLimit:limits.spaceTimeExpansions,lowLevelSearches:searches,optimality:"not-certified"}, counters:{lowLevelSearches:searches.length,expanded:searches.reduce((sum,item) => sum+item.counters.expanded,0)}}); } return { solveSpaceTime, spaceTimeAstar, staticConnection }; })(); __modules["src/solvers/cbs.js"] = (() => { const { same, key, manhattan, neighbors, stateKey, pathAt, unwindTimed } = __modules["src/core/grid-search.js"]; const { buildResultFromPaths, stationaryPlanResult } = __modules["src/domain/plan-contract.js"]; function buildConstraintIndex(constraints, agent, goal) { const vertices = new Map(); const edges = new Map(); let lastGoalVertex = -1; let lastGoalWaitEdge = -1; const goalKey = key(goal); const goalWait = goalKey + ">" + goalKey; for (const c of constraints) { if (c.agent !== agent) continue; if (c.type === "vertex") { if (!vertices.has(c.time)) vertices.set(c.time, new Set()); const location = c.x + "," + c.y; vertices.get(c.time).add(location); if (location === goalKey) lastGoalVertex = Math.max(lastGoalVertex, c.time); } else { if (!edges.has(c.time)) edges.set(c.time, new Set()); const edge = key(c.from) + ">" + key(c.to); edges.get(c.time).add(edge); if (edge === goalWait) lastGoalWaitEdge = Math.max(lastGoalWaitEdge, c.time); } } return {vertices, edges, lastGoalVertex, lastGoalWaitEdge}; } function canHoldGoal(index, arrivalTick) { return arrivalTick > index.lastGoalVertex && arrivalTick >= index.lastGoalWaitEdge; } function constrainedAstar(grid, start, goal, constraints, agent, maxT, expansionLimit = 90000, budget = {}) { const now = budget.now || (() => performance.now()); const expired = () => budget.deadline !== undefined && now() >= budget.deadline; let expanded = 0; let generated = 0; const finish = (status, path = null) => ({status, path, expanded, generated, horizon:maxT, arrivalTick:path ? path.length - 1 : null}); if (expired()) return finish("WALL_CLOCK_LIMIT"); const index = buildConstraintIndex(constraints, agent, goal); if (index.vertices.get(0)?.has(key(start))) return finish("NO_PATH_WITHIN_HORIZON"); if (Math.max(index.lastGoalVertex + 1, index.lastGoalWaitEdge) > maxT) return finish("NO_PATH_WITHIN_HORIZON"); const open = [{p:{...start}, t:0, g:0, f:manhattan(start, goal), serial:0, parent:null}]; const best = new Map([[stateKey(start, 0), 0]]); generated = 1; while (open.length) { if (expired()) return finish("WALL_CLOCK_LIMIT"); if (expanded >= expansionLimit) return finish("LOW_LEVEL_EXPANSION_LIMIT"); open.sort((a, b) => a.f - b.f || a.t - b.t || a.serial - b.serial); if (expired()) return finish("WALL_CLOCK_LIMIT"); const cur = open.shift(); expanded++; if (same(cur.p, goal) && canHoldGoal(index, cur.t)) return finish("FOUND", unwindTimed(cur)); if (cur.t >= maxT) continue; for (const np of neighbors(grid, cur.p, true)) { const nt = cur.t + 1; if (index.vertices.get(nt)?.has(key(np))) continue; if (index.edges.get(nt)?.has(key(cur.p) + ">" + key(np))) continue; const g = cur.g + 1; const sk = stateKey(np, nt); if (!best.has(sk) || g < best.get(sk)) { best.set(sk, g); open.push({p:{...np}, t:nt, g, f:g + manhattan(np, goal), serial:generated++, parent:cur}); } } } return finish(expired() ? "WALL_CLOCK_LIMIT" : "NO_PATH_WITHIN_HORIZON"); } function detectFirstPathConflict(paths, expired = () => false) { const maxLen = Math.max(1, ...paths.map(path => path.length)); for (let t = 0; t < maxLen; t++) { if (expired()) return {type:"limit"}; for (let a = 0; a < paths.length; a++) { const pa = pathAt(paths[a], t); for (let b = a + 1; b < paths.length; b++) { const pb = pathAt(paths[b], t); if (same(pa, pb)) return {type:"vertex", time:t, a, b, cell:{...pa}}; if (t > 0) { const a0 = pathAt(paths[a], t - 1); const b0 = pathAt(paths[b], t - 1); if (same(a0, pb) && same(b0, pa)) return {type:"edge", time:t, a, b, aFrom:{...a0}, aTo:{...pa}, bFrom:{...b0}, bTo:{...pb}}; } } } } return null; } function cbsNodeCost(paths) { return paths.reduce((sum, path) => sum + path.length - 1, 0); } function constraintSignature(constraints) { return constraints.map(c => c.type === "vertex" ? c.agent + ":V:" + c.time + ":" + c.x + "," + c.y : c.agent + ":E:" + c.time + ":" + key(c.from) + ">" + key(c.to)).sort().join("|"); } function solveCBS(scenario, options, limits, execution = {}) { const now = execution.now || (() => performance.now()); const started = now(); const deadline = started + limits.cbsTimeMs; const expired = () => now() >= deadline; const counters = {expanded:0,generated:0,lowLevelCalls:0,lowLevelExpanded:0,lowLevelGenerated:0,provenInfeasibleBranches:0,interruptedBranches:0}; const maxT = limits.horizon; const descriptions = { AGENT_LIMIT:"CBS supports up to " + limits.cbsAgents + " agents in this build.", WALL_CLOCK_LIMIT:"CBS reached its cooperative wall-clock limit; search is incomplete.", CBS_NODE_LIMIT:"CBS reached its high-level node limit; search is incomplete.", LOW_LEVEL_EXPANSION_LIMIT:"An individual A* search reached its expansion limit. The unresolved branch was not discarded as infeasible.", NO_PATH_WITHIN_HORIZON:"No individual path exists within the configured time horizon for the reported agent.", NO_SOLUTION_WITHIN_HORIZON:"The constraint tree was exhausted within the configured per-agent time horizon. Global impossibility is not claimed." }; function finish(status, reason, phase, agent = null, paths = null) { const searchOutcome = {objective:"sumOfCosts",goalBehavior:"stay-at-final-goal",horizon:maxT,phase,agent, terminationReason:reason,elapsedMs:Math.max(0,now()-started), solutionCost:paths ? cbsNodeCost(paths) : null, searchCompleteWithinHorizon:reason === "COMPLETED" || reason === "NO_PATH_WITHIN_HORIZON" || reason === "NO_SOLUTION_WITHIN_HORIZON", optimality:"not-certified"}; const meta = {solverStatus:status,solverReason:descriptions[reason] || "",terminationReason:reason,searchOutcome,cbsExpanded:counters.expanded,counters:{...counters}}; return paths ? buildResultFromPaths(scenario, paths, meta) : {...stationaryPlanResult(scenario,status,meta.solverReason),...meta}; } if (scenario.robots.length > limits.cbsAgents) return finish("UNSUPPORTED","AGENT_LIMIT","INPUT"); function lowLevel(agent, constraints) { const r = scenario.robots[agent]; counters.lowLevelCalls++; const search = constrainedAstar(scenario.grid,r.start,r.goal,constraints,agent,maxT,limits.cbsLowLevelExpansions,{deadline,now}); counters.lowLevelExpanded += search.expanded; counters.lowLevelGenerated += search.generated; return search; } const rootPaths = []; for (let i = 0; i < scenario.robots.length; i++) { const search = lowLevel(i,[]); if (search.status !== "FOUND") return finish(search.status === "NO_PATH_WITHIN_HORIZON" ? "PARTIAL" : "TIMEOUT",search.status,"ROOT",i); rootPaths.push(search.path); } const open = [{constraints:[],paths:rootPaths,cost:cbsNodeCost(rootPaths),serial:0}]; counters.generated = 1; const seen = new Set([""]); while (open.length) { if (expired()) return finish("TIMEOUT","WALL_CLOCK_LIMIT","HIGH_LEVEL"); if (counters.expanded >= limits.cbsNodes) return finish("TIMEOUT","CBS_NODE_LIMIT","HIGH_LEVEL"); open.sort((a,b) => a.cost-b.cost || a.serial-b.serial); if (expired()) return finish("TIMEOUT","WALL_CLOCK_LIMIT","HIGH_LEVEL"); const node = open.shift(); counters.expanded++; const conflict = detectFirstPathConflict(node.paths,expired); if (conflict?.type === "limit") return finish("TIMEOUT","WALL_CLOCK_LIMIT","CONFLICT_CHECK"); if (!conflict) return finish("SOLVED","COMPLETED","HIGH_LEVEL",null,node.paths); for (const agent of [conflict.a,conflict.b]) { if (expired()) return finish("TIMEOUT","WALL_CLOCK_LIMIT","BRANCH",agent); const constraint = conflict.type === "vertex" ? {agent,type:"vertex",time:conflict.time,x:conflict.cell.x,y:conflict.cell.y} : {agent,type:"edge",time:conflict.time,from:agent===conflict.a?conflict.aFrom:conflict.bFrom,to:agent===conflict.a?conflict.aTo:conflict.bTo}; const constraints = node.constraints.concat([constraint]); const signature = constraintSignature(constraints); if (seen.has(signature)) continue; seen.add(signature); const search = lowLevel(agent,constraints); if (search.status === "NO_PATH_WITHIN_HORIZON") { counters.provenInfeasibleBranches++; continue; } if (search.status !== "FOUND") { counters.interruptedBranches++; return finish("TIMEOUT",search.status,"BRANCH",agent); } const paths = node.paths.slice(); paths[agent] = search.path; open.push({constraints,paths,cost:cbsNodeCost(paths),serial:counters.generated++}); } } return finish("PARTIAL","NO_SOLUTION_WITHIN_HORIZON","HIGH_LEVEL"); } return { solveCBS, constrainedAstar, cbsNodeCost, canHoldGoal, buildConstraintIndex, detectFirstPathConflict }; })(); __modules["src/metrics/plan-metrics.js"] = (() => { const { same, key } = __modules["src/core/grid-search.js"]; const { deepFreeze } = __modules["src/domain/scenario.js"]; const { trajectoryCosts } = __modules["src/domain/trajectory-costs.js"]; const { validatePlanResult } = __modules["src/validation/plan-validator.js"]; const { METRIC_MODEL, COST_POLICY } = __modules["src/domain/plan-contract.js"]; const { searchContractFor, comparisonContractFor, COMPARISON_CONTRACT_VERSION } = __modules["src/domain/planning-policy.js"]; const { objectiveScore, reweightSummary } = __modules["src/domain/comparison-policy.js"]; const analysisCache = new WeakMap(); function frozenTree(value) { if (!value || typeof value !== "object") return true; return Object.isFrozen(value) && Object.values(value).every(frozenTree); } function analyzePlan(scenario, result) { const cached = result && typeof result === "object" ? analysisCache.get(result) : null; if (cached && cached.scenario === scenario) return cached.value; const validation = validatePlanResult(scenario, result); const totalAgents = validation.totalAgents; const base = {metricModel:METRIC_MODEL,costPolicy:COST_POLICY,status:validation.status,costsAvailable:false, diagnosticOnly:true,totalAgents,completed:validation.completed,goalOccupancy:null,observedHorizon:null, makespan:null,sumOfCosts:null,totalTravelSteps:null,averageTravel:null,waitTicks:null, observedTravelSteps:null,observedAverageTravel:null,observedWaitTicks:null,plannerEvents:null, agents:[],replay:[],validation}; if (!validation.replaySafe) return deepFreeze(base); const observedHorizon = result.timeline.length - 1; const costsAvailable = validation.valid; const details = result.paths.map((path,i) => trajectoryCosts(path,scenario.robots[i].goal,observedHorizon)); const agents = details.map((d,i) => ({agentId:scenario.robots[i].id,goalReachedInRecord:d.goalSuffixStartTick !== null, goalSuffixStartTick:d.goalSuffixStartTick,finalArrivalTick:costsAvailable ? d.goalSuffixStartTick : null, travelSteps:d.travelSteps,waitTicks:d.waitTicks,cost:costsAvailable ? d.goalSuffixStartTick : null})); let cumulativePlannerEvents = 0; const replay = result.timeline.map((frame,t) => { const atGoal = frame.filter((p,i) => same(p,scenario.robots[i].goal)).length; const stepWaits = details.reduce((sum,d) => sum+d.waitPrefix[t]-(t ? d.waitPrefix[t-1] : 0),0); const plannerEvents = result.events ? result.events[t].conflicts : 0; cumulativePlannerEvents += plannerEvents; return {tick:t,atGoal,goalOccupancy:atGoal/Math.max(1,totalAgents)*100, stepWaits,waitTicks:details.reduce((sum,d) => sum+d.waitPrefix[t],0), travelSteps:details.reduce((sum,d) => sum+d.travelPrefix[t],0),plannerEvents,cumulativePlannerEvents}; }); const observedTravelSteps = agents.reduce((sum,a) => sum+a.travelSteps,0); const observedWaitTicks = agents.reduce((sum,a) => sum+a.waitTicks,0); const value = {...base,costsAvailable,diagnosticOnly:!costsAvailable,observedHorizon, completed:replay[observedHorizon].atGoal,goalOccupancy:replay[observedHorizon].goalOccupancy, makespan:costsAvailable ? Math.max(...agents.map(a => a.finalArrivalTick)) : null, sumOfCosts:costsAvailable ? agents.reduce((sum,a) => sum+a.cost,0) : null, totalTravelSteps:costsAvailable ? observedTravelSteps : null, averageTravel:costsAvailable ? observedTravelSteps/Math.max(1,totalAgents) : null, waitTicks:costsAvailable ? observedWaitTicks : null, observedTravelSteps,observedAverageTravel:observedTravelSteps/Math.max(1,totalAgents),observedWaitTicks, plannerEvents:cumulativePlannerEvents,agents,replay,validation}; deepFreeze(value); if (frozenTree(result) && frozenTree(scenario)) analysisCache.set(result,{scenario,value,details}); return value; } function metricsAtTick(scenario, result, requestedTick) { const fullPlan = analyzePlan(scenario,result); const tick = Math.max(0,Math.min(fullPlan.observedHorizon || 0,Math.trunc(requestedTick) || 0)); const replay = fullPlan.replay[tick] || {tick,atGoal:null,goalOccupancy:null,waitTicks:null,travelSteps:null,plannerEvents:null,cumulativePlannerEvents:null}; return {...replay,totalAgents:fullPlan.totalAgents,fullPlan,metricModel:METRIC_MODEL}; } function agentMetricsAtTick(scenario, result, agentIndex, requestedTick) { const fullPlan = analyzePlan(scenario,result); if (!Number.isInteger(agentIndex) || !fullPlan.agents[agentIndex]) return null; const tick = Math.max(0,Math.min(fullPlan.observedHorizon,Math.trunc(requestedTick) || 0)); const cached = analysisCache.get(result); const d = cached && cached.value === fullPlan ? cached.details[agentIndex] : trajectoryCosts(result.paths[agentIndex],scenario.robots[agentIndex].goal,fullPlan.observedHorizon); return {...fullPlan.agents[agentIndex],tick,travelSoFar:d.travelPrefix[tick],waitSoFar:d.waitPrefix[tick], remainingTravel:d.travelSteps-d.travelPrefix[tick],remainingWait:d.waitTicks-d.waitPrefix[tick], ticksToSettlement:fullPlan.costsAvailable ? Math.max(0,d.goalSuffixStartTick-tick) : null, costsAvailable:fullPlan.costsAvailable,diagnosticOnly:fullPlan.diagnosticOnly,metricModel:METRIC_MODEL}; } function summarizeSimulation(scenario, strategy, result, objectiveProfile = "balanced") { const metrics = analyzePlan(scenario,result); const {validation,replay,...totals} = metrics; const summary = {...totals,strategy,name:strategyName(strategy),valid:validation.valid,validation, validationConflicts:validation.vertexConflicts+validation.edgeConflicts, yieldCount:result.events ? result.events.reduce((sum,e) => sum+(e.yieldIds ? e.yieldIds.length : 0),0) : 0, recoveryCount:result.events ? result.events.filter(e => e.recovery).length : 0, unavailable:!validation.replaySafe,comparisonModel:COMPARISON_CONTRACT_VERSION,compareObjective:objectiveProfile,comparison:comparisonContractFor(objectiveProfile),searchContract:result.searchContract || searchContractFor(strategy),searchOutcome:result.searchOutcome || null,terminationReason:result.terminationReason || null,solverReason:result.solverReason || "",solverVersion:result.solverVersion || null}; return reweightSummary(summary,objectiveProfile); } function buildHeat(paths) { const heat = new Map(); for (const path of paths) for (const cell of path) heat.set(key(cell),(heat.get(key(cell)) || 0)+1); return heat; } function buildTrafficHotspots(paths, agentCount) { const cells = []; const visitors = new Map(); paths.forEach((path,index) => { for (const cell of path) { const k = key(cell); if (!visitors.has(k)) visitors.set(k,new Set()); visitors.get(k).add(index); } }); for (const [k,v] of buildHeat(paths)) if (v >= Math.max(3,Math.ceil(agentCount*.35))) { const [x,y] = k.split(",").map(Number);cells.push({x,y,score:v,pathSamples:v,distinctAgents:visitors.get(k).size}); } cells.sort((a,b) => b.score-a.score); return cells.slice(0,12); } function strategyName(v) { return ({priorityFirst:"Priority First",spacetime:"Prioritized Space-Time A*",cbs:"CBS"})[v] || v; } function shortStrategyName(name) { return name === "Prioritized Space-Time A*" ? "Prioritized ST A*" : name; } return { analyzePlan, metricsAtTick, agentMetricsAtTick, objectiveScore, summarizeSimulation, buildHeat, buildTrafficHotspots, strategyName, shortStrategyName }; })(); __modules["src/runtime/solver-api.js"] = (() => { const { SOLVER_IDS, validateScenario, validateSolverOptions, normalizeSolverOptions } = __modules["src/validation/input-validator.js"]; const { resolveExecutionLimits } = __modules["src/domain/execution-limits.js"]; const { copyScenario, deepFreeze } = __modules["src/domain/scenario.js"]; const { classifyMapNodes } = __modules["src/core/scenario-generator.js"]; const { searchContractFor, comparisonContractFor } = __modules["src/domain/planning-policy.js"]; const { CONTRACT_VERSION, METRIC_MODEL } = __modules["src/domain/plan-contract.js"]; const { normalizePlan } = __modules["src/domain/canonical-plan.js"]; const { solvePriorityFirst } = __modules["src/solvers/priority-first.js"]; const { solveSpaceTime } = __modules["src/solvers/prioritized-space-time.js"]; const { solveCBS } = __modules["src/solvers/cbs.js"]; const { validatePlanResult } = __modules["src/validation/plan-validator.js"]; const { summarizeSimulation } = __modules["src/metrics/plan-metrics.js"]; const solverRegistry = Object.freeze({priorityFirst:solvePriorityFirst,spacetime:solveSpaceTime,cbs:solveCBS}); function rejectedResult(status, reason, issues) { return deepFreeze({paths:[],timeline:[],events:[],status,solverStatus:status,terminationReason:reason,solverReason:issues.map(i => i.message).join(" "),inputIssues:issues,contractVersion:CONTRACT_VERSION,metricModel:METRIC_MODEL,rejected:true}); } function solve(scenario, options, requestedLimits = {}) { const input = validateScenario(scenario); if (!input.ok) return rejectedResult("INVALID","INVALID_SCENARIO",input.issues); const optionCheck = validateSolverOptions(options); if (!optionCheck.ok) return rejectedResult(optionCheck.issues.some(i => i.code === "UNKNOWN_SOLVER") ? "UNSUPPORTED" : "INVALID","INVALID_OPTIONS",optionCheck.issues); const resolved = resolveExecutionLimits(scenario,requestedLimits); if (!resolved.ok) return rejectedResult("INVALID","INVALID_LIMITS",resolved.issues); const model = copyScenario(scenario); if (scenario.bufferCells === undefined) { const markers = classifyMapNodes(model.grid,model.robots); model.bufferCells = markers.buffers; model.endpointCells = markers.endpoints; } deepFreeze(model); const normalizedOptions = Object.freeze(normalizeSolverOptions(options)); const result = solverRegistry[normalizedOptions.strategy](model,normalizedOptions,resolved.value); result.contractVersion = CONTRACT_VERSION; result.metricModel = METRIC_MODEL; result.solverVersion = normalizedOptions.strategy === "cbs" ? "v1_42-cbs-sum-of-costs" : normalizedOptions.strategy === "spacetime" ? "v1_48-prioritized-st-diagnostics" : "v1_39-extraction-v1_38-search"; result.searchContract = searchContractFor(normalizedOptions.strategy); result.comparisonAtSolve = comparisonContractFor(normalizedOptions.compareObjective); result.options = normalizedOptions; result.limits = resolved.value; if (!result.terminationReason) result.terminationReason = result.solverStatus === "UNSUPPORTED" ? "AGENT_LIMIT" : result.solverStatus === "PARTIAL" ? "NO_PLAN_WITHIN_SEARCH_LIMITS" : "COMPLETED"; result.validation = validatePlanResult(model,result); result.status = result.validation.status; if (!result.counters) result.counters = {ticks:result.timeline.length - 1}; const normalized = normalizePlan(model,result); return normalized.ok ? normalized.value : deepFreeze(result); } function compareScenario(scenario, options = {}, limits = {}) { const objectiveProfile = options.compareObjective || options.objectiveProfile || "balanced"; return SOLVER_IDS.map(strategy => { const started = performance.now(); const result = solve(scenario,{strategy,objectiveProfile},limits); return {...summarizeSimulation(scenario,strategy,result,objectiveProfile),runtimeMs:performance.now()-started,terminationReason:result.terminationReason}; }); } return { solve, compareScenario }; })(); __modules["src/io/scenario-snapshot.js"] = (() => { const { INPUT_LIMITS, OBJECTIVES, TRAFFIC_SCENARIOS, GOAL_RULES, SOLVER_IDS, isRecord, inputIssue, validateScenario, validateSolverOptions, normalizeSolverOptions } = __modules["src/validation/input-validator.js"]; const { copyScenario, deepFreeze } = __modules["src/domain/scenario.js"]; const { classifyMapNodes } = __modules["src/core/scenario-generator.js"]; function fnv1a32(text) { let hash = 0x811c9dc5; for (let i = 0; i < text.length; i++) { hash ^= text.charCodeAt(i); hash = Math.imul(hash, 0x01000193); } return hash >>> 0; } function canonicalScenarioData(scenario) { if (scenario.source?.kind === "manual") return {sourceType:"manual",movement:"four-way-unit-wait",goalOccupancy:"stay-at-target",grid:{w:scenario.grid.w,h:scenario.grid.h,cells:scenario.grid.cells.map(row=>row.slice())},robots:scenario.robots.map((r,id)=>({id,start:{x:r.start.x,y:r.start.y},goal:{x:r.goal.x,y:r.goal.y}}))}; return {trafficScenario:scenario.config ? scenario.config.trafficScenario : "cross", goalMode:scenario.config ? scenario.config.goalMode : "endpoint", grid:{w:scenario.grid.w,h:scenario.grid.h,cells:scenario.grid.cells.map(row => row.slice())}, robots:scenario.robots.map((r,i) => ({id:i,start:{x:r.start.x,y:r.start.y},goal:{x:r.goal.x,y:r.goal.y}}))}; } function computeScenarioId(scenario) { const hex = fnv1a32(JSON.stringify(canonicalScenarioData(scenario))).toString(16).toUpperCase().padStart(8,"0"); return hex.slice(0,4) + "-" + hex.slice(4); } function createScenarioSnapshot(scenario, options, exportedAt = new Date().toISOString()) { const data = canonicalScenarioData(scenario); if (scenario.source?.kind === "manual") return {format:"binnode-mapf-scenario",schemaVersion:2,scenarioId:computeScenarioId(scenario),exportedAt,source:{...scenario.source},movement:"four-way-unit-wait",goalOccupancy:"stay-at-target",planner:{strategy:options.strategy,objectiveProfile:options.compareObjective || options.objectiveProfile || "balanced"},grid:data.grid,robots:data.robots}; return {format:"binnode-mapf-scenario",schemaVersion:1,scenarioId:computeScenarioId(scenario),exportedAt,config:{...scenario.config},planner:{strategy:options.strategy,objectiveProfile:(options.compareObjective || options.objectiveProfile || "balanced")},grid:data.grid,robots:data.robots}; } function decodeScenarioSnapshot(snapshot, defaultOptions = {strategy:"priorityFirst",objectiveProfile:"balanced"}) { const reject = (code,field,message) => ({ok:false,issues:[inputIssue(code,field,message)]}); if (isRecord(snapshot) && snapshot.format === "binnode-mapf-scenario" && snapshot.schemaVersion === 2) return decodeManualSnapshot(snapshot,defaultOptions); if (!isRecord(snapshot) || snapshot.format !== "binnode-mapf-scenario" || snapshot.schemaVersion !== 1) return reject("SNAPSHOT_FORMAT","snapshot","Unsupported scenario snapshot format or schema version."); const checked = validateScenario(snapshot); if (!checked.ok) return checked; if (snapshot.robots.length < 2) return reject("AGENT_LIMIT","robots","Workspace snapshots require at least 2 agents."); if (snapshot.config !== undefined && !isRecord(snapshot.config)) return reject("INVALID_CONFIG","config","Snapshot config must be an object."); const raw = snapshot.config || {}; const config = {width:snapshot.grid.w,height:snapshot.grid.h,agents:snapshot.robots.length,density:raw.density === undefined ? 0 : raw.density,seed:raw.seed === undefined ? 1 : raw.seed,trafficScenario:raw.trafficScenario === undefined ? "cross" : raw.trafficScenario,goalMode:raw.goalMode === undefined ? "endpoint" : raw.goalMode}; for (const field of ["width","height","agents"]) if (raw[field] !== undefined && raw[field] !== config[field]) return reject("CONFIG_MISMATCH", "config."+field, "Config " + field + " differs from the actual snapshot data."); if (!Number.isInteger(config.density) || config.density < 0 || config.density > 38 || !Number.isInteger(config.seed) || config.seed < 1 || config.seed > 999999) return reject("CONFIG_RANGE","config","Snapshot seed or obstacle density is out of range."); if (!TRAFFIC_SCENARIOS.includes(config.trafficScenario) || !GOAL_RULES.includes(config.goalMode)) return reject("CONFIG_ENUM","config","Unknown traffic scenario or goal rule."); const rawOptions = snapshot.planner === undefined ? defaultOptions : snapshot.planner; const optionCheck = validateSolverOptions(rawOptions); if (!optionCheck.ok) return optionCheck; const options = normalizeSolverOptions(rawOptions); const model = copyScenario({...snapshot, config, endpointCells:[], bufferCells:[]}); const markers = classifyMapNodes(model.grid,model.robots); model.endpointCells = markers.endpoints; model.bufferCells = markers.buffers; const id = computeScenarioId(model); if (snapshot.scenarioId !== undefined && snapshot.scenarioId !== id) return reject("SCENARIO_ID_MISMATCH","scenarioId","Snapshot ID does not match its scenario content."); return {ok:true,issues:[],scenario:deepFreeze(model),config:{...config},options,scenarioId:id}; } function decodeManualSnapshot(snapshot,defaultOptions) { const reject=message=>({ok:false,issues:[inputIssue("MANUAL_SNAPSHOT","snapshot",message)]}); const s=snapshot.source; if(!isRecord(s)||s.kind!=="manual"||typeof s.name!=="string"||!s.name.trim()||s.name.length>80||/[\x00-\x1f]/.test(s.name))return reject("Invalid manual scenario source."); if(s.origin!=null&&(!isRecord(s.origin)||typeof s.origin.scenarioId!=="string"||s.origin.scenarioId.length>64))return reject("Invalid manual origin."); if(snapshot.movement!=="four-way-unit-wait"||snapshot.goalOccupancy!=="stay-at-target")return reject("Unsupported movement or goal policy."); const checked=validateScenario(snapshot);if(!checked.ok)return checked; const rawOptions=snapshot.planner===undefined?defaultOptions:snapshot.planner; const selection=validateSolverOptions(rawOptions);if(!selection.ok)return selection; const options=normalizeSolverOptions(rawOptions); const blocked=snapshot.grid.cells.reduce((sum,row)=>sum+row.reduce((a,b)=>a+b,0),0); const config={width:snapshot.grid.w,height:snapshot.grid.h,agents:snapshot.robots.length,density:100*blocked/(snapshot.grid.w*snapshot.grid.h),seed:null,trafficScenario:"manual",goalMode:"manual"}; const markers=classifyMapNodes(snapshot.grid,snapshot.robots); const model=copyScenario({...snapshot,config,endpointCells:markers.endpoints,bufferCells:markers.buffers,source:{kind:"manual",name:s.name,origin:s.origin?{scenarioId:s.origin.scenarioId}:null}}); const id=computeScenarioId(model); if(snapshot.scenarioId!==undefined&&snapshot.scenarioId!==id)return reject("Snapshot ID does not match its scenario content."); return {ok:true,issues:[],scenario:deepFreeze(model),config,options,scenarioId:id}; } function parseScenarioText(text, defaultOptions) { if (typeof text !== "string" || text.length > INPUT_LIMITS.snapshotBytes || new TextEncoder().encode(text).byteLength > INPUT_LIMITS.snapshotBytes) return {ok:false,issues:[inputIssue("FILE_TOO_LARGE","file","Scenario file must not exceed 1 MiB.")]}; let snapshot; try { snapshot = JSON.parse(text); } catch { return {ok:false,issues:[inputIssue("INVALID_JSON","file","Scenario file is not valid JSON.")]}; } return decodeScenarioSnapshot(snapshot, defaultOptions); } return { canonicalScenarioData, computeScenarioId, createScenarioSnapshot, decodeScenarioSnapshot, parseScenarioText }; })(); __modules["src/io/result-exporter.js"] = (() => { const { validateSolverOptions, isRecord, inputIssue } = __modules["src/validation/input-validator.js"]; const { normalizePlan } = __modules["src/domain/canonical-plan.js"]; const { createScenarioSnapshot } = __modules["src/io/scenario-snapshot.js"]; const { analyzePlan, buildTrafficHotspots } = __modules["src/metrics/plan-metrics.js"]; const { searchContractFor, comparisonContractFor } = __modules["src/domain/planning-policy.js"]; const { CONTRACT_VERSION, METRIC_MODEL, COST_POLICY } = __modules["src/domain/plan-contract.js"]; function createResultSnapshot(scenario, result, runtimeMs = 0, exportedAt = new Date().toISOString(), comparisonOptions = {}) { const normalized = normalizePlan(scenario,result); if (!normalized.ok) return {ok:false,validation:normalized.validation}; const plan = normalized.value; const options = validateSolverOptions(plan.options); if (!options.ok) return {ok:false,validation:plan.validation,issues:options.issues}; if (!isRecord(comparisonOptions) || Object.keys(comparisonOptions).some(k => !["compareObjective","objectiveProfile"].includes(k))) return {ok:false,validation:plan.validation,issues:[inputIssue("INVALID_COMPARISON_OPTIONS","comparisonOptions","Only comparison objective fields are accepted at export.")]}; const suppliedComparison = validateSolverOptions({strategy:plan.options.strategy,...comparisonOptions}); if (!suppliedComparison.ok) return {ok:false,validation:plan.validation,issues:suppliedComparison.issues}; const requested = {strategy:plan.options.strategy,compareObjective:comparisonOptions.compareObjective ?? comparisonOptions.objectiveProfile ?? plan.options.compareObjective ?? plan.options.objectiveProfile ?? "balanced"}; const comparisonCheck = validateSolverOptions(requested); if (!comparisonCheck.ok) return {ok:false,validation:plan.validation,issues:comparisonCheck.issues}; const {validation,replay,agents,...metrics} = analyzePlan(scenario,plan); const snapshot = createScenarioSnapshot(scenario,requested,exportedAt); const hotspots = buildTrafficHotspots(plan.paths,scenario.robots.length); const value = {format:"binnode-mapf-result",schemaVersion:3,exportedAt, scenario:snapshot, planner:{strategy:plan.options.strategy,requestOptions:plan.options,solverVersion:plan.solverVersion,limits:plan.limits, searchObjective:(plan.searchContract || searchContractFor(plan.options.strategy)).objective, searchContract:plan.searchContract || searchContractFor(plan.options.strategy),searchOutcome:plan.searchOutcome || null, terminationReason:plan.terminationReason,counters:plan.counters}, comparison:comparisonContractFor(requested.compareObjective), status:validation.status,solverStatus:plan.solverStatus,solverReason:plan.solverReason,summary:{...metrics,hotspots:hotspots.length,bottlenecks:hotspots.length,plannerRuntimeMs:Number.isFinite(runtimeMs) && runtimeMs >= 0 ? Number(runtimeMs.toFixed(4)) : null}, trafficHotspots:{model:"path-samples/1.0",definition:"Canonical path samples, including initial positions and transient waits; not validated collisions or structural bottlenecks.",cells:hotspots}, agentMetrics:agents,paths:plan.paths,timeline:plan.timeline,events:plan.events,validation, observedHorizon:plan.observedHorizon,canonicalVersion:plan.canonicalVersion,contractVersion:CONTRACT_VERSION, metricModel:METRIC_MODEL,costPolicy:COST_POLICY, compatibility:{scenarioSchemaVersion:snapshot.schemaVersion,legacyBottlenecks:"summary.bottlenecks aliases summary.hotspots; selection policy unchanged",previousResultSchemaVersion:2,legacyObjectiveProfile:"comparison alias only; use planner.searchObjective and comparison.objective",legacyAveragePath:"removed; use averageTravel in steps",legacyThroughput:"removed; use goalOccupancy in percent"}}; return {ok:true,value:JSON.parse(JSON.stringify(value))}; } return { createResultSnapshot }; })(); __modules["src/core-api.js"] = (() => { const { eligibleForComparison, comparisonKey, compareSummaries, reweightSummary, rankComparisons } = __modules["src/domain/comparison-policy.js"]; const { INPUT_LIMITS, SOLVER_IDS, validateScenario, validateGeneratorConfig, validateSolverOptions } = __modules["src/validation/input-validator.js"]; const { validatePlanResult } = __modules["src/validation/plan-validator.js"]; const { resolveExecutionLimits } = __modules["src/domain/execution-limits.js"]; const { deepFreeze, copyScenario } = __modules["src/domain/scenario.js"]; const { generateScenario, classifyMapNodes } = __modules["src/core/scenario-generator.js"]; const { solve, compareScenario } = __modules["src/runtime/solver-api.js"]; const { createScenarioSnapshot, decodeScenarioSnapshot, parseScenarioText, computeScenarioId } = __modules["src/io/scenario-snapshot.js"]; const { createResultSnapshot } = __modules["src/io/result-exporter.js"]; const { analyzePlan, agentMetricsAtTick, metricsAtTick, summarizeSimulation, objectiveScore, buildHeat, buildTrafficHotspots, strategyName, shortStrategyName } = __modules["src/metrics/plan-metrics.js"]; const { normalizePlan } = __modules["src/domain/canonical-plan.js"]; const { searchContractFor, compareObjectiveLabel, comparisonContractFor } = __modules["src/domain/planning-policy.js"]; const Core = Object.freeze({version:"v1_48-dev",INPUT_LIMITS,SOLVER_IDS,eligibleForComparison,comparisonKey,compareSummaries,reweightSummary,rankComparisons,searchContractFor,compareObjectiveLabel,comparisonContractFor,validateScenario,validateGeneratorConfig,validateSolverOptions,resolveExecutionLimits,validatePlanResult,deepFreeze,copyScenario,generateScenario,classifyMapNodes,solve,compareScenario,createScenarioSnapshot,decodeScenarioSnapshot,parseScenarioText,computeScenarioId,createResultSnapshot,normalizePlan,analyzePlan,agentMetricsAtTick,metricsAtTick,summarizeSimulation,objectiveScore,buildHeat,buildTrafficHotspots,strategyName,shortStrategyName}); return { Core }; })(); __modules["src/runtime/worker-protocol.js"] = (() => { const { Core } = __modules["src/core-api.js"]; const WORKER_PROTOCOL = "binnode-mapf-worker/1"; const WORKER_BUILD = "v1_43-worker-runtime"; function executePlannerRequest(request) { if (!request || !["generate", "solve"].includes(request.kind)) throw new Error("Unknown planner operation."); let scenario = request.scenario; if (request.kind === "generate") { const generated = Core.generateScenario(request.config); if (!generated.ok) throw new Error(generated.issues.map(issue => issue.message).join(" ")); scenario = generated.scenario; } const started = performance.now(); const plan = Core.solve(scenario, request.options, request.limits || {}); const runtime = performance.now() - started; if (plan.rejected) throw new Error(plan.solverReason || "Planner input was rejected."); return {scenario:request.kind === "generate" ? scenario : null, prepared:{plan, runtime}}; } return { WORKER_PROTOCOL, WORKER_BUILD, executePlannerRequest }; })(); __modules["src/runtime/worker-entry.js"] = (() => { const { WORKER_PROTOCOL, WORKER_BUILD, executePlannerRequest } = __modules["src/runtime/worker-protocol.js"]; self.onmessage = event => { const message = event.data; if (!message || message.protocol !== WORKER_PROTOCOL || message.build !== WORKER_BUILD || !Number.isSafeInteger(message.id)) return; try { const result = executePlannerRequest(message.request); self.postMessage({protocol:WORKER_PROTOCOL, build:WORKER_BUILD, id:message.id, type:"result", result}); } catch (error) { self.postMessage({protocol:WORKER_PROTOCOL, build:WORKER_BUILD, id:message.id, type:"error", message:error instanceof Error ? error.message : "Worker calculation failed."}); } }; self.postMessage({protocol:WORKER_PROTOCOL, build:WORKER_BUILD, type:"ready"}); return {}; })(); })();

At Tick 0Replay State

Full PlanIndependent of Playback

Computation