Project LaCAM

This page summarises the LaCAM (lazy constraints addition search) algorithm for multi-agent pathfinding (MAPF) and its variants. LaCAM's goal is to provide a quick, scalable, and reliable solution for MAPF.

LaCAM suboptimally solves MAPF for 10k agents in a warehouse-style map with many narrow corridors in 5 seconds on my laptop.

Introduction

Core idea (Monash Univ., 2024)

MAPF-specific (EurMAPF-25; YouTube video is available)

YouTube videos

Research

Listed only those in which KO was involved.

Foundation

Pathfinding with Lazy Successor Generation

Okumura, K. · preprint · 2024

Enhancements, Extensions, Applications

Engineering LaCAM*: Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding

AAMAS 2024

Lightweight and Effective Preference Construction in PIBT for Large-Scale Multi-Agent Pathfinding

SoCS 2025

Okumura, K., Nagai, H.

LF: Online Multi-Robot Path Planning meets Optimal Trajectory Control

arXiv preprint 2025

Shankar, A, Okumura, K., Prorok, A.

Local Guidance for Configuration-Based Multi-Agent Pathfinding

AAAI 2026

Arita, T., Okumura, K.

Graph Attention-Guided Search for Dense Multi-Agent Pathfinding

AAAI 2026

Jain, R., Okumura, K., Amir, M. & Prorok, A.

Concrete multi-agent path planning enabling kinodynamically aggressive maneuvers

npj Robotics 2026

Okumura, K., Yang, G., Gao, Z., Woo, H. & Prorok, A.

db-LaCAM: Fast and Scalable Multi-Robot Kinodynamic Motion Planning with Discontinuity-Bounded Search and Lightweight MAPF

ICAPS 2026

Moldagalieva, A., Okumura, K., Prorok, A. & Honig, W.

Lifelong LaCAM with Local Guidance for Lifelong MAPF

SoCS 2026

Arita, T., Okumura, K.

Solving Multi-Agent Sokoban via LaCAM

arXiv preprint 2026

Okumura, K.

Citation

@inproceedings{okumura2023lacam,
  title={LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding},
  booktitle={Proceedings of AAAI Conference on Artificial Intelligence (AAAI)},
  year={2023},
  author={Okumura, Keisuke}
}