Multi-Agent Path Finding

Also known as MAPF

Multi-agent path finding studies how to route agents to their goals without collisions, often minimizing travel cost or completion time; in lifelong settings, agents repeatedly receive new tasks. Classical methods include Conflict-Based Search and space-time search for high-quality or optimal plans, while prioritized planning, PIBT, and LaCAM trade some solution quality for scalability. Other approaches use learning, local communication, optimization, or hybrid methods that combine fast planning with conflict repair, and many now address task assignment, congestion, and execution on real robots. A central tension is balancing guarantees and realistic motion or disturbances against the speed and scale needed for dense fleets.

Latest papers

92 papers12 papers in the last four weeks, up 33% on the four weeks before. 0.1% of all new papers.

Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF
Aug 7, 2026Vaibhav Sanjay, Jiaoyang LiMulti-Agent Coordination Robust MAPF
Robotics Institute, Carnegie Mellon University
Search-Aided Joint Agent-Environment Reinforcement Learning for Robust Lifelong Multi-Agent Path Finding with Rotations
Aug 6, 2026He Jiang, Jingtian Yan, Yulun Zhang +5Constrained Motion Planning Robust MAPF
1Carnegie Mellon University · University of Southern California · 3National University of Singapore
PRIMAL3: Pathfinding via Reinforcement and Imitation Multi-Agent Learning - Leveraging LaCAM3
Aug 5, 2026Chengyang He, Tanishq Duhan, Gadiel Sznaier Camps +6Multi-Robot Systems Multi-Agent Path Finding
Multi-Agent Robotic Motion Lab (MARMot), National University of Singapore · Multi-robot Systems Lab (MSL), Stanford University · Robotics and Machine Intelligence Lab (ROMI), Hong Kong Polytechnic University
Multi-Agent Planning with Spatio-Temporal and Topological Constraints using STL-GO
Jul 29, 2026Sheryl Paul, Vidisha Kudalkar, Anand Balakrishnan +3Constrained Motion Planning Combinatorial Optimization
University of Southern California, Los Angeles, CA, USA · University of Texas at Austin, Austin, TX, USA · ETH Zurich, Zurich, Switzerland +1
Cooperative Multi-UAV Navigation in Complex Environments via Systematic Multi-Agent Deep Reinforcement Learning
Jul 28, 2026Yu Su, Nabil AoufLearning from Demonstration Curriculum Learning
School of Science and Technology, City St George’s University of London, London, United Kingdom
Stigmergic Graph Memory: An Environment-Aware Approach for Many-to-Many Multi-Agent Pickup and Delivery
Jul 16, 2026Aditya Dutta, Joon-Seok KimMulti-Agent Coordination Graph-Based Agent Memory
Emory University 201 Dowman Drive Atlanta, GA 30322 USA
Model-Based Diffusion Optimal Control for Multi-Robot Motion Planning
Jul 14, 2026Zhilin He, Yorai Shaoul, Jiaoyang LiMulti-Robot Motion Planning Constrained Motion Planning
Carnegie Mellon University, Pittsburgh, PA, USA
Diffusion for Long-Horizon Multi-Robot Path Planning in Human-Shared Environments
Jul 10, 2026Vaibhav Sanjay, Yorai Shaoul, Jiaoyang LiMulti-Robot Motion Planning Diffusion-Based Planning
Robotics Institute, Carnegie Mellon University
Conflict-Based Lazy Search for Fast Multi-Manipulator Planning
Jul 5, 2026Dongliang Zheng, Zhipeng Wang, Siqi Wang +4Multi-Robot Motion Planning Conflict-Based Search
Shanghai Research Institute for Intelligent Autonomous Systems, Shanghai Institute of Intelligent Science and Technology, the State Key Laboratory of Autonomous Intelligent Unmanned Systems, and Frontiers Science Center for Intelligent Autonomous Systems of Ministry of Education, Tongji University, Shanghai 201203, China · Department of Automation, Shanghai Jiao Tong University, Shanghai 200240, China · School of Aerospace Engineering and Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332, USA
From Real-Time Planning to Reliable Execution:Scalable Coordination for Heterogeneous Multi-Robot Fleets in Industrial Environments
Jul 1, 2026Bo CaoMulti-Robot Motion Planning Robotics
Dual-Informed Vertical Expansion for Multi-Objective Node Selection in Anytime Conflict-Based Search
Jun 30, 2026Willem van Osselaer, Jiarui Li, Meshal Alharbi +1Branch and Bound Tree Search
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA, USA
Cooperative-ORCA*: Real-Time Proactive Deadlock Avoidance for Continuous-Space Multi-Agent Navigation
Jun 22, 2026Junfeng Wu, Jiaqi Chen, Hongkun Lyu +2Multi-Robot Motion Planning Robust MAPF
Monash University
Intermittent Strategic Cooperation of Two Selfish Agents on Graphs
Jun 15, 2026Itay Shedlezki, Noa AgmonNash Equilibrium Game Theory
Bar-Ilan University · Ramat Gan, Israel
Unassigned Agents in Compilation-based Multi-agent Path Finding
Jun 14, 2026Pavel SurynekCounterexample-Guided Refinement Multi-Agent Path Finding
Faculty of Information Technology, Czech Technical University in Prague Thákurova 9, 163 00, Prague, Czechia
Hardness of Multi-Agent Path Finding on Trees: A Unified Approach
Jun 4, 2026Tzvika GeftMotion Planning Multi-Agent Path Finding
Rutgers University, NJ, USA · NJ, USA
CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs
Jun 3, 2026Abhishek S, Badrikanath Praharaj, Sreeram MVMulti-Robot Systems Multi-Robot Coordination
BuildMachineLabs
On dynamic multi-agent pathfinding methods: review, simulations and modifications
Jun 2, 2026Gabriel Fejziaj, Salama Hassona, Wieslaw MarszalekMotion Planning Dynamic Obstacle Avoidance
Department of Computer Science, Opole University of Technology, Opole, 45-758, Poland.
Sentinel: Embodied Cooperative Spatial Reasoning and Planning
May 25, 2026Xiangye Lin, Hongxin Zhang, Ruxi Deng +2AI Agent Benchmarks Multi-Agent Planning
University of Massachusetts Amherst · University of Illinois Urbana-Champaign
STEAM: A Training-Free Congestion-Aware Enhancement Framework for Decentralized Multi-Agent Path Finding
May 20, 2026Mingyang Feng, Mengnuo Zhang, Shaoyuan Li +1Multi-Agent System Optimization Multi-Agent Coordination
School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, Shanghai 200240, China
Lifelong LaCAM with Local Guidance for Lifelong MAPF
May 16, 2026Tomoki Arita, Keisuke OkumuraSequential Decision Making Robust MAPF
Keio University, Japan · National Institute of Advanced Industrial Science and Technology (AIST), Japan
Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding
May 15, 2026Ning Zhou, Nikolai W. F. Bode, Edmund R. HuntMulti-Agent System Optimization Multi-Robot Coordination
University of Bristol
From Gridworlds to Warehouses: Adapting Lightweight One-shot Multi-Agent Pathfinding for AGVs
May 15, 2026Hiroki Nagai, Keisuke OkumuraMulti-Robot Motion Planning Constrained Motion Planning
National Institute of Advanced Industrial Science and Technology (AIST), Japan
Privacy Preserving Multi Agent Path Finding
May 13, 2026Rotem Lev Lehman, Roni Stern, Guy ShaniGraph-Based Planning Multi-Agent Planning
Ben Gurion University of the Negev · Be’er Sheva, Israel
Discrete Diffusion for Complex and Congested Multi-Agent Path Finding with Sparse Social Attention
May 13, 2026Yuanzhe Wang, Tian Zhi, Zihang Wei +8Multi-Agent System Optimization Diffusion-Based Planning
State Key Lab of Processors, Institute of Computing Technology, CAS · School of Advanced Interdisciplinary Sciences, CAS · University of Chinese Academy of Sciences +1
Conveyor Parcel Routing with Order-Contiguous Arrivals
May 13, 2026Takuro Kato, Keisuke OkumuraRobust MAPF Multi-Agent Path Finding
Toyota Industries Corporation, Japan · National Institute of Advanced Industrial Science and Technology (AIST), Japan
Distance-Constrained Unlabeled Multi-Agent Pathfinding
May 12, 2026Takahiro Suzuki, Yuma Tamura, Keisuke OkumuraConstrained Motion Planning Multi-Agent Coordination
Tohoku University · National Institute of Advanced Industrial Science and Technology (AIST)
Robust Multi-Agent Path Finding under Observation Attacks: A Principled Adversarial-Plus-Smoothing Training Recipe
May 12, 2026Riad AhmedMulti-Agent Path Finding Adversarial Robustness
University of New Hampshire
Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges
May 11, 2026Usman A. Khan, Joseph W. DurhamMulti-Agent System Optimization Multi-Agent Path Finding
Amazon Robotics, Boston, MA, USA · Boston College, Chestnut Hill, MA, USA · UAK holds concurrent appointments as an Amazon Scholar with Amazon Robotics and as a Professor of Computer Science at Boston College
Alternating Target-Path Planning for Scalable Multi-Agent Coordination
May 8, 2026Yu Kumagai, Keisuke OkumuraMulti-Agent Coordination Multi-Robot Task Allocation
1Hitotsubashi University, Japan · 2National Institute of Advanced Industrial Science and Technology (AIST), Japan
Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding
May 8, 2026Valeriy Vyaltsev, Alsu Sagirova, Anton Andreychuk +5Multi-Agent Coordination Robust MAPF
CogAI Lab, Moscow, Russia

Aug 7, 2026J/K move · Enter open · S save

Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF

Vaibhav Sanjay, Jiaoyang Li

Robotics Institute, Carnegie Mellon University

Multi-Agent Coordination Robust MAPF Long-Horizon Planning Multi-Agent Path Finding

Open paper AskPDF arXiv

Lifelong Multi-Agent Path Finding (LMAPF) requires generating collision-free paths for large agent fleets under strict real-time constraints. Reactive frameworks such as PIBT and Enhanced PIBT (EPIBT) scale effortlessly to thousands of agents through rule-based, step-by-step coordination but suffer from severe temporal myopia, making them ineffective in scenarios where long-horizon reasoning is essential. RHCR plans windowed paths over multi-step horizons but incurs substantial planning overheads that hinder scalability. TP tackles both challenges by planning only subsets of agents at each timestep, yet its applicability is restricted to highly structured maps. To achieve long-horizon planning at scale across general maps, we propose Path Updates over Staggered Horizons (PUSH), a LMAPF planner capable of coordinating thousands of agents in under a second while planning over multi-step horizons. PUSH combines the key advantages of PIBT, RHCR, and TP. Like TP, PUSH reduces computational complexity by planning only a subset of agents at each timestep using staggered planning windows. Unlike TP, however, PUSH plans RHCR-style windowed paths in general maps without relying on restrictive map assumptions. To maintain high throughput in congested environments, PUSH further integrates EPIBT-inspired priority inheritance, backtracking, and anytime improvements into its windowed planning. Empirical evaluations across two realistic MAPF scenarios requiring long-horizon reasoning show that PUSH scales to the same massive agent loads as EPIBT (e.g., 10k agents) while achieving significantly higher system throughput than all baselines.