Universe Today
The Traveling Salesman is a classic problem in mathematics that requires a solution to the most efficient path to take to visit a given number of cities in the least amount of time. But scale this relatively simple concept up to space travel and the calculation becomes much more complex. Instead of visiting a stationary spot on Earth, when calculating the most efficient path to visit asteroids you must account for the fact they are traveling tens of thousands of miles an hour, and their exact position will change based on when a spacecraft leaves. This is known as the Asteroid Routing Problem, and a new paper from a group of Canadian and European researchers lays out a framework that can find the exact solution to any particular combination of asteroids to be visited.
Previous efforts to do so have run into a computational bottleneck. To solve the problem of getting from point A to point B in space, engineers must calculate a spacecraft’s orbital transfer. Doing so involves calculating a series of impulsive maneuvers, which result in changes in velocity known as “delta-v”, and is calculated using a mathematical formulation known as Lambert’s Problem.
These calculations change depending on the arrival and departure times of the spacecraft, which makes it extremely computationally intensive to try to find an optimal solution. Instead, engineers rely on a system known as heuristics - in this context similar to a guess or approximation - to plan multi-target routes. But that hasn’t stopped researchers from trying to find a true solution.
Fraser talks about mining asteroids - one of the long-term use cases of this algorithm.That true solution comes in a multiple-step process, according to the research paper. The first step is a “Decision Diagram” - a tool that represents possible mission routes as a compact, layered graph. But instead of having every single point of departure calculated, they simplified the problem by saying that “waiting in orbit” to depart costs zero time - essentially removing one of the problem solution's constraints. This simplification provided a baseline from which to build the rest of the calculations.
Once that baseline was established, the authors created a specialized solution search technique they called “Peel-and-Bound”. This takes the most promising paths in the decision diagram and runs the full suite of mathematics on each individual one, comparing it to previous solutions. If the solution is better for any given path, it adopts that as the new baseline and prunes away any that violate the constraints of the best-known solution, meaning the work only results in calculating improvements.
Testing this algorithm required them to use the framework to calculate the trajectories required for different groups of asteroids. When a path involved visiting 10 different ones, the framework successfully evaluated and proved the exact optimal solutions, typically in less than two hours. For routes visiting 15-30 asteroids, the new algorithm shattered the previous time and computational records for heuristic methods.
Fraser talks to Dr. Renu Malhotra about the nuances of orbital mechanics.However, there’s still more work to be done. Like many optimization problems (which this type of problem is classed as), it can be tricked by “local minima” - essentially points on a solution path that look like the “correct” answer but are actually just a small dip in the solution rather than “absolute” minimum cost. In addition, the simulation implied that “impulsive maneuvers” were instantaneous changes in velocity. Most future planned asteroid missions will use low-thrust propulsion systems such as ion drives, which the current algorithm would not work with.
But getting optimal solutions even with those constraints is certainly better than guessing. And as we start to expand our ability to interact with, and eventually utilize, asteroids, solutions like this will be critical in planning out the best way to do so. It’s only a matter of time before this algorithm, or a very similar one, is used to plan an actual mission to an asteroid.
Learn More:
Universitat Bielefeld - Space logistics on the right track
I. Rudich et al. - An Exact Framework for Solving the Space-Time Dependent TSP
