Satellites see the stars - Part II

One of the problems in launching a satellite into space is the problem of immediate navigation - that is, the problem of finding the position and direction of a satellite hovering somewhere above the sky in real time. The stars can be the solution - Part II

Eran Galili, Galileo

To part A: the data needed for the satellite

The non-self and self motions of the stars are indeed an essential part of the process of estimating where a satellite should look for stars, but even the most sophisticated physical model is useless without baseline data. What should the satellite's database contain, so that it can "search" for the stars in the right place?

First, the database must include star positions in the sky. Star positions are often described using a spherical coordinate system - where each point P in 3D space has XNUMX coordinates: r (the distance between the principal, O, and point P), a "vertical" angle, θ (the angle between the line OP and the vertical axis z) and an angle " horizontal", φ (the angle between the projection of the straight line OP on the horizontal plane, xy, and the x-axis).

Since our goal is to observe the stars, this system can be simplified. When we look at the sky, we actually see a kind of black "sheet", on which there are white points of light - stars. If we expand this sheet of stars as it will be seen by observers in Australia, Brazil and Japan - around the Earth - we will get a spherical shell that surrounds the Earth and on it are "drawn" points representing stars. This shell is called the celestial sphere, and through it we can determine the positions of the stars.

The identification is carried out using 3 different algorithms, each of which is based on comparing the angular distances between the stars, the stars are not identified similar to the spherical coordinate system, we will use two angles, but not the distance - because all the points drawn on the celestial sphere are at the same distance from the center of the Earth ! The angles will be measured in relation to fixed reference planes - the angle θ, called inclination or declination, in relation to the ascent of the Earth's equator on the celestial sphere, and the angle φ, called right ascension, in relation to the ascent of the latitude of Greenwich.

But the position of the stars alone is not enough. After all, we showed that the position of the stars in the sky changes every moment! If so, the point of time, or date, when the star was observed must be added to the location data. Representing the date in the way we are used to - year, month, day, hour, minute and second - is problematic, because it requires 6 number fields in the database. Therefore, astrophysicists use the Julian Time method - a method in which the date is represented by the number of days that have passed since 12 noon on Monday, January 1, 4713 BC. For example, Israel's declaration of independence (May 15.5.1948, 4, at 2432686.16667 p.m.) occurred at Julian time 12 (the number is incomplete because the time is not 1.1.2000 noon), and the date 12, at 2000 noon (also marked as J2451545.0, and is the basis for epistrophysical catalogs plural) corresponds to Julian time XNUMX.

In addition to the position and time, the database must also contain data that will allow us to evaluate the changes that occur in the apparent position of the stars due to spontaneous and non-spontaneous motion, as we have described. For aberration, the position and time data together are sufficient; For parallax, the distance to the stars must also be added; And for self-motion - the estimation of the speeds at which the stars move in the sky must be added.

the catalog

The database we chose to use for our simulations is the Tycho-2 star catalog (Tycho-2, named after the astronomer Tycho Braha). This catalog is the result of an in-depth analysis of the results of the observations of the Hipparcos satellite, which was launched into space in 1989. The catalog contains about 2.5 million stars, and detailed and accurate data for most of them, which fulfill all our requirements. The catalog is synchronized to the "J2000" date - that is, the star data in the catalog was calculated to match the observations made on 1.1.2000, at 12 noon.

The chain algorithm is used to initially identify some stars for the comparison algorithm. After the initial detection, we will use the comparison algorithm to identify the rest of the stars, however, for the relatively weak processors found in the satellites, dealing with such a large amount of stars is not a matter of what-if. That's why the celestial sphere and the catalog were divided into several regions, and the identification process - into two stages: first, the satellite must roughly estimate the region in the sky where it is observing (with the help of cheap and simple systems), then it is possible to reduce the pool of stars to those found in this region only (or, in extreme cases , in the areas surrounding it), and activate the precise navigation method in a faster and more efficient way.

Identifying the stars

Now, after the construction of the appropriate database, it is finally possible to approach the work of star identification itself. The identification is carried out using 3 different algorithms, each of which is based on comparing the angular distances between the stars. Angular distance is the size of the angle separating 2 stars on the celestial sphere; In the spherical coordinates figure above, for example, the size of the angle POQ is the angular distance between point P and point Q.

The first algorithm we used is called the chain algorithm, and it is based on an article by Craig L. Cole and John L. Crassidis (Crassidis). This algorithm is the fastest of the three, but it is very vulnerable to errors, both due to the "disappearance" of stars (for example, if they are hidden by asteroids), and due to the "formation" of "new" stars (in the case that the satellite detects other asteroids as stars ).

The chain algorithm simultaneously identifies a chain of stars, according to the angular distances between them. The algorithm starts with an arbitrary selection of 2 stars in the input space - star 1 and star 2, and measures the angular distance between them. We will denote this distance by D1. Now the algorithm selects another star - star 3 - and measures the angular distance between it and star 2. We will denote this distance by D2. Now the algorithm has a "chain" of stars - stars 1, 2 and 3 - the distances between its members are D1 and D2. In fact, this chain is 2 "pairs" of stars whose angular distances between them are known (D1 and D2) and which have a common star (star 2).

The algorithm searches the catalog for exactly such star pairs - whose distances are D1 and D2, and which have a common star. If there is only one such chain, the 3 stars have been successfully identified - otherwise, the algorithm adds another star to the chain (as it added star 3), and repeats the measurement and search.

The image above demonstrates the operation of the algorithm, with the input image shown on the left, and the other images are the identification process operating on the stars in the catalog:

1. All the matches in the catalog are found for the distance between the first pair of stars, D1.

2. All the matches in the catalog are found for the distance between the second pair of stars, D2.

3. All pairs of stars with distance D1 that do not have a star in common with pairs of stars with distance D2 are rejected; The same is true for pairs of stars with a distance of D2, which do not have a star in common with pairs of stars with a distance of D1. Still not a single match, so…

4. All the matches are found in the catalog for the distance between the third pair of stars.

5. Again the pairs of stars that do not have a common star are rejected, and only one chain of 4 stars remains - we have identified the input stars.
The focused chain algorithm and the comparison algorithm

The second algorithm we used is called the focused chain algorithm, which is - as the name implies - a focused version of the chain algorithm. The difference is that in the focused method, one star is chosen that we want to identify, and the distances between it and many other stars are measured. According to the "common star" principle that we used in the chain algorithm, the star common to all the corresponding distances in the catalog is the chosen star.

Although the targeted algorithm typically requires fewer distance comparisons than the regular chaining algorithm, it is slower. This is because it detects only one star and not a whole chain at once. The third algorithm we used, the comparison algorithm, also detects only one star, but it is so fast and accurate that it is even better than the regular chain algorithm. He has only one weakness - he cannot be used alone!

The reason for this, as we will see later, is that in the comparison algorithm the stars we have already identified are used to identify additional stars, so if we have not yet identified any stars - this algorithm cannot be used!

Similar to the previous image, this image also depicts the algorithm when the input is on the left. We assume that we have already identified the red and purple star, using one of the chain algorithms. Our goal is to identify the green star.

1. Measure the distance between the green star and one of the stars we identified - the purple star, and find all the pairs with the appropriate distance in the catalog. Since we know that the green star is exactly at the chosen distance from the violet star, we will mark the stars at this distance from the violet star in the catalog as possible matches.

2. Since we have more than one match (as is usually the case), we will narrow down the possibilities by comparing with the second star we have already identified - the red star - using the same method.

3. After narrowing down the possibilities to stars with a suitable distance to the purple star and also to the red star, we were left with only the correct star.

The comparison algorithm is the fastest of the three because it requires very few comparisons to succeed - usually 2 or 3 are enough. The targeted chaining algorithm requires about 5 comparisons, and the normal chaining algorithm can sometimes require up to 8 comparisons (but when it succeeds, it detects many stars at once!).

a winning combination

Each of the three algorithms we mentioned has its own role in the general scheme of star detection. The chain algorithm is used to initially identify some stars for the comparison algorithm. After the initial detection, we will use the comparison algorithm to detect the rest of the stars.

When the normal chain algorithm or the comparison algorithm encounters a problematic star (for example, part of a pair of stars whose distance has many matches in the catalog), we will use the focused comparison algorithm to overcome the glitch.

This combination technique uses the strong sides of each algorithm to ensure fast and efficient identification of stars, and indeed, after performing the simulations of the algorithms, they managed to reach very high accuracy percentages (over 90%).

After the identification, the navigation itself is a matter of what-if: just like a person is able to recognize that a map he is holding is upside down after identifying buildings that appear on it, so too the satellite can use simple algebraic operations to deduce the exact angle at which it is aimed, in a quick, simple way, And most importantly - without any dependence on the humans on the ground.

Eran Galili is a research student in the Department of Mathematics at Bar-Ilan University.