Task Assignment, Scheduling, and Motion Planning for Automated Warehouses for Million Product Workloads

We address the Warehouse Servicing Problem (WSP) in automated warehouses, which use teams of mobile robots to move products from shelves to packaging stations. Given a list of products, the WSP amounts to finding a motion plan which brings every product on the list from a shelf to a packaging station within a given time limit. The WSP consists of four subproblems, namely, deciding where to source and deposit a product (task formulation), who should transport each product (task assignment) and when (scheduling) and how (motion planning). These problems are NP-Hard individually and made more challenging by their interdependence. The difficulty of the WSP is compounded by the scale of automated warehouses, which use teams of hundreds of agents to transport thousands of products. In this paper, we present Contract-based Cyclic Motion Planning (CCMP), a novel contract-based methodology for solving the WSP at scale. CCMP decomposes a warehouse into a set of traffic system components. By assigning each component a contract which describes the traffic flows it can support, CCMP can generate a traffic flow which satisfies a given WSP instance. CCMP then uses a novel motion planner to transform this traffic flow into a motion plan for a team of robots. Evaluation shows that CCMP can solve WSP instances taken from real industrial scenarios with up to 1 million products while outperforming other methodologies for solving the WSP by up to 2.9×.

I. Introduction

An automated warehouse uses a team of mobile robots to transfer products from its shelves to its packaging stations. Over the last decade, automated warehouses have become widely used in industrial logistics and e-commerce. Today, companies such as Amazon use teams of hundreds of robots to transport products across large warehouse complexes [1]. To orchestrate an automated warehouse, a warehouse operator must solve the Warehouse Servicing Problem (WSP). In the WSP, we are given a warehouse layout and a list of products termed a workload and asked to find a plan for a team of robots which brings every product on the list to a packaging station within a given timeframe. The WSP consists of four interdependent subproblems: 1)

task formulation. what shelf should each product be sourced from, and what station should it be taken to?

2)

task assignment. what tasks should a robot perform?

3)

Scheduling. When should a robot perform its tasks?

4)

Motion Planning. How should a robot execute its tasks?