GRACE: A Unified 2D Multi-Robot Path Planning Simulator & Benchmark for Grid, Roadmap, And Continuous Environments

AI summary

Overview

• Research area: Multi-robot path planning — specifically Multi-Agent Pathfinding (MAPF) and Multi-Robot Motion Planning (MRMP), and the simulators and benchmarks used to evaluate planners in those areas.
• Technical level: Intermediate. The paper is a systems/benchmarking contribution; readers benefit from some familiarity with MAPF terminology (grids, conflict-based search, sum-of-costs, makespan), but the architecture and experimental design are described in accessible terms.
• Scope in one sentence: GRACE is a single 2D simulator and benchmark that lets the same multi-robot task be expressed at three abstraction levels — occupancy grid, roadmap graph, and continuous space — and evaluated under one shared protocol.

What This Paper Is About

Research on coordinating multiple robots has split into two traditions: grid-based MAPF, which scales to very large teams under simplifying assumptions like discrete time and uniform agents, and MRMP, which operates in continuous space with realistic footprints and dynamics but at much smaller scale. Because these communities use different simulators, different instance definitions, and different instrumentation, it has been hard to answer basic questions such as whether a roadmap abstraction is "good enough," or how MAPF and MRMP planners actually compare on the same task. GRACE addresses this by defining explicit, reproducible conversion operators between grid, roadmap, and continuous representations, letting one physical scenario be planned at all three levels and measured with the same metrics.

Key Contributions

1. A unified simulator and benchmark supporting grid, roadmap, and continuous representations within a single API and evaluation protocol, implemented as a C++20 core built on Box2D with an interactive UI (SFML + ImGui) and external planners connected through a unified interface.
2. Explicit, reproducible abstraction operators — environment operators Φ_env^ρ and agent operators Φ_ag^ρ for ρ ∈ {cont, road, grid} — plus cross-representation conversion mechanisms (continuous→roadmap, continuous→grid, roadmap→grid, grid→continuous, roadmap→continuous) so that cross-representation studies do not require re-authoring scenarios.
3. An empirical study on a shared instance set that (i) compares representations on the same tasks across four map families, (ii) benchmarks six planner families on grids using canonical community maps and scenarios, and (iii) reports determinism and observed scalability up to approximately 2k agents in the authors' setup.
4. A capability comparison table positioning GRACE against existing platforms (MovingAI-related, asprilo, Flatland, LoRR, POGEMA, MRP-Bench, mrmg-planning, REMROC, SMART) across representation, continuous space–time environment/planning, agent dynamics, heterogeneous agents, and scale.

Main Findings

• Roadmap abstraction is "good enough" in the tested tasks. Across the four map families, roadmap sum-of-costs (SoC) stayed within approximately 108–118% of continuous MRMP, while makespan dropped to approximately 52–61% and planning time to approximately 0.16–1.6% of db-CBS.
• Grid trades more path cost for speed. Grids averaged approximately 123% SoC and approximately 61% makespan at approximately 2.4% of the planning time, i.e., more SoC penalty for comparable makespan and extreme planning speed.
• Roadmap density is a controllable knob. Superdense roadmaps tightened SoC to 108% and makespan to 52% at a modest runtime of 1.6%, compared with sparser roadmaps.
• Makespan is not directly comparable across representations. The paper states that makespan across MRMP and MAPF should be read qualitatively and relative to the per-map continuous baseline because the time and kinematic models differ (double-integrator versus single-integrator/unit-step).
• LaCAM achieved 100% success across the nominal grid sweep. In the grid-only benchmark on four maps with 25 scenarios each, LaCAM reached 100% success across the entire agent-count sweep on all four maps in the authors' setting, and maintained 100% success until N = 2500 in the extended 1-minute-budget regime.
• Other grid planners degrade differently by map. EECBS was strongest at low–mid N but degraded earlier on den312d and maze-32-32-4, MAPF-LNS2 degraded more gradually at larger N, and the learned/hybrid methods (MAPF-GPT-DDG, SCRIMP) could match or exceed search on random and warehouse maps but showed higher across-map variance.
• Solution quality tracked optimality on the common-success subset. Averaged over instances where all planners succeeded, CBSH2-RTC achieved the lowest mean SoC (3827 ± 286 m), followed by EECBS (3940 ± 288 m), MAPF-LNS2 (4206 ± 321 m), MAPF-GPT-DDG (4257 ± 333 m), LaCAM (4511 ± 358 m), and SCRIMP (5290 ± 422 m). Mean planning time ranged from 0.01 ± 0.00 s (LaCAM) to 20.86 ± 1.56 s (SCRIMP).
• Simulator scalability on large grid playback. Replaying LaCAM plans on warehouse_large (540 m × 140 m) with teams up to N = 2500, GRACE sustained real time (RTF ≥ 1) at the largest tested team size, and remained above the RTF = 10 reference level at approximately N = 550.
• Small, linear memory footprint. Peak memory grew linearly with team size with a least-squares slope of approximately 0.179 MB/agent and R² = 1.00; peak CPU stabilized around 100–110% in that configuration (measured with collision checking enabled).
• Determinism. Given the same instance, seeds, and step parameters, the paper states the state trace is bitwise identical.

Methodology in Plain English

The authors built a single simulation platform whose planning problem is defined once and then specialized. A workspace is a bounded 2D region with polygonal obstacles; three environment operators convert it into either the raw continuous free space, a directed roadmap graph extracted with OMPL, or an M-connected occupancy grid. Three agent operators similarly convert each robot — which may have an arbitrary convex footprint and its own motion profile — into continuous agents (unchanged), disc agents of radius r_com with stop-and-go single-integrator motion (roadmap), or homogeneous tile-sized discs with discrete unit-time moves (grid). The grid cell side is derived from the connectivity, a(M) = 2 L_max(M) r_com, so 4-connectivity gives a(4) = 2 r_com and 8-connectivity gives a(8) = 2√2 r_com.

For each representation, feasibility is defined explicitly: continuous plans must keep swept footprints inside free space and disjoint from each other; roadmap plans enforce vertex capacity 1, no head-on edge swaps, same-edge headway of at least 2 r_com / ν, and treat geometric edge intersections as virtual vertices with capacity 1; grid plans forbid co-occupancy, opposing edge swaps, diagonal crossings, and corner-meets. The simulation core runs deterministically in continuous time using Box2D at 60 Hz (Δt_sim = 1/60 s) with default substepping n = 4, using broad-phase dynamic AABB trees and narrow-phase contact manifolds, and logs contact events, nearest-approach distances, and tracking error.

For evaluation, the authors integrated official planner implementations through shared libraries or subprocesses and ran everything headless with fixed seeds and recorded manifests. All planners ran under identical instance definitions and budgets: 1 minute for grid and roadmap, 5 minutes for continuous, with default hyperparameters. Metrics include success rate, SoC (path length in meters), makespan (seconds), planning time (seconds), and Real-Time Factor (RTF = simulated time / wall time). The representation study used a 5 × 5 m² workspace with four map families (empty, maze, warehouse, window), up to N = 8 robots with heterogeneous convex footprints (maximum effective radius 0.08 m), three roadmap densities (sparse, dense, superdense), 32 × 32 grids, and continuous double-integrator bounds of v ∈ [−0.5, 0.5] m/s and a ∈ [−2, 2] m/s². The grid planner study used four canonical maps from the MovingAI community (random-64-64-10, maze-32-32-4, warehouse-10-20-10-2-1, den312d) with 25 scenarios each and 1-meter tiles. All experiments ran on a laptop with an Intel Core i7-13850HX CPU, 32 GB of memory, and an NVIDIA RTX 3500 Ada (12 GB) for learning-based planner inference.

Why This Matters

Impact on research. The paper argues that the current ecosystem fragments comparison: grid-centric MAPF simulators scale but omit dynamics, continuous time, and heterogeneity, while general-purpose robotics simulators offer fidelity but make cross-representation benchmarking cumbersome. By consolidating representation, execution, and evaluation into one platform with explicit conversion operators, GRACE aims to make cross-representation studies commensurate and to enable head-to-head comparison of classical, learning-based, and hybrid planners. Notably, it is compatible with established grid-style community maps from LoRR and Flatland, so grid-only studies can be run without abandoning a unified protocol.

Real-world applications (as contexts the work touches on):

• Warehouse and fulfillment robotics, where teams of mobile robots share aisles and where the paper's finding that environmental structure such as aisles can favor discrete abstractions is directly relevant.
• Intralogistics and smart-factory settings, including the sortation and fulfillment domains used in community competitions.
• Fleet management for large robot teams, which the authors name as a target for future connectors alongside ROS 2.
• Selecting a planning abstraction for a deployment — deciding when a roadmap or grid model is sufficient and when kinodynamic fidelity is actually required.

Industry relevance. The authors are affiliated with Robert Bosch GmbH Corporate Research and the Technical University of Berlin, and the explicit motivation is to support transparent, reproducible comparisons and the translation of planning research into practice. GRACE is open source (github.com/boschresearch/GRACE), and the paper demonstrates that the stack runs at real time on a modest laptop with a small per-agent memory footprint, which matters for teams that need to test planners at scale without specialized hardware.

Future Directions

• Uncertainty and dynamic changes. The formulation assumes static, fully known environments and single-shot tasks with fixed start-goal pairs; the authors list uncertainty and dynamic changes as future work.
• Lifelong and multi-goal settings. Current agents park at their goals once they arrive, so ongoing or repeated task assignment is not currently modeled.
• Richer motion dynamics and objectives, plus automated abstraction/roadmap selection. The framework does not fix the objective J and supports metrics across representations, leaving room for more objectives and for automating the choice of abstraction or roadmap density.
• Connectors to operational stacks. The authors plan integrations with ROS 2 and Fleet Management Systems (FMS) to move toward deployment.

Target Audience

Researchers and engineers working on multi-agent pathfinding and multi-robot motion planning, including those developing new grid, roadmap, or continuous planners who need a reproducible way to compare against baselines. It is also relevant to benchmarking and evaluation-focused researchers, robotics practitioners selecting a planning abstraction for warehouse, intralogistics, or fleet-scale deployments, and industry teams evaluating whether an open, deterministic simulation stack is sufficient for their scaling and reproducibility requirements. Readers looking for new planning algorithms themselves will not find them here — the contribution is the platform, the abstraction operators, and the comparative study they enable.

Authors’ abstract

Advancing Multi-Agent Pathfinding (MAPF) and Multi-Robot Motion Planning (MRMP) requires platforms that enable transparent, reproducible comparisons across modeling choices. Existing tools either scale under simplifying assumptions (grids, homogeneous agents) or offer higher fidelity with less comparable instrumentation. We present GRACE, a unified 2D simulator+benchmark that instantiates the same task at multiple abstraction levels (grid, roadmap, continuous) via explicit, reproducible operators and a common evaluation protocol. Our empirical results on public maps and representative planners enable commensurate comparisons on a shared instance set. Furthermore, we quantify the expected representation-fidelity trade-offs (MRMP solves instances at higher fidelity but lower speed, while grid/roadmap planners scale farther). By consolidating representation, execution, and evaluation, GRACE thereby aims to make cross-representation studies more comparable and provides a means to advance multi-robot planning research and its translation to practice.