Path finding in the tile assembly model
by Yuriy Brun, Dustin Reishus
Abstract:
Swarm robotics, active self-assembly, and amorphous computing are fields that focus on designing systems of large numbers of small, simple components that can cooperate to complete complex tasks. Many of these systems are inspired by biological systems, and all attempt to use the simplest components and environments possible, while still being capable of achieving their goals. The canonical problems for such biologically-inspired systems are shape assembly and path finding. In this paper, we demonstrate path finding in the well-studied tile assembly model, a model of molecular self-assembly that is strictly simpler than other biologically-inspired models. As in related work, our systems function in the presence of obstacles and can be made fault-tolerant. The path-finding systems use $\Theta(1)$ distinct components and find minimal-length paths in time linear in the length of the path.
Citation:
Yuriy Brun and Dustin Reishus, Path finding in the tile assembly model, Theoretical Computer Science, vol. 410, no. 15, April 2009, pp. 1461–1472.
Related:
Extended and revised version of "Connecting the dots: Molecular machinery for distributed robotics" in DNA Computing 2009. A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2008-802
Bibtex:
@article{Brun09path-finding,
  author = {Yuriy Brun and Dustin Reishus},
  title =
  {\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun09path-finding.pdf}{Path
  finding in the tile assembly model}},
  journal = {Theoretical Computer Science},
  venue = {TCS},
  volume = {410},
  number = {15},
  pages = {1461--1472},
  month = {April},
  date = {1},
  year = {2009},
  issn = {0304-3975},
  doi = {10.1016/j.tcs.2008.12.008},
  publisher = {Elsevier},
  address = {Essex, {UK}},

  note = {Extended and revised version of~\ref{Brun09dna-lncs}. A
  previous version appeared as University of Southern California, Center for
  Software Engineering technical report USC-CSSE-2008-802.
  \href{https://doi.org/10.1016/j.tcs.2008.12.008}{DOI:
  10.1016/j.tcs.2008.12.008}},

  previous = {Extended and revised version of "Connecting the dots: Molecular
  machinery for distributed robotics" in DNA Computing 2009. A previous version
  appeared as University of Southern California, Center for Software Engineering
  technical report USC-CSSE-2008-802},

  abstract = {Swarm robotics, active self-assembly, and amorphous computing are
  fields that focus on designing systems of large numbers of small, simple
  components that can cooperate to complete complex tasks. Many of these systems
  are inspired by biological systems, and all attempt to use the simplest
  components and environments possible, while still being capable of achieving
  their goals. The canonical problems for such biologically-inspired systems are
  shape assembly and path finding. In this paper, we demonstrate path finding in
  the well-studied tile assembly model, a model of molecular self-assembly that
  is strictly simpler than other biologically-inspired models. As in related
  work, our systems function in the presence of obstacles and can be made
  fault-tolerant. The path-finding systems use $\Theta(1)$ distinct components
  and find minimal-length paths in time linear in the length of the path.}
}