LIMA

Local Intersection Marshalling Algorithm for large-scale multi-agent path finding

Project page

LIMA is a C++20 simulator for coordinating autonomous mobile robots (AMRs) on grid-based warehouse maps. It combines global route planning with local intersection control so dense robot traffic can be simulated, inspected, and replayed.

Highlights

• Detects and models intersections directly from a grid map
• Plans global routes with BFS or A*
• Coordinates corridor traffic with priority inheritance and backtracking
• Schedules intersection traffic with configurable local solvers
• Runs headlessly, in an SDL2 viewer, or through a JSON debugging interface
• Supports deterministic random tasks and MovingAI scenario files
• Records solution replays, metrics, and JSONL traces

Requirements

• CMake 3.20 or newer
• A C++20 compiler
• SDL2 and pkg-config for the optional graphical viewer
• Python 3 for the optional trace verification tool

Build

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j

If SDL2 is unavailable, CMake builds the headless executable and prints a warning. To explicitly disable the viewer:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release -DLIMA_BUILD_GUI=OFF
cmake --build build -j

Quick start

Run a deterministic headless simulation with randomly generated tasks:

./build/lima \
  --profile lima-default \
  --mode solve \
  --map data/maps/cross_9.map \
  --agents 40 \
  --seed 42 \
  --output results/cross_9.txt \
  --validate-conflicts

The command prints a summary and writes a replayable solution to results/cross_9.txt. Generated files under results/ are ignored by Git.

Run modes

Realtime viewer

Realtime mode computes the simulation while displaying it. It requires an SDL2-enabled build.

./build/lima \
  --profile lima-default \
  --mode realtime \
  --map data/maps/cross_9.map \
  --agents 40 \
  --seed 42 \
  --fps 30

Set --fps 0 to remove the timestep rate limit.

Solve

Solve mode runs without opening a window:

./build/lima \
  --profile lima-default \
  --mode solve \
  --map data/maps/warehouse_10_20.map \
  --agents 200 \
  --seed 42 \
  --output results/warehouse_200.txt

If --output is omitted, the solution is written to build/result.txt. Use --no-trace when no replay file is needed.

Replay

Replay a previously saved solution without running the planner again:

./build/lima \
  --mode replay \
  --map data/maps/warehouse_10_20.map \
  --replay results/warehouse_200.txt \
  --fps 30

Scenario input

LIMA accepts scenarios in the MovingAI benchmark format. The map and scenario must describe the same environment. Example scenario sets are included under data/scenarios/.

./build/lima \
  --profile lima-default \
  --mode solve \
  --map data/maps/warehouse_10_20.map \
  --scenario data/scenarios/warehouse-10-20/warehouse-10-20_s0.scen \
  --agents 100 \
  --output results/scenario.txt

--agents selects the first N tasks from the scenario.

Viewer controls

Key or gesture	Action
Space	Pause or resume
Left / Right	Move through replay frames while paused
Home / End	Jump to the first or last replay frame
Up / Down	Change playback speed
Mouse wheel or + / -	Zoom
Left or middle drag	Pan
F	Fit the map to the window
G	Toggle agent-to-goal lines
Esc	Close the viewer

Common options

Option	Description
--profile legacy|lima-default	Select a component configuration
--mode realtime|solve|replay|debug	Select the run mode
--map FILE	Load a MovingAI-format map
--scenario FILE	Load tasks from a MovingAI scenario
--agents N	Set the number of robots or scenario tasks
--planner bfs|astar	Select the global route planner
--seed N	Reproduce random task generation
--max-steps N	Limit the number of simulation timesteps
--fps N	Set viewer speed; 0 removes the limit
--output FILE	Write a solution trace
--replay FILE	Load a solution trace for replay
--validate-conflicts	Check vertex and edge conflicts while recording
--metrics DIR	Write per-run CSV metrics
--trace-jsonl FILE	Write a step-by-step JSONL trace

Run ./build/lima --help for the complete list of solver and coordination options.

Validate a JSONL trace

The included verifier checks movement adjacency, vertex conflicts, edge swaps, goal-only deactivation, and route preservation outside intersection zones.

./build/lima \
  --profile lima-default \
  --mode solve \
  --map data/maps/cross_9.map \
  --agents 40 \
  --seed 42 \
  --no-trace \
  --trace-jsonl results/cross_9.jsonl

python3 tools/verify_trace.py results/cross_9.jsonl

Tests

cmake -S . -B build -DLIMA_BUILD_GUI=OFF
cmake --build build -j
ctest --test-dir build --output-on-failure

Project structure

app/                 Command-line application
include/lima/        Public C++ headers
src/                 Core implementation
data/maps/           Example grid maps
data/scenarios/      MovingAI scenario sets
tests/               Automated contract tests
tools/               Trace verification utility

License

LIMA is available under the Apache License 2.0.