# Robotics: Science and Systems VI

### A Molecular Algorithm for Path Self-Assembly in 3 Dimensions

*R. Schulman and B. Yurke*

**Abstract:**

A molecular algorithm is a set of molecular interactions
that carry out a particular task. We describe a molecular
algorithm for self-assembling a path between two stationary
points when the locations of these points are not known in
advance. While efficient path finding algorithms for electronic
robots exist, molecules lack the centralized memory or computing
power to implement them. The algorithm takes advantage of
the inherent physics at the molecular scale, and unlike other
biomimetic algorithms for path finding, is designed to work
in an unstructured environment and does not require complex
molecular components. Designed molecules self-assemble a DNA
nanotube starting from a “seed” molecule attached to the start
point. During growth, the DNA nanotube’s end diffuses through
space, and this diffusion is harnessed as a search process: when
the DNA nanotube’s end contacts the destination, it attaches to
it and stops growing, forming a stable path.

We use simulations and analysis to predict that paths of up
10 microns are formed with more than 99% probability if the
destination is larger than 500 nanometers in diameter, making it
practical. However, the probability of the DNA nanotube missing
the destination is highly dependent on destination distance and
size. It increases as exp[-1/Ω(r³)], where r is the Euclidean
distance from the start point to the destination, and scales
approximately as exp[-Ω(d)], where d is the diameter of the
destination. A path finding algorithm that could work over
longer distances or with small destinations will likely require
new molecular components; we describe how new components
could be used to solve the molecular path finding problem using
a divide and conquer approach.

**Bibtex:**

@INPROCEEDINGS{ Schulman-RSS-10, AUTHOR = {R. Schulman AND B. Yurke}, TITLE = {A Molecular Algorithm for Path Self-Assembly in 3 Dimensions}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2010}, ADDRESS = {Zaragoza, Spain}, MONTH = {June}, DOI = {10.15607/RSS.2010.VI.040} }