Optimal orderings of k-subsets for star identification
Star trackers such as the Hydra star tracker (see figure) are an important part of spacecraft to determine the attitude. The device consists of one or more cameras that detect stars and identify them based on the observed constellations. From these visible constellations it is possible to compute the orientation of the spacecraft. This is particularly challenging in the lost-in-space scenario, with no prior knowledge about the attitude.
The Pyramid algorithm for star identification developed by Mortari et al. [1] works by selecting triplets of spikes detected in an image. The spikes can either be stars or artifacts. The selected triplets are compared to a star catalog. If a triangle with the same shape is found in the catalog, another spike is added to form a pyramid. When this pyramid can be found in the catalog, the remaining spikes in the image can be identified as either stars or artifacts.
k-subset Sequences
The optimal ordering of triplets to try was described by Mortari et al. [1] as being an open problem. The ACT investigated algorithms to find the optimal order of not only triplets (3-subsets), but general k-subsets for the star identification scenario (see outcome below). An ordering of all possible k-subsets is given a score depending on how many subsets have to be tried on average before a valid star constellation is found.
A k-subset is the selection of k out of a total of n elements. The solutions were found by different algorithms and are the best ones we know of at the moment. You can download all solutions as zip file. If you have any better solution, feel free to send it to us and we will add it to the page, with proper credit of course.
References
- Mortari, Daniele, Malak A. Samaan, Christian Bruccoleri, and John L. Junkins. "The pyramid star identification technique." Navigation 51, no. 3 (2004): 171-183.