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.
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).
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.
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.
Adamatzky is a prolific author, as his Amazon author page demonstrates.
(Photo provided by Prof. Adamatzky)
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, 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.
|A globe covered with agar gel with the slime mold, Physarum polycephalum, growing towards oat flakes placed at selected urban areas.|
(Fig. 2 of
|A map covered with agar gel with the slime mold, Physarum polycephalum, growing towards oat flakes placed at urban areas.|
(Fig. 1 of
- 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.
Latest Books by Dev Gualtieri
Thanks to Cory Doctorow of BoingBoing for his favorable review of Secret Codes!
Blog Article Directory on a Single Page
- J. Robert Oppenheimer and Black Holes - April 24, 2017
- Modeling Leaf Mass - April 20, 2017
- Easter, Chicks and Eggs - April 13, 2017
- You, Robot - April 10, 2017
- Collisions - April 6, 2017
- Eugene Garfield (1925-2017) - April 3, 2017
- Old Fossils - March 30, 2017
- Levitation - March 27, 2017
- Soybean Graphene - March 23, 2017
- Income Inequality and Geometrical Frustration - March 20, 2017
- Wireless Power - March 16, 2017
- Trilobite Sex - March 13, 2017
- Freezing, Outside-In - March 9, 2017
- Ammonia Synthesis - March 6, 2017
- High Altitude Radiation - March 2, 2017
- C.N. Yang - February 27, 2017
- VOC Detection with Nanocrystals - February 23, 2017
- Molecular Fountains - February 20, 2017
- Jet Lag - February 16, 2017
- Highly Flexible Conductors - February 13, 2017
- Graphene Friction - February 9, 2017
- Dynamic Range - February 6, 2017
- Robert Boyle's To-Do List for Science - February 2, 2017
- Nanowire Ink - January 30, 2017
- Random Triangles - January 26, 2017
- Torricelli's law - January 23, 2017
- Magnetic Memory - January 19, 2017
- Graphene Putty - January 16, 2017
- Seahorse Genome - January 12, 2017
- Infinite c - January 9, 2017
- 150 Years of Transatlantic Telegraphy - January 5, 2017
- Cold Work on the Nanoscale - January 2, 2017
- Holidays 2016 - December 22, 2016
- Ballistics - December 19, 2016
- Salted Frogs - December 15, 2016
- Negative Thermal Expansion - December 12, 2016
- Verbal Cues and Stereotypes - December 8, 2016
- Capacitance Sensing - December 5, 2016
- Gallium Nitride Tribology - December 1, 2016
- Lunar Origin - November 27, 2016
- Pumpkin Propagation - November 24, 2016
- Math Anxiety - November 21, 2016
- Borophene - November 17, 2016
- Forced Innovation - November 14, 2016
- Combating Glare - November 10, 2016
- Solar Tilt and Planet Nine - November 7, 2016
- The Proton Size Problem - November 3, 2016
- Coffee Acoustics and Espresso Foam - October 31, 2016
- SnIP - An Inorganic Double Helix - October 27, 2016
- Seymour Papert (1928-2016) - October 24, 2016
- Mapping the Milky Way - October 20, 2016
- Electromagnetic Shielding - October 17, 2016
- The Lunacy of the Cows - October 13, 2016
- Random Coprimes and Pi - October 10, 2016
- James Cronin (1931-2016) - October 6, 2016
- The Ubiquitous Helix - October 3, 2016
- The Five-Second Rule - September 29, 2016
- Resistor Networks - September 26, 2016
- Brown Dwarfs - September 22, 2016
- Intrusion Rheology - September 19, 2016
- Falsifiability - September 15, 2016
- Fifth Force - September 12, 2016
- Renal Crystal Growth - September 8, 2016
- The Normality of Pi - September 5, 2016
- Metering Electrical Power - September 1, 2016
Deep Archive 2006-2008