Lifelong MAPF for Shipment Preparation in Stochastic Warehouses

The Multi-Agent Path Finding (MAPF) problem focuses on deriving collision-free paths for multiple agents in a shared environment. However, the traditional formulation of the MAPF problem does not incorporate critical aspects and requirements of shipment preparation tasks, which are essential for efficiency in modern warehouse operations. In this context, we introduce a specialized version of the MAPF problem, termed Lifelong Multi-Agent Path Finding for Shipment Preparation (lifelong MAPF-SP). Unlike the traditional MAPF paradigm, the lifelong MAPF-SP formulation includes unique features tailored to shipment preparation: (i) each robot must perform several pickup and delivery tasks until the shipment is ready, (ii) both pickup actions and delivery actions have unknown stochastic durations, and (iii) all deliveries must be made to a designated shipment loading area. The lifelong MAPF-SP problem involves first deciding which robot is assigned what task (i.e., task assignment) followed by a subsequent coordination problem requiring robots to complete their tasks without colliding with one another (i.e., MAPF). Both task assignment and MAPF are NP-hard, rendering lifelong MAPF-SP a challenging problem. In this work, we present the problem, a benchmark dataset, and a zone-based task assignment algorithm that minimizes traffic congestion. We show that a combination of our zone-based task assignment algorithm and a completely decentralized multi-agent path finding algorithm can effectively solve a range of lifelong MAPF-SP scenarios.