Tikalon Blog by Dev Gualtieri

Tikalon Header

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: