Browsing by Author "Carrillo, Maria"

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    Deterministic and stochastic exploration of long asteroid fly-by sequences exploiting tree-graph and optimal substructure properties
    (International Astronautical Federation (IAF), 2022-09-22) Sanchez, Joan-Pau; Bellome, Andrea; Carrillo, Maria; Del Ser, J.
    In the past, space trajectory design was limited to the optimal design of transfers to single destinations. However, a somewhat more daring approach is today making the space community to consider missions that visit, with one single spacecraft, a multitude of celestial objects; such as asteroid tour mission proposals CASTAway or MANTIS, which both proposed to visit 10 or more asteroids in a quick succession of asteroid fly-bys. The design of these so-called asteroid tours is complicated by the fact that the sequence of asteroids is not known a priori, but is the objective of the optimisation itself. This leads to a complex mixed-integer non-linear programming (MINLP) problem, on which the decision variables assume both continuous and discrete values. Beyond the obvious complexity of such problem formulation, preliminary mission design requires not only to locate the global optimum solution but, also, to map the ensemble of solutions that leads to feasible transfers. This paper analyses the complexity of such search space, which can be efficiently modelled as a tree-graph of interconnected Lambert arc solutions between two consecutive asteroids. This allows to exploit the optimal substructure of the problem and enables complete tree traverse explorations for limited asteroid catalogues. Nevertheless, the search space quickly grows in complexity for larger catalogues, featuring a labyrinthine multi-modal structure and extreme non-linearities. This underlying complexity ultimately renders common stochastic heuristics, such as Ant Colony Optimization, rather inefficient. Mostly, due to the fact that the metaheuristic processes are not able to gather any real understanding, or knowledge, such that it can efficiently guide the search. Instead, an astrodynamics-lead heuristic based on the distance between spacecraft and asteroid at the asteroid’s MOID-point crossing epoch, enables an efficient pruning of the asteroid catalogue. Then, deterministic processes based on dynamic programming and beam search can be efficiently applied, providing solutions to both the global optimum and the constraint satisfaction problems.
  • Thumbnail Image
    ItemOpen Access
    Efficiency of tree-search like heuristics to solve complex mixed-integer programming problems applied to the design of optimal space trajectories
    (International Astronautical Federation (IAF), 2021-10-25) Bellome, Andrea; Carrillo, Maria; Sanchez Cuartielles, Joan Pau; Del Ser, J.; Kemble, Stephen; Felicetti, Leonard
    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. In the present paper, we focus on missions that aim to visit multiple asteroids within a single launch. The trajectory design of these missions is complicated by the fact that the asteroid sequences are not known a priori but are the objective of the optimization itself. Usually, these problems are formulated as global optimization (GO) problems, under the formulation of mixed-integer non-linear programming (MINLP), on which the decision variables assume both continuous and discrete values. However, beyond the aim of finding the global optimum, mission designers are usually interested in providing a wide range of mission design options reflecting the multi-modality of the problems at hand. In this sense, a Constraint Satisfaction Problem (CSP) formulation is also relevant. In this manuscript, we focus on these two needs (i.e. tackling both the GO and the CSP) for the asteroid tour problem. First, a tree-search algorithm based upon the Bellman’s principle of optimality is described using dynamic programming approach to address the feasibility of solving the GO problem. This results in an efficient and scalable procedure to obtain global optimum solutions within large datasets of asteroids. Secondly, tree-search strategies like Beam Search and Ant Colony Optimization with back-tracking are tested over the CSP formulations. Results reveal that BS handles better the multi-modality of the search space when compared to ACO, as this latter solver has a bias towards elite solutions, which eventually hinders the diversity needed to efficiently cope with CSP over graphs.