EMBODIED COMPUTATION
Abstract
The traditional computational devices and models, such as the von Neumann architecture or the Turing machine, are strongly influenced by concepts of central control and perfection. The standard models of computation seem to cover the reality of computation only partially and lack, in particular, in the ability to describe more natural forms of computation. In this paper we propose the concept of embodied computation, a straight forward advancement of well known concepts such as amorphous computing, emergent phenomena and embodied cognitive science. Many embodied microscopic computational devices form a single macroscopic device of embodied computation. The solution to computational problems emerges from a huge amount of local interactions. The system's memory is the sum of the positional information and possibly of the internal states. Such systems are very robust and allow different methodologies to analyze computation. To back this theoretic concept some results based on simulations are given and potential benefits of this approach are discussed.
References
- Communications of the ACM 43(5), 74 (2000), DOI: 10.1145/332833.332842. Crossref, Google Scholar
-
D. H. Ballard , An Introduction to Natural Computation ( MIT Press , 1999 ) . Crossref, Google Scholar G. Beni , From swarm intelligence to swarm robotics, Proc. of the SAB 2004 Workshop on Swarm Robotics,Lecture Notes in Computer Science , eds.E. Sahin and W. Spears (2004) pp. 1–9. Google Scholar-
E. Bonabeau , M. Dorigo and G. Theraulaz , Swarm Intelligence: From Natural to Artificial Systems ( Oxford Univ. Press , 1999 ) . Crossref, Google Scholar M. Chlebík and J. Chlebíková , Approximation hardness of the steiner tree problem on graphs, Proc. 8th Scandinavian Workshop on Algorithm Theory (SWAT),LNCS 2368 (Springer-Verlag, 2002) pp. 170–179. Google Scholar-
B. Collier and J. MacLachlan , Charles Babbage: And the Engines of Perfection ( Oxford University Press , 1998 ) . Google Scholar - Pyhsica D 75(1–3), 11 (1994), DOI: 10.1016/0167-2789(94)90273-9. Crossref, ISI, Google Scholar
- Proceedings of the National Academy of Sciences 92, 10742 (1995), DOI: 10.1073/pnas.92.23.10742. Crossref, ISI, Google Scholar
-
R. P. Feynman , Feynman Lectures on Computation ( Perseus Books Group , Cambridge, MA, USA , 2000 ) . Google Scholar - Physica D 45, 254 (1990), DOI: 10.1016/0167-2789(90)90186-S. Crossref, ISI, Google Scholar
- Discrete and Computational Geometry 25(1), 1 (2001). Crossref, ISI, Google Scholar
-
H. Hamann and H. Wörn , A space- and time-continuous model of self-organizing robot swarms for design support , First IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO'07) ( 2007 ) . Google Scholar - Nature 407, 487 (2000), DOI: 10.1038/35035023. Crossref, ISI, Google Scholar
-
J. H. Holland , Adaptation in Natural and Artificial Systems ( MIT Press , Cambridge, MA, USA , 1992 ) . Crossref, Google Scholar -
F. Hwang , D. Richards and P. Winter , The Steiner Tree Problem ( North-Holland , 1992 ) . Google Scholar -
F. Iida , Cheap design approach to adaptive behavior: Walking and sensing through body dynamics , Intern. Symposium on Adaptive Motion of Animals and Machines ( 2005 ) . Google Scholar - Vistas in Astronomy 28(1), 347 (1985), DOI: 10.1016/0083-6656(85)90046-7. Crossref, ISI, Google Scholar
C. Langton , Computation at the edge of chaos: phase transitions and emergent computation, Proceedings of the ninth annual international conference of the Center for Nonlinear Studies on Self-organizing, Collective, and Cooperative Phenomena in Natural and Artificial Computing Networks (1990) pp. 12–37. Google Scholar-
Y. Litus , P. Zebrowski and R. Vaughan , Energy-eficient multi-robot rendezvous: Parallel solutions by embodied approximation , Workshop on Algorithmic equivalencies between biological and robotic swarms ( 2007 ) . Google Scholar - M. Mitchell. Self-awareness and control in decentralized systems. In Working Papers of the AAAI 2005 Spring Symposium on Metacognition in Computation. AAAI Press, 2005 . Google Scholar
- Artificial Intelligence 170(18), 1194 (2006), DOI: 10.1016/j.artint.2006.10.002. Crossref, ISI, Google Scholar
- Complex Systems 7(2), 89 (1993). Google Scholar
- , Dynamic Patterns in Complex Systems, eds.
J. A. S. Kelso , A. J. Mandell and M. F. Shlesinger (World Scientific, 1988) pp. 293–301. Google Scholar - Proceedings of the National Academy of Science 101(4), 918 (2004), DOI: 10.1073/pnas.0307811100. Crossref, ISI, Google Scholar
-
R. Pfeifer and J. C. Bongard , How the body shapes the way we think - A new view of intelligence ( MIT Press , 2006 ) . Crossref, Google Scholar G. Robins and A. Zelikovsky , Improved steiner tree approximation in graphs, Proc. of the 11th ACM-SIAM Symposium on Discrete Algorithms (2000) pp. 770–779. Google Scholar-
W. Roush , Technology Review ( 2006 ) . Google Scholar -
T. Schmickl , C. Möslinger and K. Crailsheim , Collective perception in a robot swarm , Proceedings of the Second Swarm Robotics Workshop ,LNCS 4433 , eds.E. Sahin , W. M. Spears and A. F. T. Winfield ( 2007 ) . Google Scholar -
F. Schweitzer , Brownian Agents and Active Particles. On the Emergence of Complex Behavior in the Natural and Social Sciences ( Springer-Verlag , 2003 ) . Google Scholar J. Seyfried , The ISWARM project: Intelligent small world autonomous robots for micro-manipulation, Swarm Robotics Workshop: State-of-the-art Survey, eds.E. Şahin and W. Spears (Springer-Verlag, 2005) pp. 70–83. Google Scholar-
G. J. Sussman , Designing for applications unanticipated by the designer , First IEEE International Conference on Self-Adaptive and Self-Organizing Systems ( 2007 ) . Google Scholar - Phys. Rev. Lett. 19, 1400 (1981). Google Scholar
- Phys. Rev. Lett. 54, 735 (1985), DOI: 10.1103/PhysRevLett.54.735. Crossref, ISI, Google Scholar
-
S. Wolfram , A New Kind of Science ( Wolfram Media , 2002 ) . Google Scholar - WordNet 3.0, Princeton University, 2007. http://wordnet.princeton.edu/perl/webwn?s=computation . Google Scholar
-
K. Zuse , Rechnender Raum ( Friedrich Vieweg u. Sohn ) . Google Scholar


