The Traveling Monkey

One of the classic problems of planning ahead concerns a traveling salesman who must visit customers in a number of cities scattered across the country and then return home. The problem is to find the shortest possible route visiting each city only once.

Listing all possible routes, calculating the length of each one, and picking the shortest is one possible strategy for solving the traveling salesman problem. For a large number of cities, however, such a brute-force approach takes too long.

Of course, individual instances of the salesman's problem may have simple solutions that work well under certain conditions. For example, first visiting all locations close to the starting point, then moving farther afield may work.

There's no guarantee, however, that such a strategy works in every possible case. Indeed, proceeding from the origin to the nearest point, then to the nearest point to that, and so on, doesn't generally give the shortest path.

Problems similar to the traveling salesman problem crop up in many practical situations, such as designing networks to link an array of points, routing telephone calls, allocating resources, setting timetables and schedules, planning budgets, and packing objects in bins.

It turns out that vervet monkeys can also solve the traveling salesman problem—albeit to a limited extent. In 1997, Audrey E. Cramer and C.R. Gallistel reported in an article in the journal Nature that, rather than always heading for the nearest food supply, the monkeys apparently plan their next three visits to minimize distance and travel time.

Vervet monkey (Chlorocebus pygerythrus). Wikipedia

Vervet monkeys eat fruit of various kinds, foraging on patchily distributed supplies. They typically visit several sites in a single trip. "Here we pose a question about their route-choosing mechanism: How many future destinations along the route influence the choice of the next destination," Cramer and Gallistel asked.

To find out, the researchers modeled their experiment on one performed more than two decades earlier with chimpanzees. Psychologist Emil W. Menzel carried juvenile chimpanzees around an outdoor field while he hid fruit in 18 randomly placed locations. He then released the chimps and recorded the routes taken to collect the fruits.

Menzel reported in a paper in Science that the apes remembered most of the hiding places and the type of food in each, and they rarely rechecked a place they had already emptied of food. Moreover, their search pattern bore no relation to the baiting sequence and tended to minimize the distance traveled.

Cramer and Gallistel's subjects were four adult vervet monkeys, who were carried around as grapes were hidden in six or eight small holes, randomly selected from 25 holes spaced at 1.53-meter intervals in a 5 x 5 grid.

The monkeys ignored the order in which the grapes were hidden and, like the apes, tended to minimize the distance traveled. "However, they never visited more than six hiding places, confirming earlier reports that monkeys and apes differ dramatically in how many potential destinations they can keep in mind at once," the researchers noted.

"A computer algorithm that always chose the closest site as the next destination did as well as our subjects, suggesting that such a mechanism would be adequate," they reported. "However, performance on arrays chosen specifically to test for the influence of destinations beyond the nearest showed that the choice of the next destination was strongly influenced by at least two farther destinations."

In one experiment, monkeys visited the four vertices of a diamond, one of which was the starting point. When a monkey started and ended at the same corner, it didn't simply choose the next nearest site but typically planned ahead, following the shortest route around the diamond (first to a middle location, then the far point, next to the other middle location, and back to the start).

A grape was put in the hole at the monkey's starting point (S) after it had reached the first site, requiring a return to the starting point later on in the visit sequence. The diamond route (SABCS) is shorter than the zigzag route (SACBS).

For both monkeys and chimps, future destinations affect the decision on which site to visit next.

Originally posted July 7, 1997

See also "Artful Routes."