Multi-Robot Coordination and Layout Design for Automated Warehousing

1 Introduction

Today, hundreds of robots are navigating autonomously in warehouses to transport goods from one location to another [Wurman et al., 2007; Kou et al., 2020]. Such automated warehouses are currently a multi-billion-dollar industry led by big companies like Amazon, Alibaba, and Ocado. To improve the throughput of automated warehouses, a lot of works have studied the underlying MultiAgent Path Finding (MAPF) problem for coordinating warehouse robots smoothly [Nguyen et al., 2017; Ma et al., 2017; Liu et al., 2019; Li et al., 2020; Kou et al., 2020; Chen et al., 2021; Contini and Farinelli, 2021; Varambally et al., 2022; Damani et al., 2021].

These works always use human-designed layouts, with an example shown in Figure 1a and in Appendix A, to evaluate MAPF algorithms for automated warehouses. These humandesigned layouts originated from the layouts for traditional warehouses where human workers, instead of robots, transport goods. They usually follow regularized patterns with shelves clustered in rectangular shapes. Such patterns make it easy for human workers to locate goods. But, for robots, it hardly matters to have such regularized patterns. We thus abandon pattern regularity to explore novel layouts with better throughput. Figure 1b shows one of our optimized layouts with the same number of shelves.

∗The full version of the paper can be found in https://arxiv.org/ abs/2305.06436

Therefore, instead of developing better MAPF algorithms, we propose to improve the throughput of automated warehouses by optimizing warehouse layouts. We use the Quality Diversity algorithmMAP-Elites [Mouret and Clune, 2015] to optimize the warehouse layouts with the objective of maximizing the throughput produced by a MAPF-based robot simulator while diversifying a set of user-defined measures, such as travel distances of the robots and the distribution of the shelves. In case the layout found by MAP-Elites is invalid, we follow previous work [Zhang et al., 2020; Fontaine et al., 2021a] and use a Mixed Integer Linear Programming (MILP) solver to repair it. Since both the robot simulator and the MILP solver are time-consuming, we combine them with an online trained surrogate model using Deep Surrogate Assisted Generation of Environments (DSAGE) [Bhatt et al., 2022].

We make the following contributions: (1) we show that, even with state-of-the-art MAPF algorithms, commonly used human-designed layouts can lead to congestion for warehouses with large numbers of robots, (2) we propose the first layout optimization method for automated warehouses based on MAP-Elites and DSAGE, (3) we extend DSAGE by scaling it from single-agent domains to the warehouse domain with up to 200 robots and incorporating MILP to ensure that the layouts satisfy warehouse-specific constraints, (4) we show that our optimized layouts greatly reduce the traffic congestion and improve the throughput compared to commonly used human-designed layouts, and (5) we show that our proposed layout optimization method can generate a diverse set of high throughput layouts with respect to user-defined diversity measures. 1

2 ProblemDefinition

We formally define the warehouse layouts as follows with two examples shown in Figure 2. Following the terminology in the MAPF community, we use agents to refer to robots.

Definition 1 (Warehouse layout). We represent the warehouse layout with a four-neighbor grid, where each tile can be one of the following five types. Black tiles represent shelves to store packages. Blue tiles represent endpoints where agents park and interact with the adjacent shelves. Pink tiles represent workstations where agents interact with human workers. White tiles represent empty spaces. Orange tiles represent home locations for agents, which are empty spaces with special properties used by some MAPF algorithms. Agents can traverse non-black tiles.

Since the orange, blue, and pink tiles are the potential start and goal locations of the agents, a valid warehouse layout needs to make these tiles connected to each other. Furthermore, since the agents interact with the shelves from the endpoints, a valid warehouse layout needs to also make blue and black tiles next to each other.

Definition 2 (Valid layout). A warehouse layout is valid iff (1) any two tiles of blue, pink, or orange color are connected through a path with non-black tiles, (2) each blue tile is adjacent to at least one black tile, and (3) each black tile is adjacent to at least two blue tiles.

We further define the well-formed property [Liu et al., 2019] for warehouse layouts, a required property by some MAPF algorithms.

Definition 3 (Well-formed layout). A valid warehouse layout is well-formed iff the number of orange tiles is no smaller than the number of agents, and any two tiles of blue or orange color are connected through a path with only white tiles.

We pick two common warehouse scenarios to test our layout optimization methods, one requiring well-formed layouts and one requiring valid layouts.

Home-Location Scenario Following previous work [Liu et al., 2019; Li et al., 2021], the home-location scenario simulates a warehouse in which the agents transport goods from one shelf to another. That is, the agents are asked to move from one blue tile to another. Figure 2a shows an example. We require the layouts to be well-formed.

1 We include the source code of the experiments in: https://github. com/lunjohnzhang/warehouse env gen public

(a) Home-location scenario

Figure 2: Example layouts. We optimize tiles inside the red box.

Workstation Scenario Following previous work [H¨onig et al., 2019], the workstation scenario simulates a warehouse in which the agents transport goods between workstations and shelves. That is, the agents are asked to move to pink and blue tiles alternately. Figure 2b shows an example. We require the layouts to be valid.

Finally, we define our optimization objective throughput and our layout optimization problem. Our goal is to find novel distributions of the shelves and their associated endpoints. We thus keep the non-storage area, i.e., area outside of the red box in Figure 2, unchanged for simplicity and only optimize the storage area, i.e., area inside the red box.

Definition 4 (Throughput). An agent finishes a task when it reaches its current assigned goal location. The throughput is the average number of finished tasks per timestep.

Definition 5 (Layout Optimization). Given the layout of a non-storage area and a desired number of shelves Ns, the layout optimization problem searches for the allocation of black, blue, and white tiles inside the storage area to find valid/well-formed layouts with Ns black tiles while maximizing their throughput and diversifying their user-defined diversity measures.

3 Preliminaries

We now introduce the (lifelong) MAPF algorithms that we use in our simulator and existing works on warehouse layout optimization and scenario generation with Quality Diversity algorithms.

3.1 LifelongMulti-Agent Path Finding

Multi-Agent Path Finding (MAPF) [Stern et al., 2019] aims to find collision-free paths for a group of agents from their given start locations to goal locations. Each agent has only one pair of start and goal locations and, after it reaches its goal location, waits there forever. Lifelong MAPF [Li et al., 2021] is a variant of MAPF in which the agents do not stop and wait at their goal locations. Instead, a new goal location is assigned once an agent reaches its current goal location so that the agents keep moving constantly. In this work, we use a widely-used lifelong MAPF definition [Li et al., 2021] where (1) the agents move on a four-neighbor grid, (2) in each discrete timestep, every agent can either stay at its current tile or move to an adjacent tile, (3) the agents cannot be at the same tile or swap their locations at adjacent tiles at the same timestep, and (4) the goal is to maximize the throughput.

Previous works have approached the lifelong MAPF problem by solving it as a whole [Nguyen et al., 2017] or decomposing it into a sequence of MAPF instances and solving them on the fly [C´ap et al., 2015; Ma et al., 2017; Wan et al., 2018; Liu et al., 2019; Grenouilleau et al., 2019; Li et al., 2021]. We choose two state-of-the-art lifelong MAPF algorithms of two types as representative algorithms in our experiments, namely Dummy-Path Planning (DPP) [Liu et al., 2019] and Rolling-Horizon Collision Resolution (RHCR) [Li et al., 2021].

DPP DPP plans paths for idle agents (i.e., agents that reach their current goal locations and need paths to their new goal locations) at every timestep. To ensure that there always exist paths for idle agents that do not collide with the paths of nonidle agents, it requires the layout to be well-formed and thus can be used only in the home-location scenario.

RHCR RHCR replans paths for all agents at every h timesteps, and the planned paths are provably collision-free for w timesteps. It does not require the layout to be wellformed and thus can be used in both warehouse scenarios.

3.2 ExistingWork on Layout Optimization

To the best of our knowledge, no previous works have studied the warehouse layout optimization problem as described in Definition 5 and explored the possibilities of having nonregularized warehouse layouts. Some related works include using queueing network models to estimate the throughput of a given warehouse layout [Wu et al., 2020; Lamballais et al., 2017] and guide the design of warehouse layouts. A recent work [Yang et al., 2021] proposed using integer programming to optimize the locations of the workstations. However, it keeps the shelves fixed and evaluates the quality of the layouts by the average distance between the workstations and shelves, which does not reflect traffic congestion and is thus less accurate than our optimization objective throughput.

3.3 Automatic Environment Generation and Quality-Diversity (QD) Optimization

Automatic environment generation algorithms have been proposed in different fields such as procedural content generation [Shaker et al., 2016], reinforcement learning [Risi and Togelius, 2019; Justesen et al., 2018], and robotics [Fontaine and Nikolaidis, 2021]. Among the environment generation techniques, QD algorithms [Fontaine et al., 2021a; Fontaine and Nikolaidis, 2021; Fontaine et al., 2021b] are popular because they can find a diverse set of high-quality solutions with user-specified objectives and diversity measures.

MAP-Elites [Cully et al., 2015; Mouret and Clune, 2015] is a popular QD algorithm. It discretizes the measure space, which is defined by the user-specified diversity measure functions, and searches for the best solution in each discretized cell. The resulting best solutions in each cell become a set of diverse and high-quality solutions. Deep Surrogate Assisted MAP-Elites (DSA-ME) [Zhang et al., 2022] improves MAP-Elites by using a surrogate model based on deep neural networks to speed up the solution evaluation process. DSAGE [Bhatt et al., 2022] then extends DSA-ME to the environment generation problem for single-agent domains.

4 Layout Optimization Approach

We first formulate the layout optimization problem as a QD problem and introduce our basic framework based on MAPElites, which searches over the tiles of the warehouse layout and uses a MILP solver to make the layout valid or wellformed. We then introduce our advanced framework based on DSAGE, which further introduces a surrogate model to improve optimization efficiency.

4.1 MAP-Elites

Since our warehouse layout is made of discrete tiles, we directly search over the possible tile combinations through a QD algorithm. Specifically, we represent the storage area of a warehouse layout as a vector of discrete variables ⃗x ∈ X, where each discrete variable xi ∈ {black, blue, white} corresponds to the tile type of the ith tile in the layout, and X is the space of all possible layouts.

To formulate layout optimization as a QD problem, we define an objective function to be maximized, f : X→ R, that runs a lifelong MAPF simulator on the input layout for Ne times and returns the average throughput. We also define a measure function m : X → Rm that quantifies characteristics of the layout to diversify. In our experiment, we select the number of connected shelf components and the average length of tasks in the layout as the diversity measures. We chose connected self components because shelves are often organized into "islands" of shelves in human-designed layouts. We formalize connected shelf components as a set of shelves such that any pair of shelves in the set can be connected by a path through only the shelves in the set. In addition, we pick average task length because it is one of the factors that could affect throughput. We define the average length of tasks as the average distance between any pair of blue and pink tiles for the workstation scenario and any pair of two blue tiles for the home-location scenario.

We discretize the measure space evenly into M cells and aim to find, for each cell j, the best layout ⃗xj, called an elite layout, that maximizes f(⃗xj). We call this discretized measure space with elites an archive. The bottom plot in Figure 7 shows an example. Solving this problem generates a set of layouts with high throughput and different numbers of connected shelf components and average lengths of tasks.

Main Algorithm We maintain an archive and improve its elites through iterations. In each iteration, we choose a batch of b elite layouts from the archive uniformly with replacement, where the batch size b is a hyperparameter. Inspired by previous work [Fontaine et al., 2019; Fontaine et al., 2021a], we mutate each of the b elite layouts by uniformly selecting k tiles from each layout and changing the tile type of each of them to a random tile type. The variable k is sampled from a geometric distribution with P(X = k) = (1 - p)k-1p with p = 1 2 . For the first iteration when the archive is empty, we just generate b random layouts. Then, we repair the layouts with a MILP solver to ensure that they are valid or wellformed (see details below). After getting the repaired layouts, we extract the average throughput and measures by running the lifelong MAPF simulator Ne times, each runs for T timesteps with Na agents. Finally, we add the evaluated layouts to the corresponding cells in the archive if their throughput is larger than that of the elite layouts in the same cells. We run MAP-Elites for I iterations with batch size b, resulting in a total of Neval = b × I evaluations, where each evaluation consists of Ne simulations on the lifelong MAPF simulator. Figure 8 in Appendix B gives an overview of MAP-Elites.

MILP Repair After we generate or mutate a layout, we add the non-storage area back to the layout and repair it so that it becomes valid or well-formed. We follow previous work [Zhang et al., 2020; Fontaine et al., 2021a] and formulate the repair process as a Mixed Integer Linear Programming (MILP) problem. In particular, we minimize the hamming distance between the input unrepaired layout ⃗xin and the output repaired layout ⃗xout while asking ⃗xout to satisfy the following constraints: (1) the tiles of ⃗xout in the nonstorage area are kept unchanged, (2) ⃗xout is valid for the workstation scenario and well-formed for the home-location scenario, and (3) the number of shelves in ⃗xout is equal to a predefined number Ns, which ensures that ⃗xout has the desired storage capability. We constrain the number of shelves in the MILP repair step instead of in MAP-Elites so that the QD algorithm can search freely the solution space without being constrained to Ns. The detailed formulation is shown in Appendix C.

4.2 DSAGE

Both the MILP solver and the lifelong MAPF simulator can be time-consuming for large layouts with large numbers of agents. For instance, in our experiments, the MILP solver can take as long as two minutes to repair one layout, and the lifelong MAPF simulator can take up to ten minutes to evaluate one layout. Therefore, we extend Deep Surrogate Assisted Generation of Environment (DSAGE) [Bhatt et al., 2022] as an additional method to optimize warehouse layouts, which exploits an online trained deep surrogate model to guide MAP-Elites and improve its sample efficiency. To use DSAGE for layout optimization, we make the following extensions to DSAGE: (1) our model predicts the tile usage of hundreds of agents instead of a single agent, (2) the tile usage depends on the repaired layout, thus our surrogate model includes an additional component that predicts the output of the MILP solver.

Figure 3 gives an overview of our extended DSAGE framework, which consists of three phases (model exploitation, agent simulation, and model improvement), and a surrogate model. We start by generating a set of nrand random layouts and using them to train a surrogate model, which predicts the outputs of the MILP solver and the lifelong MAPF simulator for given unrepaired layouts. The model exploitation phase runs MAP-Elites with the surrogate model, instead of the MILP solver and the MAPF simulator, and gets a surrogate archive of (predicted) elite layouts. For every n iterations of the model exploitation phase, we run the agent simulation phase, which repairs and evaluates the elite layouts from the surrogate archive using the MILP solver and the MAPF simulator and adds them to a ground-truth archive. The model improvement phase then saves all evaluated layouts in a dataset and uses it to improve the surrogate model. We run this process iteratively until Neval layouts are evaluated on the lifelong MAPF simulator. This way, we simultaneously generate a diverse set of high-quality layouts and train a deep surrogate model to predict the throughput and measures of given layouts. We show the details of the three phases below.

Model Exploitation At this phase, we run MAP-Elites by replacing the MILP solver and the lifelong MAPF simulator with the surrogate model. That is, instead of computing the ground-truth throughput f(⃗x) and measures m(⃗x) using a repaired valid layout, we query the surrogate model for the predicted throughput ˆ f(⃗x) and measures ˆm(⃗x) using an unrepaired layout. Then the model exploitation phase efficiently builds a surrogate archive, which contains the layouts that the surrogate model predicts to be high-performing and diverse.

Agent Simulation At this phase, we repair and evaluate the elite layouts from the surrogate archive to update the groundtruth archive. Since the surrogate archive sometimes contains a large number of elite layouts, we use the downsampling method from [Bhatt et al., 2022] to select a subset of elite layouts to be repaired and evaluated. Specifically, we uniformly divide the archive into sub-areas and uniformly select a layout in each sub-area. Besides updating the ground-truth archive, we also store the evaluated layouts in the dataset.

Model Improvement At this phase, we fine-tune the surrogate model with the data in the dataset. We extend the surrogate model from previous work [Bhatt et al., 2022] and use a three-stage deep convolutional neural network with a self-supervision procedure as our surrogate model. The architecture of the model is shown at the bottom of Figure 3. It contains three sub-networks s1, s2, and s3. We first use s1 to predict a repaired layout given an input unrepaired layout. We then use s2 to predict a tile-usage map of the predicted repaired layout. A tile-usage map records the number of timesteps each tile is occupied by an agent in the lifelong MAPF simulation. We then normalize the tile-usage map so that the numbers sum up to 1, forming a distribution of the tile usage in the layout. We use the tile-usage map to selfsupervise the training of the surrogate model because we observe that the distribution of the tile usage is correlated to the throughput of the layout. For example, Figure 4 shows the tile-usage maps of the two layouts in Figures 1a and 1b with 200 agents. Figure 4a indicates that the agents are congested on the right part of the warehouse, while Figure 4b has no sign of congestion. After predicting the tile-usage map, we concatenate the predicted tile-usage map with the predicted repaired layout and use s3 to predict the throughput and measures. We use a convolutional neural network with 48 layers and 974, 403 parameters as the surrogate model, with its detailed architecture and training summarized in Appendix D.1.

5 Experimental Evaluation

In this section, we evaluate MAP-Elites and DSAGE and compare the optimized layouts with the human-designed ones.

5.1 Experiment Setup

Table 1 summarizes the experiment setup. Columns 2-6 show the configurations related to the layouts. We use one map size for the home-location scenario and three map sizes for the

(a) Human-designed layout

workstation scenario (to show how our methods scale with the size of the maps). Notably, setup 4 has the same storage area size as a commonly used human-designed layout in previous works [Li et al., 2021]. The number of shelves Ns shown in column 5 is chosen to be the same as those in the humandesigned layouts so that the optimized layouts have the same storage capacity as the human-designed layouts.

Column 7 shows the lifelong MAPF simulator with RHCR and DPP. Following design recommendation of previous work [Li et al., 2021], we use PBS [Ma et al., 2019] as the MAPF solver with w = 10 and h = 5 in RHCR, and use prioritized planning [Erdmann and Lozano-Perez, 1986] as the MAPF solver in DPP. Both of them use SIPP [Phillips and Likhachev, 2011] as the single-agent solver. In the workstation scenario, the initial locations of the agents are uniformly chosen at random from non-shelf tiles, and the task assigner alternates every agent's goal location between a workstation and an endpoint, both chosen uniformly at random. In the home-location scenario, the initial locations of the agents are uniformly chosen at random from the home locations, and the task assigner assigns uniformly random goal locations from the endpoints. Since DPP can only work on well-formed layouts, we use it only for the home-location scenario.

Columns 8 and 9 show the number of agents Na and the agent density Pa. For the home-location scenario, we choose Na = 88 because we have only 88 home locations. For the workstation scenario, we run the MAPF simulator on the human-designed layouts with an increasing number of agents and choose Na when we observe a significant drop in throughput.

For both MAP-Elites and DSAGE, we set b = 50, Neval = 10, 000, T = 1, 000, and Ne = 5. For DSAGE, we further set nrand = 500 and n = 10, 000 for setup 1 and 2 and n = 50, 000 for setup 3 and 4. We stop the lifelong MAPF simulation early (i.e., before timestep T) if (unrecoverable) congestion occurs, which is defined as the case where more than half of the agents take wait actions at a particular timestep. This is because (1) we penalize the layouts that run into congestion and (2) we empirically observe that congestion can quickly decrease the number of finished tasks, and keeping running the simulation with congestion seldom increases the throughput. We summarize other hyperparameters and compute resources in Appendix D.2.

To report robust results, we run the lifelong MAPF simulator on every human-designed or optimized layout that we evaluate in this section with Teval = 5, 000 timesteps for, unless explicitly stated otherwise, 10 times, using machines specified in Appendix D.3. We report both average results and their distributions (in the format of x ± y for numerical results with standard deviations and solid lines with shared areas for graphical results with 95% confidence intervals).

5.2 Results

Comparing Optimized and Human-Designed Layouts

We take the best layout from the archive for each setup and compare them in Table 2. The results show that our optimized layouts have significantly better throughput and less congestion than the human-designed layouts in all cases. For example, we scale RHCR from complete failure to complete success for all setups except for setup 2. Moreover, we find that, for the same lifelong MAPF algorithm, a layout with better throughput often leads to a smaller CPU runtime of the lifelong MAPF simulator. Thus, we also reduce the runtime of DPP in the setup 1.

To further understand the gap of the success rates and throughput among different layouts, we plot the simulation process in Figures 5a to 5d. Here, we do not stop the simulation even if they run into congestion and report results over 100 runs (instead of 10 runs). As shown in the figures, the human-design layouts often encounter severe unrecoverable congestion, leading to a significant drop in the number of finished tasks over time. In contrast, our optimized layouts are stable in most cases. The only exception is setup 2, where the performance of our optimized layouts also decreases over time, though with a smaller decreasing speed than that of the human-design layout. This is because setup 2 has the highest agent density (see Pa in Table 1), which makes it hard to find layouts that do not cause congestion.

Generalization and Scalability

Although we run MAP-Elites and DSAGE with a fixed number of agents Na, the optimized layouts can also be applied to other numbers of agents. Figures 5e to 5h shows the throughput with different numbers of agents on layouts that are optimized with Na agents. In comparison to the human-designed layouts, our optimized layouts achieve similar throughput for small numbers of agents and significantly better throughput for large numbers of agents in setup 1. As for the workstation scenario (i.e., setups 2-4), the trend is similar, and the larger the layout, the bigger the improvement. For instance, we double the scalability of RHCR from fewer than 150 agents to more than 300 agents in setup 4.

One reason why we do not improve the throughput for small numbers of agents is that our layouts are optimized using large numbers of agents. To justify this, we optimize our layouts using three different numbers of agents in setup 1 and report the results in Figure 6. As shown, when we use a small number of agents to optimize the layout, the resulting layout leads to better throughput for small numbers of agents.

We also observe an interesting trade-off between RHCR and DPP. Previous work [Li et al., 2021] shows that RHCR leads to better throughput than DPP, which matches our results for small numbers of agents. But for large numbers of agents, we observe that RHCR is more prone to congestion and thus performs worse than DPP. Nevertheless, our optimized layouts improve the performance of both of them.

Diversity in Generated Layouts

A major benefit of using QD algorithms to optimize warehouse layouts is to get a diverse set of high-throughput layouts with user-defined diversity measures. Figure 7 shows two example optimized layouts with different numbers of connected shelf components. The layout on the left clustered more shelves together, forming 5 components, whereas the layout on the right scatters the shelves in the storage area, forming 19 components. Notably, both layouts achieve higher throughput than the human-designed layout. In addition, the optimized layouts allocate the shelves and endpoints on the borders of the storage area. The geometric structure allows the MAPF algorithms to improve throughput.

We observe that DSAGE is more capable of generating diverse layouts in the archive than MAP-Elites. For example, in setup 4, although there is no significant difference between the throughput of the best optimized layouts generated by MAP-Elites and DSAGE with 200 agents, DSAGE generates 1, 317 elite layouts in the archive, and MAP-Elites generates only 1, 039. As a result, DSAGE generates layouts with numbers of connected shelf components ranging from 146 to 218, while MAP-Elites cannot generate layouts with fewer than 153 or more than 207 connected shelf components. We show more results on DSAGE and MAP-Elites in Appendix E.

6 Conclusion

We present the first layout optimization approach for automated warehouses that explores novel layouts with nonregularized patterns and explicitly optimizes throughput. We extend DSAGE from single-agent domains to the warehouse domain with as many as 200 agents. We also incorporate MILP to DSAGE and extend the surrogate model to predict repaired layouts. Our result shows that the optimized layouts outperform commonly used human-designed layouts in throughput and CPU runtime. Our methods work with different warehouse scenarios, different MAPF algorithms, and layouts of different sizes. In addition, our methods provide diverse layouts with respect to user-specified diversity measures.

Our work has many future directions. First, we can incorporate the optimization of the non-storage area into our method because previous work [Lamballais et al., 2017] has demonstrated the impact of workstations on throughput. Second, our optimization method only works for small 2D warehouses represented as a 4-neighbor grid. Future works can focus on generating larger 2D or 3D warehouses. Third, we can improve our method to optimize layouts with a larger agent density (Pa). Overall, we are excited about the first proposed method for layout optimization and are looking forward to adapting our approach to more complex warehouse domains.

Acknowledgments

This work used Bridge-2 at Pittsburgh Supercomputing Center (PSC) through allocation CIS220115 from the Advanced Cyberinfrastructure Coordination Ecosystem: Services & Support (ACCESS) program, which is supported by National Science Foundation grants #2138259, #2138286, #2138307, #2137603, and #2138296. In addition, this work was supported by the NSF CAREER Award (#2145077) and the CMU Manufacturing Futures Institute, made possible by the Richard King Mellon Foundation.