Introduction

In reaction–diffusion computers (Adamatzky 2001; Adamatzky et al. 2005), data are presented by initial concentration profile or configuration of disturbance (e.g. sites of stimulation of excitable media), information is transfered by spreading wave patterns, computation is implemented in collisions of wave-fronts, and final concentration profile represents results of the computation. Reaction–diffusion computers are theoretically and experimentally proven to be capable for quite sophisticated computational tasks, including image processing, computational geometry, logics, and arithmetics, and robot control (Adamatzky et al. 2005). However, there still remains a range of problems where chemical processors cannot cope without external support. Shortest path is one such problem. One can use excitable medium to outline a set of all collision-free paths in a space with obstacles (Adamatzky and De Lacy Costello 2002), but to select and visualise the shortest path amongst all those that are possible, one needs to use an external cellular-automaton processor or conceptually supply the excitable chemical medium with some kind of field of local pointers (Adamatzky and De Lacy Costello 2002). Experimental setups (Steinbock et al. 1995; Agladze et al. 1997) which claim to directly compute a shortest path in chemical media are indeed employing external computing resources to store time-lapsed snapshots of propagating wave-fronts and to calculate the intersection of wave fronts. Such usage of external resources dramatically reduces the fundamental values of the computing with propagating patterns.

Graph-theoretical computations pose even more difficulties for spatially extended non-linear computers. For example, one can compute a Voronoi diagram of a planar set but cannot invert this diagram (Adamatzky et al. 2005). Let us consider a spanning tree, the most famous of classical proximity graphs. Given a set of planar points, one wants to connect the points with edges such that the resultant graph has no cycles and there is a path between any two points of the set. So far, no algorithms of spanning tree construction have been experimentally implemented in spatially extended non-linear systems. This is caused mainly by uniformity of spreading wave-fronts, their inability to sharply select directions toward locations of data points, and the fact that excitable systems usually do not form stationary structures or standing waves.

The present paper recurs to the author’s early algorithm of a computing spanning tree by an abstract growing neuroblast (Adamatzky 1991) and speculates on how such an algorithm can be implemented in excitable systems with retained excitation rules (Sect. Amoeboid patterns in excitable mediu). I demonstrate the experimental computing of a spanning tree by Physarum polycephalum slime mold (Sect. Physarum machines), which is a biological analog of a reaction–diffusion system enclosed in a membrane. Further directions of research are discussed in Sect. Conclusion.

Amoeboid patterns in excitable mediu

Is it possible to imitate bounded and non-uniformly propagating patterns similar to that exhibited by amoeboid creatures? Let us consider the model of retained excitation (Adamatzky 2007). Every cell of a two-dimensional array has eight neighbours and takes three states: resting, excited, and refractory. All cells update their states simultaneously in discrete time and depending on the states of their closest neighbours. A resting cell excites if a number of excited neighbours belong to excitation interval [θ 1, θ 2]. An excited cell remains excited if a number of excited neighbours belong to excitation retention interval [δ 1, δ 2]. Each rule therefore can be described as a tuple R(θ 1 θ 2 δ 1 δ 2).

In exhaustive analysis of excitation rules (Adamatzky 2007), I located a sub-domain of rule space, R(33δ 1 δ 2), δ 1 ∈ [1,3] and δ 2 ∈ [5,8], the elements of which are responsible for non-uniform or directed growth of the excitation patterns. As shown in Fig. 1, initial circular domains of stimulation are transformed to unevenly growing shapes. Wave-fronts are split into pseudopodia-like growing domains and also more straightforwardly growing domains (as the ones in Fig. 1h,i); all propagate with different speeds.

Fig. 1
figure 1

Snapshots of excitation dynamics of cellular automaton with retained excitation, 300 ×300 cells, taken at the 350th step of development. A locus of initial stimulation, shown in a, is a disc radius with 20 cells, each cell inside the disc were assigned refractory state or excited state with probability 0.16 each. Snapshots are provided for each rule of the domain: a R(3315), b R(3316), c R(3317), d R(3318), e R(3325), f R(3326), g R(3327), h R(3328), i R(3335), j R(3336), k R(3337), l R(3338)

Full size image

In many rules, directed, or almost directed, growth of pseudopodia is guided by small tips consisting of excited and refractory states [analogs of growth cones, which were elementary processors in algorithm (Adamatzky 1991)]. We can see that the growth phenomena have an underlying tree-like structure, where branching structure depends on the exact rules governing the cellular automata. Increase of the upper boundary, δ 2, of excitation retention interval reduces branching, while increase of the lower boundary, δ 1, makes growing patterns more compact. In cases of very wide interval of excitation retention, δ 2 = 8, the role of refractory states diminishes.

Containing and controlling excitation waves

I have demonstrated in the previous section that even extremely simple rules of local dynamics in discrete lattice can generate complex non-uniform slowly and selectively growing patterns. These models were rather analogous representations of amoeboid-like propagation of an excitable spatially extended system.

Can the excitation amoeboid pattern be guided to calculate a spanning tree, or at least, starting at some given point, to span neighbouring planar points in a manner outlined in Fig. 2b? Despite their sophisticated space-time dynamics, amoeboid patterns are barely controllable. Exact shape of the pseudopodia is determined by initial configuration of excited and refractory states in stimulation disc. We can indeed guide propagation of the wave fronts, as demonstrated in Fig. 2; however, it seems to be impossible at the present stage to span an arbitrary planar set of points with any kind of graph. This is because excitation patterns do not shrink: they can indeed cover a set of data points they do contain but do not display structure of the proximity graph.

Fig. 2
figure 2

Guided growth of amoeboid patterns. a Amoeboid excitation pattern in discrete model of retained excitation. Cells lying at the centre to north-west, centre to east and centre to south-east diagonals are always kept in excited states. Initial stimulation is a centered disc radius of five cells, where every cell takes a non-resting state with probability 0.3. Wave-fronts propagate with higher speeds along excited segments. b Scheme of original idea on spanning tree computation posed in 1991 (Adamatzky 1991)

Full size image

The diffusive component of the growing patterns must be somehow inhibited. Encapsulating the reaction–diffusion system in a membrane would be a solution. As far as I am aware, there are no theoretical models nor experimental prototypes of chemical reaction–diffusion systems contained in controllable and growing membrane.

The ultimate goal of our studies in unconventional computer architectures is to build working real-world prototypes of non-classical computers working on chemical or biological substrates. To make a shortcut toward the goal, I have not been designing a computer model of an excitable reaction–diffusion system enclosed in membrane but instead found quite a close biological analog of such a system. This is a plasmodium of true slime mold P. polycephalum. Plasmodium is P. polycephalum, which is a single cell with many nuclei which behaves like an amoeba.

I believe Physarum plasmodium is an analog of an excitable reaction–diffusion system enclosed in a membrane. This proposition is based on the following findings: Growing and feeding plasmodium exhibit characteristic rhythmic contractions with articulated sources. The contraction waves are associated with waves of potential change, and the waves observed in plasmodium (Matsumoto et al. 1986, 1988; Yamada et al. 2006) are similar to those found in excitable chemical systems, like Belousov–Zhabotinsky medium. The following wave phenomena were discovered experimentally (Yamada et al. 2006): undisturbed propagation of contraction wave inside the cell body, collision and annihilation of contraction waves, splitting of the waves by inhomogeneity, and formation of spiral waves of contraction (see Fig. 6c–f in (Yamada et al. 2006)). These are closely matching dynamics of pattern propagation in excitable reaction–diffusion chemical systems.

Yamada et al. (Yamada et al. 2006) indicate the possibility for interaction between the contraction force generating system with oscillating chemical reactions of calcium, ATP and associated pH (Ridgway and Durham 1976; Nakamura et al. 1982; Ogihara 1982). Moreover, there are evidences that chemical oscillations are primary oscillations (i.e. contraction waves are guided by chemical oscillation waves) because chemical oscillations can be recorded in the absence of contractions (Oster and Odel 1984; Nakamura and Kamiya 1985; Nakagaki et al. 1999).

The plasmodium has already been proven to be a unique fruitful object to design various schemes of non-classical computation (Aono and Gunji 2004a,b; Tsuda et al. 2004), including shortest path (Nakagaki 2001; Nakagaki et al. 2001) and even design of controllers for robots (Tsuda et al. 2006).

Physarum machines

The scoping experiments were designed as follows: I either covered the container’s bottom with a piece of wet filter paper and placed a piece of living plasmodium on it or just planted plasmodium on the bottom of a bare container and fixed wet paper on the container’s cover to keep humidity high. Oat flakes were placed at the positions of given planar points to be spanned by a tree. Plasmodium was kept fed before experiments. Experiments took place at room temperature, circa 25oC. The containers were stored in the dark except during periods of observation.

Once placed in the container and recovered, the plasmodium starts to explore the surrounding space. Numerous pseudopodia emerge, frequently branch, and proceed (Fig. 3a). The plasmodium growth from its initial position by protoplasmic pseudopodia detecting, by chemotaxis, relative locations of the closest sources of nutrients. When another source of nutrients, element of the given planar set, is reached, the relevant part of the plasmodium reshapes and shrinks to a protoplasmic strand or a tube. This tube connects initial and newly acquired sites. This protoplasmic strand represents an edge of the computed spanning tree (Fig. 3b).

Fig. 3
figure 3

Approximation of spanning trees by Physarum slime mold; data points are represented by oat flakes: a exploratory phase, first day of the experiment; b partly constructed tree, second day of the experiment; c photograph of slim mold constructed tree of 12 points, tree was constructed on the third day of the experiment; d highlighted tree; e spanning tree constructed by classical algorithms. Snapshots a and b show plasmodium grown on a bare container, no substrate, Petri dish, and c paper moistened with water. Snapshots have actual views

Full size image

Planar points distributed in a Petri dish are usually spanned by a slime mold tree in 2–3 days (Fig. 3c,d). The trees computed by P. polycephalum are remarkably close, in number of edges and total sum of edge lengths, to spanning trees computed by classical algorithms (Fig. 3e).

Conclusion

I adopted a paradigm of slime mold computing (Nakagaki et al. 2000; Nakagaki 2001) to experimentally imitate algorithms of spanning tree approximation in reaction–diffusion computers (Adamatzky et al. 2005) encapsulated in membranes. Experiments with P. polycephalum proved that the theoretical framework bears a huge potential for designing non-classical computing devices, and that the experimental approach is feasible.

By encapsulating reaction–diffusion systems in membrane, we did not speed up the computation. In general, plasmodium propagates with a speed similar to that of diffusing chemical species. Therefore, Physarum machines and reaction–diffusion computers are the same class of very slow natural computing devices. Speed of computation was not a goal of the present study. By containing a non-linear, spatially extended system in the membrane, we made the system capable of directional selectivity, controllable motion and, ultimately, building optimal graph structures.

Plasmodium can live on a wide variety of substrates, including bare glass and metal. Comparing to reaction–diffusion computers (which are mainly liquid phase or gel-based), Physarum machines are more stable, are more tolerant to unfriendly environments and can perform their tasks in a wider range of specialised computing devices.

Despite the success of the experimental implementation of the Physarum machine, I understand that criticism is coming and, to be precise, would like to make several clarifications.

First, slime mold does not compute a minimal spanning tree. To compute a minimal tree of n planar points, one should undertake at least n experiments, planting the initial piece of plasmodium at different points of the given set and then comparing total lengths of the trees calculated (however, even in such a situation, one can achieve reasonable complexity boundary O(n D(n)), where D(n) is a diameter of the given planar set). In my experiments, a minimal – plasmodium converts distance to time – tree for a given start point is computed. Second, on many occasions, slime mold calculates a Steiner tree because sometimes protoplasmic strands branch at the points not belonging to the given planar set. Third, slime mold computation is rather interactive because once the spanning tree is computed, the computation does not stop, and more strands connecting oat flakes are formed, cycles in the calculated graph emerge and the proximity graph computed resembles relative neighbourhood or Gabriel graphs. This particular feature will be the subject of future studies.