Magazine article Science News

Travels of an Ant: Mathematical Mysteries in the Trails of Virtual Ants

Magazine article Science News

Travels of an Ant: Mathematical Mysteries in the Trails of Virtual Ants

Article excerpt

Scurrying across a sidewalk, navigating the ridges of a wrinkled picnic blanket, or crowding around a crumb on a kitchen floor, these spindly, communal insects typically attract scant attention to their varied doings--except when they get in the way. Yet in their foraging and social organization, ants display remarkable behavior worthy of detailed study.

James Propp, however, is interested in the activities of a different sort of ant. A mathematician at the Massachusetts Institute of Technology, he has spent the better part of a decade tracking an imaginary critter--a virtual ant--roaming an infinite checkerboard.

Exhibited on a computer screen, this mathematical ant blindly follows the dictates of the simple rules that Propp imposes on it and traces out a winding path across the plane. "These rules allow no freedom at all, yet you can generate very complicated--even baffling--patterns," Propp says.

"The movements may remind you a little bit of a real ant," he adds.

But Propp doesn't insist on a connection between the actions of the carefully shepherded, simple-minded ants in his simulations and the multifarious antics of ants in the wild. What intrigues him are the intricate patterns and symmetries that can emerge out of a bare-bones mathematical framework.

This pursuit represents more than just recreational mathematics. Computer scientists have studied similar models to probe the limits of computation, and physicists have used them to simulate particle interactions in a liquid.

Propp's ant universe is an example of a cellular automaton.

The mathematician starts by setting up a field of cells, typically in a checkerboard or honeycomb pattern, and allowing each cell to exist in one of several possible states. A set of rules specifying how neighboring cells influence each other determines how these states change from one moment to the next. The resulting transitions can be visualized on a grid and strung together into a movie.

One of the most famous of these models is the game "Life," invented by mathematician John H. Conway of Princeton University. The game is played on an infinite grid of square cells. Each cell is initially marked as either occupied or vacant, creating some sort of arbitrary starting configuration.

Changes occur in jumps, with each cell responding according to the rules. Any cell having two occupied cells as neighbors stays in its original state. An empty cell adjacent to three occupied cells gets filled. An occupied cell surrounded by four or more occupied cells is emptied.

These simple rules engender a surprisingly complex world that displays a wide assortment of interesting events and patterns--a microcosm that captures elements of life, birth, growth, evolution, and death. Indeed, cellular automata in general have become important mechanisms for investigating pattern formation, evolution, and artificial life (SN: 7/23/94, p.63; 5/19/90, p.312).

Virtual ants inhabit a similar realm, but the rules they obey operate a little differently. In this type of cellular automaton, a change of state occurs in only one cell at a time instead of across the board with each step.

"Their lifestyle is a humble one," Propp says.

Suppose all the cells of a particular ant universe begin in one of two possible states, designated 0 and 1 (or white and black when visualized on a computer screen). Initially, the virtual ant sits on a cell, facing in one of the four compass directions. The ant then moves in that direction to the adjacent cell.

When it arrives at its new location, the ant is programmed to change its heading by 90o to the left if it lands on a 0 cell or 90o to the right if it lands on a 1 cell. As it leaves, it causes the cell's state to switch from 0 to 1 or from 1 to 0. Thus, on its next visit to this particular cell, the ant will find an altered state and behave accordingly. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.