# Search-Aided Joint Agent-Environment Reinforcement Learning for Robust Lifelong Multi-Agent Path Finding with Rotations

arXiv: https://arxiv.org/abs/2608.05588 · HTML: https://mlsanity.com/paper/2608.05588/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 40 references that are in the map.
- First posted on arXiv 6 Aug 2026.

## Builds on (most cited first, 23 of 23)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong](https://mlsanity.com/paper/2010.08184/) (2020)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [SCRIMP: Scalable Communication for Reinforcement- and Imitation-Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2303.00605/) (2023)
- [Learning Selective Communication for Multi-Agent Path Finding](https://mlsanity.com/paper/2109.05413/) (2021)
- [MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments](https://mlsanity.com/paper/2007.15724/) (2020)
- [MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale](https://mlsanity.com/paper/2409.00134/) (2024)
- [Improving Learnt Local MAPF Policies with Heuristic Search](https://mlsanity.com/paper/2403.20300/) (2024)
- [Work Smarter Not Harder: Simple Imitation Learning with CS-PIBT Outperforms Large Scale Imitation Learning for MAPF](https://mlsanity.com/paper/2409.14491/) (2024)
- [Multi-Agent Motion Planning For Differential Drive Robots Through Stationary State Search](https://mlsanity.com/paper/2412.13359/) (2024)
- [Time-Independent Planning for Multiple Moving Agents](https://mlsanity.com/paper/2005.13187/) (2020)
- [Symmetry Breaking for k-Robust Multi-Agent Path Finding](https://mlsanity.com/paper/2102.08689/) (2021)
- [Co-Optimizing Reconfigurable Environments and Policies for Decentralized Multi-Agent Navigation](https://mlsanity.com/paper/2403.14583/) (2024)
- [Graph Attention-Guided Search for Dense Multi-Agent Pathfinding](https://mlsanity.com/paper/2510.17382/) (2025)
- [Enhancing PIBT via Multi-Action Operations](https://mlsanity.com/paper/2511.09193/) (2025)
- [CAMAR: Continuous Actions Multi-Agent Routing](https://mlsanity.com/paper/2508.12845/) (2025)
- [Conflict-Based Search as a Protocol: A Multi-Agent Motion Planning Protocol for Heterogeneous Agents, Solvers, and Independent Tasks](https://mlsanity.com/paper/2510.00425/) (2025)
- [Scaling Multi-Agent Environment Co-Design with Diffusion Models](https://mlsanity.com/paper/2511.03100/) (2025)
- [CoRL-MPPI: Enhancing MPPI With Learnable Behaviours For Efficient And Provably-Safe Multi-Robot Collision Avoidance](https://mlsanity.com/paper/2511.09331/) (2025)

## Built on by (most cited first, 1 of 1)

- [Reinforcement Learning for Large-Scale Lifelong Multi-Agent Path Finding with Shared Spatial Fields](https://mlsanity.com/paper/2610.18186/) (2026)

## Abstract (arXiv)

Lifelong Multi-Agent Path Finding (LMAPF) requires repeatedly planning collision-free paths for agents that continuously receive new goals upon reaching their current ones. While many learning-based planners have been proposed for LMAPF, most rely on oversimplified kinematic assumptions that may overlook motion constraints critical to real-world performance. In this work, we study a more realistic LMAPF model derived from many real-world automated warehouse systems, termed LMAPF-R2, which incorporates robust safety constraints and in-place rotation constraints. These constraints substantially increase coordination difficulty, particularly in highly constrained spaces. To address these challenges, we propose Search-Aided Joint Reinforcement Learning (SJRL). We first augment neural policies with Causal PIBT, a single-step search-based planner that resolves agents' collisions and propagates their intentions. We then introduce a unified RL formulation that jointly optimizes agent and environment policies, where the environment policy learns graph edge costs to provide global movement guidance via backward Dijkstra search. Experiments demonstrate that SJRL achieves significant improvements over the strong search-based planner, Causal-PIBT, across multiple high-density maps. We further validate SJRL in a challenging mixed-reality warehouse environment with 8 physical robots and 248 virtual robots.