rt-lacam 0.1.2

Real-Time LaCAM: incremental MAPF solver with completeness guarantees

rt-lacam

Real-Time LaCAM: an incremental Multi-Agent Path Finding (MAPF) solver with completeness guarantees.

High-performance Zig core with Python bindings via cffi.

Overview

rt-lacam implements the Real-Time LaCAM algorithm, which enables incremental, anytime MAPF solving with persistent search state across planning steps. Unlike naive per-step replanning (which discards the search tree each iteration), RT-LaCAM preserves the explored configuration graph and re-roots it after agent execution, achieving theoretical completeness even under strict per-step time budgets.

Key Features

• Incremental DFS with configurable per-step time budgets (milliseconds)
• Persistent search state across step() calls — the core innovation over naive replanning
• Re-rooting after agent execution to continue search from actual positions
• LaCAM* mode with Dijkstra cost refinement for improved solution quality
• PIBT (Priority Inheritance with Backtracking) as the configuration generator
• Lazy BFS distance tables for efficient heuristic computation
• Zero-copy C ABI for integration with any language via FFI
• ~120KB native library (ReleaseFast), no runtime dependencies

Installation

From Source (requires Zig >= 0.15.0)

git clone https://github.com/ekusiadadus/rt-lacam.git
cd rt-lacam
zig build                          # build native library
zig build test --summary all       # run 86 Zig tests
pip install -e ".[dev]"            # install Python package with dev deps
pytest -v                          # run 17 Python tests

Build Wheel

zig build -Doptimize=ReleaseFast
cp zig-out/lib/librt_lacam.* python/rt_lacam/
pip install .

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 (~1100 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. Shuo Liang, Roni Stern, Jiaoyang Li. "Real-Time LaCAM." 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. "LaCAM*: Anytime Multi-Agent Pathfinding via Large Neighborhood Search." IJCAI, 2024. arXiv:2305.03632 — LaCAM* extension with Dijkstra cost refinement for improved solution quality.

4. Keisuke Okumura. "Priority Inheritance with Backtracking for Iterative Multi-Agent Path Finding." Artificial Intelligence, 2022. arXiv:2005.13948 — PIBT: the single-step configuration generator used inside LaCAM.

5. Yifan Bai, Rishi Veerapaneni, Jiaoyang Li. "Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings." AAAI Workshop on Multi-Agent Path Finding (WoMAPF), 2025. arXiv:2410.01798 — Analysis of windowed MAPF completeness and the need for persistent search state in lifelong settings.

6. Yimin Tang, Zhongqiang Ren, Jiaoyang Li, Katia Sycara. "Lightweight Traffic Map for 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.
• Shuo Liang, Roni Stern, and Jiaoyang Li 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.