=Paper=
{{Paper
|id=Vol-2212/paper31
|storemode=property
|title=Method monitoring of movement in the task of indoor navigation
|pdfUrl=https://ceur-ws.org/Vol-2212/paper31.pdf
|volume=Vol-2212
|authors=Mikhail Osipov,Vladislav Andreev
}}
==Method monitoring of movement in the task of indoor navigation ==
https://ceur-ws.org/Vol-2212/paper31.pdf
Method monitoring of movement in the task of indoor
navigation
M P Osipov1 and V S Andreev1
1
Lobachevsky State University of Nizhni Novgorod, Prospekt Gagarina 23, Nizhni Novgorod,
Russia, 603950
Abstract. The paper considers ways to minimize positioning errors by using information obtained
with the help of MEMS sensors available to the user. An approach for correcting a positioning
error by using information about a floor plan of a building is proposed. A set of methods is
presented to ensure monitoring of the user's movement in the task of navigation.
1. Inroduction
Inner structure of airports, railway stations, shopping and recreational centers have complex configuration.
Present-day buildings represent a huge complex of floors with staircases, corridors and rooms. Navigation
in such buildings often appears a challenging task. For instance passengers can encounter difficulties
trying to find way to the needed office in a huge business or shopping center, determine evacuation routes
and arrange salvage actions in case of emergency etc. Movement monitoring is essential for providing
users with various kinds of notifications. For example, informing about nearest shops purchase incentives
or mobile guide service in a museum.
Usage of global positioning navigation systems such as GPS-GLONASS inside buildings is rather
problematic subject to concrete walls and partitions which bring signal level to nothing. A range of visual
landmarks on the walls are traditional navigation solution for such buildings. But the draw-back of such
an approach is information overload and complexity of analysis of the received information. Technology
companies all over the world work over automatization of user location search in enclosed spaces.
There are several approaches to solving this task based on using: different data communication
networks (Bluetooth, Wi-Fi, FM-ether waves, UWB); the Earth’s magnetic field; RFID-tags; QR codes;
MEMS sensors etc. [1] However, the mentioned approaches either lack accuracy and reliability or involve
complexity of setting the corresponding infrastructure and its maintenance or require significant
investments.
2. Problem Statement
The aim of this paper is to develop an approach of a standalone inertial navigation based on using
(MEMS) and information about building layout. This approach is the "cheapest" among the existing
navigation technologies, but positioning accuracy index is not so high. MEMS installed on mobile devices
do not show high accuracy. Such MEMS positioning error value eventually increases and comes out at
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)
Data Science
M P Osipov and V S Andreev
10% of the distance covered, that makes them unreliable for navigation purposes. Positioning errors in
complex configuration of corridors and rooms can bring about incorrect evacuation routes determination
in case of emergency. The paper puts forward algorithms ensuring positioning accuracy and reliability
increase.
3. Inertial navigation methods
Usage of micromechanical inertial sensors allows to perform movement tracking along the route without
additional installations inside the buildings. MEMS include 3 types of sensors: accelerometer (measures
acceleration along the axis), gyroscope (measures angular rate along the axis), gaussmeter (device for
earth magnetic field characteristics measuring). Accelerometer is used for counting number of steps made
by the user. Gyroscope and gaussmeter are used to determine the step direction.
However, the algorithms based on movement sensors show some drawbacks which need to be levelled
down in course of algorithm execution. The low-cost gyroscopes show high displacement errors which
constantly accumulate during turning angle. Geomagnetic disturbances can cause compass errors.
It appears impossible to build a universal model of human movement due to individual peculiarities
(pace, parameters of a person) which lead to glitches of step detection and consequently to incorrect user's
position determination.
Traditional approach to step detection according to accelerometer readings include 2 stages. Primarily
accelerometer readings filtration is performed by means of a low-pass filter in oreder to decrease the noise
impact. Further the task reduces to finding signal extreme values (maximum and minimum) within a
certain time frame. Various methods of glitches excluding are used therewith.
Algorithms executing on this principle are described in the works [2-5]. It was experimentally
determined that the three-stage algorithm shows the most reliable results in step detection among the
described algorithms.
In this case MEMS sensors are placed onto the user’s feet. The algorithm essentials are in catching the
user's foot motion path in the course of making a step. Human step cycle comprises three phases: phase of
a stroke, phase of heel contact, resting phase. Hence step detecting can be performed by means of the
phase determination. A certain number of step detecting glitches occurred during the three-phase
algorithm testing.
Therefore it was decided to improve the existing algorithm towards increasing severity of the step
detecting criterion. Additionally, the algorithm should take into account physical peculiarities of the user
and adjust the threshold of detection in the course of execution.
Modification of the three-phase algorithm consists in the usage of a configurable phase pattern on each
stage of step phase determination, formed on the grounds of information about previous user’s step. At the
moment of the first step phase determination additional verification is started, specifically each new point
is compared with the existing pattern with account for possible error considered as input parameter.
If the point does not fall within the predefined locality of the pattern point the step is considered not
detected and flags of the determined phases are dropped. After the third phase is determined the step is
considered detected.
It is worth noting that the predefined locality of the acceleration pattern varies for each phase, as the
behavior of acceleration function on each phase is different. The pattern is formed as arithmetic average of
each point of the current step with the already existing step; the pattern is initiated by means of the first
detected step.
The algorithm execution is depicted on figure 1.
The conducted experiments showed that the proposed modification of the three phase algorithm makes
it possible to increase the accuracy of the step determination by 20% in comparison with the classical
approach.
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 223
Data Science
M P Osipov and V S Andreev
Figure 1. Three-phase algorithm modification.
4. Movement monitoring with the use of building floor plan
The major drawback of navigation methods based on MEMS sensors readings is the accumulation of
measuring error in the course of movement. Using the information about digital floor plan of the building
allows compensating the error accumulation. Distributed database management system is used for storing
a digital floor plan and is based on an object-oriented approach to the representation and processing of
complex structured spatially distributed information [6]. Floor plan contains information about the
building structure in the form of connectivity graph of rooms, corridors, staircases, elevators etc. [7].
Connectivity graph allows predefining all the expectable paths of user’s movement, out of which the
optimal path [8] is selected with account of specified restrictions [9]. In the course of project
implementation the algorithm was developed that allows making correction of MEMS sensors positioning
error based on the information about expectable paths of user’s movement. After sensors detect users
turning movement the search of the nearest turn on the floor plan in the specified direction is performed
[10]. The found turn makes it possible to correct positioning. Therefore the accumulated MEMS sensors
measuring error is reduced [11]. The algorithm executions result is displayed on figure 2.
Figure 2. Results of inertial navigation algorithms with movement monitoring and without it.
Due to imperfection of readings of micromechanical inertial sensors some false turns can occur. In
such a case user’s movement path can deviate considerably. To solve this problem it is recommended to
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 224
Data Science
M P Osipov and V S Andreev
use not only the main movement path but also alternative ones in the floor plan configuration when user
reaches the turn (crossroads). Each alternative movement path has a priority parameter, which is going to
be decreased in the course of further guiding along the route, if the determined by inertial sensors
expected users position does not correspond to the floor plan configuration. Paths with the lowest priority
are eliminated. Path with the highest priority gets current. The algorithm allows determining the actual
user’s movement path in a complex environment of branched rooms and corridors configuration.
Algorithm of movement paths prioritization is based on two principles:
• Principle of direction coincidence.
• Principle of configuration coincidence.
Principle of direction coincidence is based on the following statement: if the current path is true, the
current vector of path should be co-directed with the current path vector, received by means of standalone
navigation.
Principle of configuration affirms: if the current step made by a user does not belong to any of the
current path sections, the route is considered incorrect as the points not belonging to path sections belong
to different physical barriers in the process of movement (wall sections).
Let us consider how the algorithm uses the mentioned principles. The algorithm is based on the idea of
random process, basically on the Markov Chain model. A number is assigned to each movement path.
Every such number is referred to a probability which shows that at a certain time point t user is on the
current section (or current movement path), the probability is selected in such a way that the norm axiom
should be true for a random value, namely the sum of the probabilities for each number should be equal to
1. And the conclusion from this is that at each time point t the system can be described as a discrete
random value. It should be noted that the maximum amount of paths M that are examined at each time
point t equals to 6. The number was chosen based on the two heuristics:
• Crossings dividing the path of movement by two usually prevail in each building configuration.
• Difference in any two paths configuration is possible to detect after the first crossing, as lengths of
corridors are widely diverging.
Figure 3. Diagram of movement paths configuration.
Figure 3 shows the standard situation, the path is divided by two and path 1 is much different from the
path 2 according to its configuration (at least according to the length of segments next to the crossing)
By this means at each time point there is a discrete random parameter which takes a value of ,
and shows a degree of confidence in the i-th path. Probabilities for such random value are calculated
according to the formula:
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 225
Data Science
M P Osipov and V S Andreev
(1)
where f – function determiming the distance from a point to a vector
Threat the total probability at each examined path or the probability on basis of which the decision
about the chosen path is made is calculated according to the formula (in accordance with the definition of
random process):
, (2)
, (3)
The equation (3) is introduced for normalization of the obtained values in order to keep the property of
normalization of random value.
It is necessary do define the parameters of the indicated above formula, namely a, b, as parameters of
weighted sum of the two detached principles and parameters of random allocation of functions F, G. As
far as the functions f, g show the deviation from the actual value mathematical expectation were
considered equal to 0. Values of quadratic averages were picked based on the heuristic ideas specifically
for the function G the quadratic average equals 0.6, as if the angle deviation more than 45 degrees it may
be concluded that the selected direction is incorrect and the value of distribution density should be less
than 0.1.
Judgments of that kind are applicable to the function of configuration error as well, it is accepted that
the average corridor size of a large building is more than 2 meters, thus every two points the error for
which is more than two meters should take the function value less than 0.1. Based on the above stated
judgments the following distribution densities were chosen . As the principle
of configuration coincidence is more prominent in comparison with the principle of directions coincidence
it was concluded that parameter а = 3, and parameter b = 1, that does not come into conflict with the
probability definition because in case of the selected parameters .
Consequently the algorithm of prioritization sets the priority to each examined path thereafter a
decision about the current path is made. In case of the path change the path is recalculated from the
current point to the endpoint.
5. Conclusion
The paper introduces modification of three-phase algorithm that allows increasing the step detection
accuracy in the task of navigation. It considers the method to improve user’s positioning reliability by
using information about a floor plan of a building. The executed experiments proved the efficiency of
proposed algorithms.
6. References
[1] Kim J, Jang H, Hwang D and Park C A 2004 Step, Stride and Heading Determination for the
Pedestrian Navigation System Journal of Global Positioning Systems 3(1-2) 273-279 DOI:
10.5081/jgps.3.1.273
[2] Muset B and Emerich S 2012 Distance Measuring using Accelerometer and Gyroscope Sensors
Carpathian Journal of Electronic and Computer Engineering 5(1) 83-86
[3] Khan M I 2013 Design and Development of Indoor Positioning System: For Portable Devices (LAP
LAMBERT Academic Publishing) p 108
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 226
Data Science
M P Osipov and V S Andreev
[4] Lukianto C and Sternberg H 2011 Overview of Current Indoor Navigation Techniques and
Implementation Studies (Access mode: http://www.fig.net/resources/proceedings/fig_proceedings
fig2011/papers/ts09a/ts09a_lukianto_sternberg_5102.pdf)
[5] Lan K-C and Shih W-Y 2012 Estimating Step Distance Using Simple Harmonic Motion IEEE 75th
Vehicular Technology Conference (VTC Spring) 1-5 DOI: 10.1109/vetecs.2012.6239903
[6] Vasin Yu G and Yasakov Yu V 2016 Distributed database management system for integrated
processing of spatial data in a GIS Computer Optics 40(6) 919-928 DOI: 10.18287/24126179-2016-
40-6-919-928
[7] Vasin Yu G, Osipov M P, Muntyan S V and Kustov E A 2015 Procedural Modeling and Interactive
3D Visualization of Objects of the Internal Structure of Buildings and Facilities Pattern Recognition
and Image Analysis 25(2) 278-280 DOI: 10.1134/s105466181502025x
[8] Kaixu L, Gianmario M, Tianyi M and Tao G 2016 Multi-floor Indoor Navigation with Geomagnetic
Field Positioning and Ant Colony Optimization Algorithm IEEE Symposium on Service-Oriented
System Engineering (SOSE) 314-323 DOI: 10.1109/SOSE.2016.18
[9] Vasin Yu G, Osipov M P, Egorov A A and Yasakov Yu V 2015 Autonomous Indoor 3D Navigation
Pattern Recognition and Image Analysis 25(3) 373-377 DOI: 10.1134/s1054661815030256
[10] Aggarwal P, Thomas D, Ojeda L and Borenstein J 2011 Map matching and heuristic elimination of
gyro drift for personal navigation systems in GPS-denied conditions Measurement Science and
Technology 22 12 DOI: 10.1088/0957-0233/22/2/02520
[11] Osipov M P and Patrushev A O 2016 Methods of location correction in the task of Autonomous
navigation in indoor spaces GraphiCon conference proceedings 417-419
Acknowledgments
This research was supported by the Russian Foundation for Basic Research, project № 16-07-01214 А.
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 227