| This thesis describes a model for planar distributed assembly, in which unit-square assembly components move randomly and independently on a two-dimensional grid, binding together to form a desired target structure. The components are simple reactive agents, with limited capabilities including short-range sensing and rule-based control only, and operate in an entirely decentralized manner.;Using the model, we investigate two primary issues, coordination and sensing, from an algorithmic perspective. Our goal is to determine how a group of components can be reliably programmed to produce a global result (structure) from purely local interactions. Towards this end, we define the local spatiotemporal ordering constraints that must be satisfied for assembly to progress in a coordinated manner, and give a procedure for encoding these constraints in a rule set. When executed by the components, this rule set is guaranteed to produce the target structure, despite the random actions of group members. We then introduce an optimization algorithm which is able to significantly reduce the number of distinct environmental states that components must recognize in order to assemble into a structure. Experiments show that our optimization algorithm outperforms existing approaches. |
