journal article·2024-11-26Open access

An Iterative Optimization Algorithm for Planning Spacecraft Pathways Through Asteroids

Valentino Santucci

Applied Sciences· Volume 14· Issue 23

Abstract

In this article, we explore the use of meta-heuristic algorithms for costly black-box permutation optimization problems. These combinatorial problems are defined by solution spaces that consist of permutations of elements, with an objective function that lacks a closed mathematical representation and is expensive to evaluate. The focus of our investigation is the Asteroid Routing Problem (ARP), which seeks to determine the optimal sequence of asteroids to be visited by a spacecraft while minimizing energy consumption and travel time. Specifically, we assess the performance of a simple algorithm called FAT-RLS, which primarily relies on a randomized local search approach, enhanced with a tabu structure and a mechanism to adjust the perturbation strength. We conducted a series of experiments on well-established instances of the ARP to compare the effectiveness of FAT-RLS against two recognized meta-heuristics designed for this problem, namely, UMM and CEGO. Experiments were conducted in both uninformed and informed settings, where the meta-heuristics are initialized with a specifically designed constructive algorithm for the ARP. The results demonstrate that FAT-RLS is consistently superior to UMM, while there is no conclusive evidence for the comparison with CEGO, though the FAT-RLS results seem slightly better.
Source: crossref · Quality: baseline

Research context

OpenAlex topics: Spacecraft Dynamics and Control · Optimization and Search Problems · Distributed systems and fault tolerance

SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.

Affiliations

Department of International Social and Human Sciences, University for Foreigners of Perugia, 06123 Perugia, Italy

Funding

“Università per Stranieri di Perugia–Finanziamento Dipartimentale alla Ricerca per Progetti di Ricerca di Ateneo–FDR 2024”

References (47)

Show source-provided references
1. Frazier, P.I. (2018). A tutorial on Bayesian optimization. arXiv.10.1287/educ.2018.0188 ↗
2. Scalable global optimization via local bayesian optimization
3. Baioletti, M., Milani, A., and Santucci, V. (2016, January 19–21). An Extension of Algebraic Differential Evolution for the Linear Ordering Problem with Cumulative Costs. Proceedings of the 14th International Conference on Parallel Problem Solving from Nature—PPSN XIV, Edinburgh, UK.10.1007/978-3-319-45823-6_12 ↗
4. Santucci, V., Baioletti, M., and Milani, A. (2015, January 11–15). An Algebraic Differential Evolution for the Linear Ordering Problem. Proceedings of the Companion Material Proceedings of Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain.10.1145/2739482.2764693 ↗
5. López-Ibáñez, M., Chicano, F., and Gil-Merino, R. (2022, January 20–22). The asteroid routing problem: A benchmark for expensive black-box permutation optimization. Proceedings of the International Conference on the Applications of Evolutionary Computation (Part of EvoStar), Madrid, Spain.10.1007/978-3-031-02462-7_9 ↗
6. Izzo, D., Getzner, I., Hennes, D., and Simões, L.F. (2015, January 11–15). Evolving solutions to TSP variants for active space debris removal. Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, Madrid, Spain.10.1145/2739480.2754727 ↗
7. Design of end-to-end trojan asteroid rendezvous tours incorporating scientific value10.2514/1.A33396 ↗
8. On-orbit servicing: A time-dependent, moving-target traveling salesman problem10.1111/j.1475-3995.2006.00558.x ↗
9. Multiple space debris collecting mission—debris selection and trajectory optimization10.1007/s10957-012-0130-6 ↗
10. Simões, L.F., Izzo, D., Haasdijk, E., and Eiben, A. (2017, January 19–21). Multi-rendezvous spacecraft trajectory optimization with beam P-ACO. Proceedings of the Evolutionary Computation in Combinatorial Optimization: 17th European Conference, EvoCOP 2017, Amsterdam, The Netherlands. Proceedings 17.
11. 1st ACT global trajectory optimisation competition: Results found at the Jet Propulsion Laboratory10.1016/j.actaastro.2007.03.013 ↗
12. Izzo, D., Hennes, D., Simões, L.F., and Märtens, M. (2016). Designing complex interplanetary trajectories for the global trajectory optimization competitions. Space Engineering: Modeling and Optimization with Case Studies, Springer.10.1007/978-3-319-41508-6_6 ↗
13. Problem description for the 9th global trajectory optimisation competition
14. Izzo, D., and López-Ibáñez, M. (2023, January 15–19). Optimization challenges at the european space agency. Proceedings of the Companion Conference on Genetic and Evolutionary Computation, Lisbon, Portugal.10.1145/3583133.3595039 ↗
15. 4PL routing problem using hybrid beetle swarm optimization10.1007/s00500-023-08378-4 ↗
16. Two-level Tabu-predatory search for schedule risk control of IT outsourcing projects10.1016/j.ins.2019.02.061 ↗
17. Global Trajectory Optimization of Multispacecraft Successive Rendezvous Using Multitree Search
18. HOLT, H.J., Armellin, R., Baresi, N., Scorsoglio, A., and Furfaro, R. (2020, January 9–12). Low-thrust trajectory design using state-dependent closed-loop control laws and reinforcement learning. Proceedings of the 2020 AAS/AIAA Astrodynamics Specialist Conference, Virtual Event.
19. Multi-agent genetic algorithm with controllable mutation probability utilizing back propagation neural network for global optimization of trajectory design10.1080/0305215X.2018.1443083 ↗
20. Pritchard, B., Doyle, D., and Black, J. (2020, January 16–18). Linear Programming Trajectory Optimization vs. Artificial Potential Function Methods for Rendezvous and Proximity Operations. Proceedings of the ASCEND 2020, Virtual Event.10.2514/6.2020-4102 ↗
21. Santucci, V., and Baioletti, M. (2022, January 18–23). A fast randomized local search for low budget optimization in black-box permutation problems. Proceedings of the 2022 IEEE Congress on Evolutionary Computation (CEC), Padua, Italy.10.1109/CEC55065.2022.9870328 ↗
22. An algebraic framework for swarm and evolutionary algorithms in combinatorial optimization10.1016/j.swevo.2020.100673 ↗
23. Tackling Permutation-based Optimization Problems with an Algebraic Particle Swarm Optimization Algorithm10.3233/FI-2019-1812 ↗
24. Model-based Gradient Search for Permutation Problems10.1145/3628605 ↗
25. Variable neighborhood algebraic Differential Evolution: An application to the Linear Ordering Problem with Cumulative Costs10.1016/j.ins.2019.08.016 ↗
26. Genetic algorithms for the travelling salesman problem: A review of representations and operators10.1023/A:1006529012972 ↗
27. Using pairwise precedences for solving the linear ordering problem10.1016/j.asoc.2019.105998 ↗
28. The linear ordering problem revisited10.1016/j.ejor.2014.09.041 ↗
29. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem10.1016/j.ejor.2005.12.009 ↗
30. The Hungarian method for the assignment problem10.1002/nav.3800020109 ↗
31. Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search10.1016/j.ejor.2020.11.035 ↗
32. A comprehensive survey on the generalized traveling salesman problem10.1016/j.ejor.2023.07.022 ↗
33. Revisiting Lambert’s problem10.1007/s10569-014-9587-y ↗
34. SciPy 1.0: Fundamental algorithms for scientific computing in Python10.1038/s41592-019-0686-2 ↗
35. Doerr, B., and Kelley, A. (2024). The Runtime of Randomized Local Search on the Generalized Needle Problem. IEEE Trans. Evol. Comput., early access.10.1109/TEVC.2024.3453776 ↗
36. Zaefferer, M., Stork, J., Friese, M., Fischbach, A., Naujoks, B., and Bartz-Beielstein, T. (2014, January 12–16). Efficient global optimization for combinatorial problems. Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, Vancouver, BC, Canada.10.1145/2576768.2598282 ↗
37. Zaefferer, M., Stork, J., and Bartz-Beielstein, T. (2014, January 13–17). Distance measures for permutations in combinatorial efficient global optimization. Proceedings of the International Conference on Parallel Problem Solving from Nature, Ljubljana, Slovenia.10.1007/978-3-319-10762-2_37 ↗
38. Chopard, B., and Tomassini, M. (2018). An Introduction to Metaheuristics for Optimization, Springer.10.1007/978-3-319-93073-2 ↗
39. Irurozki, E., and López-Ibáñez, M. (2021, January 10–14). Unbalanced mallows models for optimizing expensive black-box permutation problems. Proceedings of the Genetic and Evolutionary Computation Conference, Lille, France.10.1145/3449639.3459366 ↗
40. Fisher-yates shuffle
41. Santucci, V., Milani, A., and Caraffini, F. (2019). An optimisation-driven prediction method for automated diagnosis and prognosis. Mathematics, 7.10.3390/math7111051 ↗
42. Santucci, V., and Milani, A. (2011). Particle Swarm Optimization in the EDAs Framework. Soft Computing in Industrial Applications, Springer.10.1007/978-3-642-20505-7_7 ↗
43. An analysis of several heuristics for the traveling salesman problem10.1137/0206041 ↗
44. Efficient global optimization of expensive black-box functions10.1023/A:1008306431147 ↗
45. A distance-based ranking model estimation of distribution algorithm for the flowshop scheduling problem10.1109/TEVC.2013.2260548 ↗
46. Hollander, M., Wolfe, D.A., and Chicken, E. (2013). Nonparametric Statistical Methods, John Wiley & Sons.
47. Doerr, B., Ghannane, Y., and Brahim, M.I. (2022, January 9–13). Towards a stronger theory for permutation-based evolutionary algorithms. Proceedings of the Genetic and Evolutionary Computation Conference, Boston, MA, USA.10.1145/3512290.3528720 ↗