(A) modified basin hopping method for interplanetary trajectory design

다국어 초록 (Multilingual Abstract)

In this thesis, a software application for optimizing impulsive interplanetary trajectories is developed and used to design trajectories for hypothetical missions to two near-Earth asteroids. The optimal control problems for impulsive trajectories are transcribed into nonlinear programming problems, which can then be solved by a global optimization algorithm. The developed software can optimize four different types of impulsive trajectories, from a simple two-impulse trajectory to difficult trajectories composed of multiple gravity assists and deep space maneuvers. As a global optimization algorithm, monotonic basin hopping in the software is chosen because the algorithm has been claimed to be effective in solving trajectory optimization problems by a few studies. The algorithm is powerful enough in its basic form, but it is further modified mainly in three ways in the hopes of improving its performance. The first modification allows the algorithm to take advantage of parallel computing, resulting in two versions of parallel monotonic basin hopping. The second one is concerned with a novel method of automatically choosing an appropriate perturbation size, which is an important factor affecting the performance of the algorithm. As the final refinement, the algorithm is hybridized with another global optimization algorithm called multi-start. Before using the developed software on designing trajectories for the hypothetical asteroid missions, it is tested on a well-known interplanetary trajectory problem called the reduced Messenger problem to see if the modifications lead to an actual improvement. It is found that parallelizing the algorithm can significantly improve its performance in a multi-core environment and that the other two modifications can help the algorithm perform better in some situations. Finally, one-way and round-trip missions to two near-Earth asteroids are designed using the software. The procedure for finding the optimal or near-optimal trajectory for each mission is discussed in detail and the best trajectory found is presented. During the designing procedure, the optimization performance of the developed algorithm is compared with other well-known metaheuristics on several different problems, which turns out to be better than all other metaheuristic algorithms compared. These exemplary simulations of designing trajectories for fictional missions demonstrate that the developed software can readily be used in preliminary trajectory design of interplanetary missions that employ impulsive maneuvers.

국문 초록 (Abstract)

이 논문에서는 순간 추력을 이용한 행성 간 탐사 궤적을 최적화하기 위한 소프트웨어를 설계하고, 가상의 소행성 탐사 미션의 궤적을 설계하는 데에 적용해 봄으로써 개발된 소프트웨어를 검증한다. 복잡한 최적 제어 문제를 유한 차원 비선형 계획법 문제로 변형한 뒤, 비선형 계획법 문제를 전역 최적화 알고리즘을 이용해 최적화하는 방식으로 이 문제에 접근한다. 개발된 소프트웨어는 네 종류의 순간 추력 궤적을 최적화할 수 있도록 만들어졌으며, 이 네 종류의 궤적에는 매우 단순한 궤적부터 중력 스윙바이를 여러 번 이용하는 복잡한 궤적까지 모두가 포함된다. 전역 최적화 알고리즘으로서는 이러한 궤적 최적화 문제를 푸는 데 효과적인 것으로 이미 알려져 있는 분지 뛰어넘기 알고리즘을 이용한다. 소프트웨어에 탑재된 알고리즘은 분지 뛰어넘기 알고리즘의 기본형에 세 가지의 추가적인 개선점을 포함한 버전이다. 우선, 병렬 컴퓨팅 기법을 적용하여 병렬화 방식이 약간 다른 두 종류의 병렬 분지 뛰어넘기 알고리즘을 사용할 수 있도록 하였다. 두 번째로, 분지 뛰어넘기 기법의 성능에 크게 영향을 끼치는 요소인 섭동의 크기 수준을 자동적으로 측정하고 계속적으로 업데이트할 수 있게 해주는 새로운 기법을 고안해 알고리즘에 적용하였다. 마지막으로, 전역 최적화 알고리즘의 일종인 다중 시작 알고리즘과 분지 뛰어넘기 알고리즘을 순차적으로 사용하는 융합 알고리즘을 설계하여 소프트웨어에서 사용할 수 있도록 하였다. 개발된 궤적 설계 소프트웨어를 가상의 소행성 미션에 적용해보기 전에, 이미 잘 알려져 있는 궤적 최적화 문제인 단축된 메신저 문제를 푸는 데에 사용해 봄으로써 실제로 소프트웨어가 정상적인 결과를 내는지, 그리고 반영된 개선점들이 실제로 성능 향상 효과를 불러오는지 확인해보았다. 최종적으로, 개발된 소프트웨어를 이용해 두 개의 지구 근접 소행성을 탐사하는 편도 궤적과 왕복 궤적의 최적화를 수행해보았다. 동시에, 이러한 궤적 설계 과정에서 풀게 되는 다양한 난이도의 서로 다른 궤적 최적화 문제들에 대해서 이 소프트웨어에서 사용하는 변형된 분지 뛰어넘기 알고리즘과 다른 유명한 전역 최적화 알고리즘의 최적화 성능을 비교해보았다. 위와 같이 가상 미션의 궤적을 설계하는 시뮬레이션을 통해서, 개발된 소프트웨어가 순간 추력을 사용하는 태양계 내 탐사 미션의 궤적을 초기적으로 설계하는 단계에서 충분히 사용될 수 있음을 확인하였다.