# Multi-Agent Terraforming: Efficient Multi-Agent Path Finding via Environment Manipulation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 34 references that are in the map.
- First posted on arXiv 20 Mar 2022.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Efficient Large-Scale Multi-Drone Delivery Using Transit Networks](https://mlsanity.com/paper/1909.11840/) (2019)
- [Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers](https://mlsanity.com/paper/1912.00253/) (2019)
- [Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds](https://mlsanity.com/paper/2104.08759/) (2021)
- [Computing High-Quality Clutter Removal Solutions for Multiple Robots](https://mlsanity.com/paper/2007.04856/) (2020)

## Abstract (arXiv)

Multi-agent pathfinding (MAPF) is concerned with planning collision-free paths for a team of agents from their start to goal locations in an environment cluttered with obstacles. Typical approaches for MAPF consider the locations of obstacles as being fixed, which limits their effectiveness in automated warehouses, where obstacles (representing pods or shelves) can be moved out of the way by agents (representing robots) to relieve bottlenecks and introduce shorter routes. In this work we initiate the study of MAPF with movable obstacles. In particular, we introduce a new extension of MAPF, which we call Terraforming MAPF (tMAPF), where some agents are responsible for moving obstacles to clear the way for other agents. Solving tMAPF is extremely challenging as it requires reasoning not only about collisions between agents, but also where and when obstacles should be moved. We present extensions of two state-of-the-art algorithms, CBS and PBS, in order to tackle tMAPF, and demonstrate that they can consistently outperform the best solution possible under a static-obstacle setting.