WO2025080154A1 - Method for indoor navigation and object location - Google Patents

Abstract

A method for determining the location of a user in an indoor environment includes creating a digital map of an indoor environment showing a floor identifier and the position of radio transmitters, loading the map onto a mobile computing device (MCD), measuring the strength of RSSI signals using the MCD, determining vectors of acceleration, MCD rotation and magnetic field orientation using inertial measuring devices of the MCD, determining from the measured data the coordinates (x, y) of the MCD, the floor identifier and the angle of rotation of the MCD relative to a vertical axis, and showing the location of the user on the digital map in an interface of the MCD. The technical result of the invention is an increase in the accuracy of determining the location of a user in an indoor environment.

Description

METHOD OF NAVIGATION AND POSITIONING OF OBJECTS INDOORS

AREA OF TECHNOLOGY

The claimed technical solution relates to the technical field of determining location indoors, and in particular to a method for determining the location of a user indoors using inertial measurement devices of the user's mobile computing device in real time.

LEVEL OF TECHNOLOGY

With the development of widespread information technology in society, the number of online users doubles every year, and more and more wireless network access zones appear. However, the requirements for wireless signal coverage in indoor areas such as high-rise offices, ordinary residential buildings, and large shopping malls with a large number of users are becoming higher and higher.

The traditional indoor distribution system uses the antenna + feeder method, which has the problems of signal dead zone, large electromagnetic pollution and the inability to concealed installation. The characteristics of radiating cables such as uniform coverage, no signal dead angle and concealed installation have attracted more and more attention and have been widely used. At the same time, with the development of urbanization, more and more large-scale commercial buildings and large-scale hubs appear in people's lives. When people move indoors, especially when people enter large spaces such as supermarkets, shopping malls, exhibition halls and underground parking lots, due to the large area, complex spatial layout and cross-distribution of passages and corridors, it is difficult for people to quickly know their location and surrounding conditions. Therefore, people's demand for indoor location is becoming increasingly urgent.

With the rapid development of Internet of Things technology and the maturity of hardware technology, indoor location technology has attracted attention. Common indoor location technologies include Wi-Fi location, radio frequency identification (RFID) location, ultra-wideband location, Bluetooth location, infrared location, ultrasonic location, inertial navigation technology, etc. These location technologies are implemented in different ways, and each has its own advantages and disadvantages. At present, the indoor communication system and the indoor location and navigation system are two independent networks, which greatly increases the complexity and space constraints of indoor wiring and construction costs.

Such navigation technologies are relevant for: offices; production sites, factories, workshops; shopping centers; warehouses; railway stations; hospitals; metro; airports.

The patent for invention RU2685227C2 is known from the patent level, the patent holder is "MICROSOFT TECHNOLOGY LICENSE", published.

17.04.2019.

This solution describes a method and a system for determining indoor location using Wi-Fi network signals. The known solution consists in improving the accuracy of performing location determination using a zonal structure. An area is divided into several zones, and one or more signal propagation models for one or more wireless access points (APs) are generated for each zone. A set of zonal signal propagation models provides improved model fitness based on each zone. The process includes receiving a location request associated with a wireless device, selecting a target zone from several available zones of the area, and estimating the location of the wireless device based on the signal propagation model associated with the target zone or based on a location determination signature. The signal propagation model associated with the target zone is generated based on training samples observed exclusively in the target zone. The disadvantages of the known solution in this area of technology are low accuracy and a large time delay in determining the location inside the building.

Also known from the prior art is the American patent US10917869B2, patent holder "LONPROX CORP", published 02/09/2021.

This patent describes a system and method for determining the location of a mobile device indoors. In an embodiment of the system, there may be at least one positioning node (PON) that has one or more antennas. Each PON may be located at a specific location indoors and configured to transmit signals through one or more antennas.

Signals transmitted from the PON antennas may be synchronized in time and frequency. A server communicatively connected to the PON networks and storing auxiliary information including location and signal information related to the PON may transmit the auxiliary information to a mobile device. The mobile device may receive signals using the PON networks and use the auxiliary information to determine a three-dimensional position indoors based on a one-way difference in the arrival time of the signals.

The disadvantage of this solution is also low accuracy and a large time delay in determining the location inside the building.

In addition, the international application is known from the state of the art

WO2016195527A1, patent holder NAVIGATION SOLUTIONS LLC, published 08.12.2016.

This application relates to a method and system for determining the user's location indoors for subsequent navigation. The problem to which the claimed invention is directed is to create a method and system for high-precision user navigation indoors without a priori information about the structure of the building and the radio signal emitters located therein, which ensures rapid orientation in an unfamiliar space. The technical result is to increase the accuracy of determining the user's location indoors. In a preferred embodiment of the claimed invention, a method is claimed for determining the user's location indoors using an inertial measurement unit (IMU) attached to the user's foot, and a user's mobile computing device, which consists of receiving information from the IMU about the user's movement and transmitting this information via wireless communication to the user's mobile computing device.

The disadvantage of this solution is the lack of adaptive transformation, which leads to insufficient accuracy in determining the location of an object inside the premises.

ESSENCE OF THE INVENTION

The claimed technical solution proposes a new approach to determining the user's location indoors. This solution uses a recursive algorithm implemented using the sequential Monte Carlo method, which processes the received vectors of acceleration, rotation and orientation of the magnetic field, as well as the power of the radio emitter signals, resulting in the refined coordinates of the device's location (x, y), floor identifier, and the angle of rotation of the device in space relative to the vertical axis.

Thus, the technical problem is solved - the creation of a method for high-precision navigation and tracking the movements of users/objects inside a building in real time.

The technical result achieved by solving this problem is an increase in the accuracy of determining the user's location indoors.

The specified technical result is achieved by implementing a method for determining the location of a user indoors using inertial measurement devices of the user's mobile computing device, comprising the stages of:

- download a digital map of the premises to a mobile computing device, containing floor plans containing the rooms located on the floors, their geometry and radio emitters located on the floors, where each floor contains an identifier; determine the presence of radio emitter signals inside the building using the user's mobile computing device; measure the power (RSSI - Received Signal Strength Indicator) of radio emitter signals; - receive the acceleration vectors, rotation vectors of the user's mobile computing device and magnetic field orientation vectors from the inertial measurement devices of the user's computing device;

- process the received vectors of acceleration, rotation and orientation of the magnetic field, as well as the power of the radio emitter signals using a recursive algorithm implemented using the sequential Monte Carlo method, while the recursive algorithm in the digital map of the room imposes natural and artificial restrictions on the user's trajectory of movement;

- as a result of processing, they obtain the refined coordinates of the device’s location (x, y), the floor identifier, and the angle of rotation of the device in space relative to the vertical axis;

- display the user's location on a digital map in the interface of a computing device.

In a particular embodiment of the described solution, the radio emitters are Wi-Fi and/or Bluetooth signal sources.

DESCRIPTION OF DRAWINGS

The implementation of the invention will be described further in accordance with the attached drawing, which is presented to explain the essence of the invention and in no way limits the scope of the invention. The following drawing is attached to the application:

Fig. 1 illustrates a block diagram of the implementation of the claimed method.

Fig. 2 illustrates a block diagram of the positioning algorithm.

Fig. 3 illustrates a flow chart of the floor selection algorithm.

Fig. 4 illustrates a block diagram of the multi-particle filter algorithm.

DETAILED DESCRIPTION OF THE INVENTION

In the following detailed description of the embodiment of the invention, numerous implementation details are set forth in order to provide a clear understanding of the present invention. However, it will be apparent to one skilled in the art how the present invention may be used with or without these implementation details. In other instances, well-known methods, procedures, and components are not have been described in detail so as not to unnecessarily complicate the understanding of the features of the present invention.

In addition, it will be clear from the above description that the invention is not limited to the embodiment shown. Numerous possible modifications, changes, variations and substitutions, preserving the essence and form of the present invention, will be obvious to those skilled in the art.

The declared technical solution is a specialized hardware and software complex for tracking users/objects and navigating indoors based on a real-time location determination system.

Below we will describe the concepts and terms necessary for understanding this technical solution.

Radio emitter — radio signal emitter (WiFi access point, BLE beacon, BEACON beacon). Radio emitter is characterized by the following parameters: x, y — coordinates of the radio emitter, measured from the upper left corner of the map; floorld — identifier of the floor on which it is located; A, B, deviation — signal propagation parameters (these parameters are described in detail below in the logarithmic signal propagation model).

Radio emitter identifier is a character sequence that uniquely identifies the radio emitter. For WiFi and BLE emitters it is a MAC address, for a BEACON beacon it is a concatenation of its uuid, major and minor. An example of a BEACON beacon identifier: 9BA60DA0-034E-47F0-9953-ED5F5ECC33EF, 25789, 12454.

Radio measurements are measurements of signals registered on the device from a radio emitter. Radio measurements can be presented as the received signal strength (RSSI - Received Signal Strength Indicator), measured in decibel-milliwatts. Typically, signal strength values vary in the range from -100 dbm to 0 dbm.

Logarithmic model of signal propagation.

где A - средняя мощность сигнала, регистрируемая на расстоянии 1 м; ^B - коэффициент затухания сигнала. The power of the received signal decreases with distance from the radio emitter. In this case, the main model of signal propagation will be the model according to which the average power registered at a distance r from the emitter is calculated by the formula:

where A is the average signal power recorded at a distance of 1 m; ^B is the signal attenuation coefficient.

The dispersion of the power of the recorded signal is calculated using the formula: ^d

² , where d is the standard deviation of the signal power from the model value.

The inverse formula will also be useful, allowing you to estimate the distance to the radio emitter based on the measured signal strength received from it:

Inertial measurements are measurements from a three-axis accelerometer, magnetometer and gyroscope.

Digital room map - a map containing floor plans containing the rooms located on the floors, their geometry and the radio emitters located on the floors, where each floor contains an identifier used for positioning the device.

Indoor positioning system is the process of determining the location of a device inside a room layout using registered signals from radio transmitters and inertial measurements. To do this, a digital map of the room is loaded onto a mobile computing device and the registered signal strengths from known transmitters in the digital map are correlated with each other.

The result of indoor positioning is:

• universal identifier of the floor on which the device is located;

• device coordinates (x, y).

Floor collection is an indexed collection by which positioning is performed.

The measurement preprocessor is a filter of transmitted radio and inertial measurements, which is responsible for dividing the continuous flow of measurements into so-called time ranges of positioning. Multiparticle filter - sequential Monte Carlo method - a recursive algorithm for the numerical solution of estimation problems (filtering, smoothing), especially for nonlinear and non-Gaussian cases.

As shown in Fig. 1, the claimed method for determining the location of a user indoors using inertial measurement devices of a mobile computing device (100) consists of the following steps.

At step (101), a digital map of the premises is loaded onto the mobile computing device, containing floor plans containing the premises located on the floors, their geometry and radio emitters located on the floors, wherein each floor contains an identifier

Next, at step (102), the presence of radio emitter signals inside the building is determined using the user's mobile computing device. In this case, the radio emitters are Wi-Fi and/or Bluetooth signal sources.

At step (103), the power (RSSI - Received Signal Strength Indicator) of the radio emitter signals is measured. After that, at step (104), the acceleration vectors, rotation of the user's mobile computing device and orientation of the inertial measuring field of the user's computing device are obtained.

The received vectors of acceleration, rotation and orientation of the magnetic field, as well as the power of the radio emitter signals are processed using a recursive algorithm implemented using the sequential Monte Carlo method at stage (105). In this case, the recursive algorithm in the digital map of the room imposes natural and artificial restrictions on the user's movement trajectory.

Natural limitations are understood as such limitations as: walls, columns and other real objects inside the premises. Artificial limitations are the so-called "barriers": invisible to the user objects of the digital map in the form of closed polygons, which serve as no-positioning zones. These may include areas outside the building.

At stage (106), the refined coordinates of the device location (x, y), the floor identifier, the angle of rotation of the device in space relative to the vertical axis are obtained based on the processing results, and the location is displayed. user on the digital map in the interface of the computing device at step (107).

In addition, the method for determining the location of a user indoors using inertial measurement devices of the user's mobile device includes the following algorithms:

Floor selection algorithm (see Fig. 3):

1. For each floor ^L of the digital map of the premises we accumulate the following signal parameters:

• the total number of measurements received from radio emitters from floor ^L over the last ^N seconds;

• total rssi of measurements received from radio emitters from floor ^L over the last ^N sec;

• total parameter A from radio emitters that sent a signal from floor ^L over the last ^N seconds.

2. At the input, the algorithm at each moment of time receives a floor-by-floor list of visible radio signals in the current positioning window. For each floor from the list, values are added to the corresponding parameter accumulators from point 1.

3. For each active floor, an evaluation function is calculated that characterizes the probability of the device being on it (the value of the evaluation function for inactive floors is not defined):

где — радио-излучатель, расположенный на этаже ^L от которого был

зарегистрирован сигнал мощностью

будет иметь вид:

где

в произвольный момент времени используются аккумуляторы параметров для соответствующего этажа. Let us assume that in the last seconds ^N measurements have been received for a floor from radio emitters located on that floor. Let us denote these measurements as

where is the radio emitter located on the floor ^L from which it was

signal strength registered

will look like:

Where

at any given moment in time, the parameter accumulators for the corresponding floor are used.

4. Then the active floors are ranked in descending order of the evaluation function. The algorithm returns the resulting ordered list of active floors. The first element of the list will eventually become the floor that will be defined as the current floor of the device location.

Multi-particle filter algorithm (see Fig. 4):

этаже, — вес в диапазоне — направление (азимутальный угол).

The algorithm uses a system of particles and their weight coefficients. Each particle is a vector - the coordinates of the particle on

floor, - weight in the range - direction (azimuth angle).

значение 1е-8) и мертвой в противном случае. A particle is called alive if its weight is greater than a certain (current

value 1e-8) and dead otherwise.

(текущее значение равно 1000). Система частиц изменяется итеративно в соответствии со следующим алгоритмом: The number of particles is fixed and described by a constant

(the current value is 1000). The particle system is modified iteratively according to the following algorithm:

1 . Sampling a particle on a floor, if necessary.

секунд (текущее значение 45), либо если сэмплирование еще не проводилось. Данный шаг заключается в том, что частицы разбрасываются случайным образом с условием, чтобы их координаты оставались в рамках геометрии этажа. Угол устанавливается случайным образом в диапазоне [-180, 180]. Вес всех частиц полагается равным (в сумме он должен составлять 1.0). Sampling criterion - if more than

seconds (current value is 45), or if sampling has not been performed yet. This step consists of randomly scattering particles with the condition that their coordinates remain within the floor geometry. The angle is set randomly in the range [-180, 180]. The weight of all particles is assumed to be equal (in total it should be 1.0).

2. Move the particles taking into account the number, length and direction of the detected steps, as well as taking into account the positional measurement.

At this step, only the position of the particles and their angle are changed. If as a result, some particle goes beyond the floor geometry, then it remains in the same place, and its angle changes randomly in the range [-180, 180].

The positional dimension (if present) is the center of attraction of the particles. Each particle moves in the direction of the positional dimension proportionally to the ratio of the radii of the indoor solution and the radius of the positional dimension. The positional dimension must first be projected on the geometry of the floor in order to avoid (reduce the probability) of the particle going beyond the geometry of the floor during such a displacement.

сэмплировать частицы на этаже заново (см. шаг 1). 3. Determine the number of living particles. If the number of living particles has dropped below the permissible limit (the current value is 100), then

resample the particles on the floor (see step 1).

4. We accumulate signals from radio emitters, performing preliminary filtering of “bad” radio emitters.

Filtering algorithm:

где d — среднеквадратическое отклонение силы сигнала от модельного значения, a ^D В — коэффициент затухания сигнала для р рааддииоо--ииззллууччааттеелляя.. Если отношение превышает допустимый порог

(текущее значение 1.5), то такой сигнал отбрасывается. Calculate the ratio for a radio emitter

where d is the standard deviation of the signal strength from the model value, and ^D B is the signal attenuation coefficient for p raaddiiooo--iiizzllluuchchaatteellya.. If the ratio exceeds the permissible threshold

(current value 1.5), then such a signal is discarded.

миллисекунд (текущее значение 1000) с момента предыдущего обновления весов частиц, то перейти к шагу 11. В противном случае, установить время обновления частиц на текущее и перейти к шагу 6. 5. If less than

milliseconds (current value 1000) since the previous particle weight update, then go to step 11. Otherwise, set the particle update time to the current one and go to step 6.

текущее значение 3), то перейти к шагу 10. 6. If the number of current visible radio emitters is not enough to carry out the mutation (constant

current value 3), then go to step 10.

7. Mutate several particles. The number of particles to mutate is set by a constant (current value 50).

The mutation algorithm can be described by the following pseudocode:

Repeat once:

• select a random particle; its coordinates and angle are reinitialized as in sampling (see step 1);

• the weight is re-initialized with the value

ближайший к местоположению радио-излучатель в текущем окне позиционирования (расстояние до радио-излучателей оценивается по логарифмической формуле распространения сигнала). 9. Сэмплировать (текущее значение равно 10) частиц вокруг центра

сэмплирования. 8. Determine the sampling center. The sampling center is

the closest radio emitter to the location in the current positioning window (the distance to radio emitters is estimated using the logarithmic signal propagation formula). 9. Sample (current value is 10) particles around the center

sampling.

раз: The algorithm for sampling around the center can be described by the following pseudocode: repeat

once:

распределению со средним в центре сэмплирования и дисперсией равной

текущее значение 5.0); • select a random particle; - coordinates are initialized randomly according to the Gaussian

distribution with a mean at the sampling center and a variance equal to

current value 5.0);

• the angle is initialized to a random value in the range [-180, 180].

• the weight is re-initialized with the value

- сигнал в dBm от радио-излучателя

10. Correction of particle weights. At this step, the particle weights are re-evaluated using the radio signal vector from the current positioning window:

- signal in dBm from the radio emitter

вес каждой частицы умножается на функцию правдоподобия - вероятность того, что, находясь в данной точке устройство будет принимать сигнал

от излучателя

Она рассчитывается по нормальному распределению следующим образом:

где

модельный сигнал от излучателя

получаемый по логарифмической формуле распространения сигнала - среднеквадратическое

отклонение силы сигнала от модельного значения, вычисленное для радиоизлучателя

Веса всех частиц нормируются таким образом, чтобы в сумме они составляли 1.0. Correction algorithm: For each index

the weight of each particle is multiplied by the likelihood function - the probability that, being at a given point, the device will receive a signal

from the emitter

It is calculated according to the normal distribution as follows:

Where

model signal from the emitter

obtained by the logarithmic formula of signal propagation - root mean square

deviation of signal strength from the model value calculated for a radio transmitter

The weights of all particles are normalized so that they add up to 1.0.

11. Resampling. After several steps of the correction procedure, the weights of particles corresponding to erroneous hypotheses may become close to zero. Such particles do not contribute to the final estimate of the device position. The resampling procedure allows redistribution of the high-power resources by discarding particles with low weights and duplicating particles with high weights. The method consists of several steps:

(текущее значение

Nr = 600). Если критерий не выполняется, то ресэмплинг частиц на данной итерации не производится. • The first step is to check the resampling criterion. To do this, the sum of the squares of the weights of all particles is calculated. The resampling criterion is met if this sum is greater than

(current value

Nr = 600). If the criterion is not met, then particle resampling is not performed at this iteration.

If the resampling criterion is met, a cumulative distribution function is constructed based on the particles and their weights.

вычисляются частичные суммы:

таким образом, что

For each particle

partial sums are calculated:

in such a way that

Then a uniformly distributed random variable is generated

Based on the value that the random variable has taken,

i G selects the minimum index such that:

i

• The particle with index is copied into a new particle array. This procedure is repeated N times.

• During the resampling procedure, particles with low weights are removed and particles with higher weights are duplicated (proportionally to their weight). For this reason, at the end of resampling, the weights of all particles are equalized:

Below is the positioning algorithm (see Fig. 2):

1. Transfer inertial and radio measurements to the measurement preprocessor. 2. Request the next positioning time range from the measurement preprocessor: if there is a positioning time range, then go to step 3; otherwise, go to step 13.

3. Distribute all radio measurements of the current positioning window by floors.

4. Based on the radio measurements of the current positioning window, determine the list of active floors in order of decreasing probability (see Floor Selection Algorithm above): if the list of active floors is not empty, go to step 5; otherwise, reset the last calculated position and go to step 12.

5. Identify all active floors in the floors collection. This way we prevent active floors from being evicted from the cache if it is full.

6. Pass the inertial measurements in the current positioning window to the inertial measurements handler. Determine the user step set and the position measurement (if any).

7. For each active floor, select the multiparticle filter corresponding to this floor and determine the possible position of the device on this floor by transmitting to the multiparticle filter information about the floor, a set of radio measurements corresponding to this floor, the number of steps made by the user, and a corrective positional measurement (see the Multiparticle Filter Algorithm above).

8. Select the first active floor L obtained in step 4 (the most probable floor where the device is located) and take the xy-coordinates of the device on this floor (calculated by the corresponding multiparticle filter in the previous step).

9. Refine the position of the device taking into account the previous position and speed.

10. Find the projection of the device position onto the currently selected floor (the closest floor geometry point to the found position).

11 . Set the last calculated position as the result obtained in the previous step.

12. Delete the current positioning time range.

13. Return the last calculated position. Go to step 2. The declared technical solution provides a new opportunity to increase the accuracy of determining the user's location indoors.

In these application materials, a preferred disclosure of the implementation of the claimed technical solution was presented, which should not be used as limiting other, particular embodiments of its implementation that do not go beyond the requested scope of legal protection and are obvious to specialists in the relevant field of technology.

Claims

Invention formula 1. A method for determining the location of a user indoors using inertial measurement devices of the user's mobile computing device, comprising the steps of: - download to a mobile computing device a digital map of the premises containing floor plans containing the premises located on the floors, their geometry and radio emitters located on the floors, with each floor containing an identifier; - determine the presence of radio emitter signals inside the building using the user's mobile computing device; measure the RSSI (Received Signal Strength Indicator) power of radio emitter signals; obtain acceleration vectors, rotation of the user's mobile computing device and magnetic field orientation from the inertial measurement devices of the user's computing device; - process the received vectors of acceleration, rotation and orientation of the magnetic field, as well as the power of the radio emitter signals using a recursive algorithm implemented using the sequential Monte Carlo method, whereby the recursive algorithm in the digital map of the room imposes natural and artificial restrictions on the user's movement trajectory; as a result of the processing, obtain the refined coordinates of the device location (x, y), the floor identifier, the angle of rotation of the device in space relative to the vertical axis; - display the user's location on a digital map in the interface of a computing device. 2. The method according to item 1, characterized in that the radio emitters are Wi-Fi and/or Bluetooth signal sources.