rt-lacam

Incremental multi-agent pathfinding with persistent search state.

rt-lacam implements Real-Time LaCAM with a high-performance Zig core and Python bindings. It keeps the explored configuration graph between planning steps, re-roots after execution, and continues searching under a configurable per-step time budget.

Install · Quick start · Algorithm · References

Ten agents solving the room-32-32-4 MAPF benchmark, rendered with mapf-visualizer.

Why RT-LaCAM?

Many real-time MAPF systems discard their search state and start over after every movement step. RT-LaCAM preserves useful work across steps while retaining completeness guarantees, making it a practical building block for lifelong planning and robot-fleet research.

Key properties

• Persistent incremental DFS across step() calls
• Configurable millisecond planning budgets
• Re-rooting from the agents' observed positions
• LaCAM* cost refinement mode
• PIBT configuration generation
• Zero-copy C ABI and Python cffi bindings
• Approximately 120 KB native library in ReleaseFast, with no runtime dependencies

Installation

From PyPI

pip install rt-lacam

Pre-built wheels are currently available for macOS on Apple Silicon. Other platforms build from source and currently require Zig 0.15.x; Zig 0.16 is not yet supported.

From source

git clone https://github.com/ekusiadadus/rt-lacam.git
cd rt-lacam
zig build
zig build test --summary all
python -m pip install -e ".[dev]"
pytest -v

Quick Start

from rt_lacam import RTLaCAM

# 5x5 open grid, 1 agent
grid = [[1]*5 for _ in range(5)]

with RTLaCAM(grid, starts=[(0, 0)], goals=[(4, 4)]) as solver:
    pos = [(0, 0)]
    for step in range(100):
        # Incremental DFS with 50ms budget per step
        result = solver.step(deadline_ms=50)
        if result is not None:
            pos = result
            solver.reroot(pos)  # re-root search tree
        # Check if agents are physically at goals (not just path found)
        if solver.is_solved(pos):
            print(f"All agents reached goals at step {step}!")
            break

Multi-Agent Example

from rt_lacam import RTLaCAM

grid = [[1]*10 for _ in range(10)]  # 10x10 open grid

solver = RTLaCAM(
    grid,
    starts=[(0, 0), (0, 9), (9, 0)],
    goals=[(9, 9), (9, 0), (0, 9)],
    flg_star=True,  # LaCAM* for better solution quality
)

positions = [(0, 0), (0, 9), (9, 0)]
for _ in range(200):
    result = solver.step(deadline_ms=100)
    if result:
        positions = result
        solver.reroot(positions)
    if solver.is_solved(positions):
        break

solver.close()

API Reference

RTLaCAM(grid, starts, goals, *, flg_star=False, seed=None)

Create a solver instance.

• grid: 2D list of int (1=passable, 0=obstacle)
• starts: list of (y, x) tuples — initial agent positions
• goals: list of (y, x) tuples — target positions
• flg_star: enable LaCAM* cost refinement (default: False)
• seed: PRNG seed for reproducibility (default: None)

solver.step(deadline_ms=100) -> list[(y,x)] | None

Run incremental DFS for up to deadline_ms milliseconds. Returns next positions or None if no solution found yet.

solver.reroot(current_positions)

Re-root the search tree after agents have moved. Call this with the actual new positions.

solver.is_solved(current_positions) -> bool

Whether all agents are physically at their respective goal positions. Use this to determine when to stop the planning loop.

solver.has_goal -> bool

Whether a goal configuration has been found in the search tree. Note: this does NOT mean agents have reached the goal — it means the solver has found a path. Use is_solved() to check physical arrival.

solver.explored_size -> int

Number of explored configurations.

Architecture

rt-lacam/
├── src/                     # Zig core (~3000 lines, 86 tests)
│   ├── solver.zig           # RT-LaCAM: incremental DFS + reroot
│   ├── pibt.zig             # PIBT configuration generator
│   ├── high_level_node.zig  # Configuration-space search node
│   ├── low_level_node.zig   # Constraint DFS node
│   ├── dist_table.zig       # Lazy BFS distance table
│   ├── grid.zig             # 2D obstacle grid
│   ├── config.zig           # Coord/Config types with hashing
│   ├── deque.zig            # Generic ring-buffer deque
│   └── exports.zig          # C ABI exports (9 functions)
├── python/rt_lacam/         # Python bindings via cffi
│   ├── __init__.py
│   └── _bindings.py         # RTLaCAM class
└── tests/                   # Python integration tests

Algorithm

RT-LaCAM (Liang et al., 2025) extends LaCAM (Okumura, 2023) for real-time, lifelong MAPF:

1. LaCAM performs a two-level search in configuration space. The high-level DFS explores joint configurations; the low-level constraint DFS generates candidate next configurations via PIBT.

2. RT-LaCAM adds three key mechanisms:

   • Persistent state: The explored graph and open list survive across planning steps.
   • Time-bounded iteration: Each step() call runs DFS only within a millisecond budget, returning the best known next configuration.
   • Re-rooting: After agents execute one step, reroot() updates the search tree's root to the actual configuration, enabling continued exploration.

3. Completeness: Because the search tree grows monotonically across steps and no explored state is discarded, RT-LaCAM is provably complete — if a solution exists, it will eventually be found (given sufficient total computation).

References

This implementation is based on the following papers. We are grateful to the authors for their foundational research in MAPF:

1. Runzhe Liang, Rishi Veerapaneni, Daniel Harabor, Jiaoyang Li, Maxim Likhachev. "Real-Time LaCAM for Real-Time MAPF." International Symposium on Combinatorial Search (SoCS), 2025. arXiv:2504.06091 — The primary reference for the real-time incremental DFS with re-rooting and completeness guarantees.

2. Keisuke Okumura. "LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding." AAAI Conference on Artificial Intelligence, 2023. arXiv:2211.13432 — The original LaCAM algorithm: two-level lazy DFS in configuration space with PIBT.

3. Keisuke Okumura. "Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding." IJCAI, 2023. arXiv:2305.03632 — LaCAM* extension with Dijkstra cost refinement for improved solution quality.

4. Keisuke Okumura, Manao Machida, Xavier Défago, Yasumasa Tamura. "Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding." Artificial Intelligence, 2022. arXiv:1901.11282 — PIBT: the single-step configuration generator used inside LaCAM.

5. He Jiang, Yulun Zhang, Rishi Veerapaneni, Jiaoyang Li. "Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities." Symposium on Combinatorial Search (SoCS), 2024. arXiv:2404.16162 — Analysis of windowed MAPF completeness and the need for persistent search state in lifelong settings.

6. Bojie Shen, Yue Zhang, Zhe Chen, Daniel Harabor. "A Lightweight Traffic Map for Efficient Anytime LaCAM*." 2026. arXiv:2603.07891 — Dynamic congestion guidance for LaCAM*, showing continued research interest in the LaCAM family.

Acknowledgments

This project was inspired by the excellent work of:

• Keisuke Okumura (@Kei18) for the original LaCAM and py-lacam reference implementation.
• Runzhe Liang, Rishi Veerapaneni, Daniel Harabor, Jiaoyang Li, and Maxim Likhachev for the Real-Time LaCAM paper that made incremental lifelong MAPF practical.
• Jiaoyang Li and the MAPF research community for their continued work on scalable multi-agent coordination.

The Zig implementation was built from scratch following the algorithm descriptions in the above papers, with the py-lacam Python implementation serving as a reference for correctness verification.

License

MIT License. See LICENSE for details.