Amoeba-Inspired Network Design: Physarum polycephalum
For anyone interested in going into engineering, I can offer a warning: prepare to get your butt handed to you repeatedly
by nature. Many of the processes at the forefront of engineering
technology are just trying to play catch-up with what nature has done an
innumerable number of times. Photosynthesis, genetic replication, the creation of joints, even the simple act of
flight—nature has done it before, with greater ease, and often cheaper or more efficiently.
A paper in the current issue of Science discusses
the ability of a single-celled creature to create a robust network while
foraging for food—one that mimicked the Tokyo rail system in
complexity. Creating a good network is a balancing act; you need to span a large number of
nodes with a minimal number of edges (keeping cost low), while being
able to function when an edge is lost (fault
tolerant). Problems of this type are a shining example of the
adage "fast, cheap, or good: pick any two."
Many organisms grow in the form
of a connected network, and they have
the benefit of innumerable generations of natural selection behind
them. Selective pressures have
forced the organism to find a happy balance among connectedness, fault
tolerance, and cost/efficiency. The authors of the Science article use
the slime mold Physarum
polycephalum as their biological network generator, and it served as a muse for the creation of an adaptive network model.
Physarum
is a single-celled amoeboid organism that spends its time searching for
physically distributed sources of food. When starting on a fresh
substrate, it spreads in all directions to maximize the area it is
capable of searching. Behind the outer perimeter of its search area, it
forms a tubular network that connects cells to any food sources that it has
discovered. Over the course of a few hours, the network it forms connects the food sources in a manner that optimizes the
network's properties.
As part of their experimentation with the slime, the
researchers placed 36 food sources on a substrate in a manner that
mimicked the geographical layout of cities around Tokyo. (Physarum is apparently fond of oat flakes.) They then
introduced the slime mold
to the foraging grounds and compared the network that it formed with
the actual Tokyo rail network in place around the city.
Initially, the Physarum began to
spread out over the entire available area but, over time, it
concentrated its network on the tubes that connected the food sources. The
resulting network topology "bore similarity to the real rail network."
To see if the organism could be coaxed into an even closer match, the
researchers used light—which is known to inhibit the growth
of physarum—to
simulate mountains, lakes, or similar impasses that the actual rail
network must contend with.
While looking like the real network is nice, it's not exactly an objective measure. To attempt to quantify the similarity, the
researchers examined a handful of metrics used for describing topological networks. The cost of the network (total length),
efficiency (average minimum distance between nodes), and robustness
(degree of fault tolerance) were examined relative to the minimum spanning tree
(MST) for each network. The MST represents the smallest possible
network that connects all the food source (or city rail station) positions.
When compared to the length of the MST, the Tokyo rail system was 1.8 times larger, while the Physarum network
was 1.75±0.30 times larger. The average minimum distance between
cities (food sources) was 0.85 and 0.85±0.04, respectively. These two measurements illustrate the fact that Physarum-based networks have a lower "cost" but provide a relatively equal distance
between nodes.
One place where engineers did a bit better: the amoeba's networks were not as robust as the actual rail network. For the rails, four percent of the possible faults could lead to the
isolation of a node, whereas a fault in the Physarum network
has a 14±4 percent chance of leading to an isolated food source. That just won't do for Tokyo, given the frequency of monster attacks there.
Using these observations of network formation, the
researchers attempted to develop a model that was
capable of describing the network's formation. Using a simple fluid
flow model for the arms, along with sink/source terms to represent the food
sources, they were able to reproduce the Physarum network with the help of a pair of free
parameters. The authors conclude that planners might consider using the model during the preliminary
planning stages of other self-organized networks, such as remote
sensors arrays or mobile, ad-hoc networks.
Source:
Science 22 January 2010: Vol. 327. no. 5964, pp. 419 - 420 DOI: 10.1126/science.1185570
by nature. Many of the processes at the forefront of engineering
technology are just trying to play catch-up with what nature has done an
innumerable number of times. Photosynthesis, genetic replication, the creation of joints, even the simple act of
flight—nature has done it before, with greater ease, and often cheaper or more efficiently.
A paper in the current issue of Science discusses
the ability of a single-celled creature to create a robust network while
foraging for food—one that mimicked the Tokyo rail system in
complexity. Creating a good network is a balancing act; you need to span a large number of
nodes with a minimal number of edges (keeping cost low), while being
able to function when an edge is lost (fault
tolerant). Problems of this type are a shining example of the
adage "fast, cheap, or good: pick any two."
Many organisms grow in the form
of a connected network, and they have
the benefit of innumerable generations of natural selection behind
them. Selective pressures have
forced the organism to find a happy balance among connectedness, fault
tolerance, and cost/efficiency. The authors of the Science article use
the slime mold Physarum
polycephalum as their biological network generator, and it served as a muse for the creation of an adaptive network model.
Physarum
is a single-celled amoeboid organism that spends its time searching for
physically distributed sources of food. When starting on a fresh
substrate, it spreads in all directions to maximize the area it is
capable of searching. Behind the outer perimeter of its search area, it
forms a tubular network that connects cells to any food sources that it has
discovered. Over the course of a few hours, the network it forms connects the food sources in a manner that optimizes the
network's properties.
As part of their experimentation with the slime, the
researchers placed 36 food sources on a substrate in a manner that
mimicked the geographical layout of cities around Tokyo. (Physarum is apparently fond of oat flakes.) They then
introduced the slime mold
to the foraging grounds and compared the network that it formed with
the actual Tokyo rail network in place around the city.
Initially, the Physarum began to
spread out over the entire available area but, over time, it
concentrated its network on the tubes that connected the food sources. The
resulting network topology "bore similarity to the real rail network."
To see if the organism could be coaxed into an even closer match, the
researchers used light—which is known to inhibit the growth
of physarum—to
simulate mountains, lakes, or similar impasses that the actual rail
network must contend with.
While looking like the real network is nice, it's not exactly an objective measure. To attempt to quantify the similarity, the
researchers examined a handful of metrics used for describing topological networks. The cost of the network (total length),
efficiency (average minimum distance between nodes), and robustness
(degree of fault tolerance) were examined relative to the minimum spanning tree
(MST) for each network. The MST represents the smallest possible
network that connects all the food source (or city rail station) positions.
When compared to the length of the MST, the Tokyo rail system was 1.8 times larger, while the Physarum network
was 1.75±0.30 times larger. The average minimum distance between
cities (food sources) was 0.85 and 0.85±0.04, respectively. These two measurements illustrate the fact that Physarum-based networks have a lower "cost" but provide a relatively equal distance
between nodes.
One place where engineers did a bit better: the amoeba's networks were not as robust as the actual rail network. For the rails, four percent of the possible faults could lead to the
isolation of a node, whereas a fault in the Physarum network
has a 14±4 percent chance of leading to an isolated food source. That just won't do for Tokyo, given the frequency of monster attacks there.
Using these observations of network formation, the
researchers attempted to develop a model that was
capable of describing the network's formation. Using a simple fluid
flow model for the arms, along with sink/source terms to represent the food
sources, they were able to reproduce the Physarum network with the help of a pair of free
parameters. The authors conclude that planners might consider using the model during the preliminary
planning stages of other self-organized networks, such as remote
sensors arrays or mobile, ad-hoc networks.
Source:
Science 22 January 2010: Vol. 327. no. 5964, pp. 419 - 420 DOI: 10.1126/science.1185570
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.