Communications of the ACM
Home/Magazine Archive/September 2007 (Vol. 50, No. 9)/Amoeba-Based Neurocomputing with Chaotic Dynamics/Full Text
Beyond silicon: new computing paradigms
Amoeba-Based Neurocomputing with Chaotic Dynamics
An amoeba of true slime mold (see Figure 1a), a multinucleated unicellular organism with a single gel layer (cellular membrane) encapsulating intracellular sol, can be regarded as a kind of massively parallel computer whose elements are microscopic actomyosins (fibrous proteins) taking contracting or relaxing states. Collectively interacting actomyosins in the gel layer generate rhythmic contraction-relaxation oscillation (period=1~2 minutes) of vertical body thickness, and their spatiotemporal oscillation pattern induces horizontal shuttle-streaming of intracellular sol (velocity=~1 mm/second) to deform the macroscopic shape. Despite its homogeneous and decentralized structure, the amoeba exhibits integrated computational capacities in its shape deformation. Indeed, the amoeba can solve a maze by connecting the shortest route between food sources at terminals of the maze to optimize the nutrient absorption efficiency [7].
We employ the amoeba as it can freely change its planar shape only inside the stellate barrier structure on an agar plate (see Figure 1b), and experimentally implement a neural network model in which its state transition is represented by the amoeba's photoavoidance-based shape deformation under optical feedback control. The ith path of the stellate structure, called "neuron i" (i 
{1, 2, ..., 8}), takes the active state xi = 1 whenever the fraction of the area occupied by the amoeba's branch exceeds a threshold value of 1/4, otherwise the inactive state xi = 0. We can inactivate a neuron by illuminating the corresponding region, because the amoeba's branch in the neuron shrinks (degenerates) due to its photoavoidance. Conversely, any neuron is activated naturally if it is not illuminated, as the amoeba inherently tries to expand (grow) all branches to occupy the entire agar region with its total volume kept constant. A branch grows or degenerates (velocity=~1 cm/hour) as shuttlewise sol influx-efflux for the branch is iterated.
Optical feedback automatically updates the illumination according to recurrent neural network dynamics [4, 6]: each neuron is activated or inactivated depending on whether the weighted sum of inputs from other neurons exceeds a certain threshold. To simplify these dynamics without spoiling the essence, and to examine the feasibility of NOR-operation known as a universal logic element, we introduced the following rule for updating the illumination at Dt = 6-second intervals: The neuron i is illuminated to be inactive (xi(t+Dt) = 0), if at least one of its adjacent neurons is active (xi-1(t) = 1 or xi+1(t) = 1), otherwise (xi-1(t) = xi+1(t) = 0) nonilluminated to be active (xi(t+Dt) = 1). This rule establishes the following constraint satisfaction problem: Find the system configuration < x1, x2, ..., x8 > such that all neurons satisfy xi = NOR(xi-1, xi+1). As the solutions of this problem, there are 10 configurations consisting of rotation symmetries of < 1, 0, 1, 0, 1, 0, 1, 0 > and < 1, 0, 0, 1, 0, 0, 1, 0 >, that are expected to be stably maintained because the amoeba taking one of these configurations is no longer forced to reshape by illumination and can terminate the expansion of its branches inside all nonilluminated neurons. Any configuration can be clearly judged as a solution, distinguished from a transient state, if and only if all neurons satisfy the following condition: If the neuron i is illuminated then xi = 0, otherwise xi = 1.
It should be noticed that concurrent processing of the circularly connected NOR-operators, analogous to Dijkstra's "dining philosophers problem," entails deadlock-like unsolvability of the problem when all operations are executed in a synchronous manner. Suppose that all branches expand or shrink with a uniform velocity. From the initial configuration < 0, 0, 0, 0, 0, 0, 0, 0 > evoking no illumination (see Figure 1b), the synchronous growth movements of all branches will lead to < 1, 1, 1, 1, 1, 1, 1, 1 > in which all neurons are illuminated. Then, all branches shall shrink uniformly to evacuate from the illuminations, until they reach the initial configuration allowing them to expand again. In this manner, the system can never reach a solution, as the synchronous movements result in perpetual oscillation between < 0, 0, 0, 0, 0, 0, 0, 0 > and < 1, 1, 1, 1, 1, 1, 1, 1 >. The synchronous movements would be inevitable, if the amoeba's oscillatory behavior could only produce periodic spatiotemporal patterns with circular symmetry. However, as shown in Figures 1ch, our system can actually solve the problem, because the amoeba produces chaotic oscillatory behavior involving spontaneous symmetry breaking [8].
The symmetry-broken oscillation pattern shown in Figure 1c yields mutual time lags among movements of branches and decides which branches should exclusively expand. Owing to this asynchronously fluctuating movements [2], the system first reached and stably maintained a solution (see Figure 1d). This result implies our system can operate as a logical circuit holding a kind of computational universality by properly altering the number of neurons (scalable up to approximately 1,000), thresholds, and weights, because the result reflects our system's correct functioning as a network of the McCulloch-Pitts neurons capable of simulating any Boolean logic operations with network architecture allowing arbitrary circuit wiring [4]. Additionally, it was confirmed that this stabilizing mode to reach and maintain a solution also serves as associative memory, when we regard the multiple solutions as prestored memories [3].
Our system's advantageous capability of successively finding several solutions is robustly maintained and qualitatively reproducible, just like robustness of strange attractors of chaotic systems.
Intriguingly, the maintained stabilizing mode of the first solution, however, was spontaneously switched to the destabilizing mode without any explicit external perturbation, as two branches newly emerged with localized high oscillation amplitude and started to invade illuminated regions contrary to photoavoidance (see Figure 1e). While aggressive expansion of the branch 7 was sustained under illumination, the branch 8 was shrunk by illumination, and the first solution eventually evolved into another solution (shown in Figure 1f). Then the spontaneous destabilization occurred again (see Figure 1g), and consequently the system achieved the transition among three solutions (Figures 1d, 1f, and 1h) within 16 hours. Afterward, the system was degraded gradually as the amoeba's photoavoidance became irrecoverably insensitive.
Our system can also be developed for solving combinatorial optimization problems, such as the "traveling salesman problem," as proposed by Hopfield and Tank [6]. The spontaneous switching between the stabilizing and destabilizing modes may assist searching for a global optimum solution without being stuck at local optima. Although its mechanism is under investigation, spatiotemporal chaos, characterized as nonperiodic but nonrandom behavior, must be a key for the spontaneous switching. We speculate that spontaneous destabilization involving spatiotemporal nonperiodicity (symmetry breaking) occurs in a macroscopically stochastic manner because collectively interacting actomyosins generate chaotic dynamics capable of amplifying intrinsic microscopic fluctuations to destabilize macroscopic conditions. Actually, the system's behavior is chaotic as its time evolution is unstable and unreproducible. However, our system's advantageous capability of successively finding several solutions is robustly maintained and qualitatively reproducible, just like robustness of strange attractors of chaotic systems. The usefulness of chaotic dynamics for optimization has already been clarified with chaotic neural network models, where both stabilizing and destabilizing effects contribute to efficient searching dynamics [1, 5].
In a conventional paradigm, deadlock is a common problem for arbitrary concurrent processes, and can be avoided in its "software level" if programmers can know about computational resources requested by all processes in advance of coding the resource allocation. In other words, deadlock avoidance is impossible for many cases, because no one can know beforehand all potential requests of the processes. In contrast, our system can flexibly avoid deadlock-like inoperative conditions and can search for reasonable solutions without any resource allocation program, because in its "hardware level" the amoeba can autonomously materialize and alter the resource allocation (allocation of sol influx-efflux for selecting which branches should expand) in a nonperiodic but nonrandom manner. This unique capability may be advantageous in the development of autonomous systems operated in actual environments, such as robot control systems, that should flexibly respond to concurrent occurrences of unexpected events by avoiding inoperative conditions even if the programs prescribed only for expected events are defective or useless.
Our system does not require highly precise control of environmental conditions, and is robust in a sense that the amoeba's branches are resilient to their growth velocity slowdown caused by temporary lowering of room temperature and humidity. On the other hand, there are some performance limitations derived from employing a living organism for computing, such as its slow processing speed and limited running time. However, our amoeba-based computing system is the first non-silicon based implementation of chaotic neural computing that can realize not only conventional logical computation but also chaotic computation beyond the simple logics due to its spontaneous destabilization utilizing intrinsic fluctuations of massively parallel microscopic elements. Our scheme will be developed by implementing with other faster materials if the amoeba's chaotic dynamics is clarified. Alternative materials may be oscillatory or excitable media capable of spontaneous breaking of spatiotemporal symmetry. To put it simply, the capability of spontaneously escaping from equilibrium and stability is essential for our biologically inspired computing.
References
1. Aihara, K., Takabe, T., and Toyoda, M. Chaotic neural networks. Physics Letters A 144, 6/7 (1990), 333340.
2. Aono, M. and Gunji, Y.-P. Beyond input-output computings: Error-driven emergence with parallel non-distributed slime mold computer. BioSystems 71 (2003), 257287.
3. Aono, M. and Hara, M. Amoeba-based nonequilibrium neurocomputer utilizing fluctuations and instability. In S.G. Aki et al, Eds., UC 2007, LNCS 4618, Springer-Verlag, Berlin (2007), 4154.
4. Arbib, M.A., Ed. The Handbook of Brain Theory and Neural Networks (2nd Edition). The MIT Press, Cambridge, MA, 2003.
5. Hasegawa, M., Ikeguchi, T., and Aihara, K. Combination of chaotic neurodynamics with the 2-opt algorithm to solve traveling salesman problems. Physics Review Letters 79, 12 (1997), 23442347.
6. Hopfield, J.J. and Tank, D.W. Computing with neural circuits: A model. Science 233, (1986), 625633.
7. Nakagaki, T., Yamada, H., and Toth, A. Maze-solving by an amoeboid organism. Nature 407 (2000), 470.
8. Takamatsu, A. Spontaneous switching among multiple spatio-temporal patterns in three-oscillator systems constructed with oscillatory cells of true slime mold. Physica D 223 (2006), 180188.
Figures
Figure 1. (a) An individual amoeba of true slime mold (scale bar=10mm). (b) Barrier structure on agar plate without nutrients (scale bar=2mm). A small piece of the amoeba cut from a huge one can survive as a complete individual even without food supply for up to approximately one week because it can store nutrients fed before the experiment as internal energy source. Initial configuration < 0, 0, 0, 0, 0, 0, 0, 0 > is input by placing the individual amoeba at the center. (c) Transient configuration < 0, 0, 0, 0, 0, 0, 0, 1 >. White light was projected to light-blue rectangular regions. The amoeba's oscillation phases are binarized as red and yellow for relaxing (thickness increasing) and contracting (decreasing) states, respectively. Phase wave propagates from the center to periphery with symmetry breaking. (d) First-reached solution < 0, 1, 0, 0, 1, 0, 0, 1 > (duration
4 hours). (e) Spontaneous destabilization of solution D. Arrows indicate the growth directions of newly-emerged branches growing under illumination contrary to photoavoidance. (f) Second-reached solution < 0, 1, 0, 0, 1, 0, 1, 0 > (duration1 hour). (g) Spontaneous destabilization of solution F. (h) Third-reached solution < 0, 1, 0, 1, 0, 1, 0, 1 > (duration7 hours).
©2007 ACM 0001-0782/07/0900 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2007 ACM, Inc.
No entries found