# Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Unassigned Agents

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 30 references that are in the map.
- First posted on arXiv 31 Aug 2025.

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

- [Integrated Task and Motion Planning](https://mlsanity.com/paper/2010.01083/) (2020)
- [Text2Motion: From Natural Language Instructions to Feasible Plans](https://mlsanity.com/paper/2303.12153/) (2023)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [BEHAVIOR: Benchmark for Everyday Household Activities in Virtual, Interactive, and Ecological Environments](https://mlsanity.com/paper/2108.03332/) (2021)
- [Graph Neural Networks for Decentralized Multi-Robot Path Planning](https://mlsanity.com/paper/1912.06095/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong](https://mlsanity.com/paper/2010.08184/) (2020)
- [Learning Symbolic Operators for Task and Motion Planning](https://mlsanity.com/paper/2103.00589/) (2021)
- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Optimal Target Assignment and Path Finding for Teams of Agents](https://mlsanity.com/paper/1612.05693/) (2016)
- [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023)
- [Solving Sokoban with forward-backward reinforcement learning](https://mlsanity.com/paper/2105.01904/) (2021)
- [Toward Efficient Physical and Algorithmic Design of Automated Garages](https://mlsanity.com/paper/2302.01305/) (2023)
- [On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles](https://mlsanity.com/paper/2312.10887/) (2023)
- [A Study on the Block Relocation Problem: Lower Bound Derivations and Strong Formulations](https://mlsanity.com/paper/1904.03347/) (2019)
- [What Matters in Hierarchical Search for Combinatorial Reasoning Problems?](https://mlsanity.com/paper/2406.03361/) (2024)

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

- [The Multi-AMR Buffer Storage, Retrieval, and Reshuffling Problem: Exact and Heuristic Approaches](https://mlsanity.com/paper/2603.26542/) (2026)
- [Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity](https://mlsanity.com/paper/2608.07734/) (2026)

## Abstract (arXiv)

We introduce the Block Rearrangement Problem (BRaP), a challenging component of large warehouse management which involves rearranging storage blocks within dense grids to achieve a goal state. We formally define the BRaP as a graph search problem. Building on intuitions from sliding puzzle problems, we propose five search-based solution algorithms, leveraging joint configuration space search, classical planning, multi-agent pathfinding, and expert heuristics. We evaluate the five approaches empirically for plan quality and scalability. Despite the exponential relation between search space size and block number, our methods demonstrate efficiency in creating rearrangement plans for deeply buried blocks in up to 80x80 grids.