Abstract
The giant amoeboid organism true slime mould Physarum polycephalum dynamically adapts its body plan in response to changing environmental conditions and its protoplasmic transport network is used to distribute nutrients within the organism. These networks are ecient in terms of network length and network resilience and are parallel approximations of a range of proximity graphs and plane division problems. The complex parallel distributed computation exhibited by this simple organism has since served as an inspiration for intensive research into distributed computing and robotics within the last decade. P. polycephalum may be considered as a spatially represented parallel unconventional computing substrate, but how can this`computer' be programmed? In this paper we examine and catalogue individual low-level mechanisms which may be used to induce network formation and adaptation in a multi-agent model of P. polycephalum.
These mechanisms include those intrinsic to the model (particle sensor angle, rotation angle, and scaling parameters) and those mediated by the environment (stimulus location, distance, angle, concentration, engulfment and consumption of nutrients, and the presence of simulated light irradiation, repellents and obstacles). The mechanisms induce a concurrent integration of chemoattractant and chemorepellent gradients diusing within the 2D lattice upon which the agent population resides, stimulating growth, movement, morphological adaptation and network minimisation. Chemoattractant gradients, and their modulation by the engulfment and consumption of nutrients by the model population, represent an ecient outsourcing of spatial computation. The mechanisms may prove useful in understanding the search strategies and adaptation of distributed organisms within their environment, in understanding the minimal requirements for complex adaptive behaviours, and in developing methods of spatially programming parallel unconventional computers and robotic devices.
Introduction
The true slime mould Physarum polycephalum is a single-celled organism with a very complex life cycle. The plasmodium stage, where a giant syncytium formed by repeated nuclear division is encompassed within a single membrane, has been shown to exhibit a complex range of biological and computational behaviours.
The plasmodium of P. polycephalum is a membrane-bound syncytium of nuclei within a cytoplasm comprised of a complex gel/sol network. The gel phase is composed of a sponge-like matrix of contractile actin and myosin bres through which the protoplasmic sol ows. Local oscillations in the thickness of the plasmodium spontaneously appear with approximately 2 minutes duration [1] . The spatial and temporal organisation of the oscillations has been shown to be extremely complex [2] and aects the internal movement of sol through the network by local assembly and disassembly of the actin-myosin structures. The protoplasm moves backwards and forwards within the plasmodium in a characteristic manner known as shuttlestreaming.
The plasmodium is able to sense local concentration gradients and the presence of nutrient gradients appears to alter the structure of external membrane areas. The softening of the outer membrane causes a ux of protoplasm towards the general direction of the gradient in response to internal pressure changes caused by the local thickness oscillations. The strong coupling between membrane contraction and streaming movement is caused by the incompressibility of the uid requiring a constant volume -the weakening of the membrane provides an outlet for the pressure. When the plasmodium has located and engulfed nearby food sources, protoplasmic veins appear within the plasmodium, connecting the food sources.
The veins transport protoplasm amongst the distributed extremes of the organism.
The relative simplicity of the cell and the distributed nature of its control system make P. polycephalum a suitable subject for research into distributed computation substrates. In recent years there have been a large number of studies investigating its computational abilities, prompted by Nakagaki et al. who reported the ability of P. polycephalum to solve path planning problems [3] . Subsequent research conrmed and broadened the range of abilities to spatial representations of various graph problems [4, 5, 6] , combinatorial optimisation problems [7] , construction of logic gates [8] and logical machines [9] , [10] , and as a means to achieve distributed robotic control [11] , robotic manipulation [12] and robotic amoeboid movement [13] , [14] .
From a pattern formation perspective, P. polycephalum can be interpreted as a complex mechanism of dynamical pattern formation based upon the two requirements of eciency in foraging behaviour (searching of a maximal area) and eciency in nutrient transport (minimal transport distance and fault tolerance) [15] .
The mechanisms used to full these requirements are growth, movement and area reduction. During the growth/foraging stage the plasmodium exhibits a`default' broadly reticulated outward growth pattern -the homogeneity of the growing plasmodium fragments to form the reticular network [16] . On nutrient rich substrates the growth is typically wave-like and expansive but on nutrient poor substrates the growth is dendritic. There is no strict separation of the two behaviours, however, and both growth types may be observed experimentally in the same environment subject to small local dierences in humidity, substrate hardness, substrate roughness or temperature. The foraging plasmodium forms a protoplasmic tube network behind the growth front used to transport nutrients within the organism. Once all nutrients have been located, the topology of the pattern (the protoplasmic tube network) is inuenced by the nutrient distribution. The tube network evolves to achieve a compromise between minimal transport costs and fault tolerance [4] . Since the plasmodium obviously cannot have any global knowledge about the initial or optimal topology, the network must evolve by physical forces acting locally on the protoplasmic transport.
In this paper we give an overview of intrinsic mechanisms (model parameters) and external mechanisms (environmental inuences) that can inuence the behaviour and pattern formation properties of a multi-agent model of P. polycephalum.
In Section 2 we give an over view of models of P. polycephalum. In Section 3 we describe the multi-agent model used in this paper. Intrinsic model parameters affecting network formation are described in Section 4. Environmental mechanisms aecting network formation and adaptation are described in Section 5. In Section 6 we show examples of how such mechanisms can be employed and combined for the approximation of spatially represented computing problems.
2. Modelling the Behaviour of P. polycephalum Tero et al. have suggested that protoplasmic ux through the network veins may be cause the physical basis for evolution of the transport network: given ux through two paths, the shorter path will receive more sol ux. By generating an autocatalytic mechanism to reward veins with greater ux (by thickening/widening them) and to apply a cost to veins with less ux (the veins become thinner), shorter veins begin to predominate as the network evolves. This approach was used for the mathematical model of P. polycephalum network behaviour to solve path planning problems [17] .
This method indirectly supports the reaction-diusion inspired notions of local activation (strengthening of shorter tubes) and lateral inhibition (weakening of longer tube paths). The starting point for the model of Tero et al. is a randomly connected protoplasmic tube network, surrounding a number of food sources (network nodes) which act as sources and sinks of ux. By beginning with a complete network this method, although successful in generating impressive solutions to network problems, sidesteps the issues and mechanisms of initial network formation and adaptation to a changing nutrient environment.
Gunji et al. introduced a cellular automaton (CA) model which considered both plasmodial growth and amoeboid movement [18, 15] . The model placed importance on the transformation of hardness/softness at the membrane and the internal transport of material from the membrane resulting in movement and network adaptation. The model was also able to approximate instances of maze path planning and coarse approximations of the Steiner tree problem.
Takamatsu's hexagonal CA [16] mimics the growth patterns displayed under diering nutrient concentrations and substrate hardness. The patterns reect experimental results well but do not (at least at this stage -oscillatory behaviour is in development) show morphological adaptation as the plasmodium grows. Hickey and Noriega adapted a classical ant colony optimisation algorithm to modify a decision tree in their representation of P. polycephalum behaviour in a simple path planning problem [19] . Their algorithm (as with many implementations of ant algorithms) transformed the spatial representation into a graph representation and provided broadly similar results to path optimisation by P. polycephalum. P. polycephalum may be interpreted as a spatially represented embodied form of parallel and distributed unconventional computation. In this form of unconventional or non-classical computation, the computation is embodied within, and performed by, physical processes within living (or indeed non-living [20] ) materials [21] . Unlike the symbolic algorithms used to control classical computing devices, problems and their solutions are represented as spatial patterns. The process of computing the problem is typically performed by propagation of information throughout the substrate until a nal or stable state is reached. The distributed control and the simple parallel nature of its component parts comprising P. polycephalum render it an attractive candidate material for synthetic collective computation and soft-robotics applications. In order to utilise this`material' for useful computation we must nd mechanisms and methods to induce morphological adaptation. Such mechanisms will lead to the ability to`program' the material to solve useful problems. AS P. polycephalum is a living organism, it suers from problems of speed, repeatability, and the unpredictability and relative fragility associated with biological systems. A suitable model is required, however one which is also composed of relatively simple parts, utilises local interactions and demonstrates distributed control of its behaviour.
A Multi-agent Model of P. polycephalum
Although slime mould has enviable computational properties, it also has limitations due to the fact that it is a living organism. Although relatively easy and inexpensive to culture, slime mould is also relatively slow (certainly compared to silicon computing substrates) and must be maintained within strict environmental parameters of temperature, light exposure and humidity. Slime mould may also be relatively unpredictable in its behaviour. Although the unpredictability is useful in certain circumstances it can be a hindrance when repeatable measures of its performance are required. We therefore require a synthetic analogue of slime mould.
One technique available is computer modelling, where we attempt to reproduce the complex patterning of slime mould along with the complex interactions it has with its environment. In [22] we introduced a large population of simple components, mobile agents, (a schematic view of a single agent is shown in Fig. 1 represented attractant stimuli (i.e. nutrients) and negative values (below zero) represented repellent stimuli. The eect of nutrient stimuli is to attract nearby agents and the network adaptation is constrained by the attraction to the nutrients. The resulting network structures (nutrient stimuli representing graph vertices and network trails representing edges) show minimisation behaviour and formed proximity graphs with the same properties as those observed in P. polycephalum [23] (as an example see the stabilised networks in Fig. 6 ). Repellent stimuli cause the networks formed by the agent population to avoid repellents, with the resultant networks approximating plane division problems such as Voronoi diagrams [24] . The collective behaves as a virtual material demonstrating characteristic network evolution motifs and minimisation phenomena seen in soap lm evolution, for example the formation of Plateau angles, T1 and T2 relaxation processes and adherence to von Neumann's law (Fig. 3 ).
Model Parametric Mechanisms Inducing Changes in

Morphological Adaptation
Dierent parametric settings within the model (although not changing the underlying algorithm for each agent) can aect the pattern formation properties of the model, altering both network structure and the evolution of the networks, even without the eect of external environmental stimuli.
Variations in Sensory Parameters
Variations of the agent sensor angle and agent rotation angle (See schematic of a single agent particle in Fig. 1 ) result in a wide range of reaction-diusion type patterns [25] (see Fig. 4 for an overall visualisation of the SA/RA parameter space).
How might these dierent patterns, all arising from the same particle behaviour, relate to P. polycephalum ? One possible relationship is the dierent pattern types seen in P. polycephalum under dierent environmental conditions, such as substrate hardness and nutrient concentration which both aect the patterning properties of the organism [16] . 
SA 90
• , RA 45 • ) result in networks disassembling to form discrete island patterns
Variations in the Scaling Parameter
The eect of the sensor scale parameter on graph evolution is also signicant. Larger sensor oset distance (SO, in pixels) results in thicker network paths, faster network evolution, and coarse-grained networks, where each edge encompasses many data points ( Fig. 6a ). Decreasing the SO parameter results in more ne-grained graphs with more edges and cycles connecting nearby data points ( Fig. 6b and c).
Environmental Mechanisms Inducing Changes in Morphological Adaptation
Graph transformation in classical computing is typically achieved by changing the algorithm operating on a set of source data (for example data points representing graph vertices). Dierent algorithms operating on the same dataset will construct (b) t=1000 (c) t=2000 . Eect of sensor scale on network structure. particles inoculated at random positions amongst 100 nodes and nal pattern recorded after 5000 scheduler steps. a) SO 15 gives very coarse-grained networks which pass between paths of nearby nodes, b) SO 10 gives thicker paths and fewer cycles, c) SO 5 results in ne-grained networks passing through the data points.
Growth of P. polycephalum is dependent on the availability, concentration and placement of nutrient sources in the environment. The plasmodium membrane is sensitive to diusion gradients and preferentially grows towards nearby sources of nutrients by extending pseudopodia towards the nutrients. On nutrient poor conditions (damp lter paper and oat ake food nodes) P. polycephalum initially constructs a spanning tree when inoculated at a single site and constructs networks relating to the upper ranges of the Toussaint hierarchy of proximity graphs when inoculated at multiple sites [6] . To assess the eect of chemoattractant diusion, nutrient concentration and nutrient placement on the growth in the particle model we inoculated a small population at a simulated food source -a stimulus value projected onto the diusion eld at regular intervals. We assumed (as in [6] ) that any food sources covered by the model plasmodium would suppress the diusion of chemoattractant from that source. 
Avoidance of Light Irradiation and Repellents
Avoidance of light irradiation and chemorepellents was implemented in the model by decreasing the chemoattractant detected by the agent sensors by multiplying by a weighting factor in areas of the arena exposed to values corresponding to light exposure (L d , weight factor from 0 to 1, default of 0.2) and repellents (R d , weight factor from 0 to −1, default -0.2) respectively. Fig. 8 illustrates the response of both xed and adaptive population sizes to simulated light hazards, in this case vertically placed bars obstructing a straight path between two nutrient sources. For xed populations the population shifts the bulk of its shape away from illuminated regions (Fig. 8, left) . In adaptive populations the model plasmodium curves around the light obstacles to connect the two nutrient sources at opposite sides of the arena (Fig. 8, right) , thus reproducing the collision-free path planning by P. polycephalum reported in [26] .
When growing in an environment containing both nutrients and repellents the model avoided the repellent regions (light squares) whilst growing towards and consuming nutrients (dark squares) in the arena (Fig. 9 ). 
The Presence of Passive Obstacles
In the previous example the removal of a nutrient source occurred in open space as changes in the diusive lattice were propagated towards the particle network.
However the retraction of the virtual pseudopodia also occurs when the environment is patterned with obstacles which cannot be occupied (in P. polycephalum such areas include agar covered in dry plastic lm, such as the`dead-ends' in the mazed in [3] ).
Even in the presence of obstacles, however, the pseudopodia can retract from areas devoid of nutrients as demonstrated in Fig. 10 in which the model slime mould is initialised in a T-shape which contains only two nutrient sources at the extremal points of two channels. At the other channel the collective forms a pseudopodium which retracts away from the region devoid of stimuli, following the channel bounded by the obstacles (Fig. 10,c-d ). Eventually this pseudopodium completely retracts and merges with the stable path connecting the two nutrients (Fig. 10,e) . 
Nutrient Distance
As the growing population discovers new food sources the transport network automatically adapts its shape in response to the new nutrient sources. Fig. 12 shows the network adaptation as information about the food locations (in the form of diusing chemoattractant gradient elds) arrives at the inoculation point at dierent times due to their increasing distance. The network adapts in response to the changing environment by extending pseudopodia towards the nutrient sources as they are encountered and constructing a transport network connecting the nutrients. The collective then minimises the network distance when all the food is located.
Nutrient Angle
The attraction of the multi-agent transport networks to discrete stimuli in the lattice causes the network adaptation to be constrained as the networks are`snagged' at the stimulus locations. The constraining eect is dependent on the angle between the outer two nutrient points connected to the central nutrient point (Fig. 13) . At large angles, the two ows connecting the outer points pass through the central point (Fig. 13, top) . As the angle is decreased, however, the two separate particle ows become closer to each other (Fig. 13, middle) . Eventually the two ows merge and, if the attraction of the ows is greater than the attraction to the central point, the network detaches partially, in a zipping motif, from the central point [23] . A new path connects the central point to the zipping paths and a Steiner point is formed at this new junction (Fig. 13, bottom) . The position of this point eventually stabilises at a location which minimises the distance between all three nodes. Note that if the Steiner point is still relatively close to the original node, a large increase 
Nutrient Size and Concentration
The eect of nutrient size and nutrient concentration was studied in the particle model by inoculating a small population at the centre of a circular arena surrounded by four food sources at identical distances (Fig. 14) . Each image in the gure shows the concentration gradients (left side of each image) and the particle positions (right side). When nutrient sources were the same size and concentration the particle collective grew by extending pseudopodia towards the food sources at the same time (Fig. 14, left column) . When the pseudopodia reached the nutrients the engulfment suppressed the projection of nutrients into the arena and reduced the concentration gradients. When the nutrients were at dierent concentrations the pseudopodia were preferentially extended in the direction of the strongest nutrients rst. Pseudopodia were only extended to the remaining nutrients (in decreasing order of concentration) when the gradient of the previous nutrient block was suppressed by engulfment.
When all sources had been located network adaptation took place (Fig. 14, middle column). When the nutrients varied in size only, the concentration gradients from the larger nutrient blocks were larger and pseudopodia were again extended to the nutrients with higher concentrations rst. After all nutrients had been discovered the network adapted again to cover the regions of the nutrients but the mass of the population was shifted towards the position of the largest nutrient block (Fig. 14, right column, bottom image). Even the quality of the nutrients can aect the growth of the plasmodium patterns [27] . The eects of such complex interactions between spatial position, concentration and consumption in the model are shown in Fig. 15 . The examples show an initial inoculation site at the bottom centre of a circular arena. Above the inoculation site are three nutrient sources of identical size but potentially dierent concentration (pixel intensity 255 or 50). In Fig. 15a ) all three nutrients are identical and the pseudopodium grows towards the closest source and extends further pseudopodia as the middle nutrient is consumed and gradients from the side nutrients reach the collective. A similar situation occurs in Fig. 15b ) but the migration from the central nutrient is delayed because the nutrient is of higher concentration than the outer nodes and its consumption takes longer. In Fig. 15c ) both outer nutrients are of higher concentration and, although the collective initially grows towards the closer central node, the mass of the collective extends towards the outer nodes as the gradient is stronger. In example Fig. 15d ) the growth of the collective towards the central nutrient node is waylaid by the stronger attraction towards the left node. Extension towards the rightmost node only occurs after the majority of the left node has been consumed. Finally, in Fig. 15e ) the collective grows towards the (closest) central node and then to the leftmost node which is equal in strength.
Growth towards the node on the right only occurs when the other nodes are mostly depleted.
Background Substrate Concentration
The emergent transport networks formed by the microscopic interactions of the particle population with their environment reect not only static pattern morphologies adopted by the P. polycephalum plasmodium, but also the long term network adaptation seen in the organism. P. polycephalum morphology, evolution and behaviours are strongly aected by the availability, location and concentration of nutrients. The organism appears to behave in a manner which initially optimises (maximises) area exploration and which later adapts its network by optimising (minimising) network distance and network resiliency to damage. The growth and adaptation morphology of P. polycephalum also depends on the nutrient concentration of the growth substrate itself -rich background environments (for example, oatmeal agar) generate orid wave-like radial expansive growth whereas nutrient poor environments (for example, dampened lter paper) result in tree-like dendritic growth. Although attempting to characterise the behaviour of such dierent growth types runs the risk of anthropomorphism, the wave-like (nutrient rich) behaviours appear more aggressive in terms of the apparent speed of growth and rapid area coverage. The dendritic (nutrient poor) behaviours appear almost tentative in terms of growth The same morphological and apparent behavioural eects were observed in the particle model when background environmental conditions were modied. Fig. 16 and Fig. 17 show the eects of high and low concentrations of background nutrient substrates on the morphology and collective behaviours of the particle population.
The environment is represented by discrete oat akes (white circles) and nutrient rich oatmeal agar medium background (grey background). In both experiments identical geometric congurations were used in the environment (i.e. the placement of simulated oat akes were identical), but the concentrations of the background substrate were dierent. In both cases the population grows as the environment is searched for nutrients. After the search is complete, and background nutrients exhausted, both conditions spontaneously undergo network contraction and minimisation until minimal network congurations are achieved. In the high concentration condition (Fig. 16 ) the growth is wave-like and expansive and the nal network conguration resembles a relative neighbourhood graph with a number of cycles in the network. The growth in low concentration background condition (Fig. 17) shows dendritic growth patterns and the search of the environment is slower. The nal network conguration is also more tree-like with only a small inner cycle.
The cause of the dierences in growth and adaptation patterns is the background nutrient concentration. In the high concentration condition, the background presents a stronger stimulus to the periphery of the model plasmodium and the`pull' of the environment causes expansive movement outwards and provides space for growth.
As nutrients are depleted by the outwardly moving population, the background stimulus moves further outward from the edge of the collective and the outer regions of When inoculated at a single food source and surrounded by isolated nutrients with no stimuli from the background substrate the behaviour of the model plasmodium mimics that of the real organism by locating nearby sources of food as the chemoattractant gradient from each source propagates outwards, surging towards the nutrients with pseudopodium growth, engulng them, and constructing a network which approximates a Steiner tree (Fig. 19, bottom) . The foraging and minimisation behaviour of the model closely approximates the behaviour of P. polycephalum (as shown in Fig. 19, top) . The low-level mechanisms have been presented in isolation in each section but they can also be combined (for example combinations of attractants and repellents, or combinations of high and low concentration stimuli) to give the necessary computation. The innate pattern formation and inuencing mechanisms may also require dierent initialisation mechanisms and be subject to external control systems in order to guide the evolution towards the desired problem outcome. In this section we present an overview of example problems that can be approximated by the material adaptation approach using some of the mechanisms described in Sections 4 and 5.
Proximity Graph Problems
Approximation of proximity graphs is a natural application of the model, since P. polycephalum networks approximate these graphs [28, 6] . The model transport networks also approximate graphs in the Toussaint hierarchy [29] , the particular type depending on nutrient concentration but typically match Relative Neighbourhood Graphs [23] . The model may be initialised on a single node, constructing the graphs as it detects and engulfs the nodes (as in Fig. 11 and Fig. 19 ). Alternatively the model may be initialised at random positions. After initialisation a network self-assembles between the data points and subsequently evolves to minimise the number of edges (Fig. 20a) . When initialised as a solid mass of particles and undergoing gradual shrinkage, the`blob' of model plasmodium minimises down the Toussaint hierarchy to construct a Spanning Tree at high nutrient concentration (Fig. 20h) or a Steiner Tree at low nutrient concentration (Fig. 20i). 
Convex Hull
The Convex Hull of a set of points is the smallest convex polygon enclosing the set, where all points are on the boundary or interior of the polygon. Classical algorithms to generate Convex Hulls may be inspired by intuitively mechanical methods, such as shrink wrapping an elastic band around the set of points, or rotating calipers around the set of points [30, 31] . It is possible to approximate the convex hull using the model plasmodium by initialising the population as a circular ring of model plasmodium outside the points (Fig. 21) , to represent a deformable elastic material. This bounding`band' then shrinks to encompass the outer region of the Firstly, the bounds of the set of points must be known in advance. Secondly, points which are inside the hull, but close to the`band' (for example near the top edge in the third image of Fig. 21 ) may attract the band inwards, forming a concavity. Alternatively it is possible to have the`band' shrink around the array of points which are actually repulsive to the band. This is achieved by projecting a repellent source at all nutrient node locations. The band will shrink towards the nodes but will not actually touch the nodes. This generates a hull which encompasses the nodes but does not directly touch them (Fig. 22) . If the boundary of the hull points is not known then it is possible to utilise a method which employs self-organisation and repulsion to approximate the hull, as shown in Fig. 23 . In this approach the particle population is initialised at random locations within the lattice. The particles are repulsed by the chemorepulsive nodes and move away from these regions. If a particle touches a node it is annihilated and randomly initialised to a new blank part of the lattice. Over time, the inner region of the lattice becomes less frequently habited by particles but in contrast the outer region (whose border is away from the repulsive region) becomes more populous.
The increasing strength of the emerging hull trail attracts particles from inside the region (because the deposited`ring' of ux is more attractive than the inner region) and the particles are drawn out into this ring. The natural contraction of the ring approximates the nal convex hull. 
Concave Hull
The Concave Hull is the area occupied by, or the`shape' of, a set of points is not as simple to dene as its convex hull. It can be considered as the minimum region (or footprint [32] ) occupied by a set of points, which cannot, in some cases, be represented correctly by the convex hull [33] . For example, a set of points arranged to form the capital letter`C' would not be correctly represented by the convex hull because the gap in the letter would be closed (Fig. 25a) . Attempts to formalise concave bounding representations of a set of points were suggested in the denition of α-shapes [34] . The α-shape of a set of points, P , is an intersection of the complement of all closed discs of radius 1/α that includes no points of P . An α-shape is a convex hull when α → ∞ (Fig. 24a) . When decreasing α, the shapes may shrink, develop holes and become disconnected ( Fig. 24b-d ), collapsing to P when α → 0.
A concave hull is non-convex polygon representing area occupied by P . A concave hull is a connected α-shape without holes.
The model plasmodium approximates the concave hull via its automatic morphological adaptation as the population size is reduced. The reduction in population size may be implemented by adjusting the growth shrinkage parameters to bias adaptation towards shrinkage whilst maintaining network connectivity. In the examples shown below the model plasmodium is initialised as a large population within the connes of a Convex Hull (calculated using an algorithmic method) of a set of points (Fig. 25b) . By slowly reducing the population size, via biasing parameters towards shrinkage, the model plasmodium adapts its shape as it shrinks. Retention to nodes is ensured by chemoattractant projection and as the population continues to reduce, the shape outlined by the population becomes increasingly concave (Fig. 25c-f ).
The graph of changing population size as the model plasmodium adapts (Fig. 26) shows that the population stabilises as the concave shape is adopted. If varying degrees of concavity are required, the current population size as a fraction of the original size, or alternatively the rate of population decline, could possibly be used as a simple parameter to tune the desired concavity.
The shrinkage of a solid mass of model plasmodium cannot construct α-shapes, shapes with vacant regions within them, for example as with the letter`A'. However, by initialising the population at the node sites themselves, the individual fragments of`plasmodium' fuse together and recover the general shape of the letter (Fig. 27,ad ). Further increasing the population size (manually or by biasing growth/shrinkage parameters) results in removal of the internal space and transition from an α-shape to a solid Concave Hull (Fig. 27 ,e-f ). 
Voronoi Diagrams and Variant Problems
The Voronoi diagram of a set of n points in the plane is the subdivision of the plane into n cells so that every location within each cell is closest to the point within that cell. Conversely the bisectors forming the diagram are equidistant from the points between them. Computation of the Voronoi diagram may be achieved with a number of classical algorithms [35, 36] and are also the prototypical application solved by chemical reaction-diusion non-classical computing devices [37, 38] . Nonclassical approaches are based upon the intuitive notion of uniform propagation speed within a medium, emanating from the source nodes. The bisectors of the diagram are formed where the propagating fronts meet.
The method of using P. polycephalum to approximate Voronoi diagrams by avoidance of chemorepellents was described in [5, 26] . In this method a fully grown large plasmodium was rst formed in a circular arena. Then repellent sources were introduced onto the plasmodium. The circular border of the arena was surrounded by attractants to maintain connectivity of the plasmodium network. The plasmodium then adapted its transport network to avoid the repellents whilst remain connected to the outer attractants, approximating the Voronoi diagram. Computation of Voronoi diagram may also be achieved by non-repellent methods. This method was proposed in [39] where plasmodia of P. polycephalum were inoculated at node sites on a nutrient-rich agar substrate. Attracted by the surrounding stimuli the plasmodia grew outwards in a radial pattern but when two or more plasmodia met they did not immediately fuse. There was a period where the growth was inhibited (presumably via some component of the plasmodium membrane or slime capsule) and the substrate at these positions was not occupied, approximating the Voronoi diagram. The position of the growth fronts remained stable before complete fusion eventually occurred.
The multi-agent model of P. polycephalum was used to approximate Voronoi diagrams in [24] and replicated both the repellent method (28) , and the attractant methods (29) . By varying the repellent concentration hybrid diagrams were formed which possessed features of both plane division and minimal object wrapping Fig.   30 . Weighted Voronoi diagrams were approximated by varying the repellent size and concentration at dierent node sites (Fig. 31b) . Hybrid Voronoi diagram and Proximity graph constructs were formed by using simultaneous placement of attractant and repellent sources 31c).
Summary and Conclusions
In this article we have examined the problem of how to inuence, or program, spatially represented parallel unconventional computing substrates, inspired by research into the remarkable computational behaviour of true slime mould Physarum polycephalum. We used a multi-agent model of P. polycephalum which collectively behaves as a morphologically adaptive virtual material. We examined and catalogued low-level mechanisms which caused shape adaptation in the material. Some These tools may be used in an ad hoc manner to solve particular problem tasks, or they may provide the basis of a more formal grammar in order to delineate the range of problems which can be tackled by unconventional computing methods [9, 40] . The simplicity of the low-level mechanisms may also be attractive to distributed robotics applications in which robotic devices composed of simple components must be amenable to indirect guidance and external control whilst integrating a large number of distributed and concurrent inputs. In future work we will examine how these unconventional computing mechanisms can be combined and used to induce graph transformations in identical datasets.

{'paper_id': '1813438', 'title': 'Mechanisms Inducing Parallel Computation in a Model of Physarum polycephalum Transport Networks', 's2_url': 'https://api.semanticscholar.org/CorpusID:1813438', 'source': 'S2ORC'}