Tuesday, 19 June 2012

Mouldy Networks

Physarum polycephalum is a type of slime mould with a certain knack for graph theory. Like most of us, the organism spends the majority of its life searching for something to eat. Unlike us however, it has the ability to exploit multiple food sources simultaneously. Upon discovering a number of edible options within it's environment, the Physarum constructs remarkably efficient transport networks between them as a means of distributing nutrients amongst its many nuclei. By way of this special talent, the brainless amoeba has managed to offer up some pointers to infrastructure engineers in recent years.

It's misleading to talk about Physarum as a singular entity however. The mould's apparent design intelligence isn't the product of a singular higher level brain. Rather it is an ecological property of many lower level decision-making entities acting in parallel. It is a classic example of decentralized problem solving. The Physarum's infrastructure emerges from local interactions amongst it's nuclei population - none of which have any idea of the global state of the system they belong to. While the specific details of these local interactions are beyond my limited knowledge of biology, as it turns out modelling them isn't so different from the chemotaxis based multi-agent systems that I've been playing with recently.

The above is based on a multi-agent approximation of Physarum network formation put forward by Jeff Jones in his paper "Characteristics of Pattern Formation and Evolution in Approximations of Physarum Transport Networks". What is most interesting about Jones's approach is the complexity differential between the agent behaviors and their emergent output. Once again agent interaction is strictly indirect. They communicate only through detection and deposition of "pheromone" gradients within their shared environment. The decision-making routines themselves are surprisingly discrete - each agent samples in 3 forward biased locations and picks only the one with the highest pheromone concentration to move towards. With a large enough population of agents however, this behaviour produces self-minimizing networks similar to those seen amongst the organism they aim to emulate. 

In implementing it myself in Processing, I've stayed mostly true to the source material. Where I did deviate a bit was in making the agent's sampling routine less discrete. Each of the 3 pheromone samples play into a weighted vector sum that determines the agent's new heading. I also added a foraging behaviour where each agent seeks out regions of low pheromone concentration rather than high (00:09).

Platforms: Processing