Phase transition in a swarm algorithm for self-organized construction

This paper reports on a system where very simple, noncommunicating mobile agents in a cellular (lattice) environment use purely local rules to construct connected structures from initially randomly distributed building blocks. We study the effect of block density on the final structure, demonstrating a percolationlike phase transition: Low block densities lead to the formation of small, disconnected structures but a single connected structure emerges abruptly beyond a critical density. The empirical study of the structure at the transition point shows scaling behavior, providing strong evidence for criticality. We also demonstrate that a simple change of rules can completely change the phase-transition effect. The results have implications for the self-organized construction of complex structures by swarms. © 2003 The American Physical Society.