No description
Find a file
Andy Li 92fe6dcf38 Add the League of Robot Runners maps to tiers 2 and 3 and the core
- src/bench/fetch_lorr.py: fetches LoRR's sortation_large,
  warehouse_large and warehouse_long_corridor_large from its
  Benchmark-Archive at a pinned commit, checking each against its git blob
  hash, and writes a plain grid beside LoRR's own file.
- gen/scen_gen.py: a map's own pickup and delivery points
  (original_format.map) are its POI.  --verify reports the measured POI
  share, not 15%.
- generate_scenarios.py: the manifest merge keeps keys that only some tasks
  report (poi_cells, poi_source).
- to_raster.py, convert_sites.py: tier-3 source lorr, converted from LoRR's
  file with its own alphabet.  terrain:Pickup and terrain:Delivery are
  appended to the class table; no existing site changes, so
  CONVERTER_VERSION stays 6.
- site_scen_gen.py, generate_site_scenarios.py: lorr sites are grid sites,
  with POI on the two classes.  free_m2 reads tier 2 at its new path.
- to_formats.py: clear_of_vertices replaces the STRtree query that dropped
  edges through a third vertex.  Same edges (checked on 11 sites), linear
  memory; the old query died on sortation_large's 24 M candidate edges.
- tier3.py, tiers.py: the LoRR maps are core, in the warehouse domain.  A
  core grid map's original_format.map is copied too.
- visualize.py, export_sites.py, build_examples.py: LoRR colours, keys and
  overviews.  examples/ gains the three LoRR overviews.
- Docs and TODO; benchmarks/ -> the LoRR data commit.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01Th5rxjKCh5uRe5JGqnZwdF
2026-11-10 23:32:29 +11:00
benchmarks@7f93b89a59 Add the League of Robot Runners maps to tiers 2 and 3 and the core 2026-11-10 23:32:29 +11:00
c Add the League of Robot Runners maps to tiers 2 and 3 and the core 2026-11-10 23:32:29 +11:00
examples Add the League of Robot Runners maps to tiers 2 and 3 and the core 2026-11-10 23:32:29 +11:00
scripts Add the League of Robot Runners maps to tiers 2 and 3 and the core 2026-11-10 23:32:29 +11:00
src Add the League of Robot Runners maps to tiers 2 and 3 and the core 2026-11-10 23:32:29 +11:00
.gitignore Stop tracking .DS_Store; point the feasibility tools at tier 1 2026-10-25 12:21:43 +11:00
.gitmodules Move benchmarks/ into the MAPF_Instance submodule 2026-10-06 09:07:25 +11:00
README.md Add the League of Robot Runners maps to tiers 2 and 3 and the core 2026-11-10 23:32:29 +11:00
TODO.md Add the League of Robot Runners maps to tiers 2 and 3 and the core 2026-11-10 23:32:29 +11:00

A MAPF benchmark on real environments

Multi-agent pathfinding is almost always benchmarked on the abstraction it is solved on: a solver plans on a grid and is scored on that same grid. Whether the plan is any good in the room the grid came from is never asked.

This benchmark asks it. You are given a real indoor environment. You choose an abstraction of it — an occupancy grid, a weighted grid, a polygonal subdivision, a roadmap — and plan on that. We score the resulting paths against the environment, not against your abstraction.

A solver that wins by exploiting a coarse abstraction loses here, because the abstraction is not what it is measured on.

Getting the instances

The maps and scenarios live in their own repository, MAPF_Instance, mounted here as the benchmarks/ submodule. A plain clone is code only, and benchmarks/ stays empty until you ask for it:

git clone --recurse-submodules https://git.andyli.info/andyli/MAPF_benchmark.git
git submodule update --init          # or later, inside a plain clone

Checked out, the instances are 29 GB in two folders:

  • core/ (2.4 GB) is the benchmark to report on.
    • Grid: the 33 maps MAPF Tracker reports results on, with tier 2's generated scenarios of up to 40,000 agents (32 maps: one is a tree that admits no multi-agent instance). Also the League of Robot Runners' three large warehouse maps: its sortation map and two fulfillment-centre maps.
    • Sites: 132 tier-3 sites. These are the same 36 grid maps as 2.5D sites, plus 96 indoor sites, 48 HouseExpo and 48 ProcTHOR, four from each of twelve layout groups (core_sites.json, chosen by scripts/select_core_sites.py). Every core site ships the seven exported formats and a picture of each.
  • extended/ holds the three tiers whole:
    • tier 1, the published MovingAI benchmark;
    • tier 2, all 842 MovingAI grid maps and the 3 League of Robot Runners maps, with 4,725 generated scenario files;
    • tier 3, all 47,840 sites, one zip each, holding the site, the file it was converted from and its 75 scenario files.

core/ is a copy of part of extended/ (src/bench/tiers.py --sync), laid out to be read:

  • the 33 maps are grouped into MAPF Tracker's seven domains (city, empty, game, maze, random, room, warehouse);
  • the indoor sites are grouped by layout group and named <source>-<group>-<rank>, such as houseexpo-M-open-compact-1.

The sites are zipped in git and unpacked locally. Core's take seconds and 2.2 GB; all of tier 3 takes ~5 min and 131 GB:

python3 scripts/pack_sites.py --unpack --core
python3 scripts/pack_sites.py --unpack

examples/ shows one overview picture per kind of site.

benchmarks/README.md describes the tiers; scripts/generate_scenarios.py is the code that produced every generated scenario, and regenerates any of them byte for byte.

Ground truth: a 2.5D raster

Every site is one file, <id>.site: three co-registered layers plus their metadata. Beside it, original_format.<ext> is the scene it was converted from, byte for byte, in the source's own format (a HouseExpo or ProcTHOR .json, a MovingAI .map).

part type contents
floor float32 floor height, metres
ceiling float32 height of the lowest obstacle above the floor
semantic uint16 class id per cell — wall, room type, object type
metadata JSON resolution, origin, class table, provenance, content hash

The file is a fixed 64-byte header, then the metadata, then each layer as a raw row-major little-endian array, so C reads it with fread and no parser. c/mapf_site.h is a single C/C++ header that reads sites and scenario files and computes where the robot fits, with the same result as the Python tools, bit for bit. c/README.md gives the byte layout; src/terrain/site_file.py is the Python reader and writer.

Why these three:

  • floor + ceiling make passability a function of the robot rather than a property of the cell: passable iff ceiling − floor > robot_height. A single occupancy layer has to commit to one answer for every robot, and an overhanging obstacle has no right answer — a wall-mounted shelf at 1.4 m is a wall to a tall robot and open floor to a short one. Note what the adopted sources can and cannot fill here: see What each fills. Furniture arrives as solid boxes, so the layer is currently exercised by wall-mounted and elevated fixtures, not by driving under tables.
  • semantic lets a cost model differentiate without re-deriving geometry, and lets users substitute their own weights.

Ground truth is a raster rather than a mesh or a point cloud because scoring is millions of queries — is this pose in collision, what does this segment cost — and a raster answers both in O(1) with no ambiguity about what the absence of data means.

Clearance and speed are derived, never stored

Clearance depends on robot radius; speed depends on the cost model. Both are benchmark parameters, not properties of the room. Storing them would bake one robot into the ground truth forever.

They are computed at scoring time from the four layers. On a real 17.9 × 5.9 m plan at 5 cm, a robot of radius 0.3 m loses 14% of the free space to clearance alone, and 29% of the remaining cells are speed-limited — mostly doorways and wall-adjacent strips. A 0.2 m robot sees a different map, which is precisely why it is not baked in.

Reproducibility

Each site manifest carries a content_sha256 over the four layers and the parameters that produced them — converter version, resolution, origin, height table. to_raster.py --expect-sha256 <hash> fails if a locally built site does not match, so two labs reporting on the same scene are demonstrably scoring the same thing. CONVERTER_VERSION is part of the hash, so a change that alters output invalidates published hashes loudly rather than producing quietly incomparable numbers.

The two datasets

HouseExpo ProcTHOR-10k
scenes 35,126 floor plans 10,000 houses
licence MIT Apache-2.0
download 24 MB (json.tar.gz) 63.4 MB (train/val/test.jsonl.gz)
extracted 105 MB + 1.5 MB asset-database.json
obstacles walls only walls and furniture
distribution GitHub raw git-LFS repo allenai/procthor-10k

Together: ~90 MB compressed, ~250 MB on disk, 45,126 scenes. Both are permissively licensed, so derived maps ship with the benchmark — no terms to accept, no gated downloads, no data anyone has to fetch themselves.

What each fills

floor ceiling semantic
HouseExpo flat binary — wall or not room category
ProcTHOR flat per-object heights, solid to the floor object types + room

The pair is a two-rung ladder: empty rooms, then furnished rooms.

HouseExpo is 2D promoted to 2.5D — its height dimension is a constant the converter supplies, not data, and with walls only there is nothing overhead at all. Useful for scale and for isolating pure geometry.

ProcTHOR adds furniture with heights. Each house JSON gives assetId, position and rotation; asset-database.json gives that asset's boundingBox: {x, y, z}. Joining them is pure Python — no Unity, no simulator — and the y dimension gives each obstacle a height, so a 1.8 m cabinet and a 0.4 m footstool are no longer the same cell.

What it does not give is traversable space underneath. A bounding box records extents, and position.y its centre, so a floor-standing table spans [0, height] and is solid from the floor up. ceiling is 0 there and the table blocks every robot, short or tall. We take that reading deliberately: granting an underside would restore the drive-under-a-table story at the cost of erasing table and chair legs, which shrinks obstacles — the failure this benchmark exists to punish. The leg geometry is absent from the source, and we do not invent it.

Measured consequence, across 20 ProcTHOR val houses at 5 cm: taking ceiling as the lowest obstacle above the floor leaves 0.30% of cells with an intermediate ceiling — 16.8% blocked, 83% fully open. The vertical dimension is therefore real but thinly exercised, and what exercises it is wall-mounted and elevated fixtures rather than furniture. A scanned source would fill it properly; see NOTES.md for why none is currently redistributable.

Two things to know about ProcTHOR:

  • Assets are axis-aligned bounding boxes, not meshes, so a chair is a solid rectangle and the gap between its legs is lost, horizontally and vertically alike. That is conservative — obstacles grow rather than shrink — which is the direction this benchmark requires anyway, and it is the reason furniture is solid rather than a canopy.
  • asset-database.json lives in the code repo, not the dataset repo. A prior.load_dataset("procthor-10k") fetches houses only, and the converter is useless without the bounding boxes. Easy to miss when writing install steps.

The houses are JSONL, one per line, gzipped, so the adapter streams and converts selected scenes without unpacking all 63 MB.

Neither dataset records traversal cost. Where a semantic class should modulate speed, that is a documented benchmark decision, not data — declared in the site manifest so results stay comparable. Clearance is derived from geometry and is identical for everyone.

The grid maps, in the same container

The 845 grid maps that make up tiers 1 and 2 (842 from Moving AI, 3 from the League of Robot Runners) also convert into the 2.5D raster, so one scorer reads every site in the benchmark rather than one path for real environments and another for grids.

Be clear about what that conversion is. A .map is already an abstraction: there is no room behind AR0011SR, so floor and ceiling cannot be recovered from it, only declared from passability. Only semantic carries anything the source actually stated — the terrain letter. Every grid-derived site says exactly this in its manifest's layers_synthesised, and nothing in the conversion invents sub-cell geometry: upsampling replicates a cell, it does not refine it.

Two parameters make the result standard rather than arbitrary:

parameter default why
--cell-size 1.0 m per grid cell the classical grid-MAPF reading: one agent per cell, corridors a metre wide
--res 0.25 m raster cell four raster cells per grid cell

The raster is finer than the grid because at 1:1 the cost model does nothing at all: every passable cell is at least 1.0 m from an obstacle, so a 0.3 m robot is never constrained, speed is v_max everywhere, and cost collapses back to uniform-cost grid MAPF. At 4:1 clearance has a 0.25 m quantum, so a one-cell corridor, a two-cell corridor and an open hall are three different speeds, and robot radius discriminates across the range a real mobile base spans (0.25–0.75 m). On den312d the effect is visible: 4.5% of grid-passable cells are too tight for a 0.3 m robot, and 11% of the rest are speed-limited.

Replication is exact — four identical cells per grid cell, no boundary moved — so this refines the robot against the geometry without inventing geometry.

Passability follows the Moving AI alphabet — ., G, S passable, @, O, T, W blocked — with one exception. The weighted collection uses A–P as traversal costs, not passability: every cell is traversable and none is an obstacle. The two alphabets never overlap — across all 842 maps the eleven standard collections use only .@TSW and weighted uses exactly A–P — so the mode is detected, not configured. This matters because O is out-of-bounds in one reading and cost 15 in the other.

The League of Robot Runners maps have an alphabet of their own: @ and T blocked; ., E (a delivery point) and S (a pickup point) passable. In LoRR's file S is not swamp. Their tier-3 sites are converted from LoRR's own file, so the pickup and delivery points become the terrain:Pickup and terrain:Delivery classes; tier 2's .map writes them as plain ..

Those cost letters are recorded but carry unit cost, exactly like every other site. Speed comes from clearance alone and the cost model never reads semantic, so a weighted site is traversed at the same rates as any other. The letters are kept in semantic rather than flattened to Ground because keeping them is free and reversible — a user who wants weighted regions has the field to key on, which is what semantic is for — while discarding them could not be undone without reconverting.

A consequence worth stating: a weighted site has no obstacles at all, so clearance is unbounded and nothing is slowed. Those twenty sites are featureless open planes that happen to carry a cost field, and they are 31% of the raw bytes.

Abstractions — what solvers consume

Raster

representation format
occupancy grid Moving AI .map — the existing grid-MAPF standard, read by every current solver
occupancy grid, tri-state .pgm + .yaml — ROS map_server; adds unknown as distinct from free and blocked
weighted grid GeoTIFF float32 or ESRI ASCII .asc — one speed per cell, m/s

Vector

representation format
polygonal subdivision, weighted regions GeoJSON — one Feature per region, properties.speed in m/s, 0 for obstacles
explicit graph — visibility graph, roadmap DIMACS .co + .gr — coordinates are mandatory, or a path cannot be lifted back
mesh OBJ or PLY
navigation mesh GeoJSON, our convention — convex polygons plus properties.neighbours

Derivation is conservative

Abstractions are derived so obstacles grow, never shrink. A path valid in an abstraction is therefore valid in the environment, and its cost is an upper bound on the true optimum. The reverse convention would let a solver win by cutting corners its abstraction had erased. Every simplification tolerance is recorded in the site manifest.

Solutions — what you return

One format for every abstraction. Waypoints in world coordinates and continuous time:

version 1
agents 2
agent 0 waypoints 3
12.500 8.000 0.000
13.500 8.000 1.414
14.500 9.000 3.121
agent 1 waypoints 2
4.000 1.200 0.000
4.000 9.500 6.250
  • x y t — metres in the site frame, seconds from episode start
  • between consecutive waypoints an agent moves in a straight line at constant speed; that is the whole motion model
  • waiting is two waypoints at the same x y with different t
  • t is strictly increasing per agent; the first need not be 0, so departures may be staggered
  • the last waypoint must be the agent's goal

A grid solver emits cell centres, a polygon solver emits corners. Neither needs to know how the other works, and scoring does not need to know which produced a given file.

Cost semantics

Cost is time, in seconds. Not steps, not cells entered.

This is what classical MAPF already measures — sum-of-costs is the sum of arrival timesteps, and waiting costs a timestep despite entering no cell. We keep that and make it continuous, so the environment can affect it.

Speed comes from clearance: how far away the nearest obstacle is.

clearance = distance to the nearest cell where ceiling - floor <= robot_height
speed     = v_max * clip((clearance - robot_radius) / (d_safe - robot_radius), 0, 1)
duration of a straight segment = integral of ds / speed(s)

A robot cannot take a doorway at open-floor speed. That is not an invented penalty — it is what every real local planner does, and what a ROS costmap's inflation layer encodes. Furniture and walls become a weighted region for free, from geometry alone, with no per-material physics to guess at.

Consequences, all deliberate:

  • Durations are not integers and not uniform, so plans are not synchronous and conflicts are checked in continuous time rather than at integer timesteps.
  • Waiting costs its own duration, at the same rate as moving.
  • Conflicts are geometric. Agents are discs of radius r; two agents conflict when their discs overlap at any instant. There are no vertex or edge conflicts, because there are no vertices.

Objectives, in seconds:

  • sum of costs — Σ over agents of (arrival − start)
  • makespan — max over agents of arrival

Scoring

A submitted solution is checked against the ground truth:

  1. every waypoint is on passable ground — ceiling − floor > robot_height
  2. every segment stays passable along its length
  3. no two agents' discs overlap at any instant
  4. every agent ends at its goal
  5. cost is recomputed from the ground truth — the solver's own estimate is ignored

A plan that is optimal on its abstraction and invalid in the environment scores nothing. That is the point of the benchmark.

Not supported

Read and scored: the formats above, nothing else.

Unsupported: Shapefile, GeoPackage, GraphML, glTF, STL, OSM, OpenDRIVE, raw point clouds, OctoMap, and true multi-level environments. A single (floor, ceiling) pair per cell expresses one free vertical interval — enough for an overhang, not for a staircase, a second storey, or a shelf with traversable space both under and over it; multi-level would be a stack of such pairs with explicit links, and is not implemented.

Also unsupported: partial observability. The ground truth is fully known to the scorer and to the solver, and there is no unknown-space class. An earlier observed.u8 layer reserved one, but no adopted source has any notion of observability — both are generated geometry rather than observations of anything — so it could only ever be 1 everywhere, making its clause in the passability test vacuous while implying a capability the benchmark did not have. It was removed in CONVERTER_VERSION = 2. Adding a scanned source would reintroduce it as a real layer and bump the version again.