  In automated warehouses, teams of mobile robots fulfill the packaging process
by transferring inventory pods to designated workstations while navigating
narrow aisles formed by tightly packed pods. This problem is typically modeled
as a Multi-Agent Pickup and Delivery (MAPD) problem, which is then solved by
repeatedly planning collision-free paths for agents on a fixed graph, as in the
Rolling-Horizon Collision Resolution (RHCR) algorithm. However, existing
approaches make the limiting assumption that agents are only allowed to move
pods that correspond to their current task, while considering the other pods as
stationary obstacles (even though all pods are movable). This behavior can
result in unnecessarily long paths which could otherwise be avoided by opening
additional corridors via pod manipulation. To this end, we explore the
implications of allowing agents the flexibility of dynamically relocating pods.
We call this new problem Terraforming MAPD (tMAPD) and develop an RHCR-based
approach to tackle it. As the extra flexibility of terraforming comes at a
significant computational cost, we utilize this capability judiciously by
identifying situations where it could make a significant impact on the solution
quality. In particular, we invoke terraforming in response to disruptions that
often occur in automated warehouses, e.g., when an item is dropped from a pod
or when agents malfunction. Empirically, using our approach for tMAPD, where
disruptions are modeled via a stochastic process, we improve throughput by over
10%, reduce the maximum service time (the difference between the drop-off time
and the pickup time of a pod) by more than 50%, without drastically increasing
the runtime, compared to the MAPD setting.
