Abstract
Existing work on programmable self-assembly has focused on deterministic performance guarantees-stability of desirable states. In particular, for any acyclic target graph a binary rule set can be synthesized such that the target graph is the uniquely stable assembly. If the number of agents is finite, communication and consensus algorithms are necessary for the dynamic process induced by the rule set to converge to a state with a maximum number of target assemblies. We suggest a self-assembly problem constrained so that communication can only occur between a pair of agents participating in a formation or severance event. We propose a stochastic decision policy for the agents that provides a performance guarantee in the form of stochastic stability for any finite number of agents and any acyclic target graph. In particular, the process will have a yield of desirable assemblies approaching 100 percent of the maximum as the number of agents increases. This is accomplished with a probability that can be made arbitrarily close to one. This result is established analytically and demonstrated via simulation. We argue that probabilistic performance criteria such as stochastic stability are relevant to the self-assembly problem. This approach allows for the analysis of robustness in the presence of uncertain disturbances to agent behavior. Another feature of probabilistic performance guarantees is the ability to model reversible processes. We also suggest how the presented process can be augmented with communications to provide stability.