Tikalon Blog by Dev Gualtieri

Tikalon Header

Slimy Computation

September 15, 2011

Science was not always a noble profession. The early practice of chemistry , as alchemy , was not well regarded, since it was a refuge for charlatans promising to change lead to gold or offering to cure incurable illnesses. There have been some isolated transgressions in today's science, such as falsification of data, plagiarism , and Ph.D.s selling items of dubious benefit on cable television , but our profession is generally clean. Perhaps I should include the occasional stretching of the truth on presentations to corporate management and funding agencies.

The adjective, "slimy," is not typically applied to science, except for the areas of biology that actually involve actual slime . The adjective, "slimy," is usually reserved for description of certain sectors of the financial industry . We certainly don't expect to hear about anything slimy in computer science . That's why a series of papers by Andrew Adamatzky , a professor of computer science at the University of the West of England (Bristol, UK), is so interesting. These papers describe computations by slime mould .[1-3]

First, a comment on nomenclature . I was taught to spell mould as "mould." This makes a lot of sense, since it eliminates the confusion between the type of mold used to make shapes. Unfortunately, the shaping mold is sometimes spelled as mould, too. Apparently the British prefer words like colour and flavour, while Americans prefer their u-barren alternates. My weekly reading of Nature has likely reinforced my mouldy habits.

Adamatzky describes himself as a "Professor in Unconventional Computing in the Department of Computer Science, ranger of the Unconventional Computing Centre, and a member of Bristol Robotics Lab." He's the Editor in Chief of the International Journal of Unconventional Computing and the Journal of Cellular Automata , and the author of numerous books and journal articles .

Using slime mould to solve problems is an example of metaheuristic problem solving using the slime mould itself as the computer. Ant Colony Optimization (ACO) is a related approach that takes its inspiration from the way that ants find a direct pathway from food to their colony. This same strategy is useful for things such as routing messages in a network , the placement of conductor traces on a printed circuit board , and solving the Travelling Salesman Problem.

While searching for food, ants initially wander aimlessly in a random search. When an ant finds food, it returns to its colony, and during his return he lays down a trail of a pheromone. Other ants will tend to remain on this pheromone trail, find the food source, and intensify the trail with their own pheromones on their return to the colony.

The pheromone will evaporate , and, as a result, short paths with the most pheromone are favored. The ants' algorithm avoids convergence to a locally optimal solution , such as going the too long way around a large rock.

The slime mould, Physarum polycephalum , is a large cell organism that's visible with the naked eye. The mould exhibits foraging behavior reminiscent of the ant example, above.[1] When an oat flake is placed at the center of a maze as an attractant, an inoculated mould will grow a pronounced protoplasmic tube towards the attractant.

This protoplasmic tube is the solution of the maze that's driven by the gradient of chemical attractants propagating from the target. A video is available at http://www.youtube.com/user/PhysarumMachines .[4] A similar experiment reconstructed an approximation of the Mexican Federal Highway System linking nineteen major cities that were marked by oat flakes. The mould was inoculated at Mexico City .[5] Maze solved by slime mould P. polycephalum

Maze solved by slime mould P. polycephalum

Maze-solving with the plasmodium, P. polycephalum. The figures show the maze, and the path of the mould from the point of inoculation to an oat flake placed at the center. A video is available at
http://www.youtube.com/user/PhysarumMachines . (Via arXiv, Ref. 1).

Leaving the slime world and entering the realm of crystallization that was one of my specialties, Adamatzky has examined the use of crystallization kinetics in computing segmentation.[6] I reviewed Voronoi tessellation in a previous article (Segmentation, June 28, 2011). The common chemical, sodium acetate , can solve a planar segmentation problem for points represented by crystal nuclei. As can be seen in the figure, the crystal domains instantiate a Voronoi tessellation for the crystal nuclei.

Figure caption

Voronoi tessellation of crystal nucleation points in sodium acetate. (Via arXiv, Ref. 6).

References: