A Physarum-inspired approach to the Euclidean Steiner tree problem

Having introduced our novel explore-and-fuse method and the Physarum Steiner Algorithm we shall dedicate this section to discussing how the algorithm’s parameters influence the model, and how the method can be used towards diverse applications.

In what follows we shall consider how different parameters such as the different shapes of cells, as well as their number, influence the results obtained by the Physarum Steiner Algorithm. We shall then conclude the section by studying different applications that our methods have.

Cell shape

Although¹³ and⁶ considered diamond shaped CELLs, we shall consider here CELLs with other shapes. The primary benefit of square cells is that their shape allows for more cytoplasm to be placed on the grid. As a result, the foraging phase is very fast so using square cells tends to result in shorter run times than using diamond-shaped cells. In addition, large square cells are able to more completely cover the standard square grid than diamond-shaped cells. On the other hand, diamond-shaped cells result in less cytoplasm and more time spent in the foraging stage. This gives the cytoplasm time to move towards a centralized location which results in better solutions.

Example A In order to illustrate the above point, in Fig. 3a.i., we begin with squares that are tightly packed. Since the squares are so tightly packed (1 apart), if any piece of cytoplasm in a square is moved, it will lead to a connection with a neighboring cell. As a result, all the points are found very quickly. In fact, many of the squares are connected and part of the network even if they are not close to any of the points, as shown in Fig. 3 (a.ii.). Shrinking these extra squares takes a long time and can also result in long paths which are far out of the way as seen in Fig. 3a.iii.

Example B In contrast to Example A, in Fig. 3b, we consider diamond-shaped cells. The cells start off diamond-shaped and with less overall cytoplasm than the square cells. The cells then spend quite a few iterations in the foraging phase. Although this does take time, it allows the cytoplasm to move towards a centralized location around the active zones as seen in Fig. 3 (b.ii.). When the cell finally proceeds to the shrinking phase, there is less cytoplasm to remove and no out of the way paths, resulting in shorter solutions. The downside to this is the increased time which in some cases can be very long (over 100 million iterations) and in some cases the algorithm may not even complete.

The effect of multiple cells

In what follows we shall examine the effects of the number of cells used. We run 10 trials on 10 grids for a total of 100 trials on each cell size and number of cells. For each trial, we measure the total amount or area of cytoplasm that is initially spawned. This is used to normalize the search area which is the number of squares in the grid (for example a (100 times 100) grid has search area 10,000).

Success rate: The algorithm may sometimes be unsuccessful at connecting all the points. For example, the cells may miss a point early on and move far away from that point, making it almost impossible to ever find that point. There may also simply not be enough cytoplasm for two far away cells to fuse into one. For each number of cells (1, 9, 25, 100), we try various sizes/amounts of cytoplasm and compute the proportion of trials (out of 100) that successfully terminate within 10 million iterations.

In Fig. 4a, we see that the black line (100 cells) extends much further to the right than the cyan line (one cell). Thus, the more cells there are, the larger of a search area we can explore. This is mainly because with more cells, we can spread out our cytoplasm instead of having it be concentrated in certain areas.

Solution length Another important metric to consider is the solution length. We measure how good the solution is by counting the amount of cytoplasm when the algorithm terminates. We ignore any cytoplasm that is part of a disjoint cell that does not contain an active zone, or in other words is separate from the cell that actually forms the tree. In Fig. 4b, we see that as the search area as a percentage of cytoplasm increases, the quality of the solution improves. This is because there is comparatively less cytoplasm to begin with. In addition, we see that as the number of cells increases, it is possible to find a better solution. This correlates with the earlier result shown in Fig. 4a that using more cells allows solutions to be found with less cytoplasm. Trials with 100 cells found the shortest solutions (rightmost data point).

Run time The last metric we consider is the run time. We consider the true number of iterations the algorithm runs for. By true iterations, we account for the fact that in a parallel algorithm or set of real-world Physarum organisms, multiple cells will be introducing and moving bubbles at the same time. As a result, the iteration count is scaled by the number of disjoint cells. In Fig. 4c, we see that the more cells there are, the lower the number of iterations. This may be because with more cells, the cytoplasm is more spread out and therefore there are less out of the way points which may take a very long time to find. From the above analysis, we see that using more cells allows us to explore bigger search areas, find shorter solutions, and solve problems faster.

Applications

The behavior of Physarum and the models it has inspired have found many different uses among which are drug repositioning, developing bio-computing chips, approximating highways layouts, and designing subway systems^2,8,9,10. In order to illustrate the operation of the Physarum Steiner Algorithm and demonstrate its applicability to real world problems, we consider the following:

• sep0em

• Network design We use the algorithm to develop a road network in the United States.

• Obstacle-avoidance We use the algorithm to solve the obstacle-avoiding Euclidean Steiner tree problem.

• VLSI routing We use the algorithm to route connections between pads in chip design.

• Topological surfaces We discuss the algorithm’s adaptability to varying surfaces and boundaries by considering topological surfaces such as the sphere, torus, Klein bottle, and (mathbb{RP}mathbb{}^2).

Road networks The Physarum Steiner Algorithm can be used to build a road network between the largest one hundred cities in the lower 48 United States (excluding Alaska and Hawaii). We use data³² containing the longitude and latitude of the 100 cities with the highest population to generate a rectangular grid of active zones.

We spawn diamond-shaped cells of size 7 with a spacing of 1 as shown in Fig. 3. After many iterations, the final road network is shown in Fig. 5a. The algorithm is particularly suited to the problem of designing transportation systems because it first connects all the points before optimizing the network into a tree. The algorithm can thus be terminated early depending on how much redundant connectivity is desired in the transportation network.

For example, in Fig. 5b, we have a network that still contains loops in high-traffic routes between the Bay Area, Los Angeles, and Las Vegas. If we allow the algorithm to continue running, we will get networks with fewer loops and eventually a tree.

We believe that this algorithm can be applied to many similar problems such as designing fiber optic or electric cable networks. Moreover, as discussed in the last section, it will be very interesting to compare this study to that of³³, where in vitro slime mold is used to investigate the construction of transportation networks over a USA map.

Obstacle avoidance Due to the cellular automaton nature of this algorithm, it is straightforward to define boundaries or other obstacles that need to be avoided. This is very useful in cases where certain areas need to be avoided such as a lake or the boundary of a county. And, unlike the current standard obstacle-avoiding Euclidean Steiner algorithm²⁷ which takes multiple hours for graphs with only 150 points, the run time of the Physarum Steiner Algorithm is not affected by the need to avoid obstacles.

As an example, consider the boundary given in Fig. 6a. Here, the grey area represents the search area and the 100 white squares outlined in dark grey are the points. There are many possible real world situations similar to this. For example, the grey area could be a county and all the points represent homes that subscribe to a certain Internet service provider (ISP). The big white area in the center could be a lake and the smaller white area could be a dog park. The ISP company could utilize the Physarum Steiner Algorithm to find networks to lay fiber optic cables.

We begin by deploying square Physarum cells of size 7 in Fig. 6b. In Fig. 6c, the cells begin to fuse, share intelligence, and find all the points. We choose a solution that still has some loops to increase reliability and ease of future modification to the network. Our final solution is shown in Fig. 6d. This solution is generated in 300,000 iterations and less than 30 seconds.

VLSI Routing for VLSI (very large-scale integration) chip design¹⁹ is one of the largest real-world manifestations of the Steiner tree problem, especially as modern chips may contain upwards of 10 billion transistors. Solving the VLSI problem would require additional modification to the Physarum Steiner Algorithm since VLSI design is typically presented as a group Steiner tree problem and has very large problem sizes, the Physarum Steiner Algorithm. Due to the usage of a square grid in the Physarum Steiner Algorithm, the algorithm is easily applied to find rectilinear networks such as those required for routing chips. In addition, our empirical results suggest that it should scale well to the large problem sizes common in chip design. Using data from³⁴, we consider a set of pads that need to be connected. In Fig. 7, we represent the pads as active zones and generate a tree between them.

Topological surfaces Finally, the Physarum Steiner Algorithm is easily applicable to finding Steiner trees on other topological surfaces. Given the nature of the algorithm, we are able to map coordinates on one edge to another. In Fig. 8, we use square identification spaces to find Steiner trees on the torus, sphere, Klein bottle, and (mathbb{RP}mathbb{}^2). These solutions on identification spaces can be seen on a torus and a sphere in Fig. 8a,b.

Concluding remarks

We have presented here a novel explore-and-fuse approach to solve problems that cannot be solved by traditional divide-and-conquer.

Our approach is inspired by Physarum, a unicellular slime mold capable of solving the traveling salesman and Steiner tree problems. Besides exhibiting individual intelligence, Physarum can also share information with other Physarum organisms through fusion. These characteristics of Physarum inspire us to spawn many Physarum organisms to independently explore the problem space and collect information in parallel before sharing the information with other organisms through fusion. Eventually, all the organisms fuse into one large Physarum that can then globally optimize using the knowledge collected earlier. Explore-and-fuse can be seen as a less rigid form of divide-and-conquer that can better handle problems that cannot be decomposed into independent subproblems.

We demonstrate the explore-and-fuse approach on the Steiner tree problem by creating the Physarum Steiner Algorithm. This algorithm has the ability to incrementally find Steiner trees. The first solution tends to contain many loops that are removed with additional iterations of the algorithm. This incremental improvement is particularly useful for applications such as road and cable networks where some degree of redundancy in the connectivity is desired. In particular, it will be very interesting to compare our work to the the one done in³³ where a protoplasmic network created by in vivo Physarum is considered to study and asses show the slime mold imitates the United States Interstate System. We foresee several applications of our algorithm in this direction, leading to similar findings to those appearing in the studies done in³³.

The algorithm operates on a rectilinear grid and is particularly applicable to rectilinear Steiner tree problems such as those that often arise in VLSI design. In addition, the algorithm performs well on the obstacle-avoidance Euclidean Steiner tree problem.

In comparison to the existing Physarum-inspired Steiner tree algorithms described in Section “The Steiner tree problem”, the Physarum Steiner Algorithm uses a completely different mechanism. While the existing algorithms use a system of equations modeling the thickening of tubes as protoplasm flows through them, the Physarum Steiner Algorithm is based on modeling Physarum spatially moving around a grid and finding a tree between squares of the grid. In addition, it should be noted that the approach taking in existing algorithms would not work on the Euclidean Steiner tree problem as in the Euclidean Steiner tree problem, there are an infinite number of possible points that could be part of the Steiner tree (essentially any point in the plane). It would not be possible to write a system of equations representing the infinite possible points and edges. In the future, we believe further work could be done to improve the Physarum Steiner Algorithm. Since the Physarum Steiner Algorithm is an approximate algorithm, future improvements could be made so its approximations are closer to the actual optimal solution. In addition, it would be interesting to see this approach applied to other problems Physarum has been able to solve such as the traveling salesmen problem.

Source: Ecology - nature.com