Star Trackers: The Next Generation

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

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

Timeline

The competition is over.

In their paper The pyramid star identification technique from 2004, Mortari, D., Samaan, M. A., Bruccoleri, C., & Junkins, J. L. present a star tracker technique using the identification of four stars based on the angles between them.

The basic star tracker algorithms work by first detecting spikes in the camera image, which are candidates for stars. They can also be artifacts like noise, radiation, reflections and the like. With just a single spike it is impossible to find out which star it is, or if it is a star at all and therefore, the angular distance between two spikes are measured. The star catalog stored by the star tracker knows these distances and when queried with a distance can determine a set of star-pairs with the given angular distance with some margin. A single distance between two stars usually results in multiple possible star pairs in the catalog and consequently it is very likely that a query with a non-star candidate results in one or multiple possible star pairs as well. This risk is reduced when multiple stars and their distances are considered. Three candidates have three angular distances building a triangle and four candidates have six angular distances building a pyramid. Mortari et al determined that with four candidates it is practically impossible (i.e. very very unlikely) to get a wrong result from the database. As soon as a valid pyramid is found, it is easy to calculate the orientation based on the detected stars in the image and their position stored in the star catalog.

The main problem which this competition tackles is, how to select the star candidates detected in the camera image, to query the database efficiently, while not nowing which candidates are real stars. The problem boils down to the order in which to go through the possible combinations of star candidates. Because this problem is so difficult only three stars and therefore three distances are selected for the first query in Mortari et al's solution. Once a triangle is found they try to find a pyramid with the remaining star candidates.

Let's look at an example. With 5 detected star candidates, we try to query the database for triangles. The stars are numbered from 1 to 5, so possible combinations are:

We can already see that this order is not ideal. In case the candidate number 1 is not a real star, all first queries would fail, because all the triangles tried include this candidate.

Can you come up with an algorithm that determines the optimal order with low use of resources such as computational time and memory?