The Taub Faculty of Computer Science Events and Talks

Lifelong Multi-Agent Pathfinding (L-MAPF) is concerned with planning collision-free paths for a team of agents as they continuously handle tasks involving pick-up and delivery. When modeling autonomous warehouses, typical approaches for L-MAPF consider the environment as populated with static obstacles in the form of inventory pods that the agents must avoid. These obstacles impose narrow passageways, forcing agents to resort to detours and suffer delays on account of bottlenecks. The problem becomes more severe when disruptions occur: whenever an agent experiences a hardware failure and cannot move, or when an item drops to the warehouse floor, a safety perimeter and partial blockage of the area is necessary, resulting in significant detriment to performance. In this work we study a challenging case of warehouse disruptions, in which an agent can become completely blocked but is still operational. Contemporary methods can only offer to wait in place, but by manipulating the environment, through a process called Terraforming, nearby agents can be rerouted to assist with mitigating disruptions. Terraforming allows agents to purposefully displace obstacles to create shortcuts trailblazing routes to agents who would otherwise be considered blocked. We present a novel approach to solving L-MAPF with disruptions, and propose an extension to the PBS algorithm that incorporates Terraforming. In this manner, agents are empowered to reason about candidate obstacles for efficient extraction, resulting in notable improvement in throughput.