Multi-Agent Path Finding in High-Rack Warehouses With Elevators

We analyze the problem of finding collision-free paths for multiple agents in high-rack warehouses, given orders for items to be shipped from the warehouse. In our model, the levels of the warehouse are connected by elevators performing all vertical motion while agents are confined to their respective level. Apart from showing the computational intractability of finding optimal solutions, we develop an approximation algorithm that produces solutions with provably low approximation factors in polynomial time for a large class of instances.