There is a famous problem in the field of computer science called the Traveling Salesman Problem (TSP for short). It goes something like this: you are a salesperson who needs to travel to some specific set of cities, and you want to travel the shortest distance possible. What is the shortest route such that you visit each city once and then return to the location you started? This problem is famous for two reasons. First, we face problems similar to this all the time, whether it is simple things like running errands after work or important business decisions like how to set up a delivery route. Second, this problem is famous is because it is hard. Really hard. Yet, people are actually pretty good at quickly and efficiently finding the shortest route, or one very close to it. This has led some scientists to wonder: if people are good at solving the TSP, are animals?

Before we dive into answering that question, we should get a sense of just how hard the TSP is, and how people are able to solve this problem anyway. The only known way to guarantee that a given route is the shortest one is to calculate every possible route and rank them by distance. For a small number of destinations, this is easy. The number of possible routes is the factorial of the number of destinations. So for four destinations there are 4 * 3 * 2 *1 = 24 possible routes. By twenty destinations, though, the number of possible routes is 2,432,902,008,176,640,000. That means if you had a super-fast computer that could calculate the distance of 1 billion routes per second, it would still take that computer 77 years to determine the shortest route!

So how do you manage to run more than a few errands without becoming paralyzed by computations? Well, humans use a few simple rules to approximate the shortest route, many of which researchers have identified and named. The simplest of these, the Nearest Neighbor rule, simply says always move to the closest destination. Another strategy, the Convex Hull, is a little more complicated, but often produces better results than Nearest Neighbor. Imagine each destination is a peg; the Convex Hull strategy finds a solution by placing a rubber band around the outside edge of all the pegs, then pulling a section of the band in to connect the pegs on the inside. What’s amazing about most of these strategies is that people don’t use them intentionally and usually aren’t even aware of what they are doing. Even more incredible, people switch between several different strategies depending on the context, so we always perform better than any single heuristic would predict¹.

Which brings us to animals. There are lots of reasons to think animals should use heuristics as well, and possibly switch between them like humans do. Moving efficiently between destinations means animals can spend more time eating and reproducing. Our basic evolutionary tenets tell us that behaviors that help an animal survive and reproduce should be selected for and thus spread through populations. Actually studying how animals solve navigational problems like the TSP, however, is quite challenging.

One animal we know the most about is the bumblebee. Because of the way bumblebees forage, it is easier to infer their navigational decision-making process than it is with most other animals. What we have learned, however, is that bumblebees don’t seem to use the same strategies as humans. Instead, they do something called traplining, where they learn one route and use that same route repeatedly. Over time, they make small adjustments to the route; if the adjustment makes the route shorter they remember it, but if the adjustment makes the route longer they forget it². Though this eventually gets bumblebees to reasonably short routes, the process is longer and less efficient than the one used by people.

Non-human primates may be the best candidate for animals that solve the TSP like humans, but the evidence is still weak. One experimental study found that macaque monkeys consider how close a destination is to other destinations when making a decision³, something humans do too. But similar studies have failed to find the same thing⁴. In the wild, chimpanzees and likely other primates will move straight to a valuable resource well before they can see or smell it, suggesting at the very least they can remember where resources are and navigate to them⁵. Capuchin monkeys also compare the value of a resource to the energy cost of getting to it when deciding whether to take a detour to that resource⁶. None of this, however, tells us how primates or other animals decide between many destinations.

The good news is that more research on the subject is underway! New GPS technology is helping scientist track the movements of animals more accurately, so it is possible to see what decisions they make over long periods of time. Satellite imagery has also helped scientists map the resources in an animal’s environment. We should start to see more information about how animals solve navigation problems like the TSP soon, so stay tuned! And if a monkey with a briefcase knocks on your door, ask how it found you.

Author Alexander Vining is a 2nd-year graduate student in the Animal Behavior Graduate Group. He studies movement planning in primates and other animals.

References

1. MacGregor, J. N., & Ormerod, T. (1996). Human performance on the traveling salesman problem. Attention, Perception, & Psychophysics, 58(4), 527-539.
2. Lihoreau, M., Chittka, L., & Raine, N. E. (2010). Travel optimization by foraging bumblebees through readjustments of traplines after discovery of new feeding locations. The American Naturalist, 176(6), 744-757.
3. Cramer, A. E., & Gallistel, C. R. (1997). Vervet monkeys as travelling salesmen. Nature, 387, 464.
4. Janson, C. (2014). Death of the (traveling) salesman: primates do not show clear evidence of multi‐step route planning. American journal of primatology, 76(5), 410-420.
5. Janmaat, K. R., Ban, S. D., & Boesch, C. (2013). Chimpanzees use long-term spatial memory to monitor large fruit trees and remember feeding experiences across seasons. Animal Behaviour, 86(6), 1183-1205.
6. Janson, C. H. (2016). Capuchins, space, time and memory: an experimental test of what-where-when memory in wild monkeys. In Proc. R. Soc. B (Vol. 283, No. 1840, p. 20161432). The Royal Society.