Algorithms in Nature – Computing with slime
I’m fascinated with the way that elegant solutions to computational problems often both:
– Pop up unpredictably in nature, often where you would least expect and
– Look really beautiful.
The Shortest Path algorithm (or series of algorithms depending on exactly what result is desired) is one such example which is both computationally and aesthetically elegant.
The shortest path algorithm does what it says on the tin. Given a set of points, with a set start and a goal end point, the algorithm moves through the point cloud and calculates the cumulative weight (cost) of each way through the path. As it finds the most efficient option, it gains confidence and eventually find the cheapest way of getting from A-B.
Illustration of Dijkstra’s algorithm, one of the Shortest Path algo variants (Source: wikipedia)
I was first introduced to the algorithm through my work in 3D animation. The algorithm is widely used in visual effects because it has a lovely, organic flow to it. It looks like a plant growing. I think I first saw it in the film X-Men – there is a shape changing character called Mystique, and every time she morphs between characters the effect on her skin is a version of this algorithm.
VFX in films like X-Men heavily utilise the shortest path algorithm (Source: Digital Domain)
Further research into it revealed that it looks natural because it is actually a process found in nature. Physarum Polycephalum is a type of slime mold, a sort of semi-sentient snot, that is innately able to solve shortest-path problems.
With food placed where the stations would be, slime draws the Tokyo subway map. (Source: Harvard)
Researchers have created fascinating challenges for it by placing its spores into a tray of agar and putting food sources into the tray. They then place obstacles between the spores and let the mold to grow and discover the food sources. As soon as they are discovered, the slime reconfigures into the optimal arrangement of mass between the food sources, and slime that is far away from the food dies out, leaving behind a highlighted trail – the shortest path result.
In an amazing example, researchers placed food sources in a tray in an arrangement corresponding to the geographic locations around Tokyo. At the end of the slime discovery process, it had grown a network of tubular channels that closely matched the Tokyo subway system.
Forms of this algorithm are used widely – from geographical mapping tools like Google Maps, to network optimisation, sorting search results, financial trading.
It would be an interesting experiment to take the algorithm and apply it to socio-economic data, combining it with a map approach and set the food-weight levels to another variable such as average income, cultural diversity or employment. Whatever the results, the way that they would appear as an organic network would add another layer to the data. I like the idea of average income levels being grown with the slime, representing the flow of capital as literally a crawling, growing animal.