Keplerian TSP

Missions in which a spacecraft needs to match its position and velocity with multiple celestial bodies, so-called multi-rendezvous missions, are becoming increasingly relevant in near-term scenarios such as active debris removal and futuristic ideas such as asteroid mining. The underlying routing and scheduling problems were, for this reason, the topic of multiple incarnations of the Global Trajectory Optimization Competition (GTOC), which led to various hand-crafted methods that mix domain-specific intuition together with several meta-heuristics.

Theoretical Sound Guarantees with Constrained Optimization

These heuristic-based approaches have the huge advantage of being reasonable fast, while they have the disadvantage of not providing any theoretical guarantee of the quality of the result whatsoever. Constrained Optimization Problems (COP) deals with the assignment of discrete values to a set of variables in order to maximize or minimize a given function, i.e., to find the optimal solution in a search problem. The cost of finding optimal solutions is, of course, that these techniques are slower than their heuristic counterparts. However, thanks to the combined efforts of multiple contributing fields and intensive algorithmic engineering, amazingly fast tools for relevant subfields of COP are available, for instance for Integer Linear Programming (e.g. Gurobi or HiGHS) or for Maximum Satisfaction (e.g., MaxHS or Open-WBO).

The Keplerian Traveling Salesperson Problem

One of the poster-child problems of combinatorial optimization is the Traveling Salesman Person problem (TSP), which bears a high similarity to the multi-rendezvous problem. The main difference is that in the latter we deal with objects on orbits instead of cities, i.e., we deal with a highly dynamic version of the problem. This similarity was already observed in the past [1,2], but this initial research was ad-hoc, i.e., specific instances were mapped to variants of TSP that are general enough to capture the multi-rendezvous problem. The first part of the project is the development of an overreaching and unifying formal definition of a TSP variant that naturally captures multi-rendezvous mission. We dub this problem Keplerian TSP.

The Keplerian TSP is specifically challenging compared to its classical counterpart as it simultaneously offers a distinct combinatorial aspect (ordering and choosing the rendezvous), and a continuous optimization problem (finding transfers between celestial bodies). Typically, those two parts are dealt separately, leading to potentially-suboptimal mission designs. The second part of this projects explores mathematical sound formulations of the Keplerian TSP in various constrained optimization frameworks such as integer linear programming (ILP), quadratic programming (QP), or maximum satisfaction (MaxSAT).

Objectives

The project has two main objectives: to formulate a unified framework to describe early-stage mission design problems involving multiple rendezvous (such as that of GTOC 12) as combinatorial optimization problems, and to leverage available exact tools to solve them. In particular, the goal is not to necessarily have the fastest algorithm possible, but the focus lies on providing theoretical guarantees on the quality of the found solutions. The primary direction of this project is the use of (integer) linear programming techniques, i.e., optimization problems in which the goal is to optimize a linear function over integer variables fulfilling a set of linear inequalities. However, the project is not limited to ILPs, we also explore alternative routes such as the use of quadratic programs, or tools from automated reasoning such as MaxSAT.

By linking problems from the early-stage design of multi-rendezvous missions with techniques from operations research and automated reasoning, this project intends to build new interdisciplinary bridges while powering research and cross-fertilization.

References

[1] Federici, Lorenzo, Alessandro Zavoli, and Guido Colasurdo
A time-dependent TSP formulation for the design of an active debris removal mission using simulated annealing
arXiv preprint arXiv:1909.10427 (2019).

[2] Federici, Lorenzo, Alessandro Zavoli, and Guido Colasurdo
Impulsive multi-rendezvous trajectory design an optimization.
8th European Conference for Aeronautics and Space Sciences (EUCASS), Madrid, Spain (2019).