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.}
}