Star Trackers: The Next Generation

Nov. 24, 2015, 11 p.m. UTC

Dec. 14, 2015, 11 p.m. UTC


The competition is over.

From the beginning of the competition the leading approach was to minimize the overlap between the tried sequences. Put differently this means that the distribution over single stars and star pairs used to build the triangles is kept flat. It is possible to extend this approach to bigger subset sizes also considering triangles, etc. Many competitors had a similar approach and the difference in the leaderboard came from how pair frequencies are weighted compared to single star frequencies and how ties are handled.

Dario Izzo then jumped ahead on the leader board and won this competition with his approach to select sequences based on how many of the remaining possible scenes they cover. Considering that all possible scenes had the same probability this approach would probably be optimal if computed for all triplets at the same time, directly minimizing the scoring function. This brute force approach is infeasible for the given problem size, so Dario's algorithm greedily selects only one triplet at a time based on the number of scenes it eliminates. Subsequently the number of scenes and sequences gets lower speeding up the decision for sequences during the runtime of the algorithm. This approach is not optimal though as a slight improvement could be shown by introducing some randomnes when selecting a sequence during a tie, where triplets cover the same amount of scenes.

In any case, the best scoring approaches are not feasible for star trackers yet, as they require too much time and memory. For example: the winning approach implemented in C++ takes almost five minutes to compute the sequences for the given scenario.