Scientists just solved a tricky asteroid-hopping spacecraft riddle

A new approach that riffs on the classic Traveling Salesperson problem could enable more efficient space missions to multiple objects that are in motion — like asteroids.

The researchers behind the fascinating solution to the problem are Isaac Rudich of the Department of Mathematical and Industrial Engineering at Polytechnique Montréal in Canada and Michael Römer, who is a decision analyst from the Faculty of Business Administration and Economics at Universität Bielefeld in Germany. “Our research is foundational, in the sense that it develops mathematical machinery that can be used by space agencies to plan missions,” the duo told Space.com.

The Traveling Salesperson problem is a mathematical approach to determining the shortest route for visiting multiple destinations before returning to the point of origin. That’s fine when you’re a double glazing salesperson visiting a dozen stationary towns and cities, but how do you calculate the optimal route when your destinations are perpetually in motion?

This is the problem faced by spacecraft that are on a mission to visit multiple celestial objects. Sometimes the decision is obvious, necessitated by the availability of gravitational slingshots from planets, as illustrated by the Voyager 1 and Voyager 2 missions.

However, a mission that skips from one asteroid to the next, relying on fuel stored on board rather than gravitational slingshots, is more problematic. The asteroids are constantly moving in their orbits and the distances between the asteroids, and therefore the travel time, are not static.

This seemingly intransigent problem now has a solution, thanks to a team led by Rudich and Römer.

They reframed the puzzle as the “Asteroid Routing Problem,” or ARP, which asks the question: In what order should a spacecraft visit multiple asteroids if both travel time and fuel consumption are to be minimized? To do so, the optimal departure time and trajectory between each pair of objects has to be calculated.

“The ARP is particularly challenging because determining the exact cost and travel time requires solving another challenging optimization problem, which is Lambert’s problem,” said Römer and Rudich.

Lambert’s problem was first posed all the way back in the 1700s by the Swiss polymath Johann Heinrich Lambert, who pondered how to find the optimal trajectory between two moving objects. The problem was solved mathematically later that century by Joseph-Louis Lagrange — yes, of Lagrange point fame.

Solving Lambert’s problem for two objects is one thing, but when many more objects — or in this case, asteroids — are involved, it very quickly becomes computational complex because the calculation must be conducted for every possible route between every possible pair of objects.

To get around this, Rudich and Römer’s team employed something called Decision Diagrams. These are a variation on Decision Trees, which map a decision problem to a graph by listing each possible set of decisions as a path on that graph, all starting from the same root, or origin. In a Decision Diagram, all the various choices that lead to the same destination in time and space are represented as a single node on the graph, making things simpler and reducing the amount of times Lambert’s problem has to be solved.

“Our approach typically achieves solutions that are about 20% better than those using standard approaches, and solutions up to 20% better for larger problems,” said Rudich and Römer. That percentage is a combination of total travel time and fuel consumption.

There aren’t many missions that visit multiple asteroids. NASA’s Dawn mission visited both Ceres and Vesta, while the Lucy mission is currently on its way to Jupiter, via the Asteroid Belt, to explore the Jovian Trojan asteroids. Lucy has flown relatively near several asteroids in the asteroid belt and will pay visits to five Trojan asteroids.

Employing their mathematical approach to see how optimal Lucy’s mission plan is “would certainly be interesting,” said Rudich and Römer, but they emphasize that the ARP is a very stylized, almost synthetic, problem that considers some, but not all, aspects of astrodynamics.

“To precisely model a real-world mission would probably require the consideration of a lot of additional aspects,” they said.

However, even if it could just bring about a 1% improvement, it would still represent a substantial saving of time, money and fuel. Their research could also be applied to terrestrial problems, such as bus routes, supply chains and shipping routes, where variable weather and traffic congestion provide the dynamic properties rather than moving destinations.

The research was published on April 2 in the INFORMS Journal on Computing.