Tikalon Header Blog Logo

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.

Figure caption

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

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 solution to Mexican highway routing

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]

Physarum populating a globe.

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]

Physarum populating a map

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:

  1. Marco Dorigo, Mauro Birattari, and Thomas Stuzle, "Ant Colony Optimization," IEEE Computational Intelligence Magazine, vol. 1, no. 4 (November, 2006), pp. 28-39.
  2. Ant Colony Optimization Home Page
  3. Andrew Adamatzky and Theresa Schubert, "Schlauschleimer in Reichsautobahnen: Slime mold imitates motorway network in Germany," arXiv Preprint Server, September 16, 2012.
  4. 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.
  5. Emanuele Strano, Andrew Adamatzky and Jeff Jones, "Vie Physarale: Evaluation of Roman roads with slime mold," arXiv Preprint Server, April 8, 2012.
  6. Soichiro Tsuda, Jeff Jones, Andrew Adamatzky and Jonathan Mills, "Routing Physarum with electrical flow/current," arXiv Preprint Server, April 8, 2012.
  7. 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.
  8. 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.
  9. Andrew Adamatzky, "Slime mould solves maze in one pass ... assisted by gradient of chemo-attractants," arXiv Preprint Server, August 24, 2011.
  10. Andrew Adamatzky, "Slime mould computes planar shapes," arXiv Preprint Server, June 1, 2011.
  11. Andrew Adamatzky and Selim G. Akl, "Trans-Canada Slimeways: Slime mould imitates the Canadian transport network," arXiv Preprint Server, May 25, 2011.
  12. 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.
  13. Jeff Jones and Andrew Adamatzky, "Towards Physarum Binary Adders," arXiv Preprint Server, May 13, 2010.
  14. Andrew Adamatzky, "Slime mould logical gates: exploring ballistic approach," arXiv Preprint Server, May 13, 2010.
  15. 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
  16. Andrew Adamatzky and Jeff Jones, "Programmable reconfiguration of Physarum machines," arXiv Preprint Server, January 28, 2009.
  17. Andrew Adamatzky, "Physarum boats: If plasmodium sailed it would never leave a port," arXiv Preprint Server, January 28, 2009.
  18. Andrew Adamatzky, "Towards Physarum robots: computing and manipulating on water surface" arXiv Preprint Server, April 13, 2008.
  19. Physarum Approximation of Mexican Federal Highways, YouTube video, Sep 13, 2010.
  20. Adam Mann, "Slime Molds Take Over the Globe," Wired, September 21, 2012.
  21. 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.