Experimental studies have shown that the slime mold Physarum polycephalum, a single-cell slime mold that feeds on bacteria and spores, is able to perform tasks that are surprisingly complex for such a simple organism: for example, finding the shortest path through a maze. From these experiments and from the mathematical model proposed by biologists, IASI researchers have developed a rigorous mathematical analysis that confirms how the process followed by Physarum is a perfect "natural algorithm" for network optimization, developed by evolution over millions of years.
In the experiments initially performed at the Hokkaido university in Japan, the slime mold was uniformly distributed over a maze where two oat flakes have been positioned; oat is the slime mold's favorite food. With the passage of time, the slime mold retracted from the less efficient paths, and concentrated its mass on the shortest route joining the two oat flakes. The study analyzed the biological mechanism that reconfigures the slime mold into the shortest path: each "vein" of the Physarum expands or contracts depending on higher or lower availability of nutrients, following precise equations identified by the biologists. In turn, the larger or smaller dilation of the veins implies a variation of the flux passing through them, thus creating a dynamical process.
The study carried out by IASI researchers in collaboration with the Max Planck Institute for Informatics in Saarbruecken (Germany) and presented at the Symposium on Discrete Algorithms in Kyoto, has clarified how network optimization is a mathematical consequence of the vein dynamics, independent of the complexity of the underlying network. One could say that evolution, during millions of years, designed Physarum's vein regulation mechanism to obtain the right algorithm for finding the shortest path in a network.
This type of research has two goals. One is to understand the mechanisms underlying "intelligent" behavior in the simplest of organisms; without this first step, one cannot hope to understand the same mechanisms in more evolved organisms, such as animals or men. The second is to explore alternative, potentially fruitful approaches for challenging network optimization problems, such as the design of connectivity networks of low total cost.
Focus