On the use of A* search for active debris removal mission planning

This paper focuses on the optimal design of a time- and fuel-constrained Active Debris Removal mission. A score is associated with each of the considered debris, which quantifies the level of threat represented by that debris. The mission goal is to maximize the cumulative score of the removed debris, that must be selected within a given large cluster of objects orbiting in SSO, while respecting constraints on both total Δ and time. Two different mathematical formulations of the problem as a Time-Dependent Orienteering Problem are proposed: an Integer Linear Programming formulation, solved by using a commercial software, and a search problem formulation, tackled through A*, an optimal search algorithm. Three admissible heuristics for A* are derived in the paper as exact solutions of relaxed versions of the original problem. Their performance is compared on missions of increasing length and complexity. A fast- computation near-optimal transfer strategy, that cleverly exploits the ! perturbation to achieve the correct alignment between the orbital planes, is used to estimate the Δ between any pair of debris, given the rendezvous epochs. Numerical results are presented for a 21-debris cluster in SSO, by analyzing the effect of the debris score distribution, of the total mission time, and of the maximum transfer duration on the computational time required by the different algorithms to solve the problem.