Cellular Automata Models Simulating Slime Mould Computing

Abstract

Slime mould computers have been used to solve graph-theoretical problems like mazes and evaluate man-made transport networks. For the laboratory experiments that demonstrate these computing capabilities, slime mould is first starved and then introduced to an area with attractants placed on key positions. The behaviour of slime mould during these laboratory experiments have been simulated by a model based on cellular automata (CAs). The advantages of a software model over the real slime mould are repeatability and faster productions of results. Using CAs can be justified by the emergence of global behaviour from local interactions, a rule that applies also on the real slime mould. The results of the model have been compared to the ones produced during laboratory experiments and found in good agreement both for maze solving and network designing. After thorough examination of the laboratory experiments an updated model was developed, which yielded more efficient networks. As the model was parametrized to produce slightly differentiated results, the effects of these parameters were studied.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Physarum polycephalum broadly noted as true slime mould, have been used lately as a substance utilizing unconventional computing capacity. Several studies demonstrated applications of this biological computer on complicated problems, such as developing logical machines [1, 2], establishing logic gates [1, 3], solving combinatorial optimization problems [4, 5], solving maze problems [6, 7], distributed robotic control [8], robotic amoebic movement [9] and finding shortest paths while designing effective networks [1, 10]. The plasmodium of Physarum which is the vegetative stage of its life cycle, is one of the most frequently employed biological computing substances. Mainly due its simple body structure, plain production, trivial manipulation and the fascinating searching and network establishing strategies [11].

In laboratory experiments [11] where the graphic intelligence of slime mould is realized, the plasmodium is firstly starved and inoculated on an oat flake. The aforementioned oat flake is later introduced on a moisturized surface, like agar plates or filter papers, at a predefined point characterized as the Starting Point (SP) for the exploration of the available area. Moreover, on the experimental surface several oat flakes, that serve as Nutrient Sources (NSs), are placed on key positions. The plasmodium of Physarum is attracted by the chemicals emitted by NSs, then covers them with protoplasmic mass to absorb nutrients and, finally, interconnects all available NSs with a tubular network. The produced network can be identified as biologically evolved in terms of efficiency and risk avoidance.

The aforementioned experiments require expensive and specialized equipment and some experience on basic biological laboratory techniques. However, the majority of scientists are unfamiliar with such methods. Moreover, given the large time periods required for the true slime mould to produce results in laboratory experiments, namely up to 5 days, it is of utter importance to accelerate these computations. A commonly proposed alternative alleviating these difficulties is software models that simulate the behavior of the plasmodium and provide similar results. In [10] a mathematical model reproducing the adaptive tubular networks of slime mould have been presented. In addition to that a multi agent model is suggested in [12] that mimics the procedure of tubular network formation by the plasmodium. Moreover, a model based on CAs, named CELL [13], proved to approximate the results of laboratory experiments and have been updated to produce more realistic results [14, 15].

As slime mould has no brain or any central processing system, its distributed control can be perfectly described by the local rule of CAs. It is noteworthy that CAs are known for emerging global behavior from local interactions. Nonetheless, the distributed receptors of plasmodium perform sensing actions in parallel [16]. That is another aspect that is easily simulated due to the inherent parallel nature of CAs. Consequently, a CA based model [17] that mimics the foraging strategy and tubular network formation is proposed. The model is based on the representation of diffusion of chemical attractants by NSs and the attraction of the plasmodium, which initiates its exploration from the SP, by these chemicals. The application of the model to problems recreated by previously presented biological experiments, like solving a maze [7] and designing a transport network [18], demonstrated that the model manages to adequately approximate the tubular network designed by the real plasmodium, as illustrated in the following.

After carefully observing the behaviour of slime mould on the conducted experiments and studying the findings presented in [19], an updated version of the model was proposed [20, 21]. The second variation of the CA model provides more decentralized networks than the first variation that better approximate proximity graphs and Physarum produced graphs. The second variation of the model have been used to evaluate the motorways of countries and regions, specifically United Kingdom, Germany, Canada, Mexico, the Iberian Peninsula and Greece. The graphs resulted by the model include the Relative neighbourhood graph ( RNG) the topologies the countries used, with minor misses, a property characterizing the real slime mould [11]. The graphs provided by the laboratory experiments, with edges appearing frequently in the conducted experiments, were approximated with small error. Nonetheless, the real motorways were partially redesigned by the model. Finally, an analysis of the effects that the parameters of the model have is presented.

2 Cellular Automata Basics

Cellular Automata (CA) are an idealization of a physical system in which space and time are discrete, and the physical quantities take only a finite set of values [22]. Non-trivial CA are obtained whenever the dependence on the values at each site is non–linear. As a result, any physical system satisfying differential equations may be approximated by a CA, by introducing finite differences and discrete variables [23]. A CA consists of a regular grid of cells. Each cell can take, not simultaneously, k different states, where k is a finite number equal or greater than 2. Cells update their states in discrete time. That means that the state of each cell in the lattice changes only at discrete moments of time, namely at time steps t. The time step $t=0$ is usually considered as the initial step and therefore no changes at the state of the cells occur.

For each cell, a set of cells called its neighbourhood (usually including the cell itself) is defined relative to the specified cell [24]. Regarding the two-dimensional CA, there are two fundamental types of neighbourhoods that are mainly considered: (a) von Neumann neighbourhood, that consists of the central cell, whose condition is to be updated, and the four cells located to the north, south, east and west of the central cell and (b) Moore neighbourhood, that consists of the [22] same cells with the von Neumann neighbourhood together with the four other adjacent cells of the central cell (the north-west, north-east, south-east and south-west cells).

The evolution of the cells demands the definition of the neighbouring cells as well as of the local transition function:

• The internal state of a CA is described by a set

  $$\begin{aligned} C ( \mathop {r}\limits ^{\rightarrow },t) = \{ C_{1}( \mathop {r}\limits ^{\rightarrow },t), C_{2}( \mathop {r}\limits ^{\rightarrow },t),\ldots , C_{m}( \mathop {r}\limits ^{\rightarrow },t)\} \end{aligned}$$

  (1)

  of Boolean variables, that connects with each position $\mathop {r}\limits ^{\rightarrow }$ of the array and expresses the local internal state of each cell at time step $t=0,1,2,\ldots$

• The local transition function is defined as:

  $$\begin{aligned} R=\{R_{1},R_{2},\ldots ,R_{m}\} \end{aligned}$$

  (2)

  and determines the evolution [22] during time of the internal state of each cell according to the following equation:

  $$\begin{aligned} C_{p,}( \mathop {r}\limits ^{\rightarrow },t+1) =R_{p} \left( C( \mathop {r}\limits ^{\rightarrow },t), C( \mathop {r}\limits ^{\rightarrow }+\,{\delta }_{1},t),\ldots , C( \mathop {r}\limits ^{\rightarrow }+\,{\delta }_{m},t) \right) \end{aligned}$$

  (3)

  where the position $\mathop {r}\limits ^{\rightarrow }+\,{\delta }_{k}$, $k \in \{1,\ldots ,m\}$ describes the neighbouring cells of each $\mathop {r}\limits ^{\rightarrow }$ cell.

CA have sufficient expressive dynamics to represent complex phenomena and, at the same time, can be simulated exactly by digital computers because of their intrinsic discreteness, i.e. the topology of the simulated object is reproduced in the simulating device [25, 26]. Prior and more recent works proved that CA are very effective in simulating physical systems and solving scientific problems, because they can capture the essential features of systems where global behavior arises from the collective effect of simple components, which interact locally [27–30]. Furthermore, they can easily handle complicated boundary and initial conditions, inhomogeneities and anisotropies [23, 31–33].

The CA approach is consistent with the modern notion of unified space–time. In computer science, space corresponds to memory and time to processing unit. In CA, memory (CA cell state) and processing unit (CA local rule) are inseparably related to a CA cell [34, 35]. Finally, CA can be easily coupled with other computational tools so as to significantly enhance their performance and extend their applications field [36–38]. Models based on CA lead to algorithms which are fast when implemented on serial computers because they exploit the inherent parallelism of the CA structure. These algorithms are also appropriate for implementation on massively parallel computers [39], such as the cellular automaton machine (CAM) [40] or Field Programmable Gate Arrays (FPGAs) [26, 41–43].

3 Cellular Automata Representation of Slime Mould Computing

The most thoroughly studied laboratory experiment that the plasmodium of Physarum is subjected to, is the imitation and optimization of human-made transport networks. Consequently, the proposed CA model will be described under the spectrum of these specific configurations. In these experiments the plasmodium is first starved and then introduced to an environment with some NSs located at characteristic points. The plasmodium explores the available area, encapsulates the NSs and creates a tubular network that connects all these NSs by a nature-inspired, cost effective and risk avoiding manner.

The model imitates the entire area that is used in a laboratory experiment using the plasmodium of Physarum. The entire area can be defined, without loss of generality, as a square grid divided into identical square cells that constitute a set defined as E. This area can be categorized as available area (a set of cells defined as A) and unavailable area (a set of cells defined as U) for the development of the plasmodium. Also some cells that are included in the available area set of cells, represent the oat flakes that are considered as NSs for the plasmodium (a set of cells defined as N) and one cell represents the place where the plasmodium is initially introduced to the experimental environment or the SP (a set of one cell defined as S). Taking the above under consideration, Eq. 4 can be defined.

$$\begin{aligned} N\subset {A},\;S\subset {A},\; A\cup {U}=E,\; A\cap {U}=\emptyset \end{aligned}$$

(4)

The neighbourhood type used for the proposed model is Moore neighbourhood and the state of the $C_{(i,j)}$ cell at time step t $(ST_{(i,j)}^t)$ is defined by Eq. 5.

$$\begin{aligned} ST_{(i,j)}^t=\left[ AA_{(i,j)},PM_{(i,j)}^t,CHA_{(i,j)}^t,TE_{(i,j)}^t\right] \end{aligned}$$

(5)

AA stands for “Available Area” for the plasmodium to explore and takes values according to Eq. 6. PM stands for “Physarum Mass”, meaning a percentage of the cytoplasm located on a specific CA cell. Note here that a cell representing a SP has PM equal to a predefined number (here 100). CHA stands for “CHemoAttractant” substances that are located on a specific CA cell and is also represented by a percentage. A cell representing a NS has the CHA parameter equal to a predefined number (here 100). Finally, TE stands for “Tube Existence” and represents the participation of a cell in the tubular network inside the body of the slime mould.

$$\begin{aligned} AA_{(i,j)}={\left\{ \begin{array}{ll} 1, &{} \forall i,j:c_{(i,j)}\in {A}\\ 0, &{} \forall i,j:c_{(i,j)}\in {U} \end{array}\right. } \end{aligned}$$

(6)

Note that from here forth, the color map of the images used as inputs of the model is illustrated in Fig. 1a and for the outputs of the model in Fig. 1b.

Fig. 1

Color map for a images used as input for the model and b images produced as outputs from the model

3.1 First Variation of the Model

The initially developed model can be described by the following procedures. The initialization step includes the definition of parameters that have a great impact on the results. These parameters include the length of the CA grid, the diffusion parameters for “Physarum Mass” (PMP1, PMP2, PMP3) and “ChemoAttractant” substances (CAP1, CAP2, CAP3), the minimum percentage of chemoattractant substances detected by the plasmodium, the consumption percentage of the chemoattractant substances by the plasmodium (CON—Consumption) and the attraction of the slime mould by chemoattractant substances (PA—Physarum Attraction). Also the topology of the NSs and the SP is introduced to the model by a picture that encodes that information as shown in Fig. 1a.

After the initialization and for 100 time steps, diffusion equations are used to calculate the values for CHA and PM for every cell in the grid. Just for the records, it should be mentioned that in all cases, the aforementioned time steps values were considered empirically after several testing runs of the model. Every cell uses the values of its neighbours at time step t to calculate the value of the CHA and PM parameter for time step $t+1$. The total “Physarum Mass” for a cell $C_{(i,j)}$ for time $t+1$ is described by Eq. 7 and the total “ChemoAttractant” for a $C_{(i,j)}$ cell for time $t+1$ is described in Eq. 8, respectively. The multiplication with the parameter CON, provides the imitation of the consumption of the chemoattractant substances by the plasmodium.

$$\begin{aligned} PM_{(i,j)}^{t+1}&=PM_{(i,j)}^{t}+PMP1 \times \{(1+PA_{(i,j),(i-1,j)}^t) \times {PM_{(i-1,j)}} - PMP3 \times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i,j-1)}^t) \times {PM_{(i,j-1)}} - PMP3 \times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i+1,j)}^t) \times {PM_{(i+1,j)}} - PMP3 \times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i,j+1)}^t) \times {PM_{(i,j+1)}} - PMP3 \times {PM_{(i,j)}^t}\} \nonumber \\&\quad +PMP2\times \{ (1+PA_{(i,j),(i-1,j-1)}^t) \times {PM_{(i-1,j-1)}} - PMP3 \times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i+1,j-1)}^t) \times {PM_{(i+1,j-1)}} - PMP3 \times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i-1,j+1)}^t) \times {PM_{(i-1,j+1)}} - PMP3 \times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i+1,j+1)}^t) \times {PM_{(i+1,j+1)}} - PMP3 \times {PM_{(i,j)}^t}\} \end{aligned}$$

(7)

$$\begin{aligned} CHA_{(i,j)}^{t+1}=CON\times&[CHA_{(i,j)}^{t}+CAP1\times \{ (CHA_{(i-1,j)}^t)-CAP3\times {CHA_{(i,j)}^t}\nonumber \\&+ (CHA_{(i,j-1)}^t)-CAP3\times {CHA_{(i,j)}^t} \nonumber \\&+ (CHA_{(i+1,j)}^t)-CAP3\times {CHA_{(i,j)}^t} \nonumber \\&+ (CHA_{(i,j+1)}^t)-CAP3\times {CHA_{(i,j)}^t} \} \nonumber \\&+CAP2 \times \{ (CHA_{(i-1,j-1)}^t)-CAP3\times {CHA_{(i,j)}^t}\nonumber \\&+ (CHA_{(i+1,j-1)}^t)-CAP3\times {CHA_{(i,j)}^t} \nonumber \\&+ (CHA_{(i-1,j+1)}^t)-CAP3\times {CHA_{(i,j)}^t} \nonumber \\&+ (CHA_{(i+1,j+1)}^t)-CAP3\times {CHA_{(i,j)}^t} \}] \end{aligned}$$

(8)

The parameter $PA_{(i,j),(k,l)}$ represents the attraction of the Physarum Mass (“Physarum Attraction”) in cell $C_{(i,j)}$ towards the direction of an adjacent cell $C_{(k,l)}$, modeling the attraction of the organism towards the higher gradient of chemoattractants. It is equal to a predefined constant (PAP) for the neighbour with the higher value of chemoattractant and equals to the negative value of the same predefined constant for the neighbour across the neighbour with the higher value of chemoattractant. For all the other neighbours the parameter PAP is equal to zero. The definition of the PA parameter for cell $C_{(i,j)}$ towards its north neighbour $(C_{(i-1,j)})$ is illustrated in Eq. 9.

$$\begin{aligned} \begin{aligned} PA_{(i,j),(i-1,j)}^t={\left\{ \begin{array}{ll} PAP,&{}\text {if }CHA_{(i-1,j)}=MAX(CHA_{(k,l)} \\ &{} \forall k,l:\;i-1\le {k}\le {i+1} \\ &{}\text {and }j-1\le {l}\le {j+1})\\ -PAP,&{}\text {if }CHA_{(i+1,j)}=MAX(CHA_{(k,l)} \\ &{}\forall k,l:\;i-1\le {k}\le {i+1} \\ &{}\text {and }j-1\le {l}\le {j+1})\\ 0,&{}\text {else}. \end{array}\right. } \end{aligned} \end{aligned}$$

(9)

Finally, after 100 time steps, the procedure of creating Tubes is initiated. During this phase, one Tube is formed for each NS, with starting point the location of the NS and the ending point the initial location of the plasmodium (SP). The route that the Tube follows is the one indicated by the gradient of the amount of the Physarum’s protoplasmic Mass, from the smallest value to the highest. Namely, every cell corresponding to a NS, sets its $TE^{t}_{i,j}$ parameter to high and, then, locates in its neighborhood the cell with the greater $PM^{t}_{i,j}$ parameter. That cell must participate in the path of the Tube. As a result, the NS cell sends to that cell a signal in order to make that cell to change its $TE^{t}_{i,j}$ parameter to high. That procedure is continued until the SP is found, or in the case of a maze, another NS is found.

3.2 Second Variation of the Model

Taking into consideration the assumptions made for the way the Physarum develops through an available area, which were confirmed by laboratory experiments in [11, 19], the model initially proposed [17], was altered. Firstly it is determined that the plasmodium is “amplified” at a NS and then searches for other NSs, considering the recently encapsulated NS as a new SP. Also, when a NS is covered by the plasmodium, the generation of chemoattractant substances is ceased. Consequently, the proposed model is altered in the way the plasmodium is exploring all the available area. In the previous model there was the initial SP and all the NSs were connected with that point, in some cases through other NSs. Now, the NSs are turned into SPs when the plasmodium encapsulates them with a sufficient amount of mass. Furthermore, it is realized that the plasmodium is propagating away from the most recently captured NS by taking a semi-circular form [19]. That feature is covered by the diffusion equation describing the foraging of the plasmodium that was previously used. Moreover, the model uses a diffusion equation to calculate the propagation of chemoattractants produced by the NSs, as observed in [19].

The updated model has some important alternation from the previously presented, thus, it will be thoroughly described, despite the fact that some procedures are identical to the initial. The new model is analyzed in the following sequence of procedures, which are also illustrated in a flowchart (Fig. 2):

• 1. Initialize the model: the parameters of the diffusion equations are set and the topology of the SP and the NSs is also introduced to the model by a picture coded as Fig. 1a indicates.

• 2. Apply the diffusion equations for 50 time steps (t).

• 3. Check if any of the NSs is covered with a predefined percentage of PM (ThPM). If there is at least one NS covered continue, else go to (2).

• 4. All NSs covered with the predefined percentage of PM (ThPM), are encapsulated by the plasmodium and therefore connected to a SP.

• 5. The NSs mentioned in (4) change into SPs, meaning their PM is set to 100. If no more than 5,000 time steps have passed ($t<$5,000) go to (2), else continue.

• 6. Redefine all the cells of “interest” (NSs and SP) as NSs, except from the second to last NS encapsulated for the previous 5,000 time steps which is redefined as a SP. Execute for a second time (2)–(5) for 5,000 time steps.

Fig. 2

Flowchart of the proposed model

Having briefly presented the outline of the model, Eqs. 10 and 11 give values for PM and CHA of cells constituting sets U, S and N.

$$\begin{aligned} PM_{(i,j)}^t={\left\{ \begin{array}{ll} 0, &{} \forall i,j:c_{(i,j)}\in {U}\\ 100, &{} \forall i,j:c_{(i,j)}\in {S}\\ 100, &{} \forall i,j:c_{(i,j)}\in {N} \text { and }PM_{(i,j)}^t\ge {ThPM} \end{array}\right. } \end{aligned}$$

(10)

$$\begin{aligned} CHA_{(i,j)}^t={\left\{ \begin{array}{ll} 100, &{} \forall i,j:c_{(i,j)}\in {N} \text { and }PM_{(i,j)}^t<ThPM\\ 0, &{} \forall i,j:c_{(i,j)}\in {N}\text { and }PM_{(i,j)}^t\ge {ThPM} \end{array}\right. } \end{aligned}$$

(11)

A logical question that comes to mind is why procedures (2) to (5) are executed for a second time. As identified in some laboratory experiments [44], after a seemingly random and not certain amount of time the plasmodium seems to change the formation of its protoplasmic networks and abandon some NSs. Then it seems to regenerate in a manner and re-colonize some NSs, meaning it forms new tubular edges that connect NSs that were already connected to other NSs. As the CA model is designed without the use of probabilistic equations, it uses a second starting point to regenerate and explore the available area once more. That point will be a point of interest (NS), which is empirically chosen to be away from the initial SP. Furthermore, if that feature was not included to the model, the result would be more like a spanning tree, than a proximity graph which is proved to be more appropriate to bear resemblance to the graphs drawn by the plasmodium [45]. The second to last NS to be encapsulated was chosen, based on the fact that it is far enough from the initial SP and it is less likely to be a point of interest surrounded by unavailable area that would cause difficulties for the growth of the plasmodium. Finally, the time period of 50 time steps for the diffusion equations, was also empirically chosen, although the alternation of that will cause little difference to the results of the model.

In order to clarify the model’s procedures, every single one will be further explained here. The initialization step includes the definition of parameters that have a great impact on the results of the model. These parameters include the length of the CA grid, the diffusion parameters for “Physarum Mass” (PMP1, PMP2) and “ChemoAttractant” substances (CAP1, CAP2), the minimum percentage of chemoattractant substances detected by the plasmodium, the consumption percentage of the chemoattractant substances by the plasmodium (CON—Consumption), the attraction of the slime mould by chemoattractant substances (PA—Physarum Attraction) and the threshold of “Physarum Mass” that encapsulates a NS (ThPM). Also the topology of the NSs and the SP is introduced to the model by a picture that encodes that information as shown, previously, in Fig. 1a.

After the initialization and for 50 time steps, diffusion equations are used to calculate the values for CHA and PM for every cell in the grid. Every cell uses the values of its neighbours at time step t to calculate the value of the CHA and PM parameter for time step $t+1$. The contribution to the diffusion of the Physarum Mass of the von Neumann neighbours (PMvNN) of the $C_{(i,j)}$ cell is described in Eq. 12. Moreover, the contribution to the diffusion of the Physarum Mass of the exclusively Moore neighbours (PMeMN) of the $C_{(i,j)}$ cell is described in Eq. 13. The total “Physarum Mass” for a cell $C_{(i,j)}$ for time $t+1$, is a sum of the contributions of its neighbours with appropriate weights and is described by Eq. 14, respectively.

$$\begin{aligned} PMvNN_{(i,j)}^t&=(1+PA_{(i,j),(i-1,j)}^t)\times {PM_{(i-1,j)}} - AA_{(i-1,j)}\times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i,j-1)}^t)\times {PM_{(i,j-1)}} - AA_{(i,j-1)}\times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i+1,j)}^t)\times {PM_{(i+1,j)}} - AA_{(i+1,j)}\times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i,j+1)}^t)\times {PM_{(i,j+1)}} - AA_{(i,j+1)}\times {PM_{(i,j)}^t} \end{aligned}$$

(12)

$$\begin{aligned} PMeMN_{(i,j)}^t&=(1+PA_{(i,j),(i-1,j-1)}^t)\times {PM_{(i-1,j-1)}} - AA_{(i-1,j-1)}\times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i+1,j-1)}^t)\times {PM_{(i+1,j-1)}} - AA_{(i+1,j-1)}\times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i-1,j+1)}^t)\times {PM_{(i-1,j+1)}} - AA_{(i-1,j+1)}\times {PM_{(i,j)}^t} \nonumber \\&\quad + (1+PA_{(i,j),(i+1,j+1)}^t)\times {PM_{(i+1,j+1)}} - AA_{(i+1,j+1)}\times {PM_{(i,j)}^t} \end{aligned}$$

(13)

$$\begin{aligned} PM_{(i,j)}^{t+1}=PM_{(i,j)}^{t}+PMP1\times {\left[ PMvNN_{(i,j)}^t+PMP2\times {PMeMN_{(i,j)}^t}\right] } \end{aligned}$$

(14)

Note here that if a neighbouring cell is representing unavailable area, there is no contribution to the diffusion (neither positive nor negative). Also, the parameter $PA_{(i,j),(k,l)}$ represents the attraction of the Physarum Mass (“Physarum Attraction”) in cell $C_{(i,j)}$ towards the direction of an adjacent cell $C_{(k,l)}$, modeling the attraction of the organism towards the higher gradient of chemoattractants. It is equal to a predefined constant (PAP) for the neighbour with the higher value of chemoattractant and equals to the negative value of the same predefined constant for the neighbour across the neighbour with the higher value of chemoattractant. For all the other neighbours the parameter PAP is equal to zero. The definition of the PA parameter for cell $C_{(i,j)}$ towards its north neighbour $(C_{(i-1,j)})$ is illustrated in Eq. 15.

$$\begin{aligned} \begin{aligned} PA_{(i,j),(i-1,j)}^t={\left\{ \begin{array}{ll} PAP,&{}\text {if }CHA_{(i-1,j)}=MAX(CHA_{(k,l)} \\ &{}\forall k,l:\;i-1\le {k}\le {i+1}\text { and }j-1\le {l}\le {j+1})\\ -PAP,&{}\text {if }CHA_{(i+1,j)}=MAX(CHA_{(k,l)} \\ &{}\forall k,l:\;i-1\le {k}\le {i+1}\text { and } j-1\le {l}\le {j+1})\\ 0,&{}\text {else}. \end{array}\right. } \end{aligned} \end{aligned}$$

(15)

Furthermore, the contribution to the diffusion of the chemoattractants for the plasmodium of the von Neumann neighbours (CHAvNN) of the $C_{(i,j)}$ cell is described in Eq. 16. The contribution to the diffusion of the chemoattractants for the plasmodium of the exclusively Moore neighbours (CHAeMN) of the $C_{(i,j)}$ cell is described in Eq. 17. As a result, the total chemoattractant parameter for a $C_{(i,j)}$ cell for time $t+1$ is described in Eq. 18.

$$\begin{aligned} CHAvNN_{(i,j)}^t&=(CHA_{(i-1,j)}^t)-AA_{(i-1,j)}\times {CHA_{(i,j)}^t}\nonumber \\&\quad + (CHA_{(i,j-1)}^t)-AA_{(i,j-1)}\times {CHA_{(i,j)}^t} \nonumber \\&\quad + (CHA_{(i+1,j)}^t)-AA_{(i+1,j)}\times {CHA_{(i,j)}^t} \nonumber \\&\quad + (CHA_{(i,j+1)}^t)-AA_{(i,j+1)}\times {CHA_{(i,j)}^t} \end{aligned}$$

(16)

$$\begin{aligned} CHAeMN_{(i,j)}^t&=(CHA_{(i-1,j-1)}^t)-AA_{(i-1,j-1)}\times {CHA_{(i,j)}^t}\nonumber \\&\quad + (CHA_{(i+1,j-1)}^t)-AA_{(i+1,j-1)}\times {CHA_{(i,j)}^t} \nonumber \\&\quad + (CHA_{(i-1,j+1)}^t)-AA_{(i-1,j+1)}\times {CHA_{(i,j)}^t} \nonumber \\&\quad + (CHA_{(i+1,j+1)}^t)-AA_{(i+1,j+1)}\times {CHA_{(i,j)}^t} \end{aligned}$$

(17)

$$\begin{aligned} \begin{aligned} CHA_{(i,j)}^{t+1}=CON\times \{&CHA_{(i,j)}^{t}+CAP1\times (CHAvNN_{(i,j)}^{t}\\&\quad +CAP2\times {CHAeMN_{(i,j)}^{t}})\} \end{aligned} \end{aligned}$$

(18)

Note here that if a neighbouring cell is representing unavailable area, there is no contribution to the diffusion (neither positive nor negative), as in the diffusion of Physarum Mass. Moreover, the multiplication with the parameter CON, provides the imitation of the consumption of the chemoattractant substances by the plasmodium.

After every 50 time steps of calculating the diffusion equations in the available area, if any NS is covered with over the predefined PM (ThPM), it is connected with a SP with a Tube that follows the gradient of the PM to the higher value. More specifically, starting from the cell representing the encapsulated NS, the adjacent cell with the higher PM value is selected to participate to the tubular network. Then the cell selected to participate to the tubular network selects the next cell from its neighbours with the higher PM value to participate to the tubular network and so on, until a SP is reached.

Finally, this NS will be transformed to a SP ($PM =100$) and will act as a SP for the remaining time steps, as illustrated in Eqs. 10 and 11, respectively. If more NSs are covered with the predefined PM, they are connected to the nearest SP and they are all transformed to SPs.

4 Application of the Model to Transport Networks

In order to compare the results provided by the model with the results produced by the real plasmodium of Physarum, the topologies of several laboratory experiments were recreated. The first variation of the model was used to simulate laboratory experiments with the plasmodium solving mazes and evaluating transport networks, while the second variation simulated only experiments evaluating transport networks. Nonetheless, the second variation is, also, capable of solving a maze.

4.1 Results of the First Variation of the Model

The topologies of the experiments were recreated by the model as CA grids of size $50 \times 50$ for the maze solving instance and $150 \times 150$ for the instance of evaluating a train network. The parameters of the first variation of the model are different for each instance, as described in the following.

4.1.1 Maze Solving

The maze topology used for the biological experiment presented in [7] (Fig. 3) was used as an input for the model. More specifically, Nakagaki and his colleagues took a growing tip from a large plasmodiums and divided it into small pieces. Then, they positioned them in a maze created by an appropriately cut plastic film, placed on an agar surface. The plasmodial pieces spread and coalesced to form a single plasmodium that filled the maze, avoiding the dry surface of the plastic film. At the start and end points of the maze, they placed agar blocks containing nutrient (ground oat flakes), with four possible routes between the start and the end points. The plasmodium’s pseudopodia reaching dead ends in the labyrinth shrank, resulting in the formation of a single thick pseudopodium spanning the minimum length between the nutrient–containing agar blocks [7].

Fig. 3

The under study maze

In our case, we artificially reconstructed the aforementioned maze taking into consideration the exact configuration of the maze used. The model was initialized with the following parameters: $CON=1$, $PAP=0.3$, $PMP1 = 0.05$, $PMP2 = 0.025$, $PMP3 = 1$, $CAP1 = 0.05$, $CAP2 = 0.025$ and $CAP3 = 1$. The model simulation results after 500, 1000, 1200 and 1500 time steps are shown in Fig. 4. Compared to the results of the biological experiment in [7], the algorithm can be considered successful. As is illustrated in Fig. 4c, it takes 1200 time steps to find a solution that is not the best one. However, after 1500 time steps (Fig. 4d), the model manages to solve the maze using the shortest possible route. It should be noted that in analogy to the real experiments, the model changes the network’s shape in the maze to form one thick tube covering the shortest distance between the NSs, so as to maximize its efficiency, and therefore, the chances for survival of the simulated plasmodium. The period of 1500 time steps (which correspond to about 45 s of real time on a PC) may seem like a long time for some applications, but compared to 8 h needed for the biological experiment, it is not a significantly long time period.

Fig. 4

The simulation results for the maze presented in Fig. 3, after a 500, b 1000, c 1200 and d 1500 time steps, respectively

4.1.2 Train Network of Tokyo Area

The first variation of the model was also used for the development of an adaptive network . More specifically, Tero et al. [18] presented a simple mathematical model for the development of a network of veins connecting multiple decisively placed NSs. In their experiment, cities around Tokyo were represented as oat flakes on a wet surface that was inoculated with plasmodium. Plasmodial veins connected these oat flakes by forming an optimized network closely approaching the decisively designed Tokyo railway system. As a result, the plasmodium can construct an efficient transportation network that meets the multiple requirements of short length and low degree of separation between NSs, as well as tolerance of accidental disconnection at random position [18].

In our case, we used a template of 36 NSs that represent geographical locations of cities in the Tokyo area as an input, and we compared the results of the model with the actual rail network in Tokyo, Japan. The template is illustrated in Fig. 5. The results after 500, 1000, 1500 and 2500 time steps, for two different initializations of the parameters of the diffusion equations, are presented in Figs. 6 and 7, respectively. It should be noted that in analogy to the real experiments, the presented networks of plasmodial veins form without any central control mechanism that might inform the plasmodium about the relative position of the oat flakes or dictate how to connect them.

Fig. 5

Template of the Tokyo area and cities in its vicinity

Fig. 6

The model results designing Tokyo railway system, after a 500, b 1000, c 1500 and d 2500 time steps, respectively. The diffusion equation parameters used are: $CAP1 = 0.06$, $CAP2 = 0.036$ and $CAP3 = 1$

Fig. 7

The model results designing Tokyo railway system, after a 500, b 1000, c 1500 and d 2500 time steps, respectively. The diffusion equation parameters used are: $CAP1 = 0.12$, $CAP2 = 0.144$ and $CAP3 = 1$

Fig. 8

The final model results designing Tokyo railway system, after 2500 time steps, for a $CAP1 = 0.06$, $CAP2 = 0.036$, and b $CAP3 = 1$ and $CAP1 = 0.12$, $CAP2 = 0.144$, $CAP3 = 1$ diffusion equation parameters, respectively. c The rail network in the Tokyo area as shown in [18]. d The real experiment’s results of the plasmodium grew out from the SP with a contiguous margin and progressively colonized each of the food sources as reported in [18]

The parameters of the “Physarum Mass” diffusion equation in both instances are the same ($PMP1 = 0.08$, $PMP2 = 0.064$, $PMP3 = 1$), while the parameters of the “ChemoAttractant” substances diffusion equation are different (for Fig. 6, $CAP1 = 0.06$, $CAP2 = 0.036$, $CAP3 = 1$, and for Fig. 7, $CAP1 = 0.12$, $CAP2 = 0.144$, $CAP3 = 1$). Moreover, other model parameters were set as $CON=1$, $PAP=0.8$. Taking into consideration the results from the instance with higher diffusion parameters (Fig. 7), it can be noted that the most significant difference was found at the north–east section, where the tube paths converge faster. In Fig. 8, the similarities and differences of the results of the model with different initial parameters, the actual rail network and the result of the biological experiment are shown. It is obvious that the results of the model are not decentralized as the other two. This leads to lower fault tolerance. Nevertheless, the pattern of the tube paths, connecting the NSs together and with the SP of the plasmodium, produced by the model bear some resemblance with a part of the results of the biological experiment. By adding to the results of the model, a path connecting the outer FSs with each other, the results become more similar to the experimental ones.

4.2 Results of the Second Variation of the Model

As mentioned previously, the plasmodium of Physarum was used in laboratory experiments, in order to reproduce human-made networks , like motorways in several countries and the results of these experiments are thoroughly examined. The networks produced by these laboratory experiments were compared to proximity graphs and the real infrastructures [21, 44–48]. Consequently, to demonstrate the efficiency and applicability of the second variation of the model, the topology of significant cities, in terms of population or transportation, as defined in laboratory experiments that were conducted in [21, 44–48], will be used as inputs for the second variation model and the results will be compared with Physarum, proximity graphs and real motorways.

More specifically the proximity graph chosen as a control is the RNG, due to the finding from laboratory experiments [47] that when inoculated in a single data point, the plasmodium finally builds a proximity graph which includes RNG. Points a and b are connected by an edge in the RNG, if no other point c is closer to a and b than dist(a, b) [49]. The parameters of the model were set with the values illustrated in Table 1 for all instances. The countries used as characteristic study cases are United Kingdom, Germany, Canada, Mexico, the Iberian Peninsula and Greece. These countries/regions were selected, among many others, based on the experimental results and their corresponding analysis as presented in [50]. More specifically, these countries can be considered as typical study cases for reproduction of human-made networks by Physarum in terms of the following two main measures: (a) matching and (b) economy of matching [50]. These measures are derived from the direct comparison of the Motorway and Physarum graphs (with the highest values of $\theta$, which do not result to disconnected graphs). As a result, one of the top three regions, where these two graphs better match, is Canada; while United Kingdom is among the top three regions where these graphs are most economically matched (adding the minimum of redundant edges). Moreover, another measure defined is the product of matching to economy, considered as a rough parameter for estimating “slime-optimality” of motorways approximation. In correspondence, the five selected countries cover the whole range from the lowest to high values of that measure.

Table 1 Parameters’ values for the second variation of the model

In order to emulate the laboratory experiments in [47], the nine most populated areas in United Kingdom—Bristol, Sheffield, Nottingham, Liverpool, Tyneside, Greater Glasgow, West Yorkshire, Greater Manchester and West Midlands—are considered as sources of nutrients (NS), while Greater London is chosen to be the initial position of the plasmodium (SP). The topology of the points of interest and the borders in United Kingdom are depicted in Fig. 9a. Figure 9b shows the results of the model ($MR_{UK}$) and Fig. 9c the RNG ($RNG_{UK}$) for the specific topology. It is obvious that the proposed model fully reproduces the RNG, while adding one edge connecting Greater London and Bristol.

Fig. 9

a Topology of cities used as points of interest for United Kingdom. b Model’s output for United Kingdom ($MR_{UK}$). c Relative Neighbour Graph ($RNG_{UK}$). d Physarum graph for $\theta =5/25$ ($PG_{UK}(5/25)$) and e for $\theta =12/25$ ($PG_{UK}(12/25)$) and f original graph of UK motorways [47]

Furthermore, in Fig. 9d and e the Physarum graph is illustrated, as derived from the laboratory experiments in [47], containing edges that appeared more than 5 and 12 times respectively in 25 experiments ($PG_{UK}(5/25)$ and $PG_{UK}(12/25))$. The following equations apply for the graphs illustrated in Fig. 9.

$$\begin{aligned}&RNG_{UK}\subset {MR_{UK}\subset {PG_{UK}(5/25)}} \end{aligned}$$

(19a)

$$\begin{aligned}&PG_{UK}(12/25)\subset {MR_{UK}}+(\text {Greater London, West Mindlands}) \end{aligned}$$

(19b)

Consequently, it can be admitted that in the instance of the United Kingdom, the model produces a graph that includes the RNG, a characteristic also displayed by the plasmodium of Physarum. Moreover, the edges constituting $PG_{UK}(12/25)$, meaning edges that appear with a frequency higher than $\theta =0.48$ in laboratory experiments are included in the graph produced by the model, with the exception of one edge, the one connecting Greater London with West Midlands.

As in the laboratory experiments in [48] where Physarum was imitating Germany motorway network, the 21 most significant areas in Germany—Berlin (1), Hamburg (2), Munich (3), Cologne (4) (including Dusseldorf, Bonn), Frankfurt (5) (including Wiesbaden), Stuttgart (6), Dortmund area (7), Bremen (8), Dresden (9), Hanover (10), Leipzig (11), Nuremberg (12), Bielefeld (13), Mannheim (14), Karlsruhe (15), Mnster (16), Augsburg (17), Aachen (18), Chemnitz (19), Braunschweig (20), Kiel (21)—are considered as points of interest. Note that the numbers next to each area is representative of the area and appear in Fig. 10a. All these areas are represented by sources of nutrients (NS), except from Berlin which is chosen to be the initial position of the plasmodium (SP), as it was in the laboratory experiments. The topology of cities used as an input for the model is illustrated in Fig. 10a. The results of the model are illustrated in Fig. 10b ($MR_{DE}$), along with the RNG for the topology of Germany in Fig. 10c ($RNG_{DE}$).

Fig. 10

a Topology of cities used as points of interest for Germany. b Model’s output for Germany ($MR_{DE}$). c Relative Neighbour Graph ($RNG_{DE}$). d Physarum graph for $\theta =9/22$ ($PG_{DE}(9/22)$) and e for $\theta =15/22$ ($PG_{DE}(15/22)$) and f original motorways graph [48]

Moreover, in Fig. 10d and e the Physarum graphs are illustrated, as they were presented in [48], with edges that are formed more than 9 and 15 times, respectively, in 22 experiments ($PG_{DE}$(9/22) and $PG_{DE}$(15/22)). The following equations are valid for the graphs illustrated in Fig. 10.

$$\begin{aligned}&\begin{aligned} {RNG_{DE}}&\subset {MR_{DE}}\\&\subset {PG_{DE}(9/22)+\left\{ (12,19),(20,11),(1,9)\right\} } \end{aligned}\end{aligned}$$

(20a)

$$\begin{aligned}&PG_{DE}(15/22)\subset {MR_{DE}} \end{aligned}$$

(20b)

As a result, the graph produced by the model ($MR_{DE}$) is a super-graph of the RNG of Germany ($RNG_{DE}$), similarly to the anticipated property of the plasmodium. The graph ($PG_{DE}(15/22)$) constituted by edges with probability $\theta =0.68$ is a sub-graph of the graph produced by the model.

The topology of the 16 higher in population and significant in terms of transportation areas in Canada—Toronto area (1), Montreal area (2), Vancouver area (3), Calgary (4), Edmonton (5), Winnipeg (6), Halifax–Moncton (7), Saskatoon–Regina (8), St. John’s (9), Sudbury (10), Thunder Bay (11), Inuvik (12), Wrigley (13), Yellowknife (14), Thompson (15), Radisson (16)—were used as an input for the model. Note that the numbers next to each area is representative of the area and appear in Fig. 11a. Toronto area is chosen to be the initial position of the plasmodium (SP) and all the others are represented by sources of nutrients (NS), reproducing the configuration from the laboratory experiments [46]. Figure 11a illustrates the topology of the cities and the borders in Canada, and is used as an input for the proposed model. Furthermore in Fig. 11b and c the results from the model ($MR_{CA}$) and the RNG ($RNG_{CA}$) are depicted, respectively. It is obvious that the model reproduces the RNG with the exception of the edge connecting regions 7 and 9. That comes as no surprise, as the borders of the topology are not considered while drawing the RNG. The model also draws 3 more edges.

Fig. 11

a Topology of cities used as points of interest for Canada. b Model’s output for Canada ($MR_{CA}$). c Relative Neighbour Graph ($RNG_{CA}$). d Physarum graph for $\theta =8/23$ ($PG_{CA}(8/23)$) and e for $\theta =17/23$ ($PG_{CA}(17/23)$) and f original graph of Canadian motorways [46]

Figure 11d and e depict the Physarum graph with edges with existence probability of 8/23 and 17/23 respectively ($PG_{CA}$(8/23) and $PG_{CA}$(17/23)). The following equations apply for the graphs illustrated in Fig. 11.

$$\begin{aligned}&\begin{aligned} {RNG_{CA}-{(7,9)}}&\subset {MR_{CA}}\\&\subset {PG_{CA}(8/23)+\left\{ (2,10),(10,16)\right\} } \end{aligned}\end{aligned}$$

(21a)

$$\begin{aligned}&PG_{CA}(17/23)\subset {MR_{CA}} \end{aligned}$$

(21b)

Note that the RNG graph is, once more, re-drawn by the model, although missing the edge connecting regions 7 and 9 together, due to the topology of the borders. Nonetheless, the edges that the protoplasmic network of plasmodium is highly likely to be formed ($\theta =0.74$) are fully reproduced by the model.

Moreover, as in the laboratory experiments using Mexico as a terrain [44], the 19 higher in population areas—Tijuana (1), Nogales (2), Ciudad Juárez (3), Hermosillo (4), Chihuahua (5), Nuevo Laredo (6), Monterrey (7), Mazatlán (8), Ciudad Victoria (9), San Luis Potosí (10), Guadalajara (11), León and Irapuato (12), Morelia (13), Edo. México (14), Xalapa and Veracruz (15), Chilpancingo and Acapulco (16), Oaxaca and Huatulco (17), Tuxtla Gutiérrez (18), Merida and Cancún (19)—are considered as the points of interest. Edo. México is chosen to be the initial position of the plasmodium (SP), in correspondence to the laboratory experiments, and all the others are represented by sources of nutrients (NS). Figure 12a is used as an input to the model and illustrates the topology of Mexico. Figure 12b and c illustrate the results ($MR_{MX}$) and the RNG ($RNG_{MX}$) for the current topology.

Fig. 12

a Topology of cities used as points of interest for Mexico. b Model’s output for Mexico ($MR_{MX}$). c Relative Neighbour Graph ($RNG_{MX}$). d Physarum graph for $\theta =10/26$ ($PG_{MX}(10/26)$) and e for $\theta =16/26$ ($PG_{MX}(16/26)$) and f original graph of Mexican motorways [44]

In Fig. 12d and e the graphs that the plasmodium designed during the laboratory experiments are illustrated, containing edges that appeared more than 10 and 16 times respectively in a total of 26 experiments ($PG_{MX}$(10/26) and $PG_{MX}$(16/26)). The following equations apply for the graphs illustrated in Fig. 12.

$$\begin{aligned}&\begin{aligned} {RNG_{MX}-\{(1,2),(5,8),(15,17)\}}\subset {MR_{MX}}&\subset {PG_{MX}(10/26)}\\&+ \{(14,17),(15,18)\} \end{aligned}\end{aligned}$$

(22a)

$$\begin{aligned}&\begin{aligned} PG_{MX}(16/26)-\{(5,6),(15,17)\}\subset {MR_{MX}} \end{aligned} \end{aligned}$$

(22b)

It is obvious that the model ($MR_{MX}$) reproduces 17 from the 20 edges of the RNG ($RNG_{MX}$) and the edges with high probability ($\theta =0.61$) to be formed by the plasmodium are included in the graph that is derived by the model, with the exception of two edges.

Using the topology of the 23 higher in population areas in Iberian Peninsula—A Coruna (1), Gijon–Ovideo (2), Santander (3), Bilbao (4), San Sebastian (5), Vigo (6), Valladolid (7), Zaragoza (8), Porto (9), Tarragona (10), Barcelona (11), Pombal (12), Madrid (13) (capital of Spain), Valencia (14), Lisboa (15) (capital of Portugal), Alicante (16), Cordoba (17), Murcia (18), Sevilla (19), Faro (20), Granada (21), Malaga–Marbella (22) and Cadiz (23)—the model imitates the behavior of the plasmodium in [45]. Madrid is chosen to be the starting point of the plasmodium (SP), in correspondence to the laboratory experiments, and the others are depicted by sources of nutrients (NS). The topology of the Iberian Peninsula is illustrated in Fig. 13a that is introduced as an input to the model. Figure 13b shows the results of the model ($MR_{IB}$) and Fig. 13c the RNG ($RNG_{IB}$).

Fig. 13

a Topology of cities used as points of interest for Iberia. b Model’s output for Iberia ($MR_{IB}$). c Relative neighbour graph ($RNG_{IB}$). d Physarum graph for $\theta =5/30$ ($PG_{IB}(5/30)$) and e for $\theta =17/30$ ($PG_{IB}(17/30)$) and f original graph of Iberian motorways [45]

Moreover, Fig. 13d and e illustrate the Physarum graphs that is constituted by edges that appeared more than 5 and 17 times, respectively, in 30 experiments ($PG_{IB}$(5/30) and $PG_{IB}$(17/30)). The following equations can be used.

$$\begin{aligned}&\begin{aligned} RNG_{IB}-\left\{ (5,8),(10,14)\right\}&\subset {MR_{IB}}\subset {PG_{IB}(5/30)}\\&+ \left\{ (7,3),(7,9),(7,12),(7,8),(8,13),(13,17)\right\} . \end{aligned}\end{aligned}$$

(23a)

$$\begin{aligned}&PG_{IB}(17/30)-\{(5,8),(15,19),(22,23),(17,21),(10,14)\} \subset {MR_{IB}} \end{aligned}$$

(23b)

Consequently, not taking into account the edges connecting region 5 with region 8 and region 10 with region 14, the RNG ($RNG_{IB}$) is a sub-graph of the graph produced by the model ($MR_{IB}$). The graph produced by the model is a super-graph of the graph $PG_{IB}$(17/30) containing edges with probability $\theta =0.57$, with the exception of five edges.

Finally, the topology of the 16 most populated major urban areas in continental Greece that also have a significant role in today’s Greek transportation network—Athens (1), Volos (2), Larissa (3), Thessaloniki (4), Kavala (5), Alexandroupoli (6), Kozani (7), Xanthi (8), Ioannina (9), Igoumenitsa (10), Tripoli (11), Lamia (12), Patra (13), Korinthos (14), Kalamata (15) and Trikala (16)—was used as input for the model. Athens is chosen to be the initial position of the plasmodium (SP), in correspondence to the laboratory experiments, and all the others are represented by sources of nutrients (NS). Figure 14a is used as an input to the model and illustrates the topology of Greece. Figure 14b and c illustrate the results ($MR_{GR}$) and the RNG ($RNG_{GR}$) for the current topology.

Fig. 14

a Topology of cities used as points of interest for Greece. b Model’s output for Greece ($MR_{GR}$). c Relative Neighbour Graph ($RNG_{GR}$). d Physarum graph for $\theta =6/14$ ($PG_{GR}(6/14)$) and e for $\theta =9/14$ ($PG_{GR}(9/14)$) and f original graph of Greek motorways [21]

In Fig. 14d and e the graphs that the plasmodium designed during the laboratory experiments are illustrated, containing edges that appeared more than 6 and 9 times respectively in a total of 14 experiments ($PG_{GR}$(6/14) and $PG_{GR}$(9/14)). The following equations apply for the graphs illustrated in Fig. 14.

$$\begin{aligned}&\begin{aligned} RNG_{GR}\subset {MR_{GR}}\subset {PG_{GR}(6/14)+\{(7,3),(12,14)\}}. \end{aligned}\end{aligned}$$

(24a)

$$\begin{aligned}&PG_{GR}(9/14)\subset {MR_{GR}} \end{aligned}$$

(24b)

The conclusion from these equations is that the graph produced by the model ($MR_{GR}$) is a super-graph of the RNG of Greece ($RNG_{GR}$), similarly to the key property of the real plasmodium. Furthermore, Physarum graph ($PG_{GR}(9/14)$) constituted by edges with probability $\theta =0.64$ is a sub-graph of the graph produced by the model, thus it recreates the edges with high appearance probability.

5 Discussion

The results of the second variation of the model, as can be easily realized by the aforementioned findings, are better approximating the networks provided by the real plasmodium on laboratory experiments, when compared with the results of the first variation. To sum up the results delivered by the second variation of the model and draw a comparison between the produced graphs and the proximity graph RNG, Physarum graphs and the real motorway networks, Table 2 is presented. The first, second, forth and fifth column depict the number of edges drawn by the proposed CA model, the number of edges in the RNG, Physarum graph and the real Motorway graph, respectively. The third column illustrates the amount of occurrences, throughout the total number of laboratory experiments, of the edges that constitute the Physarum graph that was used as a control. For instance, in the case of United Kingdom the edges that constitute the Physarum graph with high $\theta$, appeared in at least 12 experiments in a total of 25, meaning edges appearing in at least 48 % of the experiments. Finally, the three last columns depict, respectively, the number of edges in the RNG that are not included in the graph provided by the model, the number of edges in the Physarum graph that are not included in the graph provided by the model and the common edges of the Motorway graph and the results of the model.

Table 2 CA model simulation results

These results conclude to the fact that the CA model reproduces RNG in a great degree. The incorporation of the RNG to the final graph is, also, demonstrated by the real slime mould in the laboratory experiments. Consequently, the ability of the model to reproduce the RNG indicates its efficiency in emulating the real slime mould. Moreover, the production of results by the model in a matter of some minutes, compared to the 3–5 days required by the real slime mould implies the robustness of the model’s performance. In the instance of Canada, the existence of unavailable area over the minimum connection between two points of interest causes the loss of an edge and as a result there is a reproduction of the 14 from a total of 15 edges constituting the RNG. Moreover, in the cases of Mexico and the Iberian Peninsula the model constructs 17 from a total of 20 edges and 24 from a total of 26 edges, respectively, that constitute the RNG, representing an error of approximately 15 and 7.7 %, respectively. On the other hand, in the cases of the United Kingdom, Germany and Greece the results of the proposed model incorporate all the edges of RNG.

Furthermore, comparing the results of the model with the results of the laboratory experiments using Physarum as a living computing material, a direct connection can be realized. Physarum graphs with high $\theta$-parameter (0.48–0.74)—meaning consisted of edges with high probability to be constructed by the slime mould—are included in the graphs drawn by the model. More specifically, in the instance of Greece, Germany and Canada, Physarum graphs are entirely reproduced by the model. Moreover in the cases of the United Kingdom and Mexico, one and two edges, respectively, of the Physarum graphs are not reproduced, while for the topology of the Iberian Peninsula five edges of the Physarum graph are not included in the model’s results, corresponding to an error of 20 %.

Also, the last column of Table 2 illustrates the number of edges that are common for the results of the model and the actual motorway network; in specific the intersection of the two graphs. The edges of the intersection of these two graphs are over 50 % of the total edges of the real motorway network. That means that the CA model reproduces the human-made networks with at least 50 % accuracy. Also, the graphs produced by the second variation of the model have no more than 24 % “redundant” edges (not included in the real motorway network).

Although, a weak approximation of human-made networks is realized, the reproduction of the RNG supports the robustness of the proposed model. As illustrated in previous studies [11, 45] the plasmodium produces a more effective transport network, which is not identical to existing motorway networks. That finding is based on the fact that the Relative neighbourhood graph (RNG) is a subgraph of Physarum graph, while the motorway graph is not. Nonetheless, the proposed CA model uses as data only the topology of the points of interest and the available space; however, motorways are designed based on terrain morphology, population distribution, economical and political factors.

Moreover, to calibrate the second variation of the model for all the aforementioned study cases a thorough study on the effects of the values of the CA model parameters was considered. The parameters that were taken into consideration are PMP1, CAP1 and PA, as they are the ones with greater significance in the diffusion equations. The range of parameters PMP1 and CAP1 is defined from 0.01 to 0.12 and for PA from 0 to 1.2. To illustrate the effect, an individual parameter has on the final results, numerous simulations with one of the parameters taking values throughout its range, while the other two are set to constant, are conducted. To test the range of each parameter, increments of 0.01 for parameters PMP1 and CAP1 and 0.1 for PA were used. The networks produced by the model, with parameters altered slightly, have no significant differences and some times are identical. Nevertheless, the results for characteristic values are considered and presented. More specifically, to enumerate the effect that the parameters have on the final graph produced by the CA model, only the topologies of United Kingdom and Iberian Peninsula are shown for readability reasons. Table 3 depicts the number of edges constituting the graph resulting from the model and the intersection between the result and the RNG for different sets of parameters. In every line of Table 3, a typical different set of parameters was given. The values that each parameter took for every experiment is depicted in the first column of Table 3. Moreover, these values are characteristic of the range defined for each parameter and represent a low, a middle and a high value inside that range.

Table 3 CA model simulation results for United Kingdom and Iberian Peninsula with different parameters

It is obvious that for middle values of PMP1 parameter, the results match better the RNG, for the case of United Kingdom. However, for a low value, 11 edges appear but only 7 of them are included in RNG, thus, a lower accuracy is achieved and the 4 redundant edges can be characterized as unwanted noise. Moreover, for greater values of the PMP1 parameter, the model seems to have lower accuracy, too. However, in the case of the Iberian Peninsula, the higher PMP1 parameter yields greater accuracy, as the 24 out of 26 edges of RNG are reproduced. Also, the number of redundant edges increase with higher PMP1 parameters. As far as the CAP1 parameter is concerned, for the United Kingdom, the accuracy is not influenced by the alternation of the parameter, as the nine edges of RNG are reproduced in all cases. On the other hand, middle and high values of that parameter, reflect to adding one redundant edge and, thus, noise. Moreover, for the Iberian Peninsula the CAP1 parameter slightly affects the accuracy of reproducing the RNG, as one edge is omitted for high values of the parameter. Nonetheless, for middle values of the parameter the higher number of edges are drawn and many of them are redundant, namely 6. Finally, the PA parameter has a similar impact with the PMP1 parameter for the topology of the United Kingdom; for a middle value is more accurate, although, the redundant edges added for low and high values of the PA parameter are less than the ones in the case of the PMP1 parameter. For the topology of the Iberian Peninsula, however, the low values of the parameter give more accurate results and with less redundant edges. While for the high value of parameter PA the model reproduces a graph that is the least similar to the RNG, compared with all the other sets of parameters.

Bearing in mind that the RNG of the United Kingdom is consisted of just 9 edges—a relatively small graph, it is save to admit that the results of the model is not affected in a tremendous manner but rather minor changes occur. Thus, the resulting graph of the model is affected by the parameters of the equations, however, the main factor for the results is the topology of points of interest and available area. On the contrary, the RNG of the Iberian Peninsula is a quite complicated graph, with a great number of edges, namely 26. The results of the model for the different sets of parameters seem to have close results; however some of the graphs produced include several edges that do not occur in other experiments. For instance, the two edges of the RNG that were not included to the results of the model as illustrated in Fig. 13c, were produced in several experiments with other parameters. Nonetheless, many of the redundant edges, in some cases, are part of the Physarum graph with low $\theta$. Furthermore, the simulated tubes connecting two points are highly altered for each set of parameters, but as mentioned previously, we do not take into account the exact configuration of the protoplasmic tubes but merely their existence.

After this study, the second variation of the model was used with a fixed set of parameters, as illustrated in Table 1. Although this may sound disadvantageous for the adaptability of the model’s evolution in accordance with the biological processes of Physarum for specific under study cases/man-made transport networks, it has been proved that the CA model succeeds to handle and reproduce the tubular networks in all the examined cases when compared with the expected theoretical and biological results.

6 Conclusions

Using insights gained by the observation of laboratory experiments with the plasmodium of Physarum, two CA models constructing adaptive networks have been proposed. The proposed models mimic the behavior of the plasmodium that spans all NS in an available area, using a topology of NSs and borders of unavailable area that correspond to the geographical topology of cities with great significance in a country. In several previous studies, slime mould have connected all NSs with a protoplasmic tubular network compared with proximity graphs and human–made infrastructures. Consequently, the model results were compared with the proximity graph RNG, the real motorway networks and the graphs drawn by Physarum in equivalent laboratory experiments. As the comparison of these results depicted no major differences between the model and the real Physarum, the proposed CA based model inspired by Physarum can be used as a virtual, easy–to–access laboratory bio-imitation emulator that will economize large time periods needed for biological experiments. Moreover, such a proposed network using the topology of points of interest can be designed automatically in a matter of a few minutes. Specifically, the second variation of the model have been executed for all the examined cases in no more than 10 min on a commercial computer (Intel Core2 Duo @2.26 GHz with 4 GB RAM) using Matlab, while the real slime mould needed 3–5 days to connect all available NSs in the corresponding laboratory experiments on a Petri dish 12 $\times$ 12 cm.

Furthermore, the proposed model is using one CA cell for every point of interest. However, oat flakes used in the laboratory experiments are not dimensionless. As a result, a future work aspect could be the representation of points of interest with groups of CA cells. Moreover, the use of landscape information (like mountains, rivers, lakes) for every place/country as input values for the model can be considered. Using obstacles with several weights for the modeled plasmodium to overcome can simulate the excessive costs of constructing tunnels or bridges in real motorway networks. Finally, the alternation of parameters, used in the diffusion equations for the proposed model, will allow the imitation of different types of plasmodium (old or young) that explore the available area with various speeds, as realized in [11, 51], and different types of nutrient sources that have various attractive forces to the slime mould. Furthermore, and in correspondence to the presented study, different initial parameters will provide different results that would mimic better the RNG and the Physarum graphs for different configurations of points of interest. As a result, a more detailed study for the impact that parameters have in the final results of the model and the physical conditions that they can simulate is a future work aspect. Finally, further enhancement of the proposed CA models could potentially result to many diverse but fruitful applications of slime mould computing [52–54].