The design of spacecraft trajectories for missions visiting multiple celestial bodies is here framed as a multi-objective bilevel optimization problem. A comparative study is performed to assess the performance of different Beam Search algorithms at tackling the combinatorial problem of finding the ideal sequence of bodies. Special focus is placed on the development of a new hybridization between Beam Search and the Population-based Ant Colony Optimization algorithm. An experimental evaluation shows all algorithms achieving exceptional performance on a hard benchmark problem. It is found that a properly tuned deterministic Beam Search always outperforms the remaining variants. Beam P-ACO, however, demonstrates lower parameter sensitivity, while offering superior worst-case performance. Being an anytime algorithm, it is then found to be the preferable choice for certain practical applications.
Beam Search @cite_0 @cite_28 has emerged as the standard approach to tackle the combinatorial optimization sub-problems present in most GTOC competitions. Though at times called by other names, it is common to find the general architecture of a tree search that has its computational cost bounded via the selection of a limited number of nodes to branch at each depth-level (non-selected nodes at that depth being immediately discarded). We can find examples of such algorithms in the winning solutions to GTOC4 @cite_23 , GTOC5 @cite_22 , and in the second ranked solution to GTOC7 @cite_6 , which the present research builds on. The Lazy Race Tree Search described in @cite_24 , which at the time presented the best known solution to the GTOC6 problem, can also be seen as a Beam Search variant. In it, the beam'' is composed of all nodes, possibly originating from different tree depths, that fall within a given mission time window. The most promising nodes in that sliding window are branched, and the remaining ones discarded.
@cite_22 @cite_28 @cite_6 @cite_0 @cite_24 @cite_23
2204575588 2225069804 2002941233 1986159811
We discuss the relationships between three approaches to greedy heuristic search: best-first, hill-climbing, and beam search. We consider the design decisions within each family and point out their oft-overlooked similarities. We consider the following best-first searches: weighted A*, greedy search, ASeps, window A* and multi-state commitment k-weighted A*. For hill climbing algorithms, we consider enforced hill climbing and LSS-LRTA*. We also consider a variety of beam searches, including BULB and beam-stack search. We show how to best configure beam search in order to maximize robustness. An empirical analysis on six standard benchmarks reveals that beam search and best-first search have remarkably similar performance, and outperform hill-climbing approaches in terms of both time to solution and solution quality. Of these, beam search is preferable for very large problems and best first search is better on problems where the goal cannot be reached from all states. The design of interplanetary trajectories often involves a preliminary search for options later refined assembled into one final trajectory. It is this broad search that, often being intractable, inspires the international event called Global Trajectory Optimization Competition. In the first part of this chapter, we introduce some fundamental problems of space flight mechanics, building blocks of any attempt to participate successfully in these competitions, and we describe the use of the open source software PyKEP to solve them. In the second part, we formulate an instance of a multiple asteroid rendezvous problem, related to the 7th edition of the competition, and we show step by step how to build a possible solution strategy. In doing so, we introduce two new techniques useful in the design of this particular mission type: the use of an asteroid phasing value and its surrogates and the efficient computation of asteroid clusters. We show how the basic building blocks, sided to these innovative ideas, allow designing an effective global search for possible trajectories. We make use of self-adaptation in a Differential Evolution algorithm and of the asynchronous island model to design a complex interplanetary trajectory touring the Galilean Jupiter moons (Io, Europa, Ganymede and Callisto) using the multiple gravity assist technique. Such a problem was recently the subject of an international competition organized by the Jet Propulsion Laboratory (NASA) and won by a trajectory designed by aerospace experts and reaching the final score of 311 324. We apply our method to the very same problem finding new surprising designs and orbital strategies and a score of up to 316 324. We consider the problem proposed on the 4th Global Trajectory Optimization Competition (GTOC4).