A theory of local-to-global algorithms for one-dimensional spatial multi-agent systems

A spatial multi-agent system is a decentralized system composed of numerous identically programmed agents that either form or are embedded in a geometric space. The agents' computational constraints are spatially local. Each agent has limited internal memory and processing power, and communicates only with neighboring agents. The systems' computational goals, however, are typically defined relative to the global spatial structure. In this thesis, I develop the beginnings of theory of spatial multi-agent systems, for the simple case of pattern formation in a one-dimensional discrete model. First, I characterize those patterns that are robustly self-organizable in terms of a simple "necessary condition on solvability". I then solve the inverse problem, constructing an algorithmic procedure that generates robust local rule solutions to any desired solvable pattern. Next, I analyze resource usage and runtime properties of such local rule solutions. I apply this suite of mathematical techniques to two diverse "global-to-local" problems: the engineering goal of developing a generic "global-to-local" compilation procedure, and the scientific goal of analyzing an embryological development process.