Pigeons, Curves, and the Traveling Salesperson Problem

In Mo Willems’ children’s book Don’t Let the Pigeon Drive the Bus!, the main character—a pigeon, obvs—uses every trick in the book (literally) to convince the reader that it should be allowed to drive a bus when the regular human driver suddenly has to leave. Willems’s book had an unintended scientific consequence in 2012, when the entirely respectable journal Human Cognition published an entirely respectable paper by the entirely respectable researchers Brett Gibson, Matthew Wilkinson, and Debbie Kelly. They showed experimentally that pigeons can find solutions, close to optimal, to simple cases of a famous mathematical curiosity: the Travelling Salesman Problem. Their title was ‘Let the pigeon drive the bus: pigeons can plan future routes in a room.'

 

Let no one claim that scientists lack a sense of humor. Or that cute titles don’t help to generate publicity.

 

The Traveling Salesman Problem is not just a curiosity. It’s a very important example of a class of problems of enormous practical significance, called combinatorial optimization. Mathematicians have a habit of posing deep and significant questions in terms of apparent trivia.

The piece of significant trivia that inspires this article had its origins in a helpful book for—you guessed it—traveling salesmen. Door-to-door sellers. Like any sensible business person, the German traveling salesman of 1832 (and in those days it always was a man) placed a premium on using his time efficiently and cutting costs. Fortunately, help was at hand, in the form of a manual: The traveling salesman—how he should be and what he has to do, to obtain orders and to be sure of a happy success in his business—by an old traveling salesman.

 

This elderly peripatetic vendor pointed out that:

Business brings the traveling salesman now here, then there, and no travel routes can be properly indicated that are suitable for all cases occurring; but sometimes, by an appropriate choice and arrangement of the tour, so much time can be gained, that we do not think we may avoid giving some rules also on this… The main point always consists of visiting as many places as possible, without having to touch the same place twice.

The manual didn’t propose any mathematics to solve this problem, but it did contain examples of five allegedly optimal tours.

 

The Traveling Salesman Problem, or TSP, as it came to be known—later changed to Traveling Salesperson Problem to avoid sexism, which conveniently has the same acronym—is a founding example for the mathematical area now known as combinatorial optimization. Which means ‘finding the best option among a range of possibilities that’s far too big to check one at a time.'

 

Curiously, the TSP name seems not to have been used explicitly in any publication concerning this problem until 1984, although it was common usage much earlier in informal discussions among mathematicians.

In the age of the Internet, companies seldom sell their goods by sending someone from town to town with a suitcase full of samples. They put everything on the web. As usual (unreasonable effectiveness) this change of culture hasn’t made the TSP obsolete. As online shopping grows exponentially, the demand for efficient ways to determine routes and schedules is becoming ever more important for everything from parcels to supermarket orders to pizza.

 

The portability of mathematics also comes into play. Applications of the TSP are not restricted to travel between towns or along city streets. Once upon a time, prominent astronomers had their own telescopes, or shared them with a few colleagues. The telescopes could easily be redirected to point at new heavenly bodies, so it was easy to improvise. Not so any more, when the telescopes used by astronomers are enormous, ruinously expensive, and accessed online. Pointing the telescope at a fresh object takes time, and while the telescope is being moved, it can’t be used for observations. Visit targets in the wrong order and a lot of time is wasted moving the telescope a long way, and then back again to somewhere near where it started.

 

In DNA sequencing, fragmentary sequences of DNA bases must be joined together correctly, and the order in which this is done has to be optimised to avoid wasting computer time. Other applications range from routing aircraft efficiently to the design and manufacture of computer microchips and printed circuit boards. Approximate solutions of TSPs have been used to find efficient routes for Meals on Wheels and to optimise the delivery of blood to hospitals. A version of the TSP even showed up in ‘Star Wars,' more properly President Ronald Reagan’s hypothetical Strategic Defense Initiative, where a powerful laser orbiting the Earth would have been targeted at a series of incoming nuclear missiles.

 

In 1956 operations research pioneer Merrill Flood argued that the TSP is likely to be hard. In 1979, Michael Garey and David Johnson proved that he was right: no efficient algorithm exists to solve the problem in ‘worst cases.’ But worst-case scenarios often turn out to be very contrived, and not typical of examples in the real world. So mathematicians in operations research set out to see just how many cities they could handle for real-world problems.

 

In 1980 the record was 318 cities; by 1987 it was 2,392 cities. By 1994 the record had risen to 7,397 cities, an answer that took about three years of CPU time on a network of very powerful computers. In 2001 an exact solution for 15,112 German towns was obtained using a network of 110 processors. It would have taken more than twenty years on a normal desktop. In 2004, the TSP was solved for a tour of all 24,978 towns in Sweden. In 2005, the Concorde TSP Solver solved the TSP for a tour of all 33,810 points on a printed circuit board. Setting records isn’t the only reason for such research: the methods used to set them work very fast indeed for smaller problems. Up to a hundred cities can usually be solved in a few minutes, and up to a thousand in a few hours on a standard desktop machine.

The other option is to settle for less: a solution that’s not too far from the best possible, but easier to find. In some cases, this can be achieved using a startling discovery made in 1890, in an area of mathematics so novel that many of the leading figures at the time failed to see any value in it, and often failed to believe the answers that more visionary mathematicians were slowly finding. Worse, the problems they tackled seemed to be ‘mathematics for its own sake,' bearing no visible relationship to anything in the real world. Their results were widely considered to be highly artificial and the new geometric shapes that they constructed were dubbed ‘pathological.’ Many felt that even if those results were correct, they didn’t advance the cause of mathematics one iota; they just threw up silly obstacles to progress in a self-indulgent orgy of logical nitpicking.

 

The discovery concerned is a curve, but one quite unlike the traditional notion of a curve, which 'had been around since the time of the ancient Greeks This one was found to have hidden depths. The traditional examples–circles, ellipses, parabolas and so on—held their own fascination, and had led to remarkable advances. But, just as domesticated animals give a misleading picture of life in the Earth’s rainforests and desert wildernesses, these curves were much too tame to represent the wild creatures that roamed the mathematical jungle. As examples of the potential complexity of continuous curves, they were too simple and too well behaved.

 

One of the most basic features of curves, so obvious that no one sought to question it, is that they’re thin. As Euclid wrote in his Elements, ‘a line is that which has no thickness.’ But in 1890, Giuseppe Peano gave a construction for a continuous curve that completely fills the interior of a square.23 It doesn’t just wander around inside the square in a complicated scribble that comes close to any point: it passes though every point in the square, hitting it exactly. Peano’s curve does indeed ‘have no thickness’, in the sense that you make it by tracing a line with a pencil whose tip is a single geometric point, but that line wiggles around in a very convoluted manner, repeatedly revisiting regions that it has previously left. Peano realized that if you make it infinitely wiggly, in a carefully controlled manner, it will fill the entire square.

 

This discovery came as a shock to naive intuition. At the time, curves of this type were called ‘pathological’ and many mathematicians reacted to them the way we usually react to pathology—with fear and loathing. Later, the profession got used to them and absorbed the deep topological lessons that they teach us.

 

Today we see Peano’s curve as an early example of fractal geometry, and we appreciate that fractals are in no way unusual or pathological. They’re commonplace, even in mathematics, and in the real world they provide excellent models of highly complex structures in nature, such as clouds, mountains, and coastlines.

 

The pioneers of this new age of mathematics inspected ancient intuitive concepts like continuity and dimension, and started asking the difficult questions. This skeptical approach annoyed many mainstream mathematicians, who saw it as negativity for its own sake. ‘I turn away with fright and horror of this terrible scourge of continuous functions without derivative,’ Charles Hermite wrote in 1893 to his friend Thomas Stieltjes.

 

But by the 1930s, the value of this more rigorous approach was becoming evident; by the 1960s, it had taken over almost completely. Here, I want to concentrate on the concept of dimension.

 

We all learn that space has three dimensions, a plane has two, and a line has one. We don’t approach this idea by defining the word ‘dimension’ and then counting how many of them space, or a plane, has. Not exactly. Instead, we say that space has three dimensions because we can specify the position of any point using exactly three numbers. We choose some specific point, the origin, and three directions: north-south, east-west, and up-down. Then we just have to measure how far it is from the origin to our chosen point, in each of those directions. This gives us three numbers (the coordinates relative to those choices of direction), and each point in space corresponds to one, and only one, such triple of numbers. Similarly, a plane has two dimensions because we can dispense with one of those numbers, say the up-down one, and a line has one dimension.

That raises a deeper question: How do you know that two actually is the smallest number that will do the job for a plane? It’s not totally obvious. Now the floodgates open. How do we know that three is the smallest number that will do the job for space? How do we know that any choice of independent directions always gives three numbers? For that matter, how sure are we that three numbers are enough?

 

That third question is really one for experimental physics, and leads, via Einstein and his General Theory of Relativity, to the suggestion that physical space is not, in fact, the flat three dimensional space of Euclid, but a curved version. Or, if the string theorists are correct, spacetime has ten or eleven dimensions, all but four of which are either too small for us to notice, or inaccessible. The first and second questions can be resolved satisfactorily, but not trivially, by defining three-dimensional Euclidean space in terms of a coordinate system with three numbers, and then spending five or six weeks of a university course on vector spaces, where any number of coordinates is possible, to prove that the dimension of a vector space is unique.

 

Inherent in the vector space approach is the idea that our coordinate system is based on straight lines, and the space is flat. Indeed, another name is ‘linear algebra.’ What if we do an Einstein and allow the coordinate system to bend? Well, if it bends smoothly (classically called ‘curvilinear coordinates’) all is well. But in 1890 the Italian mathematician Giuseppe Peano discovered that if it bends in a wild manner—so wild that it’s no longer smooth, but remains continuous—then a space of two dimensions can have a coordinate system with only one number. The same goes for a space of three dimensions. In this more general, flexible set-up, suddenly ‘the’ number of dimensions becomes mutable.

 

One response to this strange discovery is to dismiss it; obviously we have to use smooth coordinates, or whatever. But it turned out to be much more creative, and useful, and indeed more fun, to embrace the weirdness and see what happens. The traditionalist critics were rather puritanical, and they didn’t want the younger generation to have any fun at all.

 

Peano’s discovery of a continuous curve that passes through every point in a square allows us to specify every point of that square using just one continuously varying number. So from this point of view, the square is actually one-dimensional!

 

Space-filling curves have applications to computing, such as storage and retrieval of multidimensional data.nThe basic idea is that we can traverse a multidimensional array by following an approximation to a space-filling curve, reducing the problems to the one-dimensional case. Another application yields a quick-and-dirty solution of the traveling salesman problem. Now the idea is to run a finite approximation to a space-filling curve through the region containing the cities, put the cities in order along the curve, and then visit them in that order using the shortest linking route at each step. This produces a route that’s usually no more than 25 percent longer than the optimal one.

 

Back to that pigeon paper by Gibson, Wilkinson, and Kelly in Human Cognition. They start with the remark that the TSP had recently been used to examine aspects of cognition in humans and animals, especially the ability to plan actions before taking them. However, it wasn’t clear whether this ability was restricted to primates.

 

Can other animals also plan ahead, or do they just use rigid rules, developed by evolution? The researchers decided to use pigeons in laboratory trials that presented them with simple TSPs having two or three destinations—feeders. The pigeons start from one location, travel to each feeder in some order, and continue to a final destination. The team concluded that ‘Pigeons weighed the proximity of the next location heavily, but appeared to plan ahead multiple steps when the travel costs for inefficient behavior appeared to increase. The results provide clear and strong evidence that animals other than primates are capable of planning sophisticated travel routes.’

In an interview, the researchers explained the link to the bus-driving pigeon. They suggested that the driver might have had two reasons for objecting: the obvious one of safety, or the worry that the pigeon would be unable to follow a route that would pick up passengers efficiently as the bus drove through the city. As the title of the paper indicates, the team concluded from their experiments that the second worry was unjustified.

 

Let the pigeon drive the bus.