Communication, convergence, and stochastic stability in self-assembly

Michael J. Fox, Jeff S. Shamma

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

14 Scopus citations


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.

Original languageEnglish (US)
Title of host publication2010 49th IEEE Conference on Decision and Control, CDC 2010
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Print)9781424477456
StatePublished - 2010
Externally publishedYes
Event49th IEEE Conference on Decision and Control, CDC 2010 - Atlanta, United States
Duration: Dec 15 2010Dec 17 2010

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370


Conference49th IEEE Conference on Decision and Control, CDC 2010
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'Communication, convergence, and stochastic stability in self-assembly'. Together they form a unique fingerprint.

Cite this