| Tikalon Blog is now in archive mode.
An easily printed and saved version of this article, and a link
to a directory of all articles, can be found below: |
|
This article |
| Directory of all articles |
Marco Polo Physarum
October 1, 2012
Long before
Columbus, the
Italian,
Marco Polo (1254-1324) familiarized
Europe with the unknown parts of the world to the
East. The expression, "
getting there is half the fun," certainly didn't apply in the
thirteenth century, but there were established
trade routes designed by the simple fact that they were the tried and tested best ways to get from one place to another.
These trade routes are now collectively known as the
Silk Road, which comprised routes linking
Asia, the
Middle East,
Northern Africa, the
Mediterranean, and other parts of Europe. As its name implies,
silk from
China was the principal commodity being transported. The extent of this network was several thousand
miles.
The Travels of Marco Polo. Trading along such routes had been ongoing for many centuries before Polo, but Polo was among the first Europeans to make such a trip. (Via Wikimedia Commons, modified))
Finding the best route is a common task in more ways than plotting a trip to Grandma's house. Routing
conductors on an
integrated circuit is one of the more extreme routing tasks, and it's made more difficult by the fact that you can route the conductors in various stacked
planes connected by
vias.
A few
computational tools have been developed to solve routing tasks. The most famous of these are solutions to the
Travelling Salesman Problem, and there's also
Ant Colony Optimization (ACO), which I reviewed in a
previous article (Ants in My Computer, November 8, 2006).
The ACO technique is a
probabilistic method for finding optimum paths on
graphs. Its invention took its inspiration in the way that
ants find the best path between their colony and a food source. At first, the ants wander aimlessly in search of food, but once it's found they travel back to their nest. In their travels, the ants deposit a trail of a
pheromone. This trail is followed by other ants, who add their own pheromone to the trail. The optimization of trail length occurs since the pheromone
evaporates, so short paths are favored. [1-2]
An
organism far simpler than an ant can solve for an optimum routing. The slime mold,
Physarum polycephalum, is an
organism that's visible to the naked eye. The mold exhibits
foraging behavior reminiscent of ant
foraging. The mold will extend a
protoplasmic tube towards a food source, attracted there by a chemical
gradient.
Andrew Adamatzky and his colleagues at the
Bristol Robotics Laboratory of the
University of the West of England have been using this property of slime mold for many years to solve a variety of route optimization problems. Their research is conveniently accessible on
arXiv.[3-18] I wrote about some of this work in a
previous article (Slimy Computation, September 15, 2011).
Andrew Adamatzky
Adamatzky is a prolific author, as his Amazon author page demonstrates.
(Photo provided by Prof. Adamatzky)
Using slime mold, Adamatzky's team was able to do such things as reproduce a
map of the
Mexican Federal Highway System by
inoculating a mold at
Mexico City and placing
oat flakes at the location of the principal
Mexican cities (see photograph).[12,19] In such cases, the slime mold acts to solve the routing problem by a
metaheuristic technique; that is, its
chemical sense optimizes a solution by iteratively making improvements. The slime mold gets
feedback as to how well its optimization is going, since it gets more food.
Physarum slime mold solution to Mexican highway routing.
(Still from a YouTube video)[19]
Adamatzky's most recent work involves an hypothetical
colonization of the world, which includes both land routes and
ocean crossings.[20-21] The experiment involved coating a
globe with
agar gel and placing oat flakes at strategic points (see photograph). The agar was removed from ocean areas. When the colonization is nucleated at
Beijing,
Physarum polycephalum slime mold first approximates the Silk Road. Adamatzky, quoted on
Wired News, states that the Physarum model also indicates the possible expansion of China's
sphere of influence in the world.[20]
A globe covered with agar gel with the slime mold, Physarum polycephalum, growing towards oat flakes placed at selected urban areas.
(Fig. 2 of
arXiv preprint.[21]
The strategic points for locations of the
nutrient oat flakes were twenty-four major cities, including
Tokyo,
Moscow,
Mumbai (Bombay),
Kinshasa,
New York City,
Mexico City and
Bogotá. After the mold was inoculated at Beijing, it first spread over the East, then through
India to the Middle East. From
Istanbul, it traveled to Moscow, and then to
England and
Scandinavia. Not surprisingly, from there the mold colonized
North, then
South America. Branches from the East colonized
Australia and
New Zealand.[20-21]
Multiple
experiments were conducted with both the globe, and with flat maps. There were slight differences, as discussed in the his paper on this project,[21] but the
Pacific Ocean was too wide for the Physarum to cross. This allowed the map and globe experiments to be roughly equivalent. The present day equivalent of the Silk Road is the
Asian Highway network, comprising 87,000 miles of roads connecting thirty-two countries. The slime mold model corresponded to about three-quarters of both the Silk Road and the Asian Highway network.[20]
A map covered with agar gel with the slime mold, Physarum polycephalum, growing towards oat flakes placed at urban areas.
(Fig. 1 of
arXiv preprint.[21]
![]()
References:
- Marco Dorigo, Mauro Birattari, and Thomas Stuzle, "Ant Colony Optimization," IEEE Computational Intelligence Magazine, vol. 1, no. 4 (November, 2006), pp. 28-39.
- Ant Colony Optimization Home Page
- Andrew Adamatzky and Theresa Schubert, "Schlauschleimer in Reichsautobahnen: Slime mold imitates motorway network in Germany," arXiv Preprint Server, September 16, 2012.
- Andrew Adamatzky, Michael Lees and Peter M.A. Sloot, "Bio-Development of Motorway Networks in the Netherlands: A Slime Mould Approach," arXiv Preprint Server, September 13, 2012.
- Emanuele Strano, Andrew Adamatzky and Jeff Jones, "Vie Physarale: Evaluation of Roman roads with slime mold," arXiv Preprint Server, April 8, 2012.
- Soichiro Tsuda, Jeff Jones, Andrew Adamatzky and Jonathan Mills, "Routing Physarum with electrical flow/current," arXiv Preprint Server, April 8, 2012.
- Andrew Adamatzky, Selim Akl, Ramon Alonso-Sanz, Wesley van Dessel, Zuwairie Ibrahim, Andrew Ilachinski, Jeff Jones, Anne V. D. M. Kayem, Genaro J. Martinez, Pedro de Oliveira, Mikhail Prokopenko, Theresa Schubert, Peter Sloot, Emanuele Strano and Xin-She Yang, "Are motorways rational from slime mould's point of view?" arXiv Preprint Server, March 13, 2012.
- Andrew Adamatzky, Bernard De Baets and Wesley Van Dessel, "Slime mould imitation of Belgian transport networks: redundancy, bio-essential motorways, and dissolution," arXiv Preprint Server, December 19, 2011.
- Andrew Adamatzky, "Slime mould solves maze in one pass ... assisted by gradient of chemo-attractants," arXiv Preprint Server, August 24, 2011.
- Andrew Adamatzky, "Slime mould computes planar shapes," arXiv Preprint Server, June 1, 2011.
- Andrew Adamatzky and Selim G. Akl, "Trans-Canada Slimeways: Slime mould imitates the Canadian transport network," arXiv Preprint Server, May 25, 2011.
- Andrew Adamatzky, Genaro J. Martinez, Sergio V. Chapa-Vergara, Rene Asomoza-Palacio and Christopher R. Stephens, "Approximating Mexican highways with slime mould," arXiv Preprint Server, October 4, 2010.
- Jeff Jones and Andrew Adamatzky, "Towards Physarum Binary Adders," arXiv Preprint Server, May 13, 2010.
- Andrew Adamatzky, "Slime mould logical gates: exploring ballistic approach," arXiv Preprint Server, May 13, 2010.
- Andrew Adamatzky and Jeff Jones, "Road planning with slime mould: If Physarum built motorways it would route M6/M74 through Newcastle," arXiv Preprint Server, December 20, 2009
- Andrew Adamatzky and Jeff Jones, "Programmable reconfiguration of Physarum machines," arXiv Preprint Server, January 28, 2009.
- Andrew Adamatzky, "Physarum boats: If plasmodium sailed it would never leave a port," arXiv Preprint Server, January 28, 2009.
- Andrew Adamatzky, "Towards Physarum robots: computing and manipulating on water surface" arXiv Preprint Server, April 13, 2008.
- Physarum Approximation of Mexican Federal Highways, YouTube video, Sep 13, 2010.
- Adam Mann, "Slime Molds Take Over the Globe," Wired, September 21, 2012.
- Andrew Adamatzky, "The World's Colonisation and Trade Routes Formation as Imitated by Slime Mould," arXiv Preprint Server, September 18, 2012.
Permanent Link to this article
Linked Keywords: Christopher Columbus; Italian; Marco Polo; Europe; Orient; East; Cunard Line; getting there is half the fun; thirteenth century; trade route; Silk Road; Asia; Middle East; Northern Africa; Mediterranean; silk; China; mile; The Travels of Marco Polo; Wikimedia Commons; electrical conductor; conductor; integrated circuit; plane; via; computation; Travelling Salesman Problem; Ant Colony Optimization; probability; probabilistic; graph; ant; pheromone; evaporation; organism; Physarum polycephalum; foraging behavior; foraging; protoplasmic; gradient; Andrew Adamatzky; Bristol Robotics Laboratory; University of the West of England; arXiv; Amazon; map; Mexican Federal Highway System; inoculation; Mexico City; oat; Mexican; metaheuristic; chemical; feedback; YouTube; colonization; ocean; globe; agar gel; Beijing; Physarum polycephalum; Wired News; sphere of influence; nutrient; Tokyo; Moscow; Mumbai (Bombay); Kinshasa; New York City; Mexico City; Bogotá; India; Istanbul; England; Scandinavia; North America; South America; Australia; New Zealand; experiment; Pacific Ocean; Asian Highway network.