• ESA > ACT > Artificial Intelligence > Optimal selection of star constellations for star trackers

## Optimal orderings of k-subsets for star identification

The flight model of the hydra star-tracker currently flying on the ESA Sentinel 3A satellite mission

Star trackers such as the Hydra star tracker (see figure) are an important part of spacecraft to determine the attitude. The device concists of one or multiple cameras that detect stars and identify them based on the visible 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 [2]. 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 following solutions were found by different algorithms and are the best ones we know of at the moment. You can download the solutions by either clicking on the link in the Algorithm column or 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.

n k Score Algorithm
2 1 1.33 Optimum
3 1 1.57 Optimum
3 2 1.75 Optimum
4 1 1.73 Optimum
4 2 2.55 Optimum
4 3 2.20 Optimum
5 1 1.84 Optimum
5 2 3.31 Optimum
5 3 4.19 Optimum
5 4 2.67 Optimum
6 1 1.90 Optimum
6 2 3.95 Optimum
6 3 6.40 Optimum
6 4 6.23 Optimum
6 5 3.14 Optimum
7 1 1.94 GSE
7 2 4.34 GSE
7 3 8.94 GSE
7 4 11.41 GSE
7 5 8.55 GSE
7 6 3.62 GSE
8 1 1.97 GSE
8 2 4.65 GSE
8 3 11.35 GSE
8 4 18.45 GSE
8 5 18.94 GSE
8 6 11.54 GSE
8 7 4.11 GSE
9 1 1.98 GSE
9 2 4.76 GSE
9 3 13.41 GSE
9 4 27.11 GSE
9 5 35.72 GSE
9 6 29.43 GSE
9 7 15.04 GSE
9 8 4.60 GSE
10 1 1.99 GSE
10 2 4.85 GSE
10 3 14.92 GSE
10 4 36.12 GSE
10 5 59.40 GSE
10 6 63.01 GSE
10 7 43.47 GSE
10 8 19.04 GSE
10 9 5.09 GSE
11 1 1.99 GSE
11 2 4.80 GSE
11 3 15.92 GSE
11 4 45.20 GSE
11 5 89.59 GSE
11 6 117.93 GSE
11 7 104.21 GSE
11 8 61.47 GSE
11 9 23.54 GSE
11 10 5.58 GSE
12 1 2.00 GSE
12 2 4.77 GSE
12 3 16.48 GSE
12 4 52.77 GSE
12 5 124.20 GSE
12 6 198.50 GSE
12 7 216.62 GSE
12 8 163.14 GSE
12 9 84.01 GSE
12 10 28.53 GSE
12 11 6.08 GSE
13 1 2.00 GSE
13 2 4.65 GSE
13 3 16.57 GSE
13 4 58.76 GSE
13 5 160.58 GSE
13 6 305.18 GSE
13 7 403.20 GSE
13 8 373.29 GSE
13 9 244.49 GSE
13 10 111.58 GSE
13 11 34.03 GSE
13 12 6.57 GSE
14 1 2.00 GSE
14 2 4.59 GSE
14 3 16.36 GSE
14 4 62.68 GSE
14 5 196.46 GSE
14 6 436.66 GSE
14 7 682.55 GSE
14 8 759.90 GSE
14 9 610.42 GSE
14 10 353.19 GSE
14 11 144.53 GSE
14 12 40.03 GSE
14 13 7.07 GSE
15 1 2.00 GSE
15 2 4.49 GSE
15 3 15.88 GSE
15 4 64.54 GSE
15 5 227.33 GSE
15 6 585.19 GSE
15 7 1069.52 GSE
15 8 1405.33 GSE
15 9 1349.38 GSE
15 10 954.46 GSE
15 11 494.64 GSE
15 12 183.55 GSE
15 13 46.53 GSE
15 14 7.56 GSE
16 1 2.00 GSE
16 2 4.44 GSE
16 3 15.45 GSE
16 4 64.59 GSE
16 5 252.52 GSE
16 6 741.38 GSE
16 7 1567.23 GSE
16 8 2394.47 GSE
16 9 2702.66 GSE
16 10 2277.75 GSE
16 11 1439.00 GSE
16 12 674.57 GSE
n k Score Algorithm
16 13 229.08 GSE
16 14 53.53 GSE
16 15 8.06 GSE
17 1 2.00 GSE
17 2 4.36 GSE
17 3 14.60 GSE
17 4 63.23 GSE
17 5 269.19 GSE
17 6 893.35 GSE
17 7 2160.85 GSE
17 8 3810.09 GSE
17 9 4980.14 GSE
17 10 4910.17 GSE
17 11 3684.96 GSE
17 12 2102.61 GSE
17 13 900.55 GSE
17 14 281.51 GSE
17 15 61.03 GSE
17 16 8.56 GSE
18 1 2.00 GSE
18 2 4.32 GSE
18 3 14.07 GSE
18 4 60.85 GSE
18 5 277.37 GSE
18 6 1028.54 GSE
18 7 2826.72 GSE
18 8 5694.18 GSE
18 9 8540.88 GSE
18 10 9720.97 GSE
18 11 8504.55 GSE
18 12 5748.63 GSE
18 13 2990.01 GSE
18 14 1178.43 GSE
18 15 341.53 GSE
18 16 69.02 GSE
18 17 9.05 GSE
19 1 2.00 GSE
19 2 4.26 GSE
19 3 13.38 GSE
19 4 57.56 GSE
19 5 277.82 GSE
19 6 1138.22 GSE
19 7 3522.35 GSE
19 8 8051.00 GSE
19 9 13746.43 GSE
19 10 17874.74 GSE
19 11 17982.38 GSE
19 12 14133.59 GSE
19 13 8692.41 GSE
19 14 4153.90 GSE
19 15 1516.35 GSE
19 16 409.51 GSE
19 17 77.52 GSE
19 18 9.55 GSE
20 1 2.00 GSE
20 2 4.23 GSE
20 3 12.80 GSE
20 4 54.23 GSE
20 5 271.64 GSE
20 6 1214.91 GSE
20 7 4385.89 MIS
20 8 11231.01 MIS
20 9 21546.31 MIS
20 10 31542.70 MIS
20 11 35959.83 MIS
20 12 32247.05 MIS
20 13 22905.12 MIS
20 14 12791.00 GSE
20 15 5654.22 GSE
20 16 1923.02 GSE
20 17 486.02 GSE
20 18 86.52 GSE
20 19 10.05 GSE
21 1 2.00 MIS
21 2 4.18 GSE
21 3 12.32 GSE
21 4 50.56 GSE
21 5 259.96 GSE
21 6 1319.08 MIS
21 7 5041.99 MIS
21 8 14469.44 MIS
21 9 31214.26 MIS
21 10 51517.82 MIS
21 11 66239.27 MIS
21 12 67376.56 MIS
21 13 54728.04 MIS
21 14 35605.07 MIS
21 15 18492.55 MIS
21 16 7581.02 MIS
21 17 2405.56 MIS
21 18 571.59 MIS
21 19 96.02 MIS
21 20 10.55 MIS
22 1 2.00 MIS
22 2 4.17 GSE
22 3 11.88 GSE
22 4 47.23 GSE
22 5 244.72 GSE
22 6 1327.66 MIS
22 7 5583.60 MIS
22 8 17858.30 MIS
22 9 43138.55 MIS
22 14 89781.46 MIS
22 15 53875.71 MIS
22 16 25998.94 MIS
22 17 9969.62 MIS
22 18 2973.20 MIS
22 19 666.60 MIS
22 20 106.02 MIS
22 21 11.04 MIS
23 1 2.00 MIS
23 2 4.13 GSE
23 3 11.49 GSE
23 4 44.00 GSE
23 5 227.36 GSE
23 6 1302.41 MIS
23 7 5982.36 MIS
n k Score Algorithm
23 8 21198.29 MIS
23 16 79622.89 MIS
23 17 35897.21 MIS
23 18 12923.35 MIS
23 19 3635.29 MIS
23 20 771.62 MIS
23 21 116.52 MIS
23 22 11.54 MIS
24 1 2.00 MIS
24 2 4.12 GSE
24 3 11.16 GSE
24 4 41.13 GSE
24 5 209.28 GSE
24 6 1249.69 MIS
24 7 6214.05 MIS
24 17 115192.75 MIS
24 18 48735.39 MIS
24 19 16540.86 MIS
24 20 4402.60 MIS
24 21 887.12 MIS
24 22 127.52 MIS
24 23 12.04 MIS
25 1 2.00 MIS
25 2 4.10 GSE
25 3 10.83 GSE
25 4 38.53 GSE
25 5 191.27 GSE
25 6 1176.10 MIS
25 7 6281.03 MIS
25 18 163556.91 MIS
25 19 65175.35 MIS
25 20 20920.20 MIS
25 21 5285.11 MIS
25 22 1013.58 MIS
25 23 139.02 MIS
25 24 12.54 MIS
26 1 2.00 MIS
26 2 4.09 GSE
26 3 10.57 GSE
26 4 36.27 GSE
26 5 174.32 GSE
26 6 1089.00 MIS
26 7 6190.99 MIS
26 20 85976.81 MIS
26 21 26178.85 MIS
26 22 6293.77 MIS
26 23 1151.61 MIS
26 24 151.02 MIS
26 25 13.04 MIS
27 1 2.00 MIS
27 2 4.07 GSE
27 3 10.35 GSE
27 4 34.32 GSE
27 5 158.70 GSE
27 6 995.25 MIS
27 21 112030.98 MIS
27 22 32447.29 MIS
27 23 7440.29 MIS
27 24 1301.63 MIS
27 25 163.52 MIS
27 26 13.54 MIS
28 1 2.00 MIS
28 2 4.07 GSE
28 3 10.17 GSE
28 4 32.60 GSE
28 5 149.76 MIS
28 6 899.75 MIS
28 22 144339.74 MIS
28 23 39857.85 MIS
28 24 8737.03 MIS
28 25 1464.10 MIS
28 26 176.52 MIS
28 27 14.03 MIS
29 1 2.00 MIS
29 2 4.05 GSE
29 3 10.01 GSE
29 4 31.11 GSE
29 5 136.38 MIS
29 6 806.88 MIS
29 23 184045.06 MIS
29 24 48566.24 MIS
29 25 10195.60 MIS
29 26 1639.64 MIS
29 27 190.02 MIS
29 28 14.53 MIS
30 1 2.00 MIS
30 2 4.05 GSE
30 3 9.85 GSE
30 4 29.82 GSE
30 5 124.63 MIS
30 6 719.71 MIS
30 25 58729.42 MIS
30 26 11829.74 MIS
30 27 1828.63 MIS
30 28 204.02 MIS
30 29 15.03 MIS
31 1 2.00 MIS
31 2 4.04 GSE
31 3 9.72 GSE
31 4 29.02 MIS
31 5 114.54 MIS
31 26 70523.20 MIS
31 27 13652.67 MIS
31 28 2031.61 MIS
31 29 218.52 MIS
31 30 15.53 MIS
32 1 2.00 MIS
32 2 4.04 GSE
32 3 9.60 GSE
32 4 28.06 MIS
32 5 105.91 MIS
32 27 84142.65 MIS
32 28 15674.21 MIS
32 29 2249.13 MIS
32 30 233.51 MIS
32 31 16.03 MIS

### References

1. [1] Daniele Mortari, Malak A Samaan, Christian Bruccoleri, and John L Junkins, ‘The pyramid star identification technique’, Navigation, 51(3), 171–183, (2004).
2. [2] Mueller, J. H., Sánchez-Sánchez, C., Simões, L. F. and Izzo, D. (2016, December). Optimal Orderings of k-subsets for Star Identification. In Computational Intelligence (SSCI), 2016 IEEE Symposium Series on (pp. 1-8). IEEE.