Michael Klonowski, University of Colorado Boulder; Marcus J. Holzinger, University of Colorado Boulder; Naomi Owens Fahrner, Ball Aerospace
Keywords: Monte Carlo Tree Search, Space Domain Awareness, Reinforcement Learning, Cislunar Architecture
Abstract:
Optimal Cislunar Architecture Design Using Monte Carlo Tree Search
Michael Klonowski, Marcus J. Holzinger
University of Colorado at Boulder
Patrick Handley
Ball Aerospace
The cislunar region of space is an increasingly important region of space for governments, scientific research groups, and commercial enterprises [1]. Critical to the success of these ventures is the design of cislunar architectures that meet specific mission design objectives and consider the complex and chaotic non-Keplerian dynamics associated with the cislunar region [2]. Optimal architecture design generally requires solving a high dimensional Mixed Integer Nonlinear Programming (MI-NLP) problem, a notoriously difficult problem to solve through brute-force optimization. The inclusion of complex non-Keplerian dynamics in the cislunar region combined with required guarantees of optimality only increases the difficulty in finding solutions. This research proposes a method based on Monte Carlo Tree Search (MCTS) to generate guaranteed optimal solutions to cislunar architecture design problems.
Prior work in cislunar architecture design has explored arrangement of communication satellites at Lagrange points in the Earth-Moon Circular-Restricted Three-Body Problem (CR3BP) system [3], and the use of solar sails constellations for cislunar navigation networks [4]. DiMarco [5] takes these cislunar architecture design problems and recasts them as a multi-objective particle swarm optimization problem to find locally-optimal placements of satellites in CR3BP periodic orbits subject to trivial constraints. However, in real world design problems multiple objectives and constraints must be considered. The size of the decision space in this problem, which can include number of assets, types of assets, asset capabilities, asset orbit stability, total mission costs, and numerous other specific mission design requirements inevitably requires solving a high dimensional MI-NLP problem, famously known for being computationally intractable through brute-force optimization. Because of this, a framework using MCTS is proposed that generates optimal architecture solutions with performance near the global optimum, provides guarantees on how close the solution is to the global maximum, and is computationally feasible with realistic computing resources.
Monte Carlo Tree Search is an online method for finding optimal solutions to a Markov Decision Process (MDP) that gained notoriety for beating a human in the game of Go [6]. In recent years MCTS has also found success in engineering architecture design [7, 8]. A major part of MCTS’s success in these applications comes from its ability to sample over high dimensional state and action spaces by running simulations to states that are reachable from the current state, thereby reducing exponential complexity across the horizon [9]. Furthermore, in any multi-objective optimization problem, solutions lie along the Pareto frontier, which characterizes the interaction between sets of decision variables at the optimum. As part of this framework, the Pareto frontier between multiple decision variables can be determined, allowing designers to better evaluate options in the solution space.
To expand into in the cislunar domain safely and effectively, it is imperative that resources are invested into designing architectures that consider a wide array of mission objectives and decision variables, and accounts for the complex nonlinear dynamics found within the region. Using MCTS as an online planning method, this high dimensional MI-NLP problem can be reduced to searching through the reachable state space, greatly reducing computational requirements while offering numerical guarantees of the optimality of the solution. This research presents a novel implementation of the MCTS algorithm that generates optimal solutions to various cislunar architecture design problems.
References
[1] Holzinger, M. J., Chow, C. C., & Garretson, P. (2021). A Primer on Cislunar Space. Air Force Research Laboratory.
[2] Bhasin, Kul. (2004). Developing Architectures and Technologies for an Evolvable NASA Space Communication Infrastructure. 10.2514/6.2004-3253.
[3] Ming, Xu & Wang, Jinlong & Liu, Shengli & Xu, Shijie. (2013). A New Constellation Configuration Scheme for Communicating Architecture in Cislunar Space. Mathematical Problems in Engineering. 2013. 10.1155/2013/864950.
[4] Pan, Xiao & Ming, Xu & Santos, Ramil. (2017). Trajectory optimization for solar sail in cislunar navigation constellation with minimal lightness number. Aerospace Science and Technology. 70. 10.1016/j.ast.2017.08.042.
[5] Di Marco, Stefano. “Exploiting multi-body dynamics for distributed spacecraft architecture optimal design: the cislunar services case.” (2021).
[6] Coulom, R. (2006, May). Efficient selectivity and backup operators in Monte-Carlo tree search. In International conference on computers and games (pp. 72-83). Springer, Berlin, Heidelberg.
[7] Rossi, L., Winands, M. H., & Butenweg, C. (2021). Monte Carlo Tree Search as an intelligent search tool in structural design problems. Engineering with Computers, 1-18.
[8] Huang, X., Shao, Z., & Yang, Y. (2019, May). Mips: instance placement for stream processing systems based on monte carlo tree search. In ICC 2019-2019 IEEE International Conference on Communications (ICC) (pp. 1-6). IEEE.
[9] Kochenderfer, M. J., Wheeler, T. A., & Wray, K. H. (2022). Algorithms for decision making. Mit Press.
Date of Conference: September 27-20, 2022
Best Student Award Winner 2022
Track: Cislunar SSA