This dissertation is an examination of collective systems of computationally limited agents that require coordination to achieve complex ensemble behaviors or goals. The design of coordination strategies can be framed as multiagent optimization problems, which are addressed in this work from both theoretical and practical perspectives. The primary foci of this study are models where computation is distributed over the agents themselves, which are assumed to possess onboard computational capabilities. There exist many assumption variants for distributed models, including fairness and concurrency properties. In general, there is a fundamental trade-off whereby weakening model assumptions increases the applicability of proposed solutions, while also increasing the difficulty of proving theoretical guarantees. This dissertation aims to produce a deeper understanding of this trade-off with respect to multiagent optimization and scalability in distributed settings. This study considers four multiagent optimization problems. The model assumptions begin with fully centralized computation for the all-or-nothing multicommodity flow problem, then progress to synchronous distributed models through examination of the unmapped multivehicle routing problem and the distributed target localization problem. The final model is again distributed but assumes an unfair asynchronous adversary in the context of the energy distribution problem for programmable matter. For these problems, a variety of algorithms are presented, each of which is grounded in a theoretical foundation that permits formal guarantees regarding correctness, running time, and other critical properties. These guarantees are then validated with in silico simulations and (in some cases) physical experiments, demonstrating empirically that they may carry over to the real world. Hence, this dissertation bridges a portion of the predictability-practicality gap with respect to multiagent optimization problems.

The world is filled with systems of entities that collaborate in motion, both natural and engineered. These cooperative distributed systems are capable of sophisticated emergent behavior arising from the comparatively simple interactions of their members. A model system for emergent collective behavior is programmable matter, a physical substance capable of autonomously changing its properties in response to user input or environmental stimuli. This dissertation studies distributed and stochastic algorithms that control the local behaviors of individual modules of programmable matter to induce complex collective behavior at the macroscale. It consists of four parts. In the first, the canonical amoebot model of programmable matter is proposed. A key goal of this model is to bring algorithmic theory closer to the physical realities of programmable matter hardware, especially with respect to concurrency and energy distribution. Two protocols are presented that together extend sequential, energy-agnostic algorithms to the more realistic concurrent, energy-constrained setting without sacrificing correctness, assuming the original algorithms satisfy certain conventions. In the second part, stateful distributed algorithms using amoebot memory and communication are presented for leader election, object coating, convex hull formation, and hexagon formation. The first three algorithms are proven to have linear runtimes when assuming a simplified sequential setting. The final algorithm for hexagon formation is instead proven to be correct under unfair asynchronous adversarial activation, the most general of all adversarial activation models. In the third part, distributed algorithms are combined with ideas from statistical physics and Markov chain design to replace algorithm reliance on memory and communication with biased random decisions, gaining inherent self-stabilizing and fault-tolerant properties. Using this stochastic approach, algorithms for compression, shortcut bridging, and separation are designed and analyzed. Finally, a two-pronged approach to "programming" physical ensembles is presented. This approach leverages the physics of local interactions to pair theoretical abstractions of self-organizing particle systems with experimental robot systems of active granular matter that intentionally lack digital computation and communication. By physically embodying the salient features of an algorithm in robot design, the algorithm's theoretical analysis can predict the robot ensemble's behavior. This approach is applied to phototaxing, aggregation, dispersion, and object transport.