Efficiency of Tree-Search Like Heuristics to Solve Complex Mixed-Integer Programming Problems Applied to Space Trajectory Design
- Paper number
IAC-21,C1,5,7,x64234
- Author
Mr. Andrea Bellome, United Kingdom, Cranfield University, UK
- Coauthor
Dr. Joan Pau Sanchez, United Kingdom, Cranfield University
- Coauthor
Dr. Leonard Felicetti, United Kingdom, Cranfield University
- Coauthor
Mr. Stephen Kemble, United Kingdom, Airbus Defence and Space Ltd
- Year
2021
- Abstract
In the past, space trajectory optimization was limited to optimal design of transfers to single destinations, where optimality refers to minimum propellant consumption or transfer time. New technologies, and a more daring approach to space, are today making the space community consider missions that target multiple destinations. Recent examples include European Space Agency (ESA)’s JUICE, which will perform more than twenty gravity assist manoeuvres with Jovian moons, as well as CASTAway concept (Bowles et al.) on which multiple asteroid rendezvous trajectories were presented in the context of ESA’s Medium Class mission 2016 call (ten asteroids were included in the baseline sequence). The trajectory design of these problems is complicated by the fact that the planetary or asteroid sequences are not known a priori but are the objective of the optimization itself. This leads to a complex mixed-integer non-linear programming (MINLP) problem, on which the decision variables assume both continuous and discrete values. Current approaches to MINLP problems applied to space trajectory design (STD), which we call MINLP-STD, usually require large computational effort to identify optimal sequences of orbital waypoints to visit, as well as a locally optimal trajectory for the given sequence. With this paper, we investigate the trend of MINLP-STD, showing challenges and evolution of these missions to discuss the tree-like structure of this class of problems, on which celestial bodies represent the leaves/nodes and heuristic information define the branches. The work focuses on comparing tree-search-like algorithms, as Beam Search (BS) and Ant Colony Optimization (ACO), with evolutionary-like algorithms, as Genetic Algorithm (GA). Assessment of search performance is provided for two different test cases: (1) multiple gravity assist transfer to Jupiter and (2) asteroid tour transfer aiming to maximize the number of asteroid fly-bys in fixed transfer duration. Two set-ups for both problems are used: 1) a reduced number of design parameters (like the maximum number of celestial bodies) is employed to fully map the search space, thus algorithms performances are referred to the known global optimum; 2) a complex mission scenario, on which a comprehensive search becomes impractical, is tested to assess the feasibility of solving MINLP-STD with tree-search-like and evolutionary-inspired techniques. Preliminary results show that although GA randomness gives few but very good solutions, the hybridization of intelligent heuristics, such as ACO-BS combination, outperforms GA in finding large quantities of close-to-optimal solutions.
- Abstract document
- Manuscript document
IAC-21,C1,5,7,x64234.pdf (🔒 authorized access only).
To get the manuscript, please contact IAF Secretariat.