Arbitrarily Scalable Environment Generators via Neural Cellular Automata
Authors: Yulun Zhang
Matthew Christopher Fontaine
Varun Bhatt
Stefanos Nikolaidis
Jiaoyang Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi-robot systems
quality diversity
automatic environment generation
neural cellular automata

Abstract: We study the problem of generating arbitrarily large environments to improve the throughput of multi-robot systems. Prior work proposes Quality Diversity (QD) algorithms as an effective method for optimizing the environments of automated warehouses. However, these approaches optimize only relatively small environments, falling short when it comes to replicating real-world warehouse sizes. The challenge arises from the exponential increase in the search space as the environment size increases. Additionally, the previous methods have only been tested with up to 350 robots in simulations, while practical warehouses could host thousands of robots. In this paper, instead of optimizing environments, we propose to optimize Neural Cellular Automata (NCA) environment generators via QD algorithms. We train a collection of NCA generators with QD algorithms in small environments and then generate arbitrarily large environments from the generators at test time. We show that NCA environment generators maintain consistent, regularized patterns regardless of environment size, significantly enhancing the scalability of multi-robot systems in two different domains with up to 2,350 robots. Additionally, we demonstrate that our method scales a single-agent reinforcement learning policy to arbitrarily large environments with similar patterns. We include the source code at https://github.com/lunjohnzhang/warehouse_env_gen_nca_public.

Arbitrarily Scalable Environment Generators via Neural Cellular Automata
Yulun Zhang'
Matthew C. Fontaine²
Varun Bhatt?
Stefanos Nikolaidis
Jiaoyang Li
'Robotics Institute, Carnegie Mellon University
TThomas Lord Department of Computer Science, University of Southern California vulunzhang@@cmu. edu, (mfontain, vsbhatt, nikolaii d) Busc. edu, j jiaoyang i cmm. edu
Abstract
We study the problem of generating arbitrarily large environments to improve the throughput of multi-robot systems. Prior work proposes Quality Diversity (QD) algorithms as an effective method for optimizing the environments of au- tomated warehouses. However, these approaches optimize only relatively small environments, falling short when it comes to replicating real-world warehouse sizes. The challenge arises from the exponential increase the search space as the environment size increases. Additionally, the previous methods have only been tested with up to 350 robots in simulations, while practical warchouses could host thousands of robots. In this paper, instead of optimizing environments, we propose to optimize Neural Cellular Automata (NCA) environment generators via QD algorithms. We train collection of NCA generators with QD algorithms in small environments and then generate arbitrarily large environments from the gen- erators time. We show that NCA environment generators maintain consistent, regularized patterns regardless of environment size, significantly enhancing the scalability of multi-robot systems in two different domains with up 2,350 robots. Additionally, we demonstrate that our method scales a single-agent reinforcement learning policy arbitrarily large environments with similar patterns. We include the source code at https:/ /ttp//ggtbb///////////////t..hht com wwn.zhaanngggggg///oooaooaaa warehouse_
Introduction
We study the problem of generating arbitrarily large environments improve the throughput of multi- robot systems. As motivating example, consider multi-robot system for automated warehousing where thousands of robots transport inventory pods shared warehouse environment. While numerous works have studied the underlying Multi-Agent Path Finding (MAPF) problem [42] to more effectively coordinate the robots to improve the throughput [4, 6, 8, 24, 27, 29, 31, 35, 46), we can also optimize the throughput by designing novel warehouse environments. A well-optimized environment can alleviate traffic congestion and reduce the travel distances for the robots to fulfill their tasks in the warehouse.
recent work [51] formulates the environment optimization problem Quality Diversity (QD) optimization problem and optimizes the environments by searching for the best allocation of shelf and endpoint locations (where endpoints are locations where the robots can interact with the shelves), It uses a QD algorithm to iteratively generate new environments and then repairs them with Mixed Integer Linear Programming (MILP) solver to enforce domain-specific constraints, such as the storage capacity and connectivity of the environment. The repaired environments are evaluated with an
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Emply space
Endpoint
Shelf
Workstation
(a) Optimized environ-
ment with no patterns.
(b) NCA-generated en- vironment with patterns.
(c) Scaling patterns from NCA-gemerated envi- romment to a larger environment.
Figure Examples of optimized warehouse environments. Robots move in between workstations (pink) and endpoints (blue) without traveling through shelves (black) to transport goods. In this environment, workstations on the left border are used 5 times more frequently than those on the right border. (a) shows a warchouse environment optimized directly with QD algorithms from previous work [51]. It has no obvious regularized patterns. (b) shows environment generated by our NCA generator with regularized patterns. (c)
shows a much larger environment generated by the same NCA generator (b) with similar patterns.
agent-based simulator [28] that simulates the movements of the robots in the warehouse. Figure la shows an example optimized environment, which is shown have much higher throughput and is more scalable than human-designed environments.
However, with the aforementioned method, the search space of the QD algorithm grows exponentially with the size the environment. To optimize arbitrarily large environments, QD algorithms require a substantial number of runs in both the agent-based simulator and the MILP solver. Each run also takes more time to finish. For example, in the aforementioned work [51], took up to 24 hours on a 64-core local machine optimize warehouse environment of size only 36 33 with 200 robots, which is smaller than many warehouses in reality or warehouse simulations used in the literature. For example, Amazon fulfillment centers reported to have more than 4,000 robots [2]. Previous research motivated by Amazon sortation centers run simulations in environments of size up to 179 x 69 with up 1,000 robots [48, 28).
Therefore, instead of optimizing the environments directly, we propose to train Neural Cellular Automata (NCA) environment generators capable of scaling their generated environments arbitrarily. Cellular automata (CA) [19] are well suited to arbitrary scaling as they incrementally construct environments through local interactions between cells. Each cell observes the state of its neighbors and incorporates that information into changing its own state. NCA [33] represents the state change rules via a neural network that can be trained with any optimization method.
We follow the insight from prior work [10] and use QD algorithms to efficiently train a diverse collection of NCA generators in small environments. We then use the NCA generators to generate arbitrarily large environments with consistent and regularized patterns. In case the generated envi- ronments invalid, we adopt the MILP solver from the previous works [49, 15, 51] to repair the environments. Figure lb shows an example cavironment with regularized patterns generated by our NCA generator and then repaired by the MILP solver. Figure ic shows much larger environment generated by the same NCA generator with similar patterns and then repaired by MILP. Similar to previous environment optimization methods [51], need to the MILP solver repeatedly small environments (Figure 1b) to train the NCA generator. However, once the NCA generators are trained, we only run the MILP solver once after generating large environments (Figure Ic).
We show that our generated environments have competitive or better throughput and scalability com- pared to the existing methods [51] in small environments. In large environments where the existing

---

methods are not applicable due to computational limits, we show that our generated environments have significantly better throughput and scalability than human- -emaandd environments.
We make the following contributions: (1) instead of directly searching for the best environments, we present method train a collection of NCA environment generators on small environments using QD algorithms, (2) we then show that the trained NCA generators can generate environments in arbitrary sizes with consistent regularized patterns, which leads significantly higher throughput than the baseline environments in two multi-robot systems with large sizes, (3) we additionally demonstrate the general-pura pureose nature of our method by scaling single-agent RL policy arbitrarily large environments with similar patters, maintaining high success rates.
2
Background and Related Work
2.1 Neural Cellular Automata (NCA)
Cellular automata (CA) [3, 39] originated in the artificial life community as a way to model incre- mental cell development. A CA consists of grid cells and update rule for how to change a cell based on the state of its neighbors. Later work [33] showed that these rules could be encoded by a convolutional neural network. By iteratively updating grid of cells, an NCA is capable of producing complex environments. Figure in Appendix A shows an example NCA environment generation process of 50 iterations from initial environment shown in Figure 6a.
Representing the rules of CAs by a neural network facilitates learning useful rules for the cellular automata. Several works have trained NCA generators to generate images [33], textures [36, 32], and 3D structures [43]. Other works have replaced the convolutional network with other model architectures [44, 18]. In the case of environment optimization, the objective is computed from non-differentiable agent-based simulator. Therefore, we choose derivative- optimization methods to train the NCA generators for environment optimization.
Prior work [10] shows that derivative-free QD algorithms can efficiently train a diverse collection of NCA video game environment generators. However, our work differs in the following ways: (1) we show how environments generated by NCA generators can scale to arbitrary sizes with similar regularized patterns, (2) in addition to encoding the constraints as part of the objective function of QD algorithms, we also use MILP to enforce the constraints on the generated environments, (3) the objective function of the previous work focus the reliability, diversity, and validity of the generated environments, while we primarily focus on optimizing throughput, which is a simulated agent-based metric of the multi-robot systems.
2.2 Quality Diversity (QD) Algorithms
Although derivative-fres single-objective optimization algorithms such as Covariance Matrix Adap- tation Evolutionary Strategy (CMA-ES) [20] have been used to optimize serivative-frre objective functions, we are interested QD algorithms because they generate diverse collection of solutions, providing users a wider range of options in terms of the diversity measure functions.
Inspired by evolutionary algorithms with diversity optimization [7, 25, 26]. QD algorithms simultane- ously optimize an objective function and diversify a set of diversity measure functions to generate diverse collection of high-quality solutions. QD algorithms have many different variants that incorporate different optimization methods, such as model-based approaches [1, 17, 50), Bayesian optimization [23], and gradient descent [11].
MAP-Elites [7, 34] constructs a discretized measure space, referred to as archive, from the user-defined diversity measure functions. It tries to find the best solution, referred to elite, in each discretized cell. The QD-score measures the quality and diversity of the elites by summing the objective values of elites in the archive. MAP-Elites generates new solutions either randomly or by mutating existing elites. then evaluates the solutions and replaces existing elites in the corresponding cells with superior ones. After a fixed number of iterations, MAP-Elites returns the archive with elites.
MAP-Elites.
CMA-MAE, We select Covariance Matrix Adaptation MAP-Annealing (CMA-MAB) [13, 14] as our QD method for training NCA generators because of its state-of-the-an performance in continuous domains. CMA-MAE extends MAP-Elites by incorporating the self-adaptation mechanisms of
3

---

CMA-ES [20]. CMA-ES maintains Gaussian distribution, samples from it for new solutions, evaluates them, and then updates the distribution towards the high-objective region of the search space. CMA-MAE incorporates this mechanism to optimize the QD-score. In addition, CMA-MAE implements an archive updating mechanism to balance exploitation and exploration of the measure space. The mechanism introduces a threshold value to each cell in the archive, which determines whether a new solution should be added. The threshold values are iteratively updated via an archive learning rate, with lower learning rates focusing more on exploitation. Because of the updating mechanism, some high-quality solutions might be thrown away. Therefore, CMA-MAE maintains two archives, an optimization archive implementing the updating mechanism, and separate result archive that does not use the mechanism and stores the actual elites.
2.3 Automatic Environment Generation and Optimization
Automatic environment generation has emerged in different research communities for various pur- poses such as generating diverse game content [41], training more robust RL agents [40, 22], and generating novel testing scenarios [1, 12].
In the MAPF community. Zhang al. [51] have proposed environment optimization method based on QD algorithms MAP-Elites [7, 34] and Deep Surrogate Assisted Generation of Environments (DSAGE) [1] improve the throughput of the multi-robot system in automated warehouses. In particular, they represent environments as tiled grids and use QD algorithms to repeatedly propose new warehouse environments by generating random environments or mutating existing environments by randomly replacing the tiles. Then they repair the proposed environments with MILP solver and evaluate them an agent-based simulator. The evaluated environments are added an archive to create collection of high-throughput environments.
However, since the proposed method directly optimizes warehouse environments, it is difficult to use the method to optimize arbitrarily large environments due to (1) the exponential growth of the search space and (2) the CPU runtime of the MILP solver and the agent-based simulator increase significantly. In comparison, we optimize environment generators instead of directly optimizing environments. addition, we explicitly take the regularized patterns into consideration which allows us to generate arbitrarily large environments with high throughput.
3 Problem Definition
We define the environments and the corresponding environment optimization problem as follows. Definition (Environment). We represent each environment as 2D four-neighbor grid, where each tile can be one of Ntype tile rypes. Ntype is determined by the domains.
Definition (Valid Environment). An environment is valid iff the assignment of tile types satisfies its domain-specific constraints.
For example, the warehouse environments shown in Figure have N Ntppe 4 (endpoints, worksta- tions, empty spaces, and shelves). One example domain-specific constraint for warchouse environ- ments is that all non-shelf tiles should be connected so that the robots can reach all endpoints.
Definition 3 (Eavironment Optimization). Given an objective function f R and a measure function m X - Thm where X is the space of all possible environments, the environment optimization problem searches for valid environments that maximize the objective function f while diversifying the measure function m.
4 Methods
We extend previous works [10, 51] to use CMA-MAE to search for a diverse collection of NCA generators with the objective and diversity measures computed from an agent-based simulator that runs domain-specific simulations in generated environments. Figure 2 provides an overview of our method. We start by sampling a batch of parameter vectors 0 from a multivariate Gaussian distribution, which form I NCA generators. Each NCA generator then generates one environment from a fixed initial environment, resulting in b environments. We then repair the environments using MILP solver to enforce domain-specifie constraints. After getting the repaired environments,

---

Sample 0 ~ (N,,
Form NCA generator and generate the environment
Repair the environment with MILP
Update optimization archive
Update Mis, X)
Update result archive
Run agent-based simulator
Figure Overview our method using CMA-MAE train diverse NCA generators.
evaluate each of them by running an agent-based simulator for N, times, each with T' timesteps. and compute the average objective and measures. We add the evaluated environments and their corresponding NCA generators both the optimization archive and the result archive. Finally, we update the parameters of the multivariate Gaussian distribution (i.e., μ and Σ) and sample new batch of parameter vectors, starting a new iteration. We run CMA-MAE iteratively with batch size until the total number of evaluations reaches Nemal-
NCA Generator. We define NCA generator function gs: 0,C): X X, where X is the space of all possible environments, s E is a fixed initial environment, and C E Z is a fixed number of iterations for the NCA generator. g parameterized by 0 E O. Since both s and C fixed, each parameter vector 0 E + corresponds to an NCA generator, which corresponds to an environment X. We discretize the measure space into M cells create an archive and attempt to find the best NCA generator in each cell to optimize the QD-score of the archive.
Our NCA generator is convolutional neural network (CNN) with the same architecture the previous work [10] with convolutional layers of kernel size activations. Figure
followed by ReLU or sigmoid Appendix C.I.1 shows the architecture. We represent the 2D tile-based environments as 3D tensors, with each tile as one-hot encoded vector. Depending on the tile types, NCA model has about 1,500 3,000 parameters. The input and output of the generator one-hot environments of the same size, facilitating iterative environment generation by feeding the generator's output back into By using a CNN, we can use the same NCA generator to generate environments of arbitrary sizes.
MILP Repair. The environments generated by the NCA generators might be invalid. Therefore, we follow previous works [49, 15, 51] to repair the invalid environments using a MILP solver. For each unrepaired environment X g(s 0, C). distance between Xin and X is minimized, and (2) the domain-specific constraints are satisfied. We introduce the domain-specific constraints in detail in Section 5 and Appendix B.
find Xont E X such that (1) the hamming
Objective Functions. We have two objective functions fopt and free for the optimization archive and the result archive, respectively. free runs agent-based simulator for Ne times and returns the average throughput. fopt optimizes the weighted sum of free and a similarity score between the unrepaired and repaired environments X and Xout- Specifically, fopt fres + a A, where is hyperparameter that controls the weight between fres and A. We incorporate the similarity score to fopt that the NCA generators more inclined to directly generate valid environments with desired regularized patterns, reducing reliance on the MILP solver for pattern generation. We show in Section 6 that incorporating the similarity score Sopt significantly improves the scalability of the environments generated by the NCA generators.
Let be the number of tiles in the environment, the similarity score A is computed as:
5

---

Ei=ı cip: where e₁
1 if (Xin); ) = (Xout); and P = n max (I)
A(Xims Nout)
P
otherwise.
e encodes if the tile type of tile in Xin and Xout are the same. pt assigns a weight to each tile. a result, the numerator computes the unnormalized similarity score. P is the theoretical upper bound of the unnormalized similarity score of all environments of domain. Dividing by P normalizes the score to the range of 0 to 1. Intuitively, the similarity score quantifies the level of similarity between the unrepaired and repaired environments Xin and Xout. with each tile weighted according to p..
Environment Entropy Measure. We want the NCA generators to generate environments with regularized patterns. quantify these patterns, we introduce environment entropy as diversity measure, inspired by previous work [30, 16]. We define a tile pattern as one possible arrangement of 2 x 2 grid in the environment. Then we count the occurrence of all possible tile patterns in the given environment, forming tile pattern distribution. The environment entrpyy is calculated as the entropy of this distribution. In essence, the environment entropy measures the degree of regularization of patterns within a given environment. A lower value of environment entropy indicates higher degree of pattern regularization. We use environment entropy as a diversity measure to find NCA generators that can generate a broad spectrum of environments of varying patterns.
Domains
We perform experiments three different domains: (1) a multi-agent warehouse domain [28, 51J, (2) a multi-agent manufacturing domain, and (3) a single-agent maze domain [16, 5, IJ.
Warehouse. The warehouse domain simulates automated warehousing scenarios, where robots transport goods between shelves the middle and human-operated workstations on the left and right borders. We use two variants of the warehouse domain, namely warehouse (even) and warehouse (uneven). warehouse (even), all workstations are visited with equal frequency, while in warehouse (uneven), the workstations right border. We constrain the warehouse environments such that all non-shelf tiles are connected and the number of shelves is N, to keep consistent storage capability. We use fopt and fres introduced in Section 4 as the objective functions, and environment entropy as one of the measures. Inspired by previous work [51], we use the number of connected shelf components the other measure. Figure 1 and Figure 7a in Appendix B show example warehouse environments.
the left border visited 5 times more frequently than those the
Manufacturing, The manufacturing domain simulates automated manufacturing scenarios, where robots go to different kinds of manufacturing workstations in a fixed order to manufacture products. We create this domain to show that our method can generate environments with more tile types for more complex robot tasks. We assume 3 kinds of workstations to which the robots must visit in a fixed order and stay for different time duration. We constrain the manufacturing environments such that all non workssrkstt tiles are connected and there is at least one workstation of each type. We use fopt and fres introduced in Section 4 as the objective functions. and the environment entropy and the number of workstations as the measures. The number of workstations can approximate the cost of the manufacturing environment. By diversifying the number of workstations, our method generates collection of environments with different price points. Figure and Figure 7b in Appendix B show example manufacturing environments.
Maze. We conduct additional experiments in the maze domain to show that our method can scale a single-agent reinforcement learning (RL) policy trained in small environments to larger environments with similar patterns. The maze domain does not have nomain-specifie constraints. We use the same objective and measure functions in the previous work [1]. Specifically, fopt and fres are both binary functions that return if the environment is solvable and 0 otherwise. The measures are the number of walls and the average path length of the agent over N. simulations. Figure 5 and Figure 7c in Appendix B show example maze environments.
We include more detailed information the domains in Appendix B.

---

Domain
S
Seval
N₂
Nseecu
Na
Na_eval
N₂
b
Neval
Warchouse (even)
36 x 33
101 102
240
2, 250
200
1, 1,400
50
10, 000
Warchouse (uneven)
36 33
101 102
240
2, 250
200
1,000
50
10, 000
Manufacturing
36 x 33
101
102
N/A
N/A
200
1, 800
50
10, 000
Maze
18 x 18
66 x 66
N/A
N/A
1
50
150
100, 000
Table I: Summary of the experiment setup. Columns 2-7 show the configurations related to the environment, and columns 8-10 show the parameters of C.A-MAE.. S, N₂. and Na are the size of the environments, the number of shelves in the warehouse domain, and the number of agents used in training, respectively. Seeat, Neueutt and Na are their counterparts used in evaluation. We choose Na eval to be large enough such that the human designed environments of the same size congested while our JCAA-geerrated ones are not. Therefore, the value of Na depends on the tasks the robots each domain.
6 Experimental Evaluation
Table 1 summarizes the experiment setup. We train the NCA generators with environments of size and then evaluate them in sizes of both and Seval. In addition, we set the number of NCA iterations C' 50 for environments of size S and Cevat 200 for those of size Sewat for all domains. Ceeal larger than C' because the NCA generators need more iterations to converge to a stable state while generating environments of size Seval- For the warehouse and manufacturing domains, Bolling-Horizzn Collision Resolution (RHCR) [28], a state-of ofate--ff-tee the-ttrrrt centralized lifelong MAPF planner, in the simulation. We run each simulation for T 1, 000 timesteps during training and Teval = 5, 000 timesteps during evaluation and stop early in case of congestion, which happens more than half of the agents take wait actions at the same timestep. For the maze domain, a trained ACCEL agent [9] in the simulations. We include more details of the experiment setup, compute resources, and implementation in Appendix C.
6.1 Multi-Agent Domains
Baseline Environments. We consider two types of baseline environments for the multi-agent domains (warehouse and manufacturing), namely those designed by human and those optimized by DSAGE [51], the totte-of-thealle environment optimization method. In DSAGE, we use fres as the objective function for the result archive and fopt with a = 5 for the surrogate archive. With size Secal, however, it is impractical to run DSAGE due to the computational limit. One single run of MILP repair, for example, could take 8 hours in an environment of size Seval. We use the human-designed warehouse environments from previous work [29, 28, 51]. The manufacturing domain is new, we create humannddes dessinee environments for it.
NCA -Ce-geree Environments. We take the best NCA generator from the result archive to generate environments of size S and Secal- In the manufacturing domain, we additionally take the best NCA generator that generate an environment of size S with similar number of workstations as the DSAGE-optimized environment. This is to ensure fair comparison, as we not constrain the number of workstations, which is correlated with throughput, in the manufacturing domain.
We show more details of the baselines and NCA-generated environments in Appendix D.
6.1.1 Environments of Size S
Columns 3 and 4 of Table 2 show the numerical results with N, 200 agents in the warehouse and manufacturing domains with environment size S. All NCA- -ene-reede environments have significantly better throughput than the baseline environments. In addition, we observe that larger values have no significant impact on the throughput with N₂ agents.
We also analyze the scalability of the environments by running simulations with varying numbers of agents and show the throughput in Figures to 3c. In both the warehouse (even) and manufacturing domains, our NCA- generated environments have higher throughput than the baseline environments with an increasingly larger gap with more agents. In the warehouse (uneven) domain, however, the DSAGE-oppinized environment displays slightly better scalability than those generated by NCA. This could be due to a need for more traversable tiles near the popular left-side workstations to alleviate congestion, a pattern creation task that poses significant challenge for NCA generators
7

---

Size S with No, agents
Size Seval with No agents
Domain
Algoridm
Success
Throughput
Success Rate
Throughpat
CMA-MAE NCA 03
100%
6.79 1: 0,00
0%
NIA
CMA MAE+ NCA
100%
6.73 1: 0.00
O%:
N/A
warehouse (even)
CMA-MAE NCA
100%
6.74 +: 0.00
90%
16.01 + 0,00 NIA
DSAGE (a = 5)
100%
6.35 + 0.00
N/A
Human
N/A
CMA-MAE + NCA =
100%
6,89 = 0,00
62%
12.32 = 0,00
CMA-MAE NCA
100%
6.70 =: 0.00
8%
11.56 +
warehouse (uneven)
MA-MAAE NCA
100%
6.82 1: 0.00
84%
12.03 1 0.00
DSAGE (o = 5)
100%
6.40 + 0.00
N/A
N/A
Human
0%
N/A
CMA-MAE NCA 5, opt)
94%
6,82 = 0.00
100
23.11 = 0.01
CMA-MAE- NCA comp DSAGE)
Manufacturing
DSAGE (a = 5)
28%
5.61 4: 0.12
N/A
NIA
Success rates and throughput environments of sizes S and Secat- run 50 simulations for all environments except for the manufacturing environments of size Sevat, for which we run 20 simulations. The success rate is calculated as the percentage of simulations that end without congestion. We measure the throughput of only successful simulations and report both its average and standard error.
Table 2:
CMA-MAE NCA (a=0)
CMA-MAE + NCA (a=5, comp DSAGE)
CMA-MAE NCA (a=1)
DSAGE (a=5)
CMA-MAE NCA (a=5, opt)
Human
10
Throughput
Throughput
Throughput
5
200 Number of Agents
Number Agents
Number of Agents
(a) S: Warehouse (even)
(b) S: Warehouse (uneven)
(c) Manufacturing
15
15
25
Throughput
Throughput
Throughpur
7.5
7.5
12.5
100
900
1700
1100
650
1200
1000
1225
2350
Number Agents
Number Agents
Number Agents
(d) Smeat: Warehouse (even)
(e) Samat:
Warehouse (uneven)
Seval: Manufacturing
Figure 3: Throughput with an increasing number of agents in environments of size S (a-c) and Seout (d-f). For size S. run 50 and 20 simulations and increase number agents by step sizes 25 50 warehouse and manufacturing domains, respectively. The solid lines are the average throughput while the shaded area shows the 95% confidence interval.
50 simulations and increase the number of agents by step size of 10. For Seval,
compared to DSAGE's direct tile search. In addition, in the manufacturing domain, the optimal NCA generator (green line) creates an environment with top throughput for 200 agents, but it is slightly less scalable than the sub-optimal one used for DSAGE comparison (grey line). We conjecture this due the optimizer being caught in a local optimum region due the complexity the tasks. On the effect of a values, observe that larger values enhance the scalability of the generated

---

(a) 18 18.
(b) 66 66.
Figure 4: Example manufacturing environment.
Figure 5: Maze environments with similar patterns different sizes generated by the same NCA generator.
environments in the warehouse (even) domain, as shown Figure 3a. We include further discussion of a values in Appendix E.
To further understand the gap of throughput among different environments size with N₂ agents, we present additional results on the number of finished tasks over time in Appendix E.2. All NCA-generated environments maintain a stable number finished tasks throughout the simulation.
6.1.2 Environments of Size Sevel
Columns 5 and 6 of Table compare environments of size Seeat with Na Na_eval agents. In the warehouse (even) domain, all environments, except for the one generated by CMA-MAE NCA (a = 5). run into congestion. In the warehouse (uneven) domain, CMA-MAE + NCA (a 5) also achieves the best success rate, even though it does not have the highest throughput. This shows the benefit of using a larger a value with CMA-MAE in creating large and scalable environments.
To further understand the scalability, Figures 3d to 3f show the throughput of the environments with increasing number of agents. We observe that all much more scalable than the human-designed ones. In particular, the environments generated by CMA-MAE NCA (ar 5) yield the best scalability in all domains. This is because higher value of a makes CMA-MAE focus more on minimizing the disparity between the unrepaired and repaired environments. As result, the optimized NCA generators environments with desired regularized patterns directly. On the other hand, smaller value of a makes the algorithm rely more on the MILP solver generate patterns, introducing more randomness the MILP solver arbitrarily selects an optimal solution with minimal hamming distance when multiple solutions exist. We show additional results of scaling the same NCA generators to more environment sizes in Appendix E.3. We also include a more competitive baseline by tiling environments of size S create those of size Seval in Appendix E.4.
NCA-generated environments
more capable of generating
6.2 Scaling Single-Agent RL Policy
In the maze domain, we show that is possible to scale a single-agent RL policy to larger environments with similar regularized patterns. We use the NCA generator trained from 18 x 18 maze environments to generate small 18 18 and large 66 66 maze environment, shown in Figure 5. Running the ACCEL [9] agent 100 times in these environments results in success rates of 90% and 93%, respectively. The high success rate comes from the fact that the similar local observation space of the RL policy enables the agent to make the correct local decision and eventually arrive at the goal.
For comparison, generate 100 baseline 66 x 66 maze environments by restricting the wall counts to be the same and the path lengths to range between 80% to 120% of the one in Figure 5b, to maintain similar difficulty levels. Figure 15 in Appendix D.2 shows two example baseline environments. Testing the ACCEL agent these environments yields an average success rate of 22% (standard error: 3%), significantly lower than that achieved in the NCA-generaa environments. This demonstrates

---

Size S with N₂ agents
Size Secol with No
Vaeevol agents
Domain
Algorithm
TNca
THILr
A
TAca
TRILP
A
CMA-MAE (a = 0)
0.06
2.72
0.94
0.12
228.80
0.95
Warchouse (even)
CMA-MAE (a = 1)
0.06
2.97
0.86
0.13
9278.18
0.84
CMA-MAE (ar = 5)
0.06
2.55
0.97
0.13
19.79
0.99
CMA-MAE (a= = 0)
0.06
2.41
0.35
0.13
1,376.62
0.85
Warehouse (uneven)
CMA-MAE (a 1)
0.06
2.36
0.95
0.13
26.54
CMA-MAF (a 5)
0.06
13.42
0.84
0.13
15,656.04
0.86
Manufacturing
CMA-MAE 5, opt)
0.07
3.04
0.17
0.18
15,746.00
0.18
Table 3: CPU runtime measured (in seconds) for the trained NCA generators to generate environments (TNCA), and for the MILP solver to subsequently repair the generated environments (ThrrI.)) of size S and Sevat. A refers to the similarity score between the repaired and unrepaired environments. We measure the CPU runtime machine (1) listed in Appendix C.3 and compute constraints in Appendix C.4.
the ability of our method to generate arbitrarily large environments with similar patterns in which the trained RL agent performs well.
6.3 NCA Generation Time
We show the total CPU runtime of generating and repairing the environments of sizes S and Seval in Table 3. In both sizes, larger similarity scores are correlated with shorter MILP runtime. The similarity scores of the manufacturing environments normalization factor P than that in the warehouse domains. Nevertheless, we note that even the longest combined runtime of the NCA generation and MILP repair (15, 746.10 + 0.18 15, 746.28 seconds for the manufacturing domain) on the environments of size Senat is significantly shorter than optimizing the environments of that size directly. This reduction in time is attributed to our method, which involves rumning the MILP repair Neval times with an environment size of S while training the NCA generators, and then using the MILP solver only once with size Seval while generating the environments. Our method stands in contrast to the previous direct environment optimization method [51] which requires running the MILP repair with the size of S Seval for Neval times.
significantly lower because we
larger
6.4 On the Benefit of QD Algorithms
QD algorithms can train diverse collection of NCA generators. In Appendix E.5, we compare the QD-score and archive coverage of CMA-MAE + NCA and DSAGE. We also benchmark CMA-MAE against MAP-Elites [34, 47] to highlight the benefit of using CMA-MAE in training NCA generators. We observe that CMA-MAE + NCA has the best QD-score and archive coverage all domains.
Furthermore, QD algorithms can train more scalable NCA generators than single-objective optimizers. In Appendix E,6 compare CMA-MAE with single-objective optimizer CMA-ES [20]. We observe that CMA-MAE is less prone to falling into local optima and thus better NCA generators.
7 Limitations and Future Work
We present a method to train diverse collection of NCA generators that can generate environments of arbitrary sizes within a range defined by finite compute resources. In small environments of size S, our method generates environments that have competitive or better throughput compared to the state-of-the-art environment optimization method [51]. In large environments of size Seeat, where existing optimization methods are inapplicable, our generated environments achieve significantly higher throughput and better scalability compared to human-designed environments.
Our work is limited in many ways, yielding many directions for future work. First, our method is only arbitrarily scalable under a range determined by finite compute resources. For example, with the compute resource in Appendices C.3 and C.4. the upper bound of the range is about Seval 101 x 102. Although this upper bound is significantly higher than previous environment optimization methods, future work can seek to further increase Second, we focus on generating 4-neighbor grid-based environments with an underlying undirected movement graph. Future work can consider generating similar environments with directed movement graphs or irregular-shaper environments. We additionally discuss social impacts of our work in Appendix F.
10

---

Acknowledgements
This work used Bridge-2 at Pittsburgh Supercomputing Center (PSC) through allocation CIS2201 from the Advanced Cyberinfrastructtur 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 CMU Manufacturing Futures Institute, made possible by the Richard King Mellon Foundation, and was partially supported by the NSF CAREER Award (#2145077).
References
[1] Varun Bhatt, Bryon Tjanaka, Matthew Fontaine, and Stefanos Nikolaidis. Deep surrogate assisted generation of environments. Proceedings of the Advances Neural Information Processing Systems (NeurIPS), pages 37762-37777, 2022.
[2] Alan S. Brown. How Amazon robots navigate congestion. https: /ww. amazon. science//eeeccccccc Sance/laten weweeettnewwwhwwwwaaaaaaeeeeeeee wloowamazon... www.ooosaaaaiaatttoooneeeaaaeea. Accessed: 2023-05-09.
2022.
[3] Bert Wang-Chab Chan. Lenia and expanded universe. In Proceedings of the Conference on Artificial Life (ALIFE), pages 221-229, 2020.
[4] Zhe Chen, Javier Alonso-Mora, Xiaoshan Bai, Daniel Harabor, and Peter Stuckey. Integrated task assignment and path planning for capacitated multi-agent pickup and delivery. IEEE Robotics and Automation Letters, 6(3):8816-5823, 2021.
[5] Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https::/g/ttt /t/tt/ttttuutb/ cwm/ca//aaaaoooo /wwximxxxiicbbemmmmmmmmmmmmm http//ggmmmmngggggeeeee minigrid, 2018.
[6] Antonello Contini and Alessandro Farinelli. Coordination approaches for multi-item pickup and delivery in logistic scenarios. Robotics and Autonomous Systems, 146:10387) 2021.
[7] Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean-Baptiste Mouret. Robots that can adapt like animals. Nature, 521(5533):003-507, 2015.
[8] Mehul Damani, Zhiyao Luo, Emerson Wenzel, and Guillaume Sartoretti. PRIMALg: Pathfinding via reinforcement and imitation multi-agent learning lifelong. IEEE Robotics and Automation Letters, 6(2):2666-2673. 2021.
[9] Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised en- vironment design. In Proceedings of the Advances Neural Information Processing Systems (NeurIPS), pages 13049-13061, 2020.
[10] Sam Farle, Justin Snider, Matthew C. Fontaine, Stefanos Nikolaidis, and Julian Togelius. Illuminating diverse neural cellular automata for level generation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 68-76, 2022.
[11] Matthew Fontaine and Stefanos Nikolaidis. Diffcrentiable quality diversity. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), pages 10040-10052, 2021.
[12] Matthew C. Fontaine and Stefanos Nikolaidis. quality diversity approach automatically generating human-robot interaction scenarios in shared autonomy. In Proceedings of the Robotics: Science and Systems (RSS), 2021.
[13] Matthew Fontaine and Stefanos Nikolaidis. Covariance matrix adaptation map- annealing. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 456-465, 2023.
[14] Matthew C. Fontaine, Julian Togelius, Stefanos Nikolaidis, and Amy K. Hoover. Covariance matrix adaptation for the rapid illumination of behavior space. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 94-102, 2020.

---

[15] Matthew C. Fontaine, Ya-Chuan Hsu, Yulun Zhang, Bryon Tjanaka, and Stefanos Nikolaidis. On the importance of environments in human-robot coordination. In Proceedings of the Roboties: Science and Systems (RSS), 2021.
[16] Matthew C. Fontaine, Ruilin Liu, Ahmed Khalifa, Jignesh Modi, Julian Togelius, Amy K. Hoover, and Stefanos Nikolaidis. Illuminating Mario scenes in the latent space of a generative adversarial network. Proceedings of the AAAI Conference Artificial Intelligence (AAAI), pages 5922-5930, 2021.
[17] Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret. Data-efficient design exploration through surrogate-assitted illumination. Evolationary compuiation, 26(3):381-410, 2018.
[18] Gennaro Gala, Daniele Grattarola, and Erik Quaeghebeur. E(n)-equivvariat graph neural cellular automata. ArXiv, abs/2301.10497, 2023.
[19] Martin Gardner. Mathematical games the fantastic combinations of john conway's new solitaire game "life". Scientific American, 223(4):120-12 1970.
[20] Nikolaus Hansen. The CMA evolution strategy: A tutorial. ArXiv, abs/1604.00072, 2016.
[21] IBM Corp. IBM ILOG CPLEX Optimization Studio. https: /www. ibm. com/
products/ilooo pordbutss/lloggpplee-ppppoe opt-opttiiii wwwpppiiiiiiioinniiiiiiiiiiiiiii satiiostttttiooo 2022.
[22] Niels Justesen, Ruben Rodriguez Torrado, Philip Bontrager, Ahmed Khalifa, Julian Togelius, and Sebastian Risi. Illuminating generalization in deep reinforcement learning through procedural level generation. In NeurlPS Workshop on Deep Reinforcement Learning. 2018.
[23] Paul Kent and Juergen Branke. Bayesian quality diversity search with interactive illumination. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 1019- 1026, 2023.
[24] Ngai Meng Kou, Cheng Peng, Hang Ma, T. K. Satish Kumar, and Sven Koenig. Idle time optimization for target assignment and path finding in sortation centers. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 9925-9932, 2020.
[25] Joel Lehman and Kenneth O Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary computation, (192):19-2233 2011.
[26] Joel Lehman and Kenneth O. Stanley. Evolving a diversity of virtual creatures through novelty search and local competition. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 211-218, 2011.
[27] Jiaoyang Li, Kexuan Sun, Hang Ma, Ariel Felner, T. K. Satish Kumar, and Sven Koenig. Moving agents in formation in congested environments. In Proceedings of the International Joint Conference on Autonomous Agents and Mulliagent Systems (AAMAS), pages 726-734, 2020.
[28] Jiaoyang Li, Andrew Tinka, Scott Kiesel, Joseph W. Durham, T. K. Satish Kumar, and Sven Koenig. Lifelong multi-agent path finding in large-seale warehouses. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 1 11222-11221 11281, 2021.
[29] Minghua Liu, Hang Ma, Jiaoyang Li. and Sven Koenig. Task and path planning for multi-agent pickup and delivery. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 1152-1160, 2019.
[30] Simon M. Lucas and Vanessa Volz. Tile pattern KL-divergence for analysing and evolving game levels. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 170-178, 2019.
[31] Hang Ma. Jiaoyang Li, T. K. Satish Kumar, and Sven Koenig. Lifelong multi-agent path finding for online pickup and delivery tasks. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 045, 2017.
[32] Alexander Mordvintsev and Eyvind Niklasson. jNCA: Texture generation with ultra-compact neural cellular automata. ArXiv, abs/211 2021.
12

---

[33] Alexander Mordvintsev. Ettore Randazzo, Eyvind Niklasson, and Michael Levin. Growing neural cellular automata. Distill, 2020.
[34] Saan-Baptsste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. ArXiv, 2015.
[35] Van Nguyen, Phillipp Obermeier, Tran Cao Son, Torsten Schaub, and William Yeoh. General- ized target assignment and path finding using answer set programming. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAJ), pages 1216-1223, 2017.
[36] Eyvind Niklasson, Alexander Mordvintsev, Ettore Randazzo, and Michael Levin. Self- organising textures. Distill, 2021.
[37] Jack Parker-Holder, Minqi Jiang. Michael Dennis, Mikayel Samvelyan, Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. Evolving curricula with regret-based environment design. In Proceedings of the International Conference on Machine Learning (ICML), pages 17473-17498,
2022.
[38] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary VeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, nigh-performance deep learning library. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), pages 8024-8035, 2019.
[39] Chris Reinke, Mayalen Etcheverry, and Pierre-Y Yves Oudeyer. Intrinsically motivated discov- ery of diverse patterns in oeff-organi systems. In International Conference on Learning Representations (ICLR), 2020.
[40] Sebastian Risi and Julian Togelius. Increasing generality in machine learning through procedural content generation. Nature Machine Intelligence, 2:428 436, 2020.
[41] Noor Shaker, Julian Togelius, and Mark J. Nelson. Procedural Content Generation in Games: A Textbook and an Overview of Current Research. Springer, 2016.
[42] Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma. Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Roman Barták, and Eli Boyarski. Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proceedings of the International Symposium on Combinatorial Search (SoCS), pages 151-159, 2019.
[43] Shyam Sudhakaran, Djordje Grbic, Siyan Li, Adam Katona, Elias Najarro, Claire Glanois, and Sebastian Risi. Growing 3D artefacts and functional machines with neural cellular automata. In Proceedings of the Conference on Artificial Life (ALIFE), page 108, 2021.
[44] Mattie Tesfaldet, Derek Nowrouzezahrai, and Chris Pal. Attention Attee neural cellular au- tomata. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), pages 8174-810 8186, 2022.
[45] Bryon Tjanaka, Matthew C. Fontaine, David H. Lee, Yulun Zhang, Nivedit Reddy Balam, Nathaniel Dennler, Sujay S. Garlanka, Nikitas Dimitri Klapsis, and Stefanos Nikolaidis. pyribs: A bare-bones python library for quality diversity optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 220-229, 2023.
[46] Sumanth Varambally, Jiaoyang Li, and Sven Koenig. Which MAPF model works best for automated warehousing? Proceedings of the Symposium on Combinatorial Search (SoCS), pages 190-198, 2022.
[47] Vassiis Vassiliades and Jean-Baptiste Mouret. Discovering the elite hypervolume by leveraging interspecies correlation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 149-156, 2018.
[48] Ge Yu and Michael Wolf. Congestion prediction for large fleets of mobile robots. In Proceedings of the International Conference on Robotics and Automation (ICRA), pages 7642-7649, 2023.
13

---

[49] Hejia Zhang, Matthew C. Fontaine, Amy K. Hoover, Julian Togelius, Bistra Dilkina, and Stefanos Nikolaidis. Video game level repair mixed integer linear programming In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), pages 151-158, 2020.
[50] Yulun Zhang, Matthew C. Fontaine, Amy K. Hoover, and Stefanos Nikolaidis. Deep surrogate assisted map-elites for automated hearthstone deckbuilding. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 158-167, 2022.
[51] Yulun Zhang, Matthew C. Fontaine, Varun Bhatt, Stefanos Nikolaidis, and Jiaoyang Li. Multi- robot coordination and layout design for automated warehousing. In Proceedings of the Interna- tional Joint Conference on Artificial Intelligence (IJCAT), pages 5503-5511, 2023.
14


Reviews:
[{"review_id": "xBt724QcmG", "reviewer": "Reviewer_YTho", "summary": "The research paper addresses the problem of generating large environments to improve the throughput of multi-robot systems. While previous work has proposed Quality Diversity (QD) algorithms for optimizing small-scale environments in automated warehouses, these approaches fall short when replicating real-world warehouse sizes. The challenge arises from the exponential increase in the search space as the environment size grows. Additionally, the previous methods have only been tested with up to 350 robots in simulations, whereas practical warehouses could host thousands of robots.\n\nTo overcome these limitations, the authors propose a novel approach using Neural Cellular Automata (NCA) environment generators optimized through QD algorithms. Instead of directly optimizing environments, they train a collection of NCA generators with QD algorithms in small environments and then generate arbitrarily large environments from these generators at test time. The key advantage of using NCA generators is that they maintain consistent, regularized patterns regardless of the environment size, significantly enhancing the scalability of multi-robot systems.\n\nThe research is divided into three domains: multi-agent warehouses, multi-agent manufacturing scenarios, and single-agent maze environments. In the warehouse and manufacturing domains, the authors compare their NCA-generated environments with human-designed and state-of-the-art optimized environments, demonstrating higher throughput and better scalability in the NCA-generated environments. In the maze domain, they show that their method can scale a single-agent reinforcement learning (RL) policy to larger environments with similar patterns, outperforming baseline environments.\n\nThe paper's strengths lie in its originality, proposing a novel combination of NCA generators and QD algorithms to address the scalability challenge, its quality in presenting a systematic evaluation across multiple domains, clarity in the presentation of algorithms and results, and the significance of its potential impact on various multi-robot systems applications.", "questions": "Clarification on Novelty: Can the authors provide a more detailed explanation of the novel aspects of their proposed method compared to prior works in the field of environment generation and optimization? How does their approach differ from existing approaches in terms of algorithmic design and optimization techniques?\n\nScalability Analysis: Could the authors elaborate on the reasons behind the observed differences in scalability between the warehouse (even) and warehouse (uneven) domains? What factors contribute to the better scalability in one domain compared to the other? Is it possible to improve scalability in the domain with poorer performance?\n\nComparison with Baseline Models: While the authors have compared their NCA-generated environments with human-designed environments and DSAGE, could they provide additional comparisons with other baseline models or state-of-the-art methods in related research areas? This would help establish the broader significance of their proposed method.\n\nReal-World Applicability: How feasible is the implementation of the proposed method in actual automated warehouse or manufacturing environments? What are the potential challenges or limitations when applying the method to real-world scenarios? Are there any specific requirements or modifications needed for practical implementation?\n\nGeneralization to Other Domains: Could the authors discuss the potential applicability of their proposed method to domains beyond the ones tested in this paper? How well does the approach generalize to diverse multi-agent systems and different task settings? What are the potential obstacles or adaptations required for transferring the method to other scenarios?\n\nSensitivity to Hyperparameters: How sensitive is the proposed method to the choice of hyperparameters, such as ↵? Can the authors provide insights into the effects of different hyperparameter settings on the quality and scalability of the generated environments? Are there specific guidelines for tuning these hyperparameters?\n\nOpen-Source Code Availability: Is the authors' codebase publicly available for reproducibility and further research? If not, would the authors consider releasing the code to the research community? Open-sourcing the implementation would facilitate collaboration and promote further advancements in the field.\n\nRealistic Simulation Assumptions: How well do the agent-based simulators used in the experiments represent real-world multi-agent systems? Are there any limitations or simplifications in the simulators that might affect the validity of the results or the generalizability of the findings?\n\nImpact of Environment Size: In the experiments, the authors evaluate the NCA-generated environments on larger sizes (Seval) compared to the training environments (Strain). Could the authors discuss how increasing environment size affects the performance and efficiency of the NCA generators? Are there any specific challenges or benefits associated with generating larger environments?\n\nPractical Use Cases: Can the authors provide examples of potential real-world applications or use cases where the proposed method could be applied to improve multi-robot systems' performance and scalability? What are the envisioned practical benefits of adopting the proposed approach in such scenarios?", "limitations": "Simplified Simulations: The agent-based simulators used in the experiments might oversimplify real-world scenarios, leading to potential discrepancies between simulated and actual multi-robot system behaviors. The authors should discuss the implications of these simplifications and any potential deviations from real-world performance.\n\nLack of Real-World Validation: The proposed method's evaluation is primarily based on simulations, and there is no direct validation in real-world warehouse or manufacturing environments. It would be beneficial to include experiments in real-world scenarios to assess the transferability and effectiveness of the NCA-generated environments.\n\nGeneralization to Other Environments: While the paper shows promising results in the warehouse and manufacturing domains, it remains unclear how well the proposed method generalizes to more complex and diverse environments, such as outdoor spaces, multi-floor warehouses, or environments with dynamic obstacles.\n\nHyperparameter Sensitivity: The method's performance might be sensitive to the choice of hyperparameters, such as the weight ↵ used to balance similarity and objective functions. The authors should provide a more comprehensive analysis of the sensitivity of the method to different hyperparameter settings.\n\nScalability in All Domains: While the paper demonstrates superior scalability in some domains, the method's performance in other domains, such as the warehouse (uneven) scenario, does not show the same level of improvement over baseline environments. The authors should address the limitations that might hinder scalability in certain domains and propose potential solutions.\n\nEthical and Societal Considerations: Although the paper focuses on technical aspects, it is essential to discuss the broader societal impacts and potential ethical considerations of deploying large-scale multi-robot systems in various real-world applications. Addressing ethical implications and potential negative societal consequences can provide a more well-rounded perspective on the research.\n\nReproducibility: While the paper outlines the method's details, there is no mention of whether the authors' codebase is available for replication and further research. Providing open-source code or detailed instructions for replication would improve the study's transparency and reproducibility.\n\nComparison with More Baseline Models: The paper compares the NCA-generated environments with human-designed environments and DSAGE. Including additional comparisons with other state-of-the-art environment generation and optimization methods would strengthen the research's credibility and position it in the broader context of related work.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Originality:\n\nThe paper introduces a novel approach to address the problem of generating large environments for multi-robot systems, which is distinct from prior work that focused on optimizing relatively small-scale environments.\nThe utilization of Neural Cellular Automata (NCA) environment generators, optimized through Quality Diversity (QD) algorithms, is a unique and creative combination of techniques, enabling the generation of large environments with regularized patterns.\nThe introduction of environment entropy as a diversity measure to quantify regularized patterns is an innovative concept, which contributes to understanding and evaluating the environments' structural characteristics.\nQuality:\n\nThe research paper thoroughly describes the methodology, algorithms, and experiments, providing comprehensive details for replicability and understanding.\nThe authors present a systematic evaluation across multiple domains, comparing their NCA-generated environments with human-designed and state-of-the-art optimized environments. The results are statistically analyzed and presented, demonstrating the quality of the proposed approach.\nThe utilization of CMA-MAE, a state-of-the-art optimization algorithm, adds rigor to the paper's technical foundation.\nClarity:\n\nThe paper is well-written and organized, making it easy for readers to follow the methodology and results.\nMathematical formulations and notations are clear and appropriately explained, enhancing the paper's accessibility to researchers in the field.\nThe use of illustrative figures and tables helps in visualizing the concepts and experimental outcomes.\nSignificance:\n\nThe paper addresses an important problem in the field of multi-robot systems, i.e., scalability and efficient generation of large environments.\nThe proposed NCA environment generators have the potential to impact various applications, such as automated warehouses and manufacturing systems, by providing optimized and scalable environments.\nThe demonstrated scalability of single-agent RL policies to larger environments with similar patterns indicates broader implications for other agent-based systems and RL tasks.\n", "weaknesses": "Lack of Novelty in the Proposed Method: The paper claims to propose a new method for optimizing Neural Cellular Automata (NCA) environment generators using Quality Diversity (QD) algorithms. However, the paper does not adequately demonstrate the novelty of the proposed method compared to prior works that have used similar optimization techniques for environment generation. The lack of a comprehensive literature review and clear differentiation from previous approaches weakens the paper's contribution.\n\nInsufficient Evaluation of Scalability: While the paper demonstrates improved scalability of NCA-generated environments compared to human-designed environments, it lacks a thorough analysis of scalability as the environment size increases. The experiments focus on relatively small environments (e.g., 36x33) and then evaluate the same NCA generators on larger environments (e.g., 101x102). A more systematic study with varying environment sizes and intermediate steps would provide a clearer understanding of scalability.\n\nLimited Comparison with Baseline Models: The paper compares the NCA-generated environments with human-designed environments and a state-of-the-art optimization method, DSAGE, but does not include comparisons with other baseline models or state-of-the-art methods in related areas of research. Including more comprehensive comparisons would strengthen the paper's findings.\n\nLack of Real-world Implementation and Validation: The research focuses on simulated environments and agent-based simulations. While these are suitable for initial validation, the lack of real-world implementation and validation on physical multi-robot systems in actual automated warehouses or manufacturing scenarios reduces the practical significance of the proposed method.\n\nLack of Discussion on Generalizability: The paper focuses on three specific domains (multi-agent warehouse, multi-agent manufacturing, and single-agent maze), but it lacks a discussion of the generalizability of the proposed method to other domains or applications. Addressing the potential limitations and extensions to different scenarios would enhance the paper's broader impact.\n\nInsufficient Analysis of Hyperparameters: The paper briefly mentions the use of hyperparameters, such as ↵, but does not provide a detailed analysis of how these hyperparameters affect the performance of the proposed method. A thorough sensitivity analysis and tuning of hyperparameters would provide more insights into the model's behavior and stability.\n\nLack of Open-Source Implementation: While the paper describes the proposed method in detail, it does not provide an open-source implementation or a publicly available codebase. Providing access to the code would allow researchers to reproduce the experiments and build upon the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Clarification on Novelty:\n\n    In prior environment generation methods [47], the size of the environments searched over and the size of the environments generated are the same. These methods involve thousands of agent simulations during the search. In large environments that we generate in our work, each simulation may take up to a day, making it intractable to directly apply prior methods. Hence, searching for environment generators in smaller environments and leveraging them to generate larger environments is a crucial step in scaling environment generation.\n\n    Another work [11] has combined QD algorithm and NCA to generate diverse game environments in small sizes (16 by 16). Our work is different from the following aspects: (1) while the prior work focuses on generating diverse game levels, we show that the NCA generators can be trained at a small scale and then be used to generate larger environments at various scales while maintaining consistent local patterns, which is beneficial to large multi-agent system design, (2) we incorporated the MILP solver to enforce domain specific constraints, (3) our objective function includes the throughput, which is a simulated agent-based metric, while the objective function of the previous work focuses on properties of the environments, (4) we introduced the similarity score S (introduced in section 4) to the objective function so that the generated environments can more easily scale to larger sizes.\n\n2. Scalability Analysis:\n\n    Environments of warehouse (uneven) domains are generally less scalable because the tasks of the robots are unevenly distributed. In particular, robots are 5 times more likely to go to workstations on the left border than those on the right. As a result, the robots can more easily get congested because more robots will be traveling to the left-border workstations throughout the simulation.\n\n3. Comparison with Baseline Models:\n\n    Please see **More Competitive Baselines** in the general rebuttal.\n\n4. Real-World Applicability:\n\n    Please see **Generalizing to Other Domains and Real-World Scenarios** in the general rebuttal.\n\n5. Generalization to Other Domains:\n\n    Please see **Generalizing to Other Domains and Real-World Scenarios** in the general rebuttal.\n\n6. Sensitivity to Hyperparameters: \n\n    The most important hyperparameter in our method is alpha, which controls the weighting between throughput and similarity score in the objective function. We show the experimental results of different alpha values in warehouse (even) and warehouse (uneven) domains in section 6.1. In Figure 7 and 9 of Appendix C.3, we show the generated environments trained with different alpha values. In general, larger alpha results in better scalability in larger environments. \n\n7. Open-Source Code Availability: \n\n    We have included the code with instructions to reproduce our results in the supplemental material. We will make the code public if our paper is accepted.\n\n8. Realistic Simulation Assumptions:\n\n    Please see **Generalizing to Other Domains and Real-World Scenarios** in the general rebuttal.\n\n9. Impact of Environment Size:\n\n    The performance of the NCA generator in terms of runtime is neglectable with increasing environment sizes. We provide the detailed runtime of the NCA generator and MILP solver in sizes of S_train and S_eval in table 5 of appendix D.4.\n\n10. Practical Use Cases:\n\n    Please see **Generalizing to Other Domains and Real-World Scenarios** in the general rebuttal."}, {"review_id": "T1eQ7t8yji", "reviewer": "Reviewer_fmHH", "summary": "The authors have used the Covariance Matrix Adaptation MAP-Annealing algorithm to generate warehouse environments that are efficient for robots to roam around and do their task of moving packages from one place to the other. The authors have presented the idea very nicely in step by step manner, making the concepts clear gradually. \n\nIt appears that the work is an improvement over previous works by the same authors. So this cannot be called a novel idea or work. Although, the authors have successfully applied the proposed algorithm to the problem at hand, i.e. organizing a warehouse for swift movement of robots. ", "questions": "What is a measure space that you have mentioned at different places starting from line 115, apparently, you have not defined it. Please provide a reference where this term is defined and an appropriate meaning relevant to your context.", "limitations": "Yes, the authors have dedicated a complete section to this. The present work is only limited to the square-shaped cells each having 2 to 4 neighbors. They are aiming to find a strategy for organizing irregularly shaped objects, which would be quite challenging. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The results presented by the authors are comprehensive and promising. The appendices cover the areas that are left unhandled in the paper. The authors have provided the code to execute. Although, I could not run it due to the time required for it.", "weaknesses": "Including Human design as a metric of comparison is odd, because this is very subjective. An expert human being might be able to design an environment that is far better than a machine. Then there will be a question how have you sampled a human being, have you conducted a survey, or have designed a test that can measure the knowledge of a human being? The questions will keep popping up. I am not saying that you cannot compare with a human being, but the idea is when a scientific study is done including human beings, then the appropriate representatives are picked carefully, which is missing here.\n\nThe authors should have mentioned which hardware they used for executing the algorithm. They should have also mentioned how much time it took for them to execute all the scenarios. It appears that the simulation step would have taken quite a large amount of time, then have they considered any parallelism?\n\n\nFollowing are some mistakes \n\n\t- Figure 1\n\t\t○ shows an warehouse environment optimized directly with QD algorithms\n\t\t○ [correction]\n\t\t○  shows a warehouse environment optimized directly with QD algorithms\n\t- Line 45\n\t\t○ are well suited to arbitrary scaling as they incrementally contruct\n\t\t○ [correction]are well suited to arbitrary scaling as they incrementally construct\n\t- Line 56,57\n\t\t○ we only run the MILP solver once after generating the large environments.\n\t\t○ [correction]\n\t\t○ we only run the MILP solver once after generating large environments.\n\t- Line 80\n\t\t○ However, in the case of the environment optimization\n\t\t○ [correction]\n\t\t○ However, in the case of environment optimization\n\t- Line 177\n\t\t○ The generator’s input and output are indentical sized one-hot environments\n\t\t○ [correction]\n\t\t○ The generator’s input and output are identical sized one-hot environments\n\t- Line 223 and onwards\n\t\t○ Repeatedly the work \"Manufacture\" has been used, instead in most places \"Manufacturing\" should have been used\n\t- Line 319\n\t\t○ of arbitrarily sizes.\n\t\t○ [correction]\nof arbitrary sizes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Measure Space\nMeasure space is part of the QD problem definition and we adopt the definition from the DSAGE paper [47]. Specifically, a measure space is a bounded and discretized space defined by the user-specified diversity measure functions. The goal of the QD algorithm is then to simultaneously optimize an objective function and diversity the measure functions, resulting in an archive of solutions in the measure space. In our context, the measure space of each domain is defined by measure functions specified in Section 4 and 5. We will add the definition to the revised version of the paper.\n\n# Human Subject\nRegarding the human-designed environments, we clarify that many prior works in Multi-Agent Path Finding (MAPF) [27, 29, 1*, 2*, 3*] use similar human-designed environments to benchmark the algorithms. Therefore, we take the human-designed environments used in prior works as reasonable representative of huma-designed environments in our study. We include how the human-designed environments are created in Appendix C.4.\n\n# Hardware\nWe thank the reviewer for pointing out the importance of parallization in our experiments. We did parallelize all the simulations in our experiments using compute resources specified in Appendix C.5.\n\n### References\n\n[1*] Van Nguyen, Philipp Obermeier, Tran Cao Son, Torsten Schaub, and William Yeoh. Generalized target assignment and path finding using answer set programming. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 1216–1223, 2017.\n\n[2*] Hang Ma, Jiaoyang Li, T. K. Satish Kumar, and Sven Koenig. Lifelong multi-agent path finding for online pickup and delivery tasks. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 837–845, 2017.\n\n[3*] Zhe Chen, Javier Alonso-Mora, Xiaoshan Bai, Daniel D Harabor, and Peter J Stuckey. Integrated task assignment and path planning for capacitated multi-agent pickup and delivery. IEEE Robotics and Automation Letters, 6(3):5816–5823, 2021."}, {"review_id": "VRD5oeCfFZ", "reviewer": "Reviewer_6eLV", "summary": "This paper proposes a method for generating diverse sets of environments and solving arbitrarily large environments. The main difference of this method is that the individual in QD algorithms serves as an environment generator rather than an environment, making it capable of handling very large-scale environment generation tasks.", "questions": "1/ Why are there only two lines in Figure 3-f? \n\n2/ Could you show the diverse behaviors of the different generators? \n\n3/ The problem formulation, i.e., geneate a set of environment generators rather than environments, significantly increases the optimization overhead during the training process. How to balance the cimputation cost and the final performance? \n\n4/ How about using QD algorithms to directly generate a set of environments with different scales, and taking the scales as a part of the diversity measure?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1/ The proposed method can generate large environments and significantly improve the throughput of multi-robot system. \n\n2/ Using QD algorithms to solve this problems make sense, and the effectiveness are verified.", "weaknesses": "1/ The paper is somewhat difficult to read and lacks sufficient background information. To effectively convey the significance of the problem, the authors should provide a more detailed introduction to the research and add more references. This will help readers who are unfamiliar with the content to better understand the paper\n\n2/ The technical contribution of this work is somewhat limited. The proposed method appears to be an ad-hoc combination of existing techniques, and the authors should emphasize their unique technical contributions or demonstrate the method's importance in real-world applications.\n\n3/ To further strengthen the results, it would be beneficial to include more challenging types of environments and competitive baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Why are there only two lines in Figure 3-f?\n\n    Our method has a hyperparameter alpha that controls the weighting between throughput and similarity score in the objective function. We studied the effect of hyperparameter alpha in Section 6.1 in the warehouse domains. We observe that alpha = 5 is a reasonable setting that can generate environments which outperform human-designed ones. We therefore run experiments in the manufacture domain with alpha = 5. In the final version, we will add the results with more alpha values to validate our hypothesis.\n\n2. The problem formulation, i.e., generate a set of environment generators rather than environments, significantly increases the optimization overhead during the training process. How to balance the computation cost and the final performance?\n\n    We clarify that generating a set of environment generators rather than environments does not significantly increase the optimization overhead because the majority of the computation resides in agent simulations. For example, in the warehouse (even) domain, the baseline DSAGE algorithm finishes within 24 hours while our method finishes in 28 hours on machine (2) specified in appendix C.5. The extra time is attributed to the MILP solver because, early in the optimization process, the initial NCA generators tend to generate unrepaired environments with simple patterns that do not satisfy most domain-specific constraints.\n\n 3. How about using QD algorithms to directly generate a set of environments with different scales, and taking the scales as a part of the diversity measure?\n\n    We thank the reviewer for the suggestion. By introducing scale as a diversity measure, the QD optimization problem would be much more challenging because we will be simultaneously optimizing NCA generators that generate environments of different scales. In addition, the large computational requirement for the agent-based simulator and MILP solver still remain with this approach. We acknowledge that this is an interesting direction for future work.\n\n4. For the question regarding more comptitive baseline methods such as Compositional Pattern Producing Networks, please see **More Competitive Baselines** in the general rebuttal.\n"}, {"review_id": "U3zbNMSakO", "reviewer": "Reviewer_v7gi", "summary": "In this work, the authors train neural cellular automata with a quality diversity evolutionary algorithm to grow the 2D environment of a multi-agent automated warehouse, manufacturing domain, and single agent maze domain. They show that the approach is able to generate environments that can scale to different sizes, while keeping important regularities. ", "questions": "- \"we define a tile pattern as one possible arrangement of a 2- 2 grid in the environment.\" -> What about the distribution of global patterns? I assume they would not be captured this way?\n- One important question is, how easily could this approach be applied to other domains? Does it work particularly well for the domains in this paper because of their types of patterns? Which other domains could it be applied to in the future and what type of patterns would they need to benefit of, in order to allow the scaling to happen? What about environments that need more global pattern than local ones, which the NCA is particularly good at?\n- How important is the MILP in the process? At some point in the paper, it says that the process can take 8 hours, which suggests it can also become a bottleneck. It would be good to include the number of errors that MILP fixed (including the number of enironments that were initially not functional) in the result tables for all methods. ", "limitations": "Yes for the most part. It would be good to talk a bit more about the potential limitation of NCAs to capture more global patterns.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- NCAs can be trained to generate small environments and then scaled to larger environments without further training, thereby saving computational costs\n- Compared to previous methods, the Mixed Integer Linear Programming (MILP) has to only be run once to fix the larger environments\n- the combination of NCa and MILP is an interesting idea that could be extended to many other domains that NCAs already have been successfully applied to", "weaknesses": "- The approach is only shown in similar 2D domains\n- The paper could include more environment generation baselines, beyond DSAGE. For example, a comparison to Compositional Pattern Producing Networks (which could also be scaled to larger environments without further training) could elucidate the importance of growth over time\n- It would also be useful to include a baseline in which a larger map is created by just concatenating smaller environments and running MILP. Would those perform equally well? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. \"We define a tile pattern as one possible arrangement of a 2- 2 grid in the environment.\" -> What about the distribution of global patterns? I assume they would not be captured this way?\n\n    We clarify that the environment entropy measure introduced in Section 4 only measures the local pattern. We first define a tile pattern as one possible arrangement of a 2 by 2 grid, then count the occurrences of all possible tile patterns to form a tile distribution. The environment entropy is calculated as the entropy of the tile distribution. High environment entropy represents low regularity in the patterns while low environment entropy represents high regularity. We are more interested in the local patterns instead of global patterns because warehouse and manufacture system designers care more about resolving congestion in the environment with scalable local patterns. If our method is to be applied to other domains in which global patterns are important, we can develop diversity measures that consider global patterns.\n\n2. One important question is, how easily could this approach be applied to other domains? Does it work particularly well for the domains in this paper because of their types of patterns? Which other domains could it be applied to in the future and what type of patterns would they need to benefit of, in order to allow the scaling to happen? What about environments that need more global pattern than local ones, which the NCA is particularly good at?\n\n    Please see **Generalizing to Other Domains and Real-World Scenarios** in the general rebuttal.\n\n3. How important is the MILP in the process? At some point in the paper, it says that the process can take 8 hours, which suggests it can also become a bottleneck. It would be good to include the number of errors that MILP fixed (including the number of environments that were initially not functional) in the result tables for all methods.\n\n\tPlease see **Role of MILP** in the general rebuttal.\n\n4. For the question regarding more comptitive baseline methods such as Compositional Pattern Producing Networks, please see **More Competitive Baselines** in the general rebuttal.\n"}, {"review_id": "TMBVehwa15", "reviewer": "Reviewer_ShTu", "summary": "The authors' goal is to optimize large floorplans for warehouses or manufacturing facilities, where robots need to drive during completion of tasks, while avoiding a congestion of the system.\nTheir innovation is to use the framework of neural cellular automata (NCA) to generate optimized patterns from an initial pattern. Optimized here means maximizing the number of robots in the system.\nThe training of the NCA's parameters is done using an unsupervised objective, the troughput of the system for the robot drivers, and simoultaneaously optimizing for the diversity of the solution using quality diversity algorithms.\nIt is shown that the NCA produce regular floor plans for envirnments larger than seen in their training and also perform well under the desired metrics, while being much more efficient to generate than what existing optimizers can achieve.", "questions": "1. Why should a bigger warehouse plan be more difficult to optimize overall? I understand that the complexity of the search space grows, but why is simply tiling good solutions for small environments not mentioned as a (possibly) good baseline? After all, this is how the NCA environments seem to behave (but I might also be missing an obvious problem here).\n2. Isn’t a cool thing about your approach that it possibly also scales to arbitrarily shaped environments? I think it would be interesting to see what happens when the constraints of the warehouse are more intricate, e.g. integrating an old warehouse plan with a new one.\n3. How ‘broken’ are the NCA’s plans typically? Is there a lot of extra work that is done by the extra solver?\n4. Why is it necessary to use quality diversity as an algorithm for warehouse plan optimization? I can imagine how a diversity of environments is interesting in video games, but why should the diversity of the tiling types (which is the entropy measure here) be necessary? I would rather expect a low entropy to be useful, as repeated patterns in the warehouse probably make manufacturing the hall and plans cheaper and less complex.\n5. What was the process of manually designing the human-created solutions?\n6. Does congestion occur only during testing on the 5,000 time steps? If not, how do you handle it during training?\n7. Do you have an idea of how the environment size scale with respect to the maximum number of robots/tasks achievable without congestion? \n\nMinor:\n1. L.14 regularized -> regular (?) … if you truly mean regularized, please explain what is being regularized here.\n2. L.41 sortation -> sorting (?)\n3. L.49 it would be helpful to clarify that your objective is unsupervised and simply comes from the different losees you define.\n4. Overall, an (at least informal) definition of the throughput objective missing in the main text.\n5. L.168 what kind of object is $\\Theta$ and $\\mathbf{\\theta}$?\n6. I think in L.178 it should be “Due to the locality of the NCA operation…” rather than “By using a CNN …” Whatever mechanism you use to implement, the NCA will behave locally as it is its inherent property. The CNN is just an efficient way of implementing it in ML frameworks.", "limitations": "Overall, I think the ideas presented in the paper are interesting and a good work of engineering.\nHowever, to make the paper more relevant and useful to a broad audience, it is missing a more abstract perspective on the interesting techniques it proposes.\nFor this, it should be possible for other researchers to better understand the working principle so that they can estimate how well the techniques could work in different settings. I think this requires more introspection on the results than in the current draft.\nMoreover, to make the claim that the NCAs are ‘arbitrarily scalable’, as in the title, the evaluation is lacking different levels of floor plan scales, NCA time scales and an analysis of the regular patterns obtained from the NCA.\nFor the application to the warehouses, I do not find it very comprehensible that quality diversity plays a big role as emphasized in the paper.\nThese factors are what lead me to my score.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Interesting unsupervised objective for training environments of NCA with a combination of different optimization techniques.\n2. The authors found a way of optimizing patterns from small environments that seems to scale/generalize to larger environments of a similar structure.\n3. I find the evaluation strategy with the RL agent that scales with the NCA interesting and creative. I have not seen jointly scaling agents and environments before and would find this a generally interesting point to investigate independent of this work (although I might not be aware of existing literature on this topic). ", "weaknesses": "1. An ablation or discussion is missing towards what can break the scalability and generalization ability to new settings: What happens for non-rectangular environments? What if the positioning of the stations is not as in the training set? More diverse test samples would strengthen the argument, that NCAs truly scale well. Also, at which size does the NCA start to fail?\n2. I think the setup explored here has big potential for introspecting the solutions. Can one derive the strategy the NCA learned from its produced examples and directly apply it? I.e. find the scalable simple rules that seem to underly the regular patterns generated?\n3. Since quality diversity is a big part of the main draft, it would be interesting to see several examples of generated environments in the main draft.\n4. To me, the design choices of experimenting with NCA and quality diversity objectives for warehouse plan optimization are not clearly justified (see question section). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Why should a bigger warehouse plan be more difficult to optimize overall? I understand that the complexity of the search space grows, but why is simply tiling good solutions for small environments not mentioned as a (possibly) good baseline? After all, this is how the NCA environments seem to behave (but I might also be missing an obvious problem here).\n\n    Please see **More Competitive Baselines** in the general rebuttal.\n\n2. Isn’t a cool thing about your approach that it possibly also scales to arbitrarily shaped environments? I think it would be interesting to see what happens when the constraints of the warehouse are more intricate, e.g. integrating an old warehouse plan with a new one.\n\n    We thank the reviewer for pointing out arbitrarily shaped environments. One naive way of considering non-rectangular shaped environments is encoding the shape of the environments as additional constraints in the MILP solver. We admit in Section 7 that generating environments with irregular shape is one of the future directions of our work.\n\n3. How ‘broken’ are the NCA’s plans typically? Is there a lot of extra work that is done by the extra solver?\n\t\n\tPlease see **Role of MILP** in the general rebuttal.\n\n4. Why is it necessary to use quality diversity as an algorithm for warehouse plan optimization? I can imagine how a diversity of environments is interesting in video games, but why should the diversity of the tiling types (which is the entropy measure here) be necessary? I would rather expect a low entropy to be useful, as repeated patterns in the warehouse probably make manufacturing the hall and plans cheaper and less complex.\n\n    We argue that simultaneously optimizing an objective function and diversifying measure functions with a QD algorithm result in better solutions than merely optimizing an objective function. In Appendix D.3, we compare a popular derivative-free single objective optimization algorithm, CMA-ES, with our chosen QD optimizer, CMA-MAE. Figure 16 and Table 4 shows the scalability of the generated environments and numerical results. While CMA-ES generally matches CMA-MAE in throughput and scalability for environments of size S_train, it significantly lags in scalability for size S_eval. In fact, in the warehouse (even) and the manufacture domains, the MILP solver fails to find valid solutions in size of S_eval with the given computational budget specified in Appendix D.4.\n\n5. What was the process of manually designing the human-created solutions?\n\n    For the warehouse domains, we take the commonly human-designed environments from previous works [28, 29, 47], which 1 x 10 blocks of shelves are repeated placed. We scale this pattern to create human-designed environments of size S_eval.\n\n    For the manufacture domain, we create the human-designed environments of size S_train by taking design insights from the optimal NCA-generated warehouse environment (shown in figure 7f) and maintaining similar number of workstations with the DSAGE optimized environment. With size of S_eval, we take design insights from the NCA generated manufacture environment of the same size (shown in figure 10b) to create the human-designed environment.\n\n    We describe the detailed process of creating human-designed environments in appendix C.4.\n\n6. Does congestion occur only during testing on the 5,000 time steps? If not, how do you handle it during training?\n\n    During training, we run 5 simulations with 1000 timesteps for each environment. Following previous work (cited in line 482), we stop the simulation early in case of congestion and return the current throughput as the result. This is because (1) we penalize the environments that run into congestion, and (2) we empirically observe that the number of finished tasks per timestep will quickly drop after congestion occurs, resulting in low throughput.\n\n\n7. Do you have an idea of how the environment size scale with respect to the maximum number of robots/tasks achievable without congestion?\n\n\tPlease see **Scalability in More Environment Sizes** in the general rebuttal.\n"}]

Author rebuttal:
We thank all reviewers for the detailed feedback. We appreciate that the reviewers find the combination of NCA, QD, and MILP novel and interesting (Reviewer YTho, v7gi) and the results comprehensive and promising (Reviewer fmHH).

## Role of MILP
Q3 of reviewer v7gi and Q3 of ShTu

The role of MILP varies by the domains. To clarify it, we show the unrepaired and repaired environments of size S_train in Figure 1 in the rebuttal as well as Figure 8e and 8f in Appendix C.3. In the warehouse (even) domain, its role is minimal, merely enforcing constraints due to slight disparities between unrepaired and repaired environments. Conversely, in the warehouse (uneven) and manufacture domains, MILP plays a role in pattern creation in addition to constraint enforcement. For example, shown in Figure 1c, the NCA generator for the warehouse (uneven) domain generates more endpoints (blue) on the left and more storage shelves (black) on the right. This facilitates the MILP in repairing the environment such that the left part has less obstacles (storage shelves), enabling agents to more efficiently access the frequently visited left-border workstations.

For S_train environments, MILP takes up to 1 minute, while for larger S_eval sizes, it's up to 8 hours. This longer duration is a one-time event after training NCA generators. Our method reduces the overhead of frequent large environment repairs when optimizing with size S_eval.

## Scalability in More Environment Sizes
Q7 of reviewer ShTu

To further demonstrate our method’s scalability, we use the trained NCA generators from Section 6 to generate progressively larger environments and run simulations. Figure 2 in the rebuttal shows the result. The y-axis illustrates two metrics: maximum mean throughput over 50 simulations (right) and the maximum scalability, defined as the agent count at this maximum (left).

We see an increasing trend for both maximum scalability and maximum mean throughput as the environment size increases since more space will be available for the agents to move. Layouts generated by our algorithm generally scale better than the human-designed warehouse layouts.

We see two exceptions: Maximum mean throughput in the 69x69 warehouse (uneven) environment and both metrics in the 57x58 manufacture environment. We can attribute this to the interaction between the MILP and the specific environment generated by the NCA. Since MILP makes numerous changes to the generated environment in these domains (e.g. Fig. 1c and 1d in the rebuttal), it is possible that certain combinations of generated environments and MILP random seeds can lead to repaired layouts that create congestion. However, if we encounter such issues in practice, it is possible to either leverage a different NCA generator from the archive or re-run the MILP repair with a different random seed.

## More Competitive Baselines
Q3 of reviewer YTho, Q1 of ShTu, and concerns regarding baseline from reviewers 6eLV and v7gi

Multiple reviewers (YTho, 6eLV, v7gi) suggested adding more baseline methods. We chose two representative baselines in our work: DSAGE [47] (a state-of-the-art technique for multi-agent environment optimization) and human-designed environments. Previous environment generation techniques often have the same searched and generated environment sizes, likely facing computational challenges similar to DSAGE. We thank reviewer v7gi for pointing out the Compositional Pattern Producing Network (CPPN) as another baseline. Yet, CPPN, mainly adept at generalizing global patterns, isn't well-suited for our use cases, which focus on local patterns to alleviate robot congestion.

### Tiling Environment Baseline
Suggested by reviewer v7gi and ShTu, we add a new baseline. We tile the environments of S_train shown in Appendix C.3, Figure 7f (warehouse (even)), 7i (warehouse (uneven), and 8d (manufacture), to create the large S_eval environments. We then use MILP to enforce constraints. 

We run 50 simulations with N_a_eval agents specified in table 1 of the paper. The new baseline failed in the warehouse (even) domain and achieved only a 23% success rate in the warehouse (uneven) domain. Figure 3 in the rebuttal displays the S_eval-sized tiled environments and tile-usage maps, which show the frequency of each tile used in the simulation. As shown in Figure 3b and 3d, the agents are congested, resulting in low success rates. In contrast, for the manufacture domain, the baseline matches our method, with a 100% success rate and 22.73 average throughput. This success is attributed to Figure 8d's tiling resembling NCA-generated patterns in Figure 10b. Thus, the tiling baseline may be a good method for the manufacture domain, yet it falls short in the warehouse domains.

## Generalizing to Other Domains and Real-World Scenarios
Q4, 5, 8, 10 of reviewer YTho, and Q2 of v7gi

Large companies such as Amazon and Alibaba have deployed multi-robot systems in warehouses to transport packages or inventory pods. Therefore, one real world application of our method is optimizing the layout of the automated warehouses to improve throughput. Since our method is agnostic to the specific agent simulator and only requires metrics such as throughput post-simulation, we can plug-in different simulators and apply our environment generation algorithm. We selected our simulator because similar ones are used in the prior works [28, 47].

Nevertheless, the potential obstacles of applying our method to the real-world physical scenarios are sim-to-real gaps and availability of a realistic and efficient simulator. Similar to prior works [27, 28, 29, 47], we make simplifications in our agent-based simulators such as perfect robot motion dynamics and deterministic environment dynamics. We are excited about integrating our idea of scalable environment generation via NCAs with physical robots and warehouse simulators in the future.

We will include all the above discussions in the appendix of the revised paper.

Meta-review: This paper proposes to optimize Neural Cellular Automata (NCA) environment generators via QD algorithms to generate arbitrarily large environments to improve the throughput of multi-robot systems. All the reviewers agreed that the paper aimed to solve an important problem, and the solution is interesting and original. The reviewers also raised concerns about the quality of writing, overclaims of scalability, simple evaluations, and choice of baselines. The authors' rebuttal has sufficiently addressed most of these concerns. During discussion, most of the reviewers voted for acceptance. Please incorporate your response in rebuttals and reviewer's suggestions, especially around "scalability" into the final version of this paper.
Decision: Accept (poster)