Today in a press conference, three UCB astronomers announced the first image of an extrasolar planet. And it’s around Fomalhaut, a star we profiled in this week’s featured article by Danae Schulz, From Dust to Dawn: How Solar Systems Arise. (Well, the Berkeley astronomers tied for first. Another group today announced an image of three stars around HR 8799 in Pegasus.)

This is big news! We know of over 200 extrasolar planets (planets orbiting stars other than our Sun) already, but so far we’ve only detected them indirectly, either by the gravitational tug of the planet on its host star, or by the faint dimming of the host star as the planet crosses between us and it. These are the very first images of planets themselves. They might just look like dots, but they’re EXCITING dots.

The UC Berkeley astronomers who made the announcement are Paul Kalas, James Graham, and Eugene Chiang. They’ve been imaging Fomalhaut (pronounced FOO-mal-oh or FO-mal-hout, depending who you talk to) with the Hubble Space Telescope for a few years now, and the star is known to have a dusty debris disk around it. The inner edge of the ring is very abrupt, a phenomenon astronomers suspected could indicate the presence of a planet. Detecting a planet, however, required overcoming two challenges: how to see the planet in the glare of the central star, and how to tell a dot of light is actually a planet and not a background star.

Astronomers overcome the first obstacle by obscuring the central star with a coronagraph, a small disk that blocks out the star’s light and allows observers to take longer exposures that reveal the star’s surroundings.

The key to the second obstacle, differentiating between planets and background stars, is time. Stars have some velocity in space and move relative to one another. Their motion is slow enough that most stars appear to be fixed in the sky, but nearby stars like Fomalhaut (which is only 25 light years away) will move relative to the more distant background stars. Anything that is in orbit around Fomalhaut will move along with Fomalhaut—anything that isn’t, won’t.

The Berkeley team took an image of Fomalhaut’s dust ring in 2004 and again in 2006, both times with a coronagraph on the Hubble Space Telescope. As expected, most of the dots of light didn’t move in the same direction as Fomalhaut (indicating they’re background objects), but one little dot did. And it even progressed along a circular path centered on the star, just as astronomers would expect an orbiting planet to do. The UCB team thinks that the planet is orbiting at 25 astronomical units from Fomalhaut, and that it’s probably about three times the mass of Jupiter.

There will likely be plenty more direct observations of planets in the future, but this is the first, and it has astronomers pretty excited. Every time observers detect a planet by a new method, they take a great leap in learning about worlds other than our own. And to think, the extrasolar planets field didn’t even exist twenty years ago. It’s a brave new world out here.

Read more:
The UC Berkeley Press Release
The NASA Press Release
The New York Times (good graphic of the planet’s progress over time, and HR 8799)
From Dust to Dawn: How Solar Systems Arise

Last year, the New York Times reported that UPS managed to save 3 million gallons of gas in 2006 by altering the routes of delivery trucks to avoid left turns. According to the article, the company uses software called “package flow” to map out daily routes for drivers. Clearly, the algorithm or method this software employs to design efficient routes has sizeable economic (and greenhouse gas) consequences. And, not only is it far from perfect, but the general routing problem is so difficult that, well, if in the course of reading this article you happen upon an efficient solution, you will become immediately famous, at least among computer scientists.

The problem the UPS driver faces, generally speaking, is that of the “traveling salesman”, in which our hero seeks the shortest possible round trip route given a list of required stops. Arising in road trip planning, school bus pickups, parking meter coin collection, power cable layout, and microchip design, it is not a new problem. The famous 19^th century Irish mathematician Sir William Rowan Hamilton, who at age 12 once defeated the notorious American “calculating boy” Zerah Colburn in an arithmetic-off, invented the “Icosian game”, in which players attempt to find round-trip routes through a twelve-sided figure such that each vertex is visited exactly once and no edge is visited twice (Regarding the spin-off “Traveler’s Dodecahedron”, the puzzle museum website states, “the rules have been simplified and made much more attractive than the original”. The puzzle museum also notes that the Icosian game is more of a puzzle than a game.) Inspired by Hamilton’s early work and puzzle-making prowess, mathematicians in Vienna and Cambridge began studying the general form of the traveling salesman problem (TSP) in the 1930s.

In 1972, UC Berkeley Professor Richard Karp published perhaps the most famous paper written to date in computer science, called “Reducibility Among Combinatorial Problems”. The point, broadly speaking, is that most problems that appear difficult to solve exactly most likely are. Rather than proving that all kinds of problems have no easy solution, Karp gave a clever method for showing that many different sorts of problems are equivalent in a certain sense: if you provide a magic fast solver for hard problem A, Karp uses it to build a fast solver for hard problem B. As a result, researchers are amassing an impressive set of hard problems, all reducible to each other, so that if anyone ever found a magic solver for just one of them, well, things would get pretty crazy. A variant of the TSP, that of undirected Hamiltonian Circuits (same Hamilton), was in Karp’s original list of 21 problems.

To understand what this means for the salesman, consider: A TSP with 5 cities has 12 possible routes; with 10 cities there are 181,440 possibilities; with 61 cities there are more possible paths than there are atoms in the universe. Seriously. In computer science terms, the solution space is exponential – adding one city roughly doubles the number of possible paths. Karp’s result suggests that in general, determining the optimal path for the salesman is a matter of checking all those possibilities – though shortcuts may exist, none are likely to lift the exponential burden. And though computers are growing more powerful, even IBM’s supercomputer, Blue Gene, which can perform a ridiculous 500 thousand billion computations per second, would have little hope of solving a 30-city TSP by the brute-force approach.

Instead, computer scientists spend much time devising heuristics – approximate methods for dealing with intractable situations. Here’s a simple heuristic for the traveling salesman: when trying to decide which stop to visit next on the tour, pick the closest remaining one. While in many cases, this rule yields a route much less efficient than the optimal one, it works reasonably well on average. Many papers have been written about more complex heuristics for the TSP. For example, in 1997 Marco Dirigo used a simulated ant colony to explore the space of solutions, iteratively refining paths left by virtual ants (virtual pheromones were also involved).

The TSP variant that UPS would like to solve is no Icosian puzzle game. There are 95,000 trucks delivering packages every day, and each one needs a route assignment. These routes are not independent: removing a stop from one means adding it to another. The resulting problem is staggeringly difficult to solve exactly, and good heuristics are necessary. The no-left-turn innovation is a heuristic that helps realize the difference between driving time and driving distance. Or, as Jim Winestock, a UPS vice president in Atlanta, explains, “I know it drives my wife crazy, but I’ve been known to pass up drug stores, three or four on the left-hand side of the road, just to get to the one on the right.”

–Dan Gillick