# An Iterative Optimization Algorithm for Planning Spacecraft Pathways Through Asteroids
## 3 Asteroid Routing Problem  
[PERSON] et al. [5] first presented the Asteroid Routing Problem (ARP) as a testing framework for computationally intensive optimization problems involving permutations and black-box evaluations. The problem focuses on determining an optimal trajectory for a spacecraft that departs from Earth and needs to sequentially visit each member of a specified collection of \(n\) asteroids \(A=\{a_{1},a_{2},\ldots,a_{n}\}\). The goal is to simultaneously minimize propellant usage and the duration of the mission. From a computational point of view, the ARP can be seen as a bilevel optimization problem: the outer task focuses on finding the sequence for visiting all the asteroids in the set \(A\), while the inner task involves computing, at each step in the sequence, the parking and transit times required by the spacecraft to reach the next asteroid. A solution of the ARP is represented as a pair \((\sigma,\mathbf{t})\), where \(\sigma\in\Sigma_{n}\) defines the sequence in which the asteroids in \(A\) are visited, and the vector \(\mathbf{t}\in\mathbb{R}_{\geq 0}^{2n}\) specifies the parking and transit times. More precisely, let the Earth be denoted as the asteroid \(a_{0}\), we have for each step \(i=1,2,\ldots,n\) that the spacecraft stays in the orbit of (or is launched from, in case \(i=1\)) asteroid \(a_{\sigma(i-1)}\) for a time \(t_{2i-1}\)--called the _parking time_--then it travels from the orbit of \(a_{\sigma(i-1)}\) to the orbit \(a_{\sigma(i)}\) for a time \(t_{2i}\)--called the _transit time_. Considering the spacecraft to be launched from the Earth at epoch \(\tau_{0}\), its launch epoch from the orbit of every asteroid in the sequence is \(\tau_{i}=\tau_{0}+\sum_{i=1}^{2i}t_{j}\), for \(i=1,2,\ldots,n\). Between two consecutive epochs \(\tau_{i-1}\) and \(\tau_{i}\), the spacecraft receives two impulsive maneuvers \(\Delta v_{2i-1}\) and \(\Delta v_{2i}\) for, respectively, transiting from \(a_{\sigma(i-1)}\) to \(a_{\sigma(i)}\) and aligning its orbit with that of \(a_{\sigma(i)}\). Impulsive maneuvers are rapid changes in velocity of the spacecraft, typically achieved by firing thrusters briefly, thus allowing the spacecraft to change its trajectory or orbit quickly. They are measured in meters per second, thus \(\Delta\mathbf{v}\in\mathbb{R}^{2n}\). The magnitude of the impulses are calculated as  
\[(\Delta v_{2i-1},\Delta v_{2i})=\text{Lambert}(a_{\sigma(i-1)},a_{\sigma(i)}, \tau_{i-1},t_{2i}), \tag{2}\]  
i.e., they are the solutions of the Lambert problem: a two-point boundary value problem commonly used for preliminary mission details. Its mathematical details are not relevant for this work, though they can be found, e.g., in [5; 33]. Once the permutation \(\sigma\) is determined as the solution of the outer task, Equation (2) is repeatedly solved in the inner task in order to find the impulsive maneuvers for each step \(i=1,2,\ldots,n\). Therefore, after sequentially solving the \(n\) continuous optimization problems, we have the values for the \(2n\)-dimensional vectors \(\mathbf{t}\) and \(\Delta\mathbf{v}\). In [5], the continuous problems in the inner task are solved by means of the sequential least squares programming (SLSQP) algorithm, which is a well-known quasi-Newton approach for non-linear optimization, having the peculiarity of being a deterministic method [34]. This aspect enables focusing on the outer task of the ARP, as the computation of the values of \(\mathbf{t}\) and \(\Delta\mathbf{v}\) is treated as an internal and deterministic process that solely depends on the given asteroid ordering \(\sigma\). Its objective function to be minimized is therefore defined as  
\[f(\sigma)=\sum_{i=1}^{2n}|\Delta v_{i}|+\frac{2\text{ km}/\text{s}}{30\text{ days}}\cdot\sum_{i=1}^{2n}t_{i}, \tag{3}\]  
where the first term is directly related to the energy required by the spacecraft to execute all the maneuvers, while the second term accounts for the total time required to complete the mission.