Design Automation for Smart Factories

The paper titled Co-Design of Topology, Scheduling, and Path Planning in Automated Warehouses, authored by Christopher Leet, Chanwook Oh, Michele Lora, Sven Koenig, and Pierluigi Nuzzo, has been accepted at the 2023 IEEE/ACM Design Automation and Test in Europe that will be held in Antwerp, 17 - 19 April 2023.

In the accepted paper, we address the warehouse servicing problem (WSP) in automated warehouses, which use teams of mobile agents to bring products from shelves to packing stations. Given a list of products, the WSP amounts to finding a plan for a team of agents which brings every product on the list to a station within a given timeframe. The WSP consists of four subproblems, concerning what tasks to perform (task formulation), who will perform them (task allocation), and when (scheduling) and how (path planning) to perform them. These subproblems are NP-hard individually and become more challenging in combination. The difficulty of the WSP is compounded by the scale of automated warehouses, which frequently use teams of hundreds of agents. In this paper, we present a methodology that can solve the WSP at such scales. We introduce a novel, contract-based design framework which decomposes an automated warehouse into traffic system components. By assigning each of these components a contract describing the traffic flows it can support, we can synthesize a traffic flow satisfying a given WSP instance. Component-wise search-based path planning is then used to transform this traffic f low into a plan for discrete agents in a modular way. Evaluation shows that this methodology can solve WSP instances on real automated warehouses.

A pre-print of the paper is available here.