×

Computational ability of cells based on cell dynamics and adaptability. (English) Zbl 1192.68653

Summary: Learning how biological systems solve problems could help to design new methods of computation. Information processing in simple cellular organisms is interesting, as they have survived for almost 1 billion years using a simple system of information processing. Here we discuss a well-studied model system: the large amoeboid Physarum plasmodium. This amoeba can find approximate solutions for combinatorial optimization problems, such as solving a maze or a shortest network problem. In this report, we describe problem solving by the amoeba, and the computational methods that can be extracted from biological behaviors. The algorithm designed based on \(Physarum\) is both simple and useful.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Nakagaki, T., Yamada, H. and Tóth, A., ”Maze-solving by an amoeboid organism,” Nature 407, pp. 470, 2000.
[2] Nakagaki, T., Yamada, H. and Tóth, A., ”Path finding by tube morphogenesis in an amoeboid organism,” Biophys. Chem. 92, pp. 47–52, 2001 · doi:10.1016/S0301-4622(01)00179-X
[3] Aono, M., and Gunji, Y-P., ”Beyond input-output computings: Error-driven emergence with parallel non-distributed slime mold computer,” BioSystems, 71, pp. 257–287, 2003 · doi:10.1016/S0303-2647(03)00085-6
[4] Tsuda, S., Zauner, K. P. and Gunji, Y-P., ”Robot Control with Biological Cells,” in Proc. IPCAT, pp. 202–216, 2005.
[5] Aono, M. and Hara, M., ”Dynamic Transition among Memories on Neurocomputer Composed of Amoeboid Cell with Optical Feedback,” in Proc.NOLTA 2006, Bologna, Italy, pp. 763–766, 2006.
[6] Aono, M. and Hara, M., ”Amoeba-based Nonequilibrium Neurocomputer Utilizing Fluctuations and Instability,” in UC 2007, LNCS 4618(Aki, S.G., et al. eds.), pp. 41–54, Springer-Verlag, Berlin, 2007. · Zbl 1175.68155
[7] Aono, M., Hara, M. and Aihara, K., ”Amoeba-based Neurocomputing with Chaotic Dynamics,” Comm. ACM, 50(9), pp. 69–72, 2007 · Zbl 05394836 · doi:10.1145/1284621.1284651
[8] Adamatzky, A., ”Physarum machine: implementation of a Kolmogorov-Uspensky machine on a biological substrate,” Parallel Processing Letters, 2007.
[9] Shirakawa, T. and Gunji, Y. -P., ”Emergence of morphological order in the network formation of Physarum polycephalum,” Biophys. Chem., 128, pp. 253-260, 2007 · doi:10.1016/j.bpc.2007.04.010
[10] Aono, M. and Hara, M., ”Spontaneous deadlock breaking on amoeba-based neurocomputer,” BioSystems, 91, pp. 83–93, 2008 · doi:10.1016/j.biosystems.2007.08.004
[11] Special issue on Physarum Computing in Int. J. Unconventional Computing, 2008.
[12] Kamiya, N., ”Protoplasmic streaming”, in Protoplasmatologia, (L.V. Heilbrunn ed.), 8, Springer, 1959.
[13] Kessler, D., ”Plasmodial structure and motility,” in Cell biology of Physarum and Didymium (Aldrich, H.C. and Daniel, J.W., eds.), pp. 145–196, Academic Press, New York, 1982.
[14] Nakagaki, T., ”Smart behavior of true slime mold in labyrinth,” Res. Microbiol. 152, pp. 767–770, 2001 · doi:10.1016/S0923-2508(01)01259-1
[15] Narby, J., Intelligence In Nature -An Inquiry Into Knowledge-, pp. 95–121, Penguin Group Inc., New York, 2005
[16] Steinbock, O., Tóth, Á., and Showalter, K., ”Navigating complex labyrinths: Optimal paths from chemical waves,” Science 267, pp. 868–871, 1995 · doi:10.1126/science.267.5199.868
[17] Nakagaki, T., Yamada, H. and Ueda, T., ”Interaction between cell shape and contraction pattern,” Biophys. Chem. 84, pp. 195–204, 2000 · doi:10.1016/S0301-4622(00)00108-3
[18] Nakagaki, T. and Guy, R., ”Intelligent behaviors of amoeboid movement based on complex dynamics of soft matter,” Soft Matter, 4, pp. 1–2, 2008 · doi:10.1039/b706317m
[19] Tero, A., Kobayashi, R. and Nakagaki, T., ”Mathematical model for adaptive transport network in path finding by true slime mold,” J. Theor. Biol. 244,pp. 553–564, 2007 · doi:10.1016/j.jtbi.2006.07.015
[20] Miyaji T., Ohnishi I., ”Mathematical analysis to an adaptive network of the Plasmodium system,” Hokkaido Mathematical Journal, 36, pp. 445–465, 2007 · Zbl 1136.34045
[21] Miyaji, T., Ohnishi, I., ”Physarum can solve the shortest path decision problem mathematically rigorously,” International Journal of Pure and Applied Mathematics, in press. · Zbl 1235.92004
[22] Miyaji, T., Ohnishi, I., Tero, A., and Nakagaki, T., ”Failure to the shortest path decision of an adaptive transport network with double edges in Plasmodium system,” Int. J. of Dynamical Systems and Differential Equations,” in press. · Zbl 1159.34328
[23] Tero, A., Kobayashi, R. and Nakagaki, T., ”Physarum solver -A biologically inspired method for road-network navigation-,” Physica A363, pp. 115, 2006.
[24] Nakagaki, T., Iima, M., Ueda, T., Nishiura, Y., Saigusa, T., Tero, A., Kobayashi, R., and Showalter, K., ”Minimum-risk path finding by an adaptive amoebal network,” Phys. Rev. Lett., 99, 068104.
[25] Nakagaki, T., Yamada, H. and Hara, M., ”Smart network solutions in an amoeboid organism,” Biophys. Chem. 107, pp. 1–5, 2004 · doi:10.1016/S0301-4622(03)00189-3
[26] Nakagaki, T., Kobayashi, R., Nishiura, Y. and Ueda, T., ”Obtaining multiple separate food sources: Behavioural intelligence in the Physarum plasmodium,” in Proc. R. Soc. Lond. B 271, pp. 2305–2310, 2004 · doi:10.1098/rspb.2004.2856
[27] Tero, A., Yumiki, K., Kobayashi, R., Saigusa, T., Nakagaki, T., ”Flow-network adaptation in Physarum amoebae,” Theory in Biosciences, 127, pp. 89–94, 2008 · doi:10.1007/s12064-008-0037-9
[28] Tero, A., Nakagaki, T., Toyabe, K., Yumiki, K. and Kobayashi, R., ”A method inspired by Physarum for solving the Steiner problem,”Int. Journ. of Unconventional Computing, in press, (2008).
[29] Nakagaki, T., Saigusa, T., Tero, A., and Kobayashi, R., ”Effects of food amount on path selection in transport network of an amoeboid organism,” Topological Aspects of Critical Systems and Networks, pp. 94–100, 2007. · Zbl 1131.92066
[30] Akiyama, J. and Graham, R. L., Introduction to Discrete Mathematics, pp. 86–103, Asakura Shoten, Tokyo, ISBN4-254-11419-2, in Japanese, 1993.
[31] Dijkstra, W., Numer. Math. 1, pp. 269, 1959.
[32] Ouchi, A., Yamamoto, M., Kawamura, H., Shiba, T., Takayanagi, T., Toma, N., and Endo, S, Paradigm of computing from living complex systems, Morikita Shuppan, Tokyo ISBN4-627-8502102, in Japanese, 2003.
[33] Dorigo, M. and Stutzle, T., Ant Colony Optimization, The MIT Press, Massachusetts, USA, 2004. · Zbl 1092.90066
[34] Adamatzky, A., De Lacy Costello, B. and Asai, T., Reaction-diffusion computers, Elsevier, 2005. · Zbl 1011.68062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.