Article Title

Spanning tree trajectory optimization in the galaxy space


trajectory optimization, Settlers of the Galaxy, minimum spanning tree, ant colony optimization, greedy search


The 10th edition of the Global Trajectory Optimization Competition considered the problem of the galaxy settlement wherein competitors from all over the world were expected to design the trajectories of different settler vessels to maximize the given multi-faceted merit function. The synthesis methods used by the winning team, led jointly by the National University of Defense Technology (NUDT) and Xi’an Satellite Control Center (XSCC), are described along with a greedy search method and the improved solution obtained by University of Jena. Specifically, we presented a layout-first topology-second approach that allows an efficient settlement tree search guided by the pre-specified ideal spatial distribution. We also explained how the problem of constructing settlement trees can be modeled as the widely studied minimum spanning tree problem. Furthermore, University of Jena explored the possibility that a greedy search can generate even better settlement trees, based on the same initial conditions, when compared to that of the winning solution.


Tsinghua University Press