  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.
