Interplanetary Trajectory Planning with Monte Carlo Tree Search
Planning an interplanetary trajectory is a very complex task, traditionally accomplished by domain experts using computer-aided design tools. Recent advances in trajectory optimization allow automation of part of the trajectory design but have yet to provide an efficient way to select promising planetary encounter sequences. In this project, we aim to develop a heuristic-free approach to automated trajectory planning (including the encounter sequence planning) based on Monte Carlo Tree Search (MCTS). We investigate a number of modifications to traditional MCTS unique to the domain of interplanetary trajectory planning and test the algorithm on the Rosetta and Cassini-Huygens interplanetary mission design problems.
Interplanetary Trajectories
Even today's most powerful launch systems are not able to send a spacecraft on a direct trajectory to target bodies in the outer solar system. Therefore, most interplanetary missions require a well designed trajectory that guides the spacecraft through a number of gravity assist maneuvers, also called fly-bys. Each fly-by provides the spacecraft with a gravitational kick by "stealing" a small amount of the planet's orbital energy. A sequence of carefully planned and executed fly-bys allows the spacecraft to save propellant (or time) and enables trajectories otherwise impossible. Interplanetary trajectory optimization holds its most challenging aspect in its combinatorial part, that is the selection of the planetary encounters.
Monte Carlo Tree Search
Monte Carlo Tree Search (MCTS) is a technique widely applicable in domains that require sequential decision making, including game-tree search and planning problems. The MCTS paradigm combines informed tree search with the generality of Monte Carlo simulations. Although, MCTS exist in many variants, all are based on the concept of incrementally building an internal tree to inform its search policy. MCTS algorithms are any-time algorithms that repeat the following four basic steps until the computational budget is depleted:
- Selection: Starting from the root a selection policy is deployed to descend through the tree while balancing exploration and exploitation.
- Expansion: Once the tree reaches a leaf node, the state is advanced by performing a random available action and the resulting state is added as a new node to the tree.
- Simulation: A Monte Carlo simulation is run with random action selection. Heuristic knowledge can be used to give higher weight to promising actions.
- Back-propagation: Once a final state is reached, the value is back-propagated upwards trough the search tree and each node selected in step 1 is updated accordingly.