Intelligent Self-Assembly from Communicative Mobile Components
University of Southern California - Laboratory for Molecular Robotics,
Los Angeles, CA 90089-0781 USA
This is an abstract
for a presentation given at the
11th
Foresight Conference on Molecular Nanotechnology
This paper presents a methodology by which autonomous but very limited agents may be programmed to self-assemble into asymmetric non-repeating structures. Message propogation is used to guide the choices made by members of the swarm, resulting in much simpler onboard logic than would otherwise be needed to produce the same result.
 The agents are assumed to have the following capabilities:
- attaching to other agents that they are touching
- roughly periodic state changes
- very low bandwidth communication with other agents that they are touching
- execution of nondeterministict finite state machines
- detection of relevant environmental properties
- motion relative to other agents that they are touching
This methodology is of interest due to the low computational requirements needed to implement useful behavior in the agents. Each agent is controlled by a nondeterministic finite state machine. The memory requirements vary with the task, but tend to be low. We have demonstrated the construction of a path between two points through an obstructed area using only four bits of state memory and approximately 500 bits of read-only memory per agent.
We believe that this method will be of particular utility in programming swarms of nanorobots. The use of message propogation to guide state changes results in a dramatically smaller state table than would be generated by straight Intelligent Self-Assembly[1], which ought to translate to greater ease of manufacture in in a nanorobot swarm.
This work differs from [1] in two major ways, aside from the smaller state table. First, the agents are assumed to be mobile relative to other agents with which they are in contact. This means that once an agent has drifted into contact with an under-construction object, it can move to some place where it is needed before joining the formation, which means that the final structure is generated either more quickly than [1], or alternatively that the concentration of agents can be lower. Second, message propogation allows the contruction of structures that are only partially defined. For example, our path-finding algorithm could not be written using [1], because the locations of the beginning and end of the path are variable. Message propogation allows a more flexible definition of the desired final state.
The accompanying image is a path generated between the two squares using this method. The rectangle in the middle is an obstacle through which the agents can not pass.
References
[1] Chris Jones, Maja J. Mataric, ``From Local to Global Behavior in
Intelligent Self-Assembly'', submitted to the IEEE Conference on
Robotics and Automation 2003
*Corresponding Address:
Daniel J. Arbuckle
Computer Science Department
University of Southern California - Laboratory for Molecular Robotics
Los Angeles, CA 90089-0781 USA
Phone: (213) 740-4502 Fax: (213) 740-7512
Email: [email protected]
Web: http://lipari.usc.edu/~lmr/
|