Application of nonparametric estimation of the regression function to increase the accuracy of navigation problem solution

Толық мәтін

Introduction

Task description

Global Navigation Satellite Systems (GNSS) help determine location and time using special satellites. The most famous systems are GPS, created in the USA, GLONASS from Russia, Galileo from the European Union and Beidou, developed in China.

Currently, satellite navigation systems are an integral part of our lives. GNSS technology has many practical applications [1–3]:

• with the help of GNSS, people and vehicles can determine their location and navigate their route. This is especially useful when there are no other landmarks or you need to get to the desired place quickly;
• satellite navigation helps to create accurate maps and determine the coordinates of various objects. It is important for construction, agriculture, natural resource management and other areas of activity;
• in the military sphere, satellite navigation provides precise positioning and navigation for operations;
• satellite navigation is used to control unmanned aerial vehicles.

However, satellite navigation systems also have disadvantages:

• satellite signals may be distorted due to various factors such as weather conditions or technical problems;
• in urban areas, densely populated areas or forested areas, satellite navigation may have some error in determining location;
• the performance and availability of satellites affects the functionality of the system (if satellites fail or become unavailable, the system stops working).

Global navigation satellite systems (GNSS) are actively used in the control of unmanned aerial vehicles (UAV). However, when using UAV, there may be factors that lead to loss of orientation in space [4; 5].

These factors include:

• movement in the woods or forest
• impact of radio electronic interference;
• movement in complex landscape conditions or dense urban development.

If current location information is lost, it may have serious consequences for the device. The longer the interruption in determining coordinates lasts, the higher the probability of an emergency situation occurring.

One approach to solving this problem is the use of inertial navigation systems. They complement the satellite navigation system at the moment of “break in the navigation field” [6; 7].

This approach has a drawback – the mass of an inertial system of "medium accuracy" on laser or optical gyroscopes is more than 8 kg. This makes them difficult to use on short- and medium-range UAV.

Since the correct operation of a satellite navigation system requires at least 4 satellites simultaneously observed by the receiver, methods that increase the reliability of GNSS use in complex landscape conditions, with high building density or in forests can be useful in various fields.

The research is devoted to the development of an algorithm that will improve the reliability of the solution of the navigation problem in conditions of a small number of observed NSV.

 Algorithms for restoring values of a sample of observations

As a rule, for a high-quality reconstruction of the values of a sample of observations, the remaining part of the sample must be of high quality and complete. However, in reality, for one reason or another, data with gaps sometimes occurs. This complicates mathematical treatment because the bias of key statistical characteristics such as mean or variance increases with the number of missing values.

In the case of solving a navigation problem, gaps in data are caused by the fact that the navigation satellite “hides” behind an obstacle (mountain, building, bridge, etc.).

In mathematical statistics there are several methods for working with incomplete data [8; 9]:

• exclude incomplete objects from the sample – as a rule, this is an incorrect approach, since incomplete data may contain important information for constructing a model or control algorithm;
• use special mathematical methods for analyzing incomplete data, such as the weighting method, the maximum likelihood method, and the EM-algorithm.
• restoring gaps is a common and effective way to solve the problem.

For this purpose, methods of filling by mean value or regression are used.

We could consider common methods for restoring gaps in data.

1. The k-nearest neighbors method. This algorithm is based on the assumption that objects that are similar in the values of n-1 properties will have a similar value for the n-th property.
2. The mean filling method is a method in which missing data are replaced by the arithmetic mean of all available observations.
   This method is not always suitable for working with data that has significant systematic fluctuations or is unstable.
   This method is most effective when working with time series in which it is difficult to identify a regular component.
3. Resampling method is used to fill gaps in the data. The essence of the method is to randomly select values from the original data set X_i to replace missing elements.

Analyzing these methods, it is clear that to restore gaps, a vector of the same variable that we are restoring is used. But it is obvious that for a problem in which a correlation dependence between different variables has been discovered, using this dependence in solving the problem of filling in gaps in a sample of observations is the correct approach. In this regard, it was decided to develop a new gap recovery algorithm for this task.

Sample analysis

Data collection

The quality of an experiment conducted in real conditions depends largely on the equipment. If the equipment is of poor quality, the results of the experiment may be interpreted incorrectly. This may lead to erroneous conclusions regarding the effectiveness of the developed algorithm.

The “PRO-04” navigation receiver was chosen for the experiment. We need to consider it in detail.

The navigation receiver "PRO-04" is designed to calculate the current coordinates and speed of an object in real time in autonomous and differential modes, generate a second time stamp and exchange with external equipment via serial UART ports.

The module provides the following functions:

• measurement of pseudo-range to GNSS spacecraft, radial pseudo-velocity of GNSS spacecraft and carrier frequency phase using GLONASS and GPS/SBAS, Galileo signals;
• determination and output of time-related current location coordinates and the current speed vector of movement;
• reception and accounting of corrective information in RTCM SC-104 format when solving a navigation problem;
• retrieval of time reference signal (synchronizing pulse (1PPS)).

Dependency between navigation parameters

At the initial stage of development of a new nonparametric algorithm for data recovery in the field of navigation problems, an experiment was conducted, during which the dependence between changes in the pseudo-ranges of different satellites was revealed.

First, it is necessary to define the concept of “pseudo-range”. Pseudo-range (P) is the distance between a satellite and a receiver, calculated based on the signal propagation time without taking into account the time difference between the satellite and the receiver’s clocks.

The goal of the experiment was to accumulate pseudo-ranges to all visible navigation satellites with a measurement frequency of once per second.

The experiment was conducted as follows. The navigation receiver antenna was installed on a stationary platform on the roof of the building, and the receiver was connected to a laptop. The program was then launched on the laptop and data collection began. The results are shown in Table 1.

 

Table 1

Part of a measurement set with pseudo-ranges to navigation satellites

 

Date and time	Navigation satellite number	Pseudo-range to satellite (P), mm
2024-07-10 06:30:01.000	1	15980895088
2024-07-10 06:30:01.000	8	13408743693
2024-07-10 06:30:01.000	17	16465445531
2024-07-10 06:30:01.000	26	13303756619
2024-07-10 06:30:02.000	1	15980041540
2024-07-10 06:30:02.000	8	13408433227
2024-07-10 06:30:02.000	17	16464741876
2024-07-10 06:30:02.000	26	13303506602
2024-07-10 06:30:03.000	1	15979188039
2024-07-10 06:30:03.000	8	13408122896
2024-07-10 06:30:03.000	17	16464038239
2024-07-10 06:30:03.000	26	13303256756
2024-07-10 06:30:04.000	1	15978334580
2024-07-10 06:30:04.000	8	13407812709
2024-07-10 06:30:04.000	17	16464038239
2024-07-10 06:30:04.000	26	13303007075

 

The next step in the experiment was to transform the table with data on the range to the satellite into a table that showed the change in this range relative to the previous moment in time (ΔP).

In other words, the magnitude of the change in range was calculated for each moment in time.

$\Delta P\left(t\right)=P\left(t\right)-P(t-1).$

 

Table 2

Part of the ΔP set of navigation satellites 

Date/time	ΔP, mm (Satellite 1)	ΔP, mm (Satellite 8)	ΔP, mm (Satellite 17)	ΔP, mm (Satellite 26)
2024-07-10 06:30:02.000	–853548	–310466	–703655	–250017
2024-07-10 06:30:03.000	–853501	–310331	–703637	–249846
2024-07-10 06:30:04.000	–853459	–310187	–703641	–249681
2024-07-10 06:30:05.000	–853421	–310038	–703656	–249502

 

Table 2 demonstrates the value of the corresponding ΔP recorded at the intersection of the satellite number and time.

The final stage of the experiment was the pairwise calculation of the correlation coefficient [10] ΔP_i, ΔP_j, i, j = (1, n), where n is the number of observed satellites.

The coefficient shows whether there is a linear relationship between the features. The Pearson correlation coefficient formula allows us to accurately determine the strength of this relationship if it is linear. Therefore, the coefficient is also called Pearson linear correlation coefficient.

If the correlation coefficient is close to 1 in absolute value, this indicates a high level of connection between the variables. For example, when a variable is correlated with itself, the correlation coefficient will be +1. This indicates a directly proportional relationship. If the values of variable X are set in ascending order, and the corresponding values of variable Y are set in descending order, then the correlation coefficient between X and Y will be –1. This correlation coefficient indicates an inversely proportional relationship.

The formula to calculate the correlation coefficient is as follows:

$r_{xy}=\frac{{\displaystyle \sum (x_i-M_x)(y_i-M_y)}}{\sqrt{{\displaystyle \sum {(x_i-M_x)}^2{(y_i-M_y)}^2}}},$

where x_i are the values taken by variable X; y_i are the values taken by variable Y; М_х is the average
for X; М_у is the average for Y.

The sample calculated values of the correlation coefficient modules are presented in Table 3.

 

Table 3

Sample values of the modules of the correlation coefficients 

Satellite numbers	1	8	17	26
1	1,0	0.98647545852077	0.99969232684640	0.98482950569361
8	0.98647545852077	1.0	0.98245104435400	0.9999522654286
17	0.999692326846407	0.98245104435400	1,0	0.9805910475390
26	0.98482950569361	0.99995226542863	0.9805910475390	1.0

 

In the process of studying the collected data, a correlation was revealed between changes in pseudo-ranges to satellites. In other words, the change in the distance between the receiver and one satellite is interconnected with the change in the distance between the receiver and another satellite.

To verify this, additional studies were conducted. Their results also demonstrated the presence of a correlation.

It is worth emphasizing that with increasing observation time, this connection became less pronounced.

Based on the data obtained, we assumed that there is a certain pattern between the changes in distances to different satellites.

The essence of the hypothesis is this: since the satellites move in orbits with a large radius, it can be assumed that over a short period of time the change in distance from each satellite to the observer will have a linear law. This means that when the distance to one satellite changes, it is possible to predict the amount of change in the distance to another satellite. To confirm this hypothesis, ΔP graphs were constructed for various satellites (Fig. 1).

 

Рис. 1. Изменение ΔP в период времени от 06:30 до 07:30 для НКА номер 1, 8, 17, 26

Fig. 1. Change of ΔP in the time period from 06:30 to 07:30 for NSV number 1, 8, 17, 26

 

The ability to predict changes in pseudo-ranges will allow the use of satellites with short periods of information loss to solve navigation problems.

Based on this hypothesis, a nonparametric algorithm for data recovery was developed when solving a navigation problem.

 

Algorithm to restore navigation parameters

Nonparametric estimation of the regression function

We suppose that we have a set of statistically independent observations of two random variables
(u, x) = (u₁, x₁),.., (u_n, x_n), which represent pairs of values. These random variables are characterized by an unknown probability density P(u, x), where p(u) > 0"u ∀ Ω(u) [11]. This means that in this region there is a non-zero probability of observing the value u. To approximate unknown stochastic relationships between variables x from u, the x-by-u regression method is often used, which allows to estimate the effect of a change in one variable on another. The nonparametric estimate of this dependence has the form [12; 13]:

$x_n=f_n\left(u\right)={\left(\sum _{i=\text{1}}^n\text{Φ}\left(\frac{u-u_i}{C_n}\right)\right)}^{-\text{1}}\left(\sum _{i=\text{1}}^n{x}_i\Phi \left(\frac{u-u_i}{C_n}\right)\right)$

where Ф is the kernel function; C_n is the kernel blur coefficient.

The idea of the algorithm is based on the hypothesis described above.

The algorithm contains the following steps:

1. Form a set of observations that contains changes in the pseudo-ranges of the observed navigation satellites. When solving the navigation problem for the first time, it is necessary to calculate the radio visibility zones for all observed satellites.
2. Determine the sample size sufficient to construct a nonparametric estimate of the regression function [14; 15]. The sample size should be large enough to reliably estimate the regression function, but not too large to preserve the correlation between the parameters.
3. When adding new data, include the new ΔP values in the sample of observations. If the sample size exceeds the one set in step 2, it is prescribed to remove the oldest value from the observation sample.
4. If there is a gap in the measurement of the pseudo-range to the satellite, the proceed could be as follows.

If the accumulated sample contains information about a missed satellite and the satellite should be visible according to the calculation of the radio visibility zone, it is necessary to extrapolate this change using the following formula:

$p_{k\left(n\right)}=p_{k(n-1)}+\mathrm{\Delta }p,\mathrm{\Delta }p=$$\frac{{\displaystyle \sum _{i=1}^{n-1}\mathrm{\Delta }{p}_{ki}\prod _{j=1}^{k-1}\Phi \left(\frac{\mathrm{\Delta }{p}_{ki}-\mathrm{\Delta }{p}_{ji}}{c_{sj}}\right)}}{{\displaystyle \sum _{i=1}^{n-1}\prod _{j=1}^{k-1}\Phi \left(\frac{\mathrm{\Delta }{p}_{ki}-\mathrm{\Delta }{p}_{ji}}{c_{sj}}\right)}},$

where p_k is the missing parameter in satellite k; n is the number of selected observations; k is the number of observed satellites.

This algorithm can restore the parameters of a missing signal. However, experiments have shown that the longer the signal is missing, the greater the error of the algorithm.

 

Result of recovery

To evaluate the efficiency and accuracy of the algorithm, the data from Table 2 were used. As part of the study, random gaps were introduced into these data for all satellites. Gaps accounted for five percent of the total sample size. When a satellite gap was included, measurements of duration from 3 to 15 minutes were excluded from the sample.

The purpose of introducing gaps is to simulate conditions in which the navigation receiver loses signal from some navigation satellites (for example, due to high building density). This allows to evaluate the ability of the algorithm to reconstruct missing values and its effectiveness in working with incomplete data.

After the gaps were introduced, the developed algorithm was applied to restore the missing values. Then a comparison was made between the real data and the recovered data. This stage permitted to evaluate the accuracy and reliability of the algorithm in the data recovery process. Some of the compared results are shown in Table 4 (1 satellite is given as an example).

 

Table 4

Results of restoring pseudo-range values for NSV 1

Date/time	Actual value ΔP, mm (Satellite 1)	Recovered ΔP value, mm (Satellite 1)	Difference between values, mm
2024-07-10 6:30:34	–852594	–852624.0	30.0
2024-07-10 6:30:48	–852011	–852044.0	33.0
2024-07-10 6:31:40	–850527	–850564.0	37.0
2024-07-10 6:31:59	–849770	–849793.0	23.0
2024-07-10 6:32:34	–848503	–848518.9999999999	15.999999999883585
2024-07-10 6:33:04	–847705	–847738.0	33.0
2024-07-10 6:35:49	–841668	–841675.0	7.0
2024-07-10 6:35:54	–841499	–841563.0	64.0
2024-07-10 6:36:05	–841126	–841177.0	51.0
2024-07-10 6:36:22	–840296	–840298.0	2.0
2024-07-10 6:37:01	–838586	–838607.0	21.0
2024-07-10 6:40:06	–830571	–830609.0	38.0

 

Conclusion

In this research, an algorithm based on a nonparametric estimate of the regression function was developed, aimed at restoring a sample of observations. The experiment was conducted to restore pseudo-ranges to GLONASS navigation satellites under the following conditions: the antenna was located on the roof of a building in a city with large closing angles, the receiver and antenna did not move, and signal interruption was detected for only one satellite from the entire sample.

The results showed that the difference between the real and reconstructed pseudo-range values did not exceed one percent, which allows them to be used to solve the navigation problem, although there was still an impact on the accuracy of navigation determination. This confirms the effectiveness of the proposed algorithm under certain conditions.

Further research will be aimed at modifying the algorithm for mobile receiver conditions and a larger number of missing satellite signal values. Expanding the capabilities of the algorithm will improve the accuracy and reliability of navigation systems.

 

Acknowledgments

The study was supported by a grant from the Russian Science Foundation and the Krasnoyarsk Regional Foundation for the Support of Scientific and Scientific-Technical Activities No. 25-19-20070, https://rscf.ru/project/25-19-20070/.

Авторлар туралы

Alexander Karavanov

Siberian Federal University

Хат алмасуға жауапты Автор.
Email: karavanov_92@mail.ru
ORCID iD: 0009-0000-4942-4080

Lecturer

Ресей, 79g, Svobodny Av., Krasnoyarsk, 660041

Evgeny Mihov

Siberian Federal University

Email: edmihov@mail.ru
ORCID iD: 0000-0002-9561-8596

Cand. Sc., Associate Professor

Ресей, 79g, Svobodny Av., Krasnoyarsk, 660041

Әдебиет тізімі

Қосымша файлдар