- 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 |
||
|---|---|---|
| benchmarks@7f93b89a59 | ||
| c | ||
| examples | ||
| scripts | ||
| src | ||
| .gitignore | ||
| .gitmodules | ||
| README.md | ||
| TODO.md | ||
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 byscripts/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 ashouseexpo-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+ceilingmake passability a function of the robot rather than a property of the cell: passable iffceiling − 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.semanticlets 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.jsonlives in the code repo, not the dataset repo. Aprior.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 ywith differentt tis strictly increasing per agent; the first need not be0, 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:
- every waypoint is on passable ground —
ceiling − floor > robot_height - every segment stays passable along its length
- no two agents' discs overlap at any instant
- every agent ends at its goal
- 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.