American Scientist

Five years ago a column in this series titled "How to Avoid Yourself" described the geometry of paths traced out by a random walker who refuses to set foot in the same place twice. Soon after the article appeared, I received a letter from Mark A. Wilson of the College of Wooster, who pointed out that some of my computer-generated paths were anticipated by millions of years in the fossil record of early life. He referred me to the Treatise on Invertebrate Paleontology, an immense multivolume work sponsored by the Geological Society of America. Specifically, I was directed to Part W, Miscellanea, and within that part to Supplement 1, Trace Fossils and Problematica, written by the late Walter Häntzschel. As promised, I found there photographs and drawings of rock surfaces bearing intricate zigzag and spiral patterns that look very much indeed like certain computer-generated self-avoiding walks. Most of these "trace fossils" are interpreted as trails left behind by worms foraging in the muddy sediments of the seafloor. Can computer programs that generate similar geometric figures reveal anything about the creatures that made the fossil trails?

Wilson and I were not the first to ask this question. As a matter of fact, trace fossils were the inspiration for one of the earliest computer simulations of animal behavior, published in 1969 by David M. Raup of the University of Rochester and Adolf Seilacher of the University of Tübingen. Their ingenious model reproduced some of the more distinctive features of the fossilized trails, such as the prevalence of zigzag and spiral motifs. And the principle of the self-avoiding walk was a key element of the simulations: No worm was allowed to waste effort grazing in territory that had already been traversed.

In the decades since then, convoluted worm trails have remained a favorite subject for computer simulations. Here I shall review four more models designed specifically to explain the same trace fossils. The point of departure for all the simulations is a supposition about why the animals created trails of this general type. The driving force is taken to be a need to optimize foraging efficiency, so that every bit of territory is grazed once but only once. Given this underlying imperative, the question becomes how the animals created the patterns, or in other words what algorithms they employed to guide their movement. Because the primitive organisms had limited sensory and cognitive capabilities, the algorithms must have been fairly simple. And the computer simulations confirm that a few simple rules are enough to generate most of the observed patterns. Thus it appears that the how question has a plausible answer. But certain doubts remain about the why question. Is foraging efficiency really what motivated these mysterious animals?

Ichnology for the Ichnorant

When I first saw the photographs in Trace Fossils and Problematica, I assumed that the meandering paths had been inscribed by animals browsing on the surface of the seafloor, like snails leaving a slime trail on the glass of an aquarium. My assumption was mistaken; most of the fossils are actually burrows formed by worms living below the sediment surface. This was my first clue that understanding the nature of the trails might require some actual knowledge of fossils, rather than merely treating them as an exercise in abstract pattern formation.

The study of trace fossils—as distinct from body fossils—is the discipline known as ichnology (from the Greek ichnos, footprint). It is practiced by a small but thriving community, which has its own journals, conferences, traditions and vocabulary. Lots of vocabulary. Ichnology lives in a kind of parallel universe set apart from the rest of paleontology, identifying and naming "ichnospecies," which often have no known correlates among conventional biological species. In other words, ichnologists may conclude that various trace specimens were all made by the same kind of organism (thus constituting an ichnospecies), but they can rarely associate the ichnospecies with an animal known from body fossils.

The traces that resemble self-avoiding walks have been classified in ichnospecies such as Nereites cambrensis (from the Paleozoic era) and Helminthoida labyrinthica (found in Cretaceous and Eocene strata). None of these ichnospecies have been matched with known organisms, but most authors suggest they were worms of one kind or another. Expert opinion on the structure of the fossils is that they are tunnels rather than surficial grooves. Some tunnels are hollow, with walls consolidated by a mucous secretion; others are packed with fecal pellets, indicating that the animal was eating its way through the sediment.

Even though the animals lived in rather than on the seafloor, their trails are remarkably planar. This is mildly curious—what constrained their movements to two dimensions?—and also important in the context of self-avoiding walks. When confined to a plane, a self-avoiding walker is in constant peril of becoming trapped in a cul de sac of its own creation, surrounded by previously occupied sites. Although such one-way dead ends are also possible in higher dimensions, they are rarer. In two-dimensional space, trapping is so common that a random self-avoiding walker almost never gets far; constructing a long walk takes careful planning. The walk usually has a repetitive pattern—as seen in the ichnofossils.

Anyone who has ever mowed a lawn will recognize two of the most common motifs in the fossils. The first is the back-and-forth meandering pattern known as boustrophedon. (The original sense of this word is always given as "going as the ox plows," although I suspect the ox has little choice in the matter.) The worm follows a straight track for a certain distance, then makes a hairpin turn and proceeds parallel to the first track, then another 180-degree turn the other way. Thus the pattern grows as a series of alternating left and right hairpin turns, connected by straight segments traversed in opposite directions.

The second common motif is a spiral, which is even simpler. A left-handed worm follows the rule: Always turn left as sharply as you can without crossing your own path. The result is an Archimedean spiral, with the radius increasing by equal increments on each revolution. Note that the spiral is an outward one, formed of ever-larger loops. When I mow my lawn, I start at the perimeter and spiral inward, so that the last patch of grass to be mown is near the middle. As research for this article, I decided to try it the other way, beginning where I usually end. The experiment was not a success; I ran out of lawn on one edge while there was still a wide swath to mow elsewhere. I'll have more to say on this point below.

Phobotaxis, Thigmotaxis, Strophotaxis

When Raup and Seilacher wrote their fossil-trail simulation in the 1960s, the output of the program was a path drawn by an x-y plotter, a mechanical contraption that today is in itself something of a fossil. In other respects, however, the model takes a thoroughly modern, algorithmic approach to understanding animal behavior. Following earlier work by Rudolf Richter, they assumed the worm obeys three basic impulses. Phobotaxis forbids the worm to cross its own trail (or any other trail, for that matter). Thigmotaxis, in contrast, urges the worm to stay close to an existing trail. Finally strophotaxis is a proclivity for making U-turns from time to time. Raup and Seilacher added a fourth action: Go straight if none of the other rules apply.

In the program, the worm examines the territory immediately ahead and to each side, looking for evidence of previous passages, then acts accordingly. If it senses a trail, it turns either toward it or away from it, depending on the balance of phobotactic and thigmotactic forces; if the way ahead is clear, the worm can either go straight or make a U-turn. Program parameters determine the propensity to choose each of these alternatives, as well as other variables such as the length of a straight run or the minimum turning radius. By tuning the parameters, Raup and Seilacher were able to reproduce some features of fossil tracks with impressive fidelity. The plotter's pen traced out spirals and meanders as well as curves that begin as a spiral and later switch to meandering (a transition frequently observed in real fossils).

But perhaps the program's ability to match the fossil patterns is not so surprising, since it was designed explicitly for that purpose. Present-day tastes favor a less direct approach. The rules of phobotaxis and thigmotaxis—which together cause the worm to adhere to its own path without crossing it—seem natural enough, but strophotaxis—the penchant for making U-turns—is something one would like to see emerge from simpler rules rather than being a built-in axiom.

Consider a worm burrowing parallel to a straight segment of trail. What happens when the segment abruptly ends? A spiral-drawing program handles this situation gracefully: The worm just continues applying the thigmotactic rule, turning around the end of the segment. The zigzag algorithm is not so simple. One idea is to interpret the end of the guide segment as a signal to make a hairpin turn in the opposite direction. This works well in the mathematically uniform world of computer simulations but might be unreliable for real worms on an irregular seafloor. Another strategy is to let the worm generate the pattern without reference to external cues, alternating left and right U-turns and connecting them by straight segments of equal length. But such an algorithm seems to require more cognitive capacity than we want to attribute to a Paleozoic worm. The trail-maker must remember when to turn left and right and must measure the straight segments.

Seilacher proposed an ingenious alternative: The worm's body length might serve as a natural unit of measure. The worm would start a new U-turn whenever it sensed its tail uncoiling from the last one, and this same signal would also indicate the direction to turn. It's a clever notion and seems like just the kind of thing that natural selection would come up with. But natural selection has come up with something else as well. Certain fossil trails have a recursive, multiscale structure: Large meanders are composed of smaller meanders of similar shape. It's hard to see how Seilacher's mechanism could account for these paths.

Rectangulus and the Quadrille Worm

A few years after the Raup-Seilacher model appeared, Frank Papentin of Tübingen chose trace fossils as one of several examples he explored in a simulation of Darwinian evolution. Instead of tuning parameters by hand to achieve the desired patterns, Papentin encoded the parameters in genes subject to mutation and recombination, then applied selection pressure favoring compact but self-avoiding configurations. His worms lived on a square lattice—he named the species Rectangulus—and so they could make turns only in multiples of 90 degrees. If you make allowance for this geometric limitation, the patterns bear a strong resemblance to some trace fossils.

On the other hand, the genes that governed the behavior of Rectangulus were rather complex, which somewhat diminishes the sense of wonder when an intricate pattern evolves without the programmer's direct intervention. The genes regulated behaviors such as turning spontaneously, turning to avoid a trail, avoiding narrow channels between trails, maintaining contact with existing trails, and switching from spiraling to zigzag motion. Given these traits as tools to work with, it's not hard to see how Darwinian selection would construct patterns as elaborate as those of the trace fossils; the question is how such traits evolved. Still, Papentin's study was another pioneering one, an early application of the technique now known as genetic programming.

In the same period, Michael S. Paterson of the University of Warwick, John Horton Conway of the University of Cambridge and Michael Beeler of MIT were also inspired by the trace-fossil patterns. They turned the foraging process into a mathematical puzzle, which was described in a technical report by Beeler and in a Scientific American article by Martin Gardner. Their version of the worm's world is highly abstract. The worm eats its way along the links of a regular lattice, at each node choosing a new link from among those that have not already been eaten. (If there are no uneaten links, the worm dies.) The choice of direction is determined entirely by the pattern of eaten and uneaten links. For example, suppose a worm on a square grid enters a node and finds that the link to its right is already eaten but the links to the left and straight ahead are still available. The worm must choose one of the uneaten links, and will always make the same choice in the same circumstances. The set of rules for making decisions defines the species of worm.

On a square grid (Beeler calls this a "quadrille worm") there are only a few possible species, and none of them lives long; the largest quadrille fossil consists of just 16 links. But on a triangular grid, where six links meet at each node, Beeler counted 1,296 species. Most of these worms too have only a limited lifespan, but some sail off toward infinity and will never die. The fate of a few species remains uncertain even today: They do not have the kind of repetitive, propagating pattern seen in the infinite species, but they have been followed for hundreds of millions of steps without showing any sign of expiring.

What's lost in this model, of course, is most of the biology; the scheme is too abstract to predict the behavior of real worms. Even so, it offers evidence that very simple rules might be enough to generate the trace-fossil patterns.

Following the Paper Trail

Surely the least abstract simulation of trace-fossil worms was described in 1997 by Tony J. Prescott and Carl Ibbotson of the University of Sheffield. They did it with hardware—specifically, a robot built from Lego parts, which marked its trail by paying out a roll of toilet paper behind it. Arms extending from each side of the body carried pairs of optical sensors, which could detect the white paper against a dark floor. An on-board computer steered the machine by applying the now-familiar rules of thigmotaxis, phobotaxis and strophotaxis. The basic idea was to stay parallel to an existing trail by keeping the edge of the paper between the two sensors on one side of the chassis. If both sensors lost contact with the trail, the robot would steer toward it; if both sensors detected the presence of paper, the robot would veer away to avoid a crossing.

Getting the robot to produce a spiral was particularly easy. In fact, a spiral is the natural product of the rules just stated, given a bias favoring the sensors on one side or the other. Initially there is no trail to detect, and so the robot turns continually toward the favored side. After making a 360-degree loop, it encounters its own trail and begins spiraling outward.

Making zigzag traces is only slightly more complicated. All that's needed to initiate a U-turn is to transfer control from the sensors on one side of the body to those on the other. But the robot must still decide when to turn. Prescott and Ibbotson used a simple timer: The worm always turns after a fixed interval. With appropriately chosen parameters, they were able to generate the common motif of a spiral that evolves into a meander. At the outset, when the radius of the spiral is small, the worm can complete a few full revolutions before the internal timer runs out; later, at a larger radius, the timer triggers a U-turn before a full revolution is completed.

Back in the immaterial world of software, a model published in 1998 by Oyvind Hammer of the Paleontological Museum in Oslo returns to the simulated-evolution methods of Papentin. A population of 400 worms is let loose in an environment with limited food resources, and only the most successful grazers are allowed to pass on their genes. Each worm's movements are controlled by a network of components such as sensors, oscillators, memory elements, adders and multipliers, which initially are wired up randomly. It is the connections between these modules that are altered by mutation and recombination.

Under conditions of intense competition, Hammer's worms evolve from random toward systematic foraging. In particular, the worms learn to move rapidly between isolated patches of food, but they dawdle within a patch. Hammer's worms did not develop the kind of tightly organized meanders produced by ichnospecies such as H. labyrinthica. They also seem to have a habit of nibbling around the edges of a patch of food, rather than spiraling from the inside out.

The Worm Turns

This long series of computer (and Lego) experiments, extending over almost 35 years, leads to reasonable conjectures about how primitive burrowing invertebrates could have created the intricate patterns seen in ichnofossils. But the question of why the worms evolved these peculiar habits is harder to resolve. The assumption has always been that they were optimizing their feeding strategy, maximizing the input of food while minimizing the effort to acquire it. This is still the leading hypothesis, but perhaps there is room for doubt.

One reason for skepticism is that many other species live by grazing or foraging, but none (as far as I know) organize their feeding with such compulsive geometric precision. Sheep and cattle do not crop a pasture in neat boustrophedonic rows. Of course there are many differences between a cow and a worm, most notably the worm's greater difficulty in seeing and moving. Still, similar obstacles confront other organisms, such as bark beetles, which must chew their way through wood. The beetles tend to avoid crossing their own path, but their galleries are usually stellate rather than spiralling or meandering.

Another question is why so many ichnofossil burrows are planar. Other burrowing animals range through a three-dimensional medium. Perhaps the worms were chasing prey that lived at some specific horizon within the sediment.

A related mystery is how the worm got to the middle of a spiral. Most simulations do not address this issue: The program merely puts the worm at an arbitrary starting point. A real worm cannot simply materialize in this magical way. If it is strictly confined to two-dimensional life, then it must cross its own path as it spirals outward. An alternative is to tunnel above or below the spiral-to-be to reach the center—but if the worm can pop into the third dimension whenever it wants to, the carefully crafted planar trails are not needed at all.

Finally, even if self-avoiding paths are advantageous to a forager, why do they have to be compact paths? After all, straight lines are also self-avoiding. Staying in one place and cleaning your plate seems tidy and well-mannered, but does such fussiness actually improve foraging efficiency?

Authors differ in their answers to this question. Some cite a patchy food distribution, suggesting that it's better to consume everything in one patch before going in search of another. Other workers argue that the deep sea is the most uniform habitat on earth, with little patchiness in the distribution of nutrients. To account for the compact fossil trails they cite the effect of competition from other worms. Although a straight trail will never cross itself, in a densely populated region many trails will cross one another. In other words, the worm's aim is not just to avoid itself but to avoid everyone else as well.

Whether the motivating factor is patchiness or competition, it remains to be shown that outward spirals and meanders are the best way to achieve the objective. For an animal foraging within a patch of seafloor—just as for a homeowner mowing a patch of lawn—spiralling in from the perimeter seems like an attractive alternative. An inward spiral might also be a useful tactic against competitors, since the initial outermost loop would effectively fence off a territory for private exploitation. I have tried to explore these possibilities in a few simulations of my own, but the results are inconclusive. The efficiency of spiralling into a patch depends critically on the shape of the patch; nonconvex shapes are troublesome. In the absence of patches, the algorithm for inward spirals has a hard time getting started: How does the worm decide how large a spiral to draw?

My personal guess is that the answers to all these questions will come not from computer simulations but from further examination of the fossil material itself. In the meantime it seems worth considering the possibility that foraging efficiency is simply not what these structures are all about. There is precedent for such a change of view. A living worm, Paraonis fulgens, makes spiral burrows that look much like some trace fossils. But Paraonis is not a forager; its burrows work like a spider's web in the sand to catch small organisms. And Seilacher has proposed that some deep-sea fossil traces are structures built not by foragers but by farmers: The tunnels were used to grow fungi, much as some ants do today.

When fossils such as Nereites and Helminthoida were first discovered, most of them were classified as plants. The sinuous paths were thought to be stems or fronds. Indeed, there was a whole phantom taxonomic group, the Fucoids, made up of plant species that are now understood to be animal trails. Is it possible that ichnology will undergo another such interpretive upheaval?

© Brian Hayes