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.
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:
- Daniel Hennes and Dario Izzo. Interplanetary Trajectory Planning with Monte Carlo Tree Search. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2015). AAAI, 2015.