Solving the Towers of Hanoi – how an amoeboid organism efficiently constructs transport networks

Biological networks are constructed in the absence of central control, with the final network topology resulting from the interactions between many components (Bonabeau et al., 1999). Transport networks have been studied in many kingdoms of life, from the vasculature of plants and animals (Banavar et al., 1999; West et al., 1999), to the interconnected tubular networks of fungal mycelia (Bebber et al., 2007) and protists such as slime moulds (Nakagaki et al., 2004a; Nakagaki et al., 2004b; Tero et al., 2010). The networks produced by many biological systems balance maintenance costs, network efficiency and robustness against damage (Nakagaki et al., 2004b; Bebber et al., 2007).

Some of the most widely studied biological networks are those of the trail-laying ants (Gordon, 1995; Jackson et al., 2004; Garnier et al., 2009). Argentine ants (Linepithema humile) form supercolonies consisting of many nests, which are connected by a network of pheromone trails. The inter-nest trails are used to distribute food, workers and brood between nests (Holway and Case, 2000). Such inter-nest transportation networks tend to have short total length (which minimizes costs) but a low level of robustness (which makes the network vulnerable) (Latty et al., 2011). The inter-nest networks the ants construct are topologically similar to either minimum spanning trees (MST), where the networks are connected by the minimum number of edges, or Steiner networks, which contain intermediate junctions in the network where edges intersect to achieve the minimal total length (Latty et al., 2011). The process of network formation initially involves construction of multiple links between nests followed by a pruning process that reduces the number of trails until they approach either a MST or a Steiner network.

The slime mould Physarum polycephalum has been used extensively to study the formation of biological networks (Nakagaki et al., 2004a; Nakagaki et al., 2004b; Tero et al., 2006; Tero et al., 2010). Physarum polycephalum is a unicellular, multinucleate protist and connects food patches by distributing its biomass, forming connecting tubes via positive feedback. The resulting networks are both efficient and resilient. Like ant trails, slime mould networks contain intermediate junctions (Steiner points) that reduce their overall length (Nakagaki et al., 2004a; Nakagaki et al., 2004b).

While it is known that both trail-laying ants and slime mould are capable of building robust networks, the ways in which such networks are formed are not clearly understood. Recently we examined how Argentine ants adapt their foraging network to solve a dynamic version of the Towers of Hanoi (ToH) problem, a well-known shortest-path problem (Reid et al., 2011). In the ToH problem, N discs of different diameters are stacked upon one of three pegs in order of decreasing diameter from the base (see Fig. 1B). The problem is solved optimally when the stack of discs is transferred to one of the remaining two pegs using the smallest number of possible moves while obeying the following rules: only one disc can be moved at a time; only the top disc in a stack can be moved; and a disc can never be stacked upon another of smaller diameter. All possible moves to solve the problem can be mapped on a 2D maze (Fig. 1A). We connected this maze to its mirror image, forming a maze with a total of 32,678 unique paths between the opposing ends (Fig. 2C). Only two of these paths are the shortest. This problem can be made dynamic by blocking and opening paths while the biological system is constructing its solution (see Fig. 2).

Superficially, trail-laying ants and slime moulds appear similar in the way they construct network solutions. This is because both systems build their networks via positive feedback. For trail-laying ants, pheromone laid by foragers attracts other ants to follow the trail, laying their own pheromone, thus amplifying the strength of the trail (Hölldobler and Wilson, 1990). The pheromone on disused and longer trails evaporates (Dorigo et al., 1996). For slime moulds, tubes lying in the direction of cytoplasmic flow towards a food source or direction of travel become thicker, allowing more flow through them (Tero et al., 2006). Tubes leading to other directions collapse from lack of flow and their biomass is subsequently withdrawn (Nakagaki et al., 2001).

We used the same ToH setup used for ants (Reid et al., 2011) to investigate how the slime mould reconstructs a network when its initial solution is disturbed. This allows us to compare the properties of the networks built by our study organism to the properties of the most efficient network possible. Additionally, constricting the environment of the slime mould to a maze-like setup facilitates the analysis of the constructed network while reducing the degrees of freedom. By comparing the networks built by ants and slime mould when solving the dynamic ToH problem, we can determine whether both organisms use common mechanisms to construct efficient transport networks in a dynamic environment.

The vegetative state of P. polycephalum, called a plasmodium, is a unicellular, multinucleate cell. The plasmodium can grow to cover an area in excess of 900 cm², and is capable of moving at speeds of up to 5 cm h⁻¹ (Kessler, 1982). The general morphology of a plasmodium includes an extending ‘search front’ at the leading edge of the migrating cell, typically forming a dense fan-shape. This is followed by a system of intersecting tubules towards the trailing edge of the organism (Dove and Rusch, 1980). Cytoplasm is constantly and rhythmically streamed back and forth through the network of tubules, circulating chemical signals and nutrients throughout the cell (Collins and Haskins, 1972). The plasmodium consists of small oscillating units, each oscillating at a frequency dependent on both the local environment and its interactions with neighbouring oscillators (Durham and Ridgway, 1976). Attractants such as food increase the oscillation frequency in the area closest to the attractant, causing biomass to flow in this direction (Latty and Beekman, 2011), while repellents such as light have the opposite effect (Ueda et al., 1980). The collective behaviour of the oscillators, each transferring information to its neighbours, allows efficient networks to be constructed.

We maintained P. polycephalum plasmodia in the dark at 22°C on large 2% agar plates. Original cultures were obtained from Southern Biological Supplies (Nunawading, Australia). We fed laboratory stocks with rolled oats (Coles brand) and sub-cultured onto new agar plates weekly.

We used a version of the maze from our study on Argentine ants (Reid et al., 2011), but scaled down to 135 mm in length (Fig. 1C), the standard Petri dish size used by Nakagaki et al. (Nakagaki et al., 2000) in their labyrinth maze-solving experiments with P. polycephalum. We constructed the ToH using acetate on agar substrate. The dry surface of the acetate is repellent to the slime mould, so the plasmodia were restricted to areas of exposed agar only. We placed two food sources (oat flakes) at each end of the maze (see Fig. 1C). We starved plasmodial cultures for 48 h and then added 0.2 cm³ of search front biomass to the maze via a syringe, spread out evenly in small globules across the entire agar surface of the maze. Such small globules become separate plasmodia within minutes (Kobayashi et al., 2006; Aono et al., 2010), and extend exploratory pseudopodia and fuse with their neighbours to form a single plasmodium across the entirety of the maze. Once the plasmodium is formed, it begins to optimise the number and length of tubules connecting the two food sources. This approach is not maze-solving by chemotaxis as reported previously in slime moulds (Adamatzky, 2012) and nematodes (Reynolds et al., 2011); the shortest path in our maze is constructed entirely by feedback within the maze-spanning plasmodium (Nakagaki et al., 2000; Nakagaki et al., 2001).

We collected data for 24 h. Pilot studies showed that this time period was sufficient for the plasmodium to construct one or a few stable solutions. In 14 of our experiments, we altered the layout of the maze after 24 h to produce the modified Towers of Hanoi, as shown in Fig. 2B. This was our dynamic treatment group. The two connecting bridges (and any biomass on them) were removed and a central bridge of agar inserted. The agar from which the central bridge was constructed was of the same origin as the rest of the maze, so bridge and maze had similar hydration levels. We collected data for a further 52 h, giving a total duration of 76 h for the experiment. In our other 15 experiments we left the maze untouched for the remaining 52 h. This was our static treatment group, and was included to control for any network modification the slime mould may make even when the maze was not changed, for instance as a result of growth, satiation or simply with time.

We took still photographs of the maze every 4 h with a Sony HDR-HC5 Handycam. The camera was mounted 30 cm above the maze inside a darkbox containing 200 ml of water, which acted to reduce ambient light and increase humidity surrounding the slime mould. In our first analysis we determined the mean area covered (in terms of number of edges) by slime mould biomass at each 4 h time point. This measure included both established tubules and extending search fronts. For the remainder of the analyses, we only included established tubules connecting the two food sources through the maze, thus ignoring all edges containing dead end tubules and search fronts. We calculated the proportion of replicates that utilised a minimal path at each 4 h time point. We then counted the mean number of minimal paths utilised within each network constructed by plasmodia. The minimal path solution consists of 31 edges as shown in Fig. 2A, with two unique minimal solutions in the ToH, and four in the modified ToH, as detailed in Fig. 2B. Finally, we quantified the optimality of the solutions by determining the number of ‘corrective moves’. Corrective moves, shown in Fig. 2B, are moves between nodes perpendicular to the long axis of the maze. The number of corrective moves in a maze solution scales directly with the divergence of the solution from optimal. The mean area covered, proportion of replicates with a minimal solution, mean number of minimal paths, and mean number of corrective moves were calculated across all replicates at each 4 h period and graphed over the total time of the experiment. For each metric we statistically compared the static and dynamic treatment groups after 24 h, as prior to this time both treatments were identical. We used a two-way ANOVA with repeated measures, with maze conformation (static/dynamic) as the between-subjects variable, and time as the repeated measure.

Immediately after the food sources were added to the maze, plasmodia began retracting biomass from large areas of the maze; total area covered by biomass decreased from 162 edges (complete maze filled) to near the minimal path length of 31 edges (Fig. 3A). However, in most instances the most direct connection or connections between the two food sources involved one or more corrective moves (Fig. 3D) so that the majority of replicates did not include one or two minimal paths.

The slime mould networks underwent little further modification after 24 h when the maze remained unchanged. The mean area covered by biomass increased slightly over time (Fig. 3A), but this did not result in any greater utilisation of minimal paths (Fig. 3B,C), and only a slight increase in the number of corrective moves (Fig. 3D). Thus the plasmodia did not improve the network once the two food sources were connected.

When we changed the maze after 24 h to the modified ToH the plasmodia expanded throughout the maze, resulting in a significant increase in area covered by biomass relative to the static treatment (F_1,18=0.303, P=0.026; Fig. 3A). Obviously severing the tubules in order to modify the maze resulted in an immediate drop in the proportion of replicates that contained a minimal path (Fig. 3B). However, the proportion of plasmodia using a minimal path increased after the change to the maze, until all networks included a minimal path (Fig. 3B). Thus only after we changed the maze did plasmodia significantly increase the use of minimal paths relative to the static treatment (F_1,18=0.907, P<0.001; Fig. 3B). The consistently low number of corrective moves observed in the dynamic treatment networks indicates that, while the plasmodia expanded through the new maze conformation and built minimal length paths, they did not construct tubules with additional, sub-optimal corrective moves (Fig. 3D), and the number of corrective moves did not differ between the static and dynamic treatments (F_1,18=0.043, P=0.389).

Interestingly, the plasmodia rapidly utilised more than one minimal path after the modification to the maze, whereas use of minimal paths had stabilised prior to the change in the first 24 h (Fig. 3C). The dynamic treatment group was significantly different from the static treatment group (F_1,18=3.610, P<0.001), which exhibited no increase in number of minimal paths used. This suggests that after the change in conformation, the plasmodia utilised existing parts of the network that earlier did not form part of a minimal path (Fig. 4). Indeed, a large number of edges used in the final networks contained a tubule that was in use before the change to the maze was made (mean ± s.e.m.=12.78±3.57, equating to 14.2% of final network length). Thus, an average of 14.2% of the edges utilised in the final networks in the modified ToH were edges that were already being utilised prior to the change.

Using existing parts of the network to build shortest paths only partly explains how the plasmodia constructed optimal solutions in the modified ToH maze. In many instances the plasmodium retracted its biomass after the existing tubules were severed, and constructed a solution from scratch (Fig. 4). This could happen throughout the maze, or only in part of the maze, depending on whether any existing tubules could be used to construct new shortest paths. In half of our replicates the plasmodia retracted completely from both halves of the maze after cutting the tubules. In 36% of our replicates the plasmodia retracted from just one half, with search fronts extending from the network tubules that remained in place (Fig. 4). In the remaining replicates, the plasmodia did not retract at all, but immediately started to build new solutions using the existing network.

Our slime mould rapidly connected the two food sources in our ToH experimental setup, but failed to consistently do this by using one or two shortest paths. Failure to construct the shortest path solution was not due to lack of sufficient time, as in our static treatment the number of shortest paths did not increase as time went on. When the plasmodia were forced to reconstruct their networks in the modified ToH, all of the final networks contained one or more shortest paths. Construction of optimal solutions in the modified ToH was partly due to the plasmodia recycling existing tubules that were already present prior to the change to the maze. The slime mould thus ‘recycled’ parts of its old network after the two food sources were no longer connected. We also observed that, after the change that severed the tubules on the connecting bridges, the slime mould often retracted and re-explored the maze to construct new solutions. The construction of new minimal paths in the modified ToH requires the slime mould to largely avoid areas that were part of the shortest path prior to the modification, because these areas are not part of the new optimal solution. We now know that the slime mould is reluctant to move over areas it has been before (Reid et al., 2012). It is therefore conceivable that the slime mould avoided areas it had just retracted from after the modification was made, thus facilitating the construction of the new minimal paths. This would require the slime mould to distinguish between areas it had just left, and areas it had left hours earlier. At this stage it is not clear if the slime mould is capable of making such distinction (C. R. Reid, unpublished observations). Alternatively, the slime mould may be more efficient when constructing a new solution when it is forced to search the space by expanding pseudopodia through the maze, as opposed to retracting existing tubules at the start of the experiment. Hence the plasmodia could make use of multiple options to construct minimal solutions to the modified ToH, which were not available when solving the initial ToH. This may explain why the slime mould found more minimal solutions to the modified ToH than the ToH.

Using the ToH maze allowed us to compare the ability of the slime mould to construct efficient networks with that of another distributed, self-organised natural system: ant colonies. Using the Argentine ant Linepithema humile we previously showed that trail-laying ants are efficient at solving the ToH, and are capable of adapting to the modified ToH maze (Reid et al., 2011). Argentine ants were better able to construct one or two shortest paths in the original ToH maze compared with the slime mould, and required a lower number of corrective moves.

In adapting their established trail network from the ToH to the modified ToH, Argentine ants initially maintained as much of their existing trail network as possible. The ants connected a new shortest path directly from the blocked area of the trail to the newly opened central bridge via the perpendicular path indicated by the three corrective moves etched in grey in Fig. 2B (Reid et al., 2011). Over time the ants abandoned the sub-optimal edges of their network to construct the new shortest path (dotted lines in Fig. 2B). Hence the ants initially utilised the maximum amount of established network infrastructure, before adapting the efficiency of their network. For the ant trail networks, this method of network adaptation resulted in a rapid increase in corrective moves directly after the change to the maze, followed by a rapid decrease in corrective moves back to initial levels as they utilised the new shortest path. We did not observe such a pattern in the slime mould networks. Instead the increase in network efficiency after 24 h in the modified ToH was accompanied by an increase in the mean area covered by biomass, indicating that after the change the plasmodia expanded through the maze, building large networks that included minimal paths.

Whereas ants use volatile trail pheromones to construct their networks, slime moulds build physical structures to transport biomass through the maze. Due to the volatility of ant trail pheromones, the networks of the ants tend to converge onto the shortest path(s) because pheromone evaporates from longer trails through the maze, which carry less traffic, and hence receive less pheromone compared with short trails (Dorigo et al., 1996; Dorigo and Stützle, 2004). In the slime mould, convergence onto the shortest path is due to contraction waves that are initiated by oscillators within the cell. The contraction frequency is highest around the food sources, and this difference in contraction frequency induces neighbouring oscillators to propagate a contraction wave throughout the organism. Contraction waves modify the tube structures by reinforcing tubes parallel to the wave, and deteriorating tubes perpendicular to the direction of propagation (Nakagaki et al., 2001). Any tubes leading to dead ends are retracted, and where multiple tubes link food sources, all but the shortest tube are likely to disappear (Nakagaki et al., 2001). However, this mechanism often results in the slime mould not using the shortest possible path, but a path that is close to the shortest route (Nakagaki et al., 2001). Our ToH maze contained more than 32,000 possible paths; yet the slime mould constructed a connection between the two food sources that was only approximately 5% longer than the optimal solution. Whereas the trail pheromone of ants is highly volatile, thus constraining the length of the ant networks, it seems that the tubular network of the slime mould is less sensitive to negative feedback when competing paths are similar in length.

It has previously been shown that the amount of food available to the slime mould can have an effect on the formation of the network that the slime mould builds to join the food sources (Nakagaki et al., 2001). Nakagaki and colleagues found an inverse relationship between food source surface area and the number of tubes between food sources; with an excess of food, the plasmodium will usually connect two food sources with a single tubule, even occasionally with no tubules, splitting itself in two (Nakagaki et al., 2001). If the surface area of the food is limited, additional tubules are used to connect the food sources. The slime mould is thought to use this rule to trade-off the need to engulf food sources to ingest them, and the ability to span multiple food sources whilst staying physically connected (Tero et al., 2007). As such, the surface area of the food sources in our maze may influence the number of solutions in the organism's network. By adjusting the surface area of the food sources, we may be able to manipulate how many tubules are used to connect the food sources in the initial ToH.

By comparing the networks built by ants and slime mould when solving an identical problem, we aimed to determine whether these two distributed natural systems use common mechanisms to construct efficient transport networks in dynamic environments. The observed differences in network adaptation between these two systems are attributable largely to their fundamentally distinct construction media; slime moulds build physical networks consisting of their own biomass, while ant colonies build chemical networks made from pheromone depositions. The strong positive feedback cycle inherent in the pheromone trail system ensures that ants are adept at converging on the shortest path with great accuracy. However, in dynamic environments this feedback forces ants to utilise outdated, sub-optimal parts of the existing network, thus delaying convergence to the new optimal path. In contrast, our slime mould was less likely to find the initial shortest path, but in the dynamic experiments the organism rapidly withdrew biomass from outdated parts of the network, instantly destroying the physical trail. The organism was then free to find the new shortest path without being influenced by past network construction, except where parts of the past network now lay along the new optimal path.

We thank members of the Behaviour and Genetics of Social Insects Laboratory, David Sumpter and two anonymous reviewers for comments on an earlier version of the manuscript.