X-raying a slime mold
Discovering the hidden discrete network in a continuous body
Coauthored by: Miriam Rateike.
This article is a tribute to Network Extraction From Routing Optimization by D. Baptista, D. Leite, E. Facca, M. Putti, and C. De Bacco, and a tutorial on how to use the code published with it.
Slime molds are biological organisms that have gained attention in research after shown to find the shortest path through a maze. Not possessing a brain, it is their complex biological processes that enable them to solve transportation problems. Beyond biology, their desired properties have been — to some extent — captured mathematically by the Monge-Kantorovich Dynamics. Building on this, we introduce Nextrout (Network Extraction From Routing Optimization). Nextrout is an algorithm that allows you to solve a transportation problem in a continuous space — just like a slime mold! It x-rays your slime mold solution to reveal the network as an optimal path in the discrete space.
What are a slime molds? — A-maze-ing!
It’s not a plant! It’s not an animal! It’s not a fungus! As the father and pioneer of slime mold research, John Tyler Bonner [1], described it: it’s a social amoeba! Especially the species Physarum polycephalum has gained notable attention in research after shown to find the shortest path between sources of food, which were separated from each other by a maze. Without a brain, their communication functions directly over fluids within their cell arms. Their fluid properties have been modeled mathematically and have influenced the development of transportation algorithms for over 20 years. We will introduce the traditional mathematical modeling further below. But first, let’s start with the problem.
What are transportation problems?
Transportation Theory is a branch of mathematics originally formalized by the mathematician Gaspard Monge around 1780. This theory studies ways of optimally transporting and allocating resources.
A typical transportation problem consists of a set of senders and receivers that must be connected by a set of paths that minimize some cost function. It sounds simple, right? Let’s illustrate how a problem like this might look like.
Imagine for a second that you own a delivery company. You receive packages every day, and you gladly deliver them. New packages continuously arrive. You send a fully loaded truck from the main office towards the different destinations and have the truck return for a refill once it is empty. After a while in the business, you realize that this is not efficient. Distances are long, and going and coming back is expensive. Therefore, you decide to decentralize your business. Building some distribution centers around the city seems to be a good idea to reduce the distance your truck is to cover every day.
You grab a pen and paper and start sketching ways of solving this seemingly simple problem. It’s clear that you must first draw a map of the city. Your version of the city’s map looks like the network in Fig. 1.
Next step: the headquarters. Easy, right? In principle, it’s just a matter of drawing a few buildings around a small city. You place the first building and measure the distance between the main headquarter and the new building as well as the distance from the new one to all the other end destinations. You draw a transportation route to connect all of these locations on the map, and right there get the feeling that the problem is now solved.
Sadly, this feeling lasts only a few minutes. You think more carefully about this “solution” and tons of questions immediately come to your mind: Is the chosen location far enough from the main building? Is it too far from the main building? Is one distribution center better than two? Should I consider building three, four, …, ten of them? Is this the best transportation route?
It all suddenly gets blurry. You thought it was easy and then you got all these doubts. While trying to find answers to these questions, you wonder if the map you have drawn is accurate enough. You think: Am I leaving out relevant information about the city?
You call your friend who you know is a PhD student working on optimal transportation problems. She says: “I see you are trying to solve this problem by drawing a network. You might be restricting too much the space where the solution will be! What if we would try to use the continuous version of the map (see Fig. 10, spoiler) instead of the network?”
Imagine there would be a way of solving this problem directly on the continuous representation (the map, and not the network), and still get useful discrete insights from the solution (things like the number of distribution centers, path lengths,…).
Good news! There is one and we will teach you how to use it in this post.
Following nature’s wisdom
As we mentioned before, solutions will be built in a continuous framework. But how do we do it? Facca et al. [2] proposed a technique to map certain transportation problems into an evolutionary process. They start with a guess of the solution and then improve it over time until reaching a final solution. This is a biologically-inspired approach that follows the behavior of some organisms — famous in the scientific community — called slime molds.
Slime molds, especially of the species Physarum polycephalum, have been widely used to solve transportation problems. One of the best-known tasks this organism has been asked to solve is the maze problem. Tero et al. [3] (check out the cool picture there) placed a slime mold into a maze together with two sources of food. (Physarum polycephalums like to eat bacteria on oat flakes — see drawings below.) The authors showed not only that the slime mold was able to solve the maze, but also that the solution was the shortest path connecting the two locations! That means: Slime molds can be seen as naturally solving a transportation problem in the continuous space! We will review the mathematical formulation used to solve these transportation problems in the next sections.
Nextrout: Slime-mold-inspired network extraction
Facca et al. [2] presented a procedure to find a continuous solution to our distribution center problem. Nonetheless, this does not enable us to answer our question: Should I consider building three, four, …, ten distribution centers? We could find an answer to this, if we could turn a continuous solution into a network like the one drawn at the beginning (see Fig. 1). As we show in our paper [4], it is possible to extract graphs from a continuous transportation plan in an automatized way! We call our algorithm Nextrout and we will now briefly explain some of its functionalities and mathematical foundations.
A slime mold’s guide to Monge-Kantorovich Dynamics
As mentioned before, the behavior of the slime molds can be modeled mathematically. Facca et al [2], inspired by the work done by Tero et al [3], proposed a system of partial differential equations to represent the dynamics of the organic system:
As the model has been inspired by slime molds, we use one of them to explain you the ideas behind it!
Imagine you’ve placed a slime mold on a Petri dish of size [0,1]x[0,1] (this would be the domain Ω) as in Fig. 4. Two sources of food (namely, oat boxes) have been also located in this domain. The slime mold’s shape is represented by the quantity μ, the transportation density, or capacity. The positive number μ( t, (x,y) ) tells you how much flow can be transported by the slime mold at point (x,y) and at time t. The initial shape of our slime mold corresponds to μ( t=0, (x,y) ), which it is positive for each point (x,y) (Equation (E1)).
The capacity μ of the body will change in time depending on the flow passing through it, i.e., if the flow is low, then the body will shrink; if it is high, it will grow to cope with the demand. The hyperparameter β controls the speed of the shrinking or growing behavior. The pressure u inside of the body is a function, which will change over time depending on the capacity μ. This process is expressed by a differential equation known as the adaptation equation (E2). It consists of two terms: the first term is the demanded capacity and the second one is the currently available capacity. The difference indicates the necessary capacity change (if positive, growing, if negative, shrinking). Different from the original definition exhibited in our paper, we introduce — as a scientific contribution of this post — a binary penalization variable κ(x,y) that indicates where obstacles will be. κ(x,y) can assume two possible values for each point (x,y): an arbitrary large a, if you do not want to cross the point (obstacles, buildings,…), or 1, if the point can lay in a path (see Fig. 5).
A real slime mold communicates signals or sends nutrition to its body parts by transporting fluids (protoplasmic sol) through its tubes (arms). Based on these observations, Tero at al. [3] suggested to frame the slime mold dynamics as a flow problem. You could think of the sources of food as being points where the flow is injected or extracted (these are the pipes in Fig. 4). The function f[+](x,y) indicates the amount of mass entering the system at point (x,y). f[+] is 0 whenever point (x,y) is not part of a source, and equal to a positive value when the point is located in a source. The same holds f[-](x,y) with regards to points located in sinks.
Equation (E3) then states the law of conservation in fluid dynamics: the amount of fluid injected into the system is exactly the amount of fluid leaving from it. The last equation (E4) assures that the flow cannot change in places other than the sources and the sinks. We recall that a point (x,y) can either be located in a source (f[+] >0, f[-]=0), in a sink (f[+]=0, f[-]>0) or neither in a source nor a sink (f[+]=0, f[-]=0). The term μ ( t,(x,y) ) ∇ u ( t,(x,y) ) is often described as flow in the mathematical sense. In a point that is neither located in a sink nor in a source, the change, i.e. gradient, of the flow will be zero, because the flow is entering and leaving the point (passing through). In a point located in a source (sink) the gradient of the flow will be negative (positive), because in this point flow is only leaving (entering).
We inject and thus extract a constant amount of mass in/out of the system at all times t. The combination of these four rules will describe the change of the size of the tubes over time until reaching a steady state. This steady-state μ* is known as the solution to the flow problem (see Fig. 5). The set of rules is known as the Dynamical Monge-Kantorovich Problem (DMK for short). Note: these equations are inspired by slime molds, but do not map their organism 1:1. Slime molds do not connect a source of food with a sink but two or more sources of food (e.g. in the maze). And as it is the case for most (of us) organisms, slime molds’ body naturally grow in mass with the intake of food.
Nextrout: Tutorial
With this in mind, we will now take a look at how to use the Nextrout algorithm provided in our GitHub repository.
First step: DMK solutions
The first step consists of defining the transportation problem that we would like to solve with the DMK solver.
The solver takes as inputs:
- μ( t=0, (x,y) ): initial capacity (the initial shape of the slime mold),
- f[+](x,y), f [-](x,y): source and sink locations (or sources of food),
- κ(x,y): obstacles or restrictions, and
- β: traffic rate in (0,2).
and generates:
- μ*(x,y): optimal transport density (solution),
In our initial example of a distribution center problem, we do not have a clear guess for the solution, and we can use a uniform distribution μ(t=0 ,(x,y) ) = 1 as initialization. This means that every point in the domain could be part of the solution. At the same time, we do know about the locations of the sources (senders) and the sinks (receivers). i.e., f[+] and f[-]. Further, we have the map of the city, and thus also know where the obstacles will be, i.e., κ.
The traffic rate β controls the speed of the shrinking or growing behavior of the tubes. In the experiment that produced Fig. 6 and 7, β is set to be 1.5. More details about this parameter can be found in [3].
The DMK solver generates as solution the function μ*(x,y) shown in Fig. 7. This function shows the paths we should follow in order to achieve our connectivity goal.
Second step: Network pre-extraction
Once the DMK solver gets a solution to our transportation problem, it is time to see the graph structure associated with it. The inputs of the pre-extraction algorithm are:
- graph_type: the type of connections we would like to see, and
- δ: the threshold used to discard small values of the capacities.
This generates a first draft of the network (see Fig. 8): Gpe. Note: yellow is the source and red are the sinks. Details about the usage of each parameter can be found in [4].
Third step: Network filtering
The first step gave us an idea of how to move around the city. The second step gave us a network. But if we zoom into Fig. 8, we observe a triangle nature of the network: Whenever we reach a node we need to take a decision on which path to follow next (we always have at least two options to move forward). So if we take a wrong turn, we might end up going in circles, and will perhaps never reach our desired destinations. To overcome this issue, a cleaning step is applied. We filter out redundancies in a systematic way following our recently acquired natural wisdom: We give our slime mold algorithm the network as a maze to solve! Facca et al. [5] propose an efficient algorithm to solve the DMK problem on graph structures instead of continuous domains. This adaptation is called discrete DMK solver.
For this new filtering step we provide the solver with some specific information:
- Gpe: graph to be simplified,
- β: traffic rate,
- δ: threshold used to discard small and not interesting values of the capacities,
- T: source and sink nodes obtained from f[+] and f[-].
The output of this step is the network in Fig. 9.
A few post-processing steps like removing repeated destination nodes (e.g., the bottom middle red node in Fig. 9) will give us a final network looking like the one in Fig. 10.
We have found a solution to our original problem! The number of distribution centers we should build is the number of those nodes in the graph, which count exactly three connections. By inspection of the image, we can gladly say that six is the golden number! Six distribution centers placed in the locations where these nodes are will give us an efficient way of connecting the main building to the different destinations (see Fig. 11).
Conclusion
We have proposed an automatic way of extracting networks from raw solutions to transportation problems in continuous space. This tool allows us to get useful network insights about transport plans.
References
[1] Bonner, J. (2009). The Social Amoebae: The Biology of Cellular Slime Molds. Princeton; Oxford: Princeton University Press.
[2] Facca, E., Cardin, F., & Putti, M. (2018). Towards a Stationary Monge — Kantorovich Dynamics: The Physarum Polycephalum Experience. SIAM Journal on Applied Mathematics, 78(2), 651–676.
[3] Tero, A., Kobayashi, R., & Nakagaki, T. (2007). A mathematical model for adaptive transport network in path finding by true slime mold. Journal of theoretical biology, 244(4), 553–564.
[4] Baptista, D., Leite, D., Facca, E. et al. (2020) Network extraction by routing optimization. Sci Rep 10, 20806.
[5] Facca, E., Cardin, F., & Putti, M. (2018). Physarum Dynamics and Optimal Transport for Basis Pursuit. arXiv: Numerical Analysis.
Acknowledgements
This work was developed under the supervision of Dr. Caterina De Bacco in the Physics for Inference and Optimization group at Max-Planck for Intelligent Systems.
