Connecting the dots: Molecular machinery for distributed robotics
by Yuriy Brun, Dustin Reishus
Abstract:
Nature is considered one promising area to search for inspiration in designing robotic systems. Some work in swarm robotics has tried to build systems that resemble distributed biological systems and inherit biology's fault tolerance, scalability, dependability, and robustness. Such systems, as well as ones in the areas of active self-assembly and amorphous computing, typically use relatively simple components with limited computation, memory, and computational power to accomplish complex tasks such as forming paths in the presence of obstacles. We demonstrate that such tasks can be accomplished in the well-studied tile assembly model, a model of molecular self-assembly that is strictly simpler than other biologically-inspired models. Our systems use a small number of distinct components to find minimal-length paths in time linear in the length of the path while inheriting scalability and fault tolerance of the underlying natural process of self-assembly.
Citation:
Yuriy Brun and Dustin Reishus, Connecting the dots: Molecular machinery for distributed robotics, Lecture Notes on Computer Science, vol. 5347/2009, 2009, pp. 102–111.
Related:
Extended and revised in "Path finding in the tile assembly model" in Theoretical Computer Science. A previous version appeared in the Proceedings of the 14th International Meeting on DNA Computing, pp. 27–35, 2008.
Bibtex:
@article{Brun09dna-lncs,
  author = {Yuriy Brun and Dustin Reishus},
  title =
  {\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun09dna-lncs.pdf}{Connecting
  the dots: Molecular machinery for distributed robotics}},
  journal = {Lecture Notes on Computer Science},
  booktitle = {{DNA} Computing},
  venue = {DNA},
  volume = {5347/2009},
  pages = {102--111},
  year = {2009},
  doi = {10.1007/978-3-642-03076-5_9},

  note = {Extended and revised in~\cite{}{Brun09path-finding}. A
  previous version appeared in the Proceedings of the 14th International
  Meeting on {DNA} Computing (DNA), pages 27--35, 2008.
  \href{http://dx.doi.org/10.1007/978-3-642-03076-5\_9}{DOI:
  10.1007/978-3-642-03076-5\_9}},

  previous = {Extended and revised in "Path finding in the tile assembly model"
  in Theoretical Computer Science. A previous version appeared in the
  Proceedings of the 14th International Meeting on DNA Computing, pp.
  27–35, 2008.},

  abstract = {Nature is considered one promising area to search for inspiration
  in designing robotic systems. Some work in swarm robotics has tried to build
  systems that resemble distributed biological systems and inherit biology's
  fault tolerance, scalability, dependability, and robustness. Such systems, as
  well as ones in the areas of active self-assembly and amorphous computing,
  typically use relatively simple components with limited computation, memory,
  and computational power to accomplish complex tasks such as forming paths in
  the presence of obstacles. We demonstrate that such tasks can be accomplished
  in the well-studied tile assembly model, a model of molecular self-assembly
  that is strictly simpler than other biologically-inspired models. Our systems
  use a small number of distinct components to find minimal-length paths in time
  linear in the length of the path while inheriting scalability and fault
  tolerance of the underlying natural process of self-assembly.},
}