Keywords

1 Introduction

Physarum polycephalum is widely used in the last decade as an unconventional computing substrate, because it demonstrates complex behavior, regardless of its apparent simplicity, easy culturing and very low-cost experimentation. In vivo experiments with that biological, massively parallel computing prototype were developed [1]. A plasmodium, the ‘vegetative’ stage of P. polycephalum life cycle, was persuaded to scout for nutrients in its vicinity and link all of them with a tubular network. The importance of the functionality of the tubular network to the survival of the plasmodium (transfer of nutrients, metabolites, and chemical and electrical messages) subjects its actual configuration in rounds of optimization by the actual plasmodium and the local conditions of the experiment. This is the reason why the plasmodium is such a successful paradigm of a biological substrate computer with inputs of geometrical configuration of nutrient sources (NSs) and an output of an interconnected graph [2].

Some examples of the vast range of problems tackled by P. polycephalum [3] are labyrinth solving [4, 5], approximation of Voronoi diagrams and Delaunay triangulation [6], travelling salesman problem [7], simulation of Boolean logic [8] and evaluation of transport [9] and ancient road networks [10]. Nonetheless, the abilities of P. polycephalum inspired scientists to invest efforts towards the simulation of its behavior and its usage to solve complex problems, like designing routes in information networks [11]. Some examples of the computerized approximation of the behavior of the plasmodium are a mathematical model with feedback of the tube dynamics [12], agent–based particle models [13] and cellular automata (CA) [14,15,16] We propose a novel approach towards computerizing the abilities of the slime mould by designing a hybrid model, which combines CA and a multi–agent system is introduced.

Moreover, a rather interesting paradigm of in-vivo experiments utilizing P. polycephalum is the approximation of Kolmogorov–Uspensky machine [17, 18]. Thus, here the results produced from these experiments were used as a control for the novel hybrid model proposed. Kolmogorov and Uspensky [19, 20] proposed that a dynamically changing graph could represent an abstract computing machine. This graph has a finite amount of nodes and the edges between them are not directed. Each of the graph’s nodes are alternatively labelled and only one of the nodes can be activated for a given time step. This structured was initially defined as the Kolmogorov complex and, then, was more commonly known as Kolmogorov-Upsensky machine (KUM). This term will be used hereafter.

KUM is an alternative to the Turing machine, with the main difference of the replacement of the tape of the Turing machine by a graph. Given this geometric substrate of the KUM (the graph), it can accurately mimic growth phenomena and computation influenced by structure in natural systems (like biological systems, chemical systems etc.). An additional meaningful distinction is that whereas the Turing machine was intended to replicate a human-executed computation, the KUM aims to portray “computation as a physical process” [21].

Despite their differences, Turing and KU machines belong the same classes of abstract mathematical machines. A physical implementation of a KUM is searched within biological substrates, like the plasmodium of P. polycephalum [17, 18]. P. polycephalum is an ideal choice for this because of its capacity of exploring and growing in a graph-like configuration and dynamic reshaping of the edges and nodes in the graph.

Moreover, as the plasmodium is stimulated by chemoattractant nutrient sources, utilizing a vast distributed array of membrane–bound sensor proteins, distributed tools were chosen for its simulation, like CA and multi-agent models. In this paper, we focus on the hardware implementation of the proposed hybrid model of P. polycephalum to mimic the physical implementation of a KUM in the plasmodium of P. polycephalum.

2 Description of the CA-Multiagent Model

A new model of CA was developed, in order to combine CA [15, 16], and multi-agent modeling [22]. This new model integrates the parallel nature of CA along with the dynamic behavior in space and time of the multi-agent system without, however, increasing the complexity of the system. The model is computationally simple by using distributed local sensory behaviors, although approaching some of the complex phenomena observed in Physarum. In order to configure Physarum’s adaptive motif, the selected mechanism must be able to adjust its pattern over time, i.e. the pattern must be more flexible to show the emerging properties, which are extensible and can be calculated.

In this model, the inherent flow of the colloidal solution is provided by agent-to-cell mediation, and gel matrix resistance is provided by the agent-agent collisions. The consistency of this set of “crowd” is ensured by the fact that there is mutual attraction to the stimuli deposited by the population of the agents. The directional orientation and movement of the activated plasmodium front is created by coupling the emerging mass behaviors by dragging local source stimuli. Changing the value of cell identities is equivalent to secreting a quantity of chemoattractant during their successful motion and detecting the largest amount in the cell’s neighborhood by three sensors. As a result, they adjust the cell’s angle, so the behavior of other agents can also affect their behavior.

The area of the experiment is divided into a grid of identical square cells, with the side of length equal to \(\alpha \) and represented by a CA assuming that each square element of the surface is a cell of a CA. The width of the neighborhood of (i, j) cell is assumed to be equal to one on both sides, meaning that, we have a Moore neighborhood. The state of the new CA model at time t is:

$$\begin{aligned} C^t_{i,j}=\{griddata^t_{i,j} , trail^t_{i,j} , particle\_ids^t_{i,j} , angle^t_{i,j} \} \end{aligned}$$
(1)

Parameter \(griddata^t_{i,j}\) can get values at time t that indicate whether the cell is a wall or a food stimulus. Referring to \(trail^t_{i,j}\), is the value derived from the food diffusion equation and represents the strength of the smell of the food stimuli at time t in the (i, j) cell. Additionally, \(particle\_ids^t_{i,j}\) is the value of the agent’s (i, j) identity at time t. When there is no agent in the cell, then, as normal, its value is equal to zero. Finally, \(angle^t_{i,j}\) is a variable that shows the angle of the agent in a cell.

Some program variables are specified at the initialization of the model. The main parameters are the amount of agents in the population, grid size, consumption of food value (diffdamp) and the variable that indicates how large the value of the data nodes are. This is displayed as \(griddata^t_{i,j}\) to \(trail^t_{i,j}\) and can get two values, the projectvalue (when there is no agent nearby or on the central cell) or the suppressvalue (when there is at least one agent in the neighborhood of the central cell on which the food is placed).

Subsequently, the agents are placed in random positions within the CA grid with their velocity vectors oriented at random angle values. When a CA neighborhood contains one agent or is fully occupied of agents then the value of the trail value is generated by the equation:

$$\begin{aligned} trail^{t+1}_{i,j}=trail^t_{i,j}+suppressvalue \end{aligned}$$
(2)

Else, if the area is free from agents then it gets the value

$$\begin{aligned} trail^{t+1}_{i,j}=trail^t_{i,j}+projectvalue \end{aligned}$$
(3)

During the evolution of the model, the cell motor behavior is activated to move the agents along their velocity vectors, thus renewing the values of the \(particle\_ids\) and their velocity vectors. The new coordinates of an agent are calculated and an attempt is made to move by one cell in the Moore neighborhood of the central cell (where the agent is located).

$$\begin{aligned} tvi=i+\cos (angle(i,j))\times speed \quad \text {and}\quad tvj=j+\sin (angle(i,j)) \times speed \end{aligned}$$
(4)

If a cell is bound or wall and is selected by an agent to make a move towards it, then that agent will not move to that cell but the angle of the velocity vector will be renewed to a random value, i.e. \(angle^{t+1}_{i,j}=random() \times 360\). However, if all the prerequisites are met in order to make a movement, the value of the agent’s identifier of the given cell will be given to the new cell, as well as its angle, and the trail value will be renewed by increasing it by an amount depT. This will be an attractive means for other agents to move towards it in order to create a single structure as the biological organism.

$$\begin{aligned} \begin{aligned}&particle\_ids^{t+1}_{i,j}=particle\_ids^{t}_{i+1,j+1} \\&angle^{t+1}_{i,j}=angle^{t}_{i+1,j+1} \\&trail^{t+1}_{i,j}=trail^{t}_{i,j}+depT \end{aligned} \end{aligned}$$
(5)

The algorithm proceeds by calculating the sensory inputs of the cells. Each cell containing an agent has 3 sensors that are located in the neighborhood of this cell in the direction of the agent’s angle. The neighborhood could be larger, e.g. by integrating all the cells that are spaced \(2, 3, \ldots \) cells away from the central one. Moreover, this would act as an escalation parameter in a large CA, a cell would receive values in its sensors from a more distant area and could direct its agent towards that direction (Fig. 1).

Fig. 1.
figure 1

Placement of 3 sensors in the Moore neighborhood of the cell according to its angle.

Full size image

The sensors receive the trail values of neighboring cells in which they are located. Then those three variables are compared, in order to decide the highest food value from the trail of the neighboring cells. The prevailing sensor, will be the one who will also indicate which direction the agent should follow to reach the point of feeding.

If f sensor has the highest value, then the cell’s angle retains the same value. If the value of f is less than the other two, then if fl is less than f, \(angle^{t+1}_{i,j}=angle^{t}_{i,j}+45\), otherwise, if fr is less than fl then \(angle^{t+1}_{i,j}=angle^{t}_{i,j}-45\). Finally, if f is greater than fl and less than fr then \(angle^{t+1}_{i,j}=angle^{t}_{i,j}+45\), otherwise, if f is greater than fr and less than fl then \(angle^{t+1}_{i,j}=angle^{t}_{i,j}-45\).

The final step of the algorithm is to update the trail of each cell, where its value is given by the equation of food diffusion.

$$\begin{aligned} \begin{aligned} trail^{t+1}_{i,j}=\{ ( trail^{t}_{i-1,j-1}+trail^{t}_{i,j-1}+ trail^{t}_{i+1,j-1}+ trail^{t}_{i-1,j}+ trail^{t}_{i,j}+ \\ trail^{t}_{i+1,j}+trail^{t}_{i-1,j+1}+ trail^{t}_{i,j+1}+ trail^{t}_{i+1,j+1} )/9 * (1-diffamp) \} \end{aligned} \end{aligned}$$
(6)

3 Hardware Implementation of the Proposed Model

The proposed hardware system is comprised of the same basic structure representing a CA cell. Each cell circuit (Fig. 2) is interconnected with other cells in its vicinity.

Fig. 2.
figure 2

Input and output signals of the circuit generated by the VHDL code.

Full size image

This circuit is equipped with 46 inputs and 19 outputs. As inputs we consider eight signals, 9 bits each, that indicate an integer from 0 to 511, representing the identifier number of the agents; eight signals, 9 bits each, that indicate an integer number with range from 0 to 511, which represents the food value; eight signals, 9 bits each, that indicate an integer number ranging from 0 to 360, representing the angle of agents in the CA; eight signals one bit each, needed to inform the cell that an agent is going to move in its direction.

Eight additional signals one bit each that inform the central cell that the agent cannot move to a neighboring cell; an 8-bit signal used to characterize the central cell (\(food = 255\), \(wall = 51\), \(normal cell = 0\)); two signals, 9 bits each that are used to initialize agents and angles in the grid and three signals, 1 bit each for clk, reset and initialize.

As outputs there are eight signals, one bit each to inform neighbors that the agent will move in that direction; eight signals, one bit each indicating that the central cell is free to receive an agent and three signals, 9 bits each, which represent the identifier, the angle and the smell of the food in the central cell.

Firstly, initialize signal is set high, for cells to obtain random values needed. In the first stage, the cell in which the food stimuli is found, renews the trail value by noticing whether there is an agent in the neighborhood. The following stage is the motor behavior where each cell will signal if there is an agent to attempt to move in the direction which is indicated by the angle. If the agent cannot move, then the angle will be modified to a random value and the algorithm will continue.

However, if the agent can move, then the central cell will raise a flag to inform its neighbors. Two additional steps in relation to the software code are introduced to check whether two or more agents attempt to move to the central cell. In the next stage, if the previous prerequisites are met, the agent’s identifier and angle of the neighboring cell will be transferred to the central cell and its trace value will be increased by depT. Afterwards, the sensory behavior of the food and the adjustment of the angle of each cell are followed. Direction is indicated by the higher smell of food detected by the sensors. Sensors f, fl and fr receive the trail of the neighboring cells and the front is impacted by the angle of the central cell. The final stage is the food diffusion equation.

A \(n\times {n}\) grid of cells is designed and interconnected Then the grid circuit received the following input signals: \(p+1\) \((0\le {p}\le {511})\) signals, 9 bits each, that indicate an integer with range from 0 to 511. These signals are used to load agents’ identifiers into different cells within the grid. Another \(p + 1\) signals are used to give angle values in the cells. An 8-bit signal set to zero, i.e. to the absence of food in a cell and another one 8-bit signal corresponding to the number 255 and given to the cells that we intend to have food stimulus. Three signals, one bit each corresponding to clk, reset and initialize. The outputs are \(n\times {n}\) signals, 9 bits each representing the ID number of the agent in each cell of the grid.

In order to prove that the software program and the CA hardware circuit generated by the VHDL code have the same behavior, the following section presents the results of trying to create a Kolmogorov–Uspensky machine.

4 Simulation Results

In this section, the proposed CA–multiagent model will be used to reproduce functions Fuse and Mult. These functions are characteristic of the Physarum machine presented in [18], which mimics universal storage modification machines, like the Kolmogorov-Uspensky machine. The CA is selected to have a size of \(20\times 20\). The agents are placed in random locations and with random angles. The deposition value of the chemoattractant is equal to one for each successive transfer of the particle’s identifier from one cell to another. The input signals given to the system designed with the VHDL code were: the period of the clk signal is set to 1 ns, the rst signal for 9 ns equal to 1 and then 0, the initialize signal equal to one for 10 ns and then equal to 0.

The experimental operations with the active zones as recorded by Adamatzky and Jones [17, 18] were used as verification of the model.

Initialization of the CA is illustrated in Fig. 3a for the software model and in Fig. 3c for the hardware model. It is noted that cell values that are closer to food sources will modify their status and will undergo changes in both identifiers and angles. As already mentioned the output signals are 400, so for convenience, all the changes noted in the cells are shown in a table. In the example of Fig. 3, each agent has a sensory behavior of a larger neighborhood (3 cells), so that it can detect the smell of the food of another cell on the grid without staying only around a constant food stimuli. The pieces of plasmodium are attracted by the food sources (red color) and plasmodium spots are created around these sources. The food stimuli are initially placed in the cells (4, 10) and (17, 10).

Fig. 3.
figure 3

Output of the model in software (a, b) and in hardware (c, d) with initial and final positions of agents.

Full size image
Fig. 4.
figure 4

The Fuse operation in software (a, b) and in hardware (c, d).

Full size image
Fig. 5.
figure 5

(adopted from [18]).

The Mult operation of the Physarum machine

Full size image

By comparing these two models, we observed that they present similar results. On the other hand, the time spent by the CA circuit to form the result (554 ns) is much less than the time spent in the software (0.3381 s).

In the following, a new stimulus is placed to attract the plasmodium in its location. The new food source is installed in cell (10, 10). The growing plasmodium is attracted by the inner source and the propagation continues inwards from each initial source (Fig. 4). These two active zones fuse and retain a structure spanning the array of nodes. After a few time steps, it is observed that the cells near the new food source are starting to change their ID values, which means that the active zones migrate in these directions. In software the chain structure is formed at 0.7366 s (Fig. 4b), while in hardware at 786 ns (Fig. 4d).

An example is displayed in Fig. 5, given a food source chain where the plasmodium has formed protoplasmic tubes, two oat flakes can be added right and left and cause new active zones (Fig. 5a). After 10 h, 2 new active zones A1 and A2 are formed (Fig. 5b).

Using the chain structure created by the previous method (Fig. 4) two additional food sources are added to each side of the array, at points (10, 6) and (10, 14). Two active fronts were produced to engulf the sources (Fig. 6). In Fig. 6 is illustrated the function Mult of physarum machine, some agents will gradually become aware of the existence of new food stimuli and will start moving in that direction developing a diamond area.

Fig. 6.
figure 6

(a, b, c, d). Mult operation of the virtual model. At the time of 1.5628 s the formation result for the software program (top) is produced, while for the program that is designed with hardware description language (below) the formation of the network is generated at 850 ns.

Full size image

5 Conclusions

A novel hybrid model was used to approximate the computing abilities of a (geometrically represented) biological substrate, namely the plasmodium of P. polycephalum. The model proposed here is a CA-based method incorporating a multi–agent system. The results of the computerized plasmodium were closely imitating the results obtained from in vivo experimental studies. The developed methodology was implemented in software as well as in hardware. The motivation was the fact that the parallel nature of CA is lost in the software implementation. The higher the complexity of the problem, the longer it will take to be resolved. Whereas, the circuit generated by the VHDL code uses the advantage of parallel processing and, therefore, solves the problem within a vast range of complexity, using the resources for a given amount of time.