  We study the power of uncontrolled random molecular movement in the nubot
model of self-assembly. The nubot model is an asynchronous nondeterministic
cellular automaton augmented with rigid-body movement rules (push/pull,
deterministically and programmatically applied to specific monomers) and random
agitations (nondeterministically applied to every monomer and direction with
equal probability all of the time). Previous work on the nubot model showed how
to build simple shapes such as lines and squares quickly---in expected time
that is merely logarithmic of their size. These results crucially make use of
the programmable rigid-body movement rule: the ability for a single monomer to
control the movement of a large objects quickly, and only at a time and place
of the programmers' choosing. However, in engineered molecular systems,
molecular motion is largely uncontrolled and fundamentally random. This raises
the question of whether similar results can be achieved in a more restrictive,
and perhaps easier to justify, model where uncontrolled random movements, or
agitations, are happening throughout the self-assembly process and are the only
form of rigid-body movement. We show that this is indeed the case: we give a
polylogarithmic expected time construction for squares using agitation, and a
sublinear expected time construction to build a line. Such results are
impossible in an agitation-free (and movement-free) setting and thus show the
benefits of exploiting uncontrolled random movement.
