GPS-free navigation based on using inertial

and odometry, data fusion and map

matching algorithm
Cite as: AIP Conference Proceedings 2029, 020062 (2018); https://doi.org/10.1063/1.5066524
Published Online: 29 October 2018

Piotr Prusaczyk, Jarosław Panasiuk, and Leszek Baranowski

ARTICLES YOU MAY BE INTERESTED IN

Comparison of complementary and Kalman filter based data fusion for attitude heading
reference system
AIP Conference Proceedings 1919, 020002 (2017); https://doi.org/10.1063/1.5018520

A low-cost GPS/INS integrated vehicle heading angle measurement system

AIP Conference Proceedings 1955, 040097 (2018); https://doi.org/10.1063/1.5033761

The concept of using the mobile robot for telemechanical wires installation in pipelines
AIP Conference Proceedings 2029, 020054 (2018); https://doi.org/10.1063/1.5066516

AIP Conference Proceedings 2029, 020062 (2018); https://doi.org/10.1063/1.5066524 2029, 020062

© 2018 Author(s).
 GPS-free navigation based on using inertial and odometry,
data fusion and map matching algorithm.
Piotr Prusaczyk1, a), Jarosław Panasiuk1, b) and Leszek Baranowski 1, c)
1
Faculty of Mechatronics & Aerospace, Military University of Technology, Urbanowicza 2, 00-908, Warsaw, PL
a)
Corresponding author: Piotr.Prusaczyk@wat.edu.pl
b)
Jaroslaw.Panasiuk@wat.edu.pl
c)
Leszek.Baranowski@wat.edu.pl

Abstract. This paper discusses the capability to create GPS-free navigation system for land vehicles, using integrated data
from inertial and odometer sensors coupled with the road map data. The data from accelerometers and gyros embedded in
low cost strapdown IMU units are combined with differential odometry data provided by the wheels’ speed sensors using
dedicated filter. The INS exponential growing errors over time can be eliminated or significantly reduced by using the Zero
Update Velocity (ZUPT) method based on a dedicated filter. The aim of the problem is to use merged data with map-
matching algorithm to accomplish mapping the computed trajectory onto the road network for determination of the position
of the vehicle in two dimensional space.

INTRODUCTION
Knowledge of actual position and velocity of the object is a crucial task in many land applications. Old times of
using the paper’s maps are gone. Nowadays GPS (Global Positioning System) is widely used for navigation purposes
for aircraft, vehicles and pedestrians because of its affordability and convenience. Unfortunately pure GPS localization
can be highly inaccurate in urban environments such as tunnels and urban canyons. In specific situations the GPS can
be jammed or turned off by the owner which are United States of America. This are the reasons that other countries
making its own alternatives navigation systems based on satellites. The final users of that systems are still dependent
on devices that fly many kilometers above their heads.

GLOBAL POSITIONING SYSTEM

Global Positioning System (GPS) use satellites to obtain current geographic location of the object equipped with
receiver on the globe. The system contains of 28 satellites that orbit the Earth which is shown on FIGURE1. The
location accuracy is from 100 meters up to few meters, and it depends on the factors that include satellite geometry,
signal blockage, atmospheric conditions and receiver quality.
The GPS is based on the time measurement of the receiving signal between satellite and receiver. Knowing the
speed of electromagnetic wave and the exact time when the signal has been send it is available to calculate the distance
between satellite and receiver. At least 4 satellites are required to obtain the position in three dimensional space. The
navigation message received from each satellite contains date, time, ephemeris and almanac data. The satellite use
atomic clock to hold precise date and time. The ephemeris is orbital information which allows the receiver to calculate
the position of the satellite. The almanac data contains information and status concerning all the satellites.

Mechatronics Systems and Materials 2018

AIP Conf. Proc. 2029, 020062-1–020062-8; https://doi.org/10.1063/1.5066524
Published by AIP Publishing. 978-0-7354-1751-9/$30.00

020062-1
 FIGURE 1 GPS constellation.[Source: NASA]

INERTIAL NAVIGATION SYSTEM

The Inertial Navigation System (INS) unlike GPS, are entirely self-contained within the object, they do not depend
on external radiation and optical information. The INS use the inertial properties of sensors mounted in the object to
proceed the navigation function. The system process the data obtained from force and inertial angular velocity
measurements. The system calculate the position and orientation change in time. Knowledge of the position and
orientation at the start of navigation is crucial for inertial navigation system to be able to continuously determinate the
vehicle position and velocity without the usage of external data. The INS consists of gyroscopes and accelerometers.
The gyroscopes can measure angular-velocity based on conservation of the angular momentum principle. Three
structurally mounted gyroscopes determine the relative orientation between the initial and present object coordinate
frame. The accelerometer measures the specific force, using sophisticated variations of the simple pendulum. The
motion of the pendulous element is related to the motion of the object upon which the accelerometer is mounted via
Newton’s second law of motion. Motion of the pendulous element is correlated with the inertial acceleration. As
FIGURE 2 shows, the first time integration of the inertial acceleration gives velocity information. The second time
integration gives the position information. [1]

FIGURE 2 Double integration process.

STRAPDOWN TECHNOLOGY
Modern systems have removed most of the mechanical complexity of platform systems, by attaching the sensor to
the body of the object. This reduces the cost, size and weight of the inertial navigation systems. The major disadvantage
is increasing computing complexity, and necessity to use sensors capable of measuring at higher rates of turn. New
applications that demand low-cost sensors for providing measurements of acceleration and angular motion push the
development of micro-machined electromechanical system sensors (MEMS). Usage of silicon as the base material
drastically reduced the size and number of elements that leads to reducing the cost. MEMS gyroscope is non-rotating

020062-2
device that use the Coriolis acceleration effect on a vibrating proof mass to detect inertial angular rotation. MEMS
accelerometer operates similar to the pendulous open-loop and force-feedback accelerometers, that are described in
[2]. The MEMS sensors are usually made of silicon. The Strapdown Inertial Navigation System can achieve very high
accuracy and high autonomy. Unfortunately the accuracy of INS system depends on the quality of the IMU sensors.
The nonlinearity, bias, drift and noise of the sensor affect on the measurements, which are integrated once and twice
for velocity and position calculation, causing the accuracy of the predicted values valid for short period of time. The
navigation signal will be divergence with the accumulation of time in the long-range time and long-movement [3][5].
For error minimalisation it is crucial to know the model of the sensor. The generalized inertial sensor model was
presented in [3]:

𝑦 = 𝑦 + 𝑏+𝑛 (1)

where 𝑦 = [ 𝑓 𝜔 ] and 𝑓 = 𝑎 + 𝑅𝑔 is the specific force vector. The vector 𝑦 is corrupted by a

slowly changing bias b = [ b b ] and measurement noise n. The symbols b b are accelerometer and
gyrometer biases. 𝑎 denotes the body frame acceleration and the 𝑔 is the gravity vector in navigation frame g =
[0 0 g ]. According to inertial sensor model the INS error state vector is:

𝛿𝑥 = 𝛿𝑝 𝛿𝑣 𝜌 𝛿𝑏 𝛿𝑏 (2)

𝛿𝑝 − position error, 𝛿𝑣 − velocity error, 𝛿𝑏 – accelerometer bias, 𝛿𝑏 –gyroscope bias, 𝜌 −estimated

angle variation
Thus, error state differential equations are [3]:

𝛿𝑝̇ = 𝛿𝑣 (3)
𝛿𝑣̇ = −[ 𝑓 ×] 𝜌 + 𝑅 𝛿𝑏 + 𝑅 𝑛 (4)
𝜌̇ = 𝑅 𝛿𝑏 + 𝑅 𝑛 (5)
𝛿𝑏̇ = 𝑛 (6)
𝛿𝑏̇ = 𝑛 (7)

qhere 𝑏 and 𝑏 are the accelerometer and gyroscope measurement noise respectively.

ODOMETRY
Another kind of localization method is dead-reckoning, wheel encoder based odometry. For land navigation,
odometry is a cost-effective and convenient method of determining the position change. The data from the motion
sensors is used to estimate change in position over time. This method is widely used in robotics[4]. In classical
approach, the distance is calculated from the angle displacement measurement of the rotating wheel on the surface
without slipping. Like for INS the knowledge of the initial position and orientation is important for determination the
actual position. The major disadvantages of the odometry are connected with the instability of the scale factor linking
the distance traveled with the measured wheel angle. This errors grows potentially with travelled distance. The errors
that come with the changing environmental conditions are called non-systematic deviation. That errors can be
generated by nonlinear surface or wheel slippery. For two-dimensional navigation the differential odometry can be
used[5]. Given a two wheeled robot, odometry estimates position (8)(9) and orientation (10), from left and right
velocities as a function of time. The velocities are calculated by counting the encoders’ signals edges in specific period
of time. Monitoring of the encoder channels can be performed by external interruptions of the microcontroller.

020062-3
 FIGURE 3 Differential odometry.

( ) ( )
𝑥(𝑡) = 𝑥(0) + ∫ ( )𝑐𝑜𝑠𝛩(𝜏)𝑑𝜏 (8)
( ) ( )
𝑦(𝑡) = 𝑦(0) + ∫ ( )𝑠𝑖𝑛𝛩(𝜏)𝑑𝜏 (9)
( ) ( )
𝛩(𝑡) = 𝛩(0) + ∫ ( )𝑑𝜏 (10)

where: VR – right wheel velocity, VL – left wheel velocity, k – wheel separation

ERROR MINIMIZATION COMBINING DIFFERENT LOCALIZATION METHODS

GPS & INS

Inertial Navigation system has high accuracy in short period of time. This is caused by integration of noise-
contaminated inertial measurements that leads to an unbounded drift. To mitigate the error drift other absolute sensor
can be used. GPS can be treated as an absolute updating sensor with a long-term stability with homogenous accuracy.
GPS combined with INS have been used intensively in aeronautics [7] and become a standard approach in modern
navigation area. There are three main coupled integration approaches: loosely coupled integration, tight coupled
integration and ultra-tight coupled integration. All methods are based on the INS error dynamic model that uses the
GPS information to calibrate INS accumulation error with dedicated navigation filters. Kalman filter are commonly
used as a standard data fusion method. [8]

020062-4
 Acceleration, INS INS error corrections
IMU data Angular-velocity computation

Position, Velocity

Position, Velocity Navigation Estimated

GPS data Position, Velocity
Fusion Filter
FIGURE 4 Block diagram of example GPS/INS integration method.

INS & ODOMETRY

Dead reckoning navigation estimates a relative position from the initial starting point information. As it was written
earlier, it uses an inertial measurement unit or a control variable, such as a wheel encoder and so there is no necessity
to depend on external signals. Simplicity, low cost, and easier time estimating the position in real time compared to
absolute positioning (GPS) are big advantages of dead reckoning methods. In odometry, position and yaw angle of
the travelling mobile robot can be estimated by encoders attached to the robot’s wheels. Unfortunately, odometry
generates unbounded errors because of slippage, mismatches in the system parameters, measurements inaccuracies,
and noise from the encoder signals. These errors accumulates over travelled distance. The INS, provides the position
and orientation at high rate with high short-term precision but low long-term precision. By the double integrate
process, low frequency noise and sensor biases are amplified. Standalone working odometry and INS generates
accumulated errors over long periods of time. In the article [9] authors combine odometry and INS in order to reduce
the accumulated errors of those navigation methods. Data fusion process and position and orientation estimation was
performed by designed Kalman filter. When the object is stationary the inertial, compass data estimates the bias of the
inertial. In moving state inertial data is used for calculation velocity and orientation corrected by state estimation
kalman filter that uses encoder data. [9]

ZUPT

Zero velocity update is effective technique of error suppression and compensation for high-precision inertial
positioning and orientation system (INS). When the object is in standstill state (zero speed) the velocity observation
is set to zero, and the velocity and position of the inertial navigation systems are corrected. The detection of the
stopping time intervals of INS is very crucial for this method. Bad precision of navigation will bring the mistakenly
detected stationary state. There are several types of zero-velocity detectors, like acceleration moving variance detector,
acceleration magnitude detector, and angular rate detector. [6][10]

Orientacja
Dane z AHRS

Przyspieszenie INS Korekcja

Dane z IMU Prędkoć kątowa ZUPT
computation

Position, Velocity

Obliczana
Dane z Prędkosć Navigation Orientacja
Orientacja Prędkosć
Odometrii Fusion Filter Pozycja

FIGURE 5 Block diagram of example of INS/ODOMETRY method.

MAP MATCHING TECHNIQUE FOR MAINTAINING GLOBAL POSITION

GPS systems or even combined methods of navigation do not always provide the location of a vehicle in road map
with the required accuracy. This is caused by various error sources. Many methods were presented to reduce these
errors. Another approach in reducing the navigation error is Map Matching algorithm. In this technique the estimated
position of the object in map is computed by comparison of the real position and the road network of digital map. [13]
There are multiple map matching algorithms, which can be divided to geometric and topological algorithms.

020062-5
Geometric information is used in a geometric map matching algorithms. Point-to-point map matching algorithm uses
GPS coordinates that are matched to the nearest shape point of a road segment. This method can be easily and fast
implemented. Point-to-curve map matching algorithm uses coordinates that are matched to the closest curve in the
road network. The geometry of the road network is used in topological algorithm. In this method the links that have
no connectivity with previous matched road network are exluded from the checking algorithm.[14]

CONCEPTION
In order to downgrade the dependency on the GPS signal, other navigation methods need to be used.
The independent from the external radiation and optical information, dead reckoning methods, generates accumulated
errors, when working separately. In paper [9] and [11] authors perform tests that combine the INS with the odometry
and confirm that position estimation error can be significantly reduced. Nevertheless, remaining errors need to be
suppressed. The map-matching algorithm is very promising in correcting actual calculated position by attaching the
position to the most probable place on the digital road network map. The authors propose different approach to
navigation problem.
Navigation is used in order to reach some specific destination in the world, moving along the route calculated by
the navigation algorithm (figure 6). The route is represented by a succession of road centerline points. The reference
trajectory (figure 7) is generated from the route, constrained by geometric and dynamic limitations of the vehicle,
using mathematical models of the vehicle.

FIGURE 6 Calculated path.

FIGURE 7 Ideal trajectory generated from calculated path.

The trajectory can be described as continuous sequence of reachable configurations q=(𝑥, 𝑦, 𝛩, 𝜑) defined by
Wheeled Rolling System’s (figure 9) Centre of Gravity coordinates (𝑥, 𝑦), Centre of Gravity orientation (𝛩) and
curvature of the path (𝑘). Reaching destination point (𝑥 , 𝑦 , 𝛩 , 𝜑 ) is possible performing that reference trajectory
from start point (𝑥 , 𝑦 , 𝛩 , 𝜑 ). [17]

020062-6
 FIGURE 8 Global X and Y coordinates depending on covered distance of ideal trajectory.

FIGURE 9 Wheeled Rolling System model

The real trajectory of the vehicle is obtained by the combined dead reckoning methods like inertial navigation
system and wheel speed sensors (rotational encoder). The inertial navigation system equipped with the magnitude
sensor, creates the attitude and heading reference system (AHRS). There are several approaches to velocity and
distance measuring using odometry that have been proposed [15]. Using high accuracy optic encoders, the current
velocity and travelled distance can be obtained. The odometry can also be used as a trigger to Zero Velocity update
method for the inertial measurement unit calibration.

FIGURE 10 The deviation of the trajectory (blue line), reference (real) trajectory (black line).

Using dead reckoning methods, the errors of the position increase on each meter while driving along generated
trajectory. Thus the false trajectory appear and false position coordinates are the calculated.

FIGURE 11 The correction of the deviation using intersection matching method.

020062-7
 The real trajectory compared with the reference one gives the deviation that should be decreased in navigation
process. The conception is based on natural landmarks, which for the road can be curvature, intersections and etc.
Those characteristic points are used for trajectory matching and trajectory progress detection.

CONCLUSION
In this paper, different types of navigation strategies were described as well as position deviation minimization
using different navigation techniques. Most of the navigation techniques using GPS satellite signal for positioning
process. Some of them are assisted with odometry and inertial systems for increasing the accuracy in short period of
time. The next stage can be the development of navigation systems that operate independently of the GPS signal.
In these techniques, odometry, inertial and the matching algorithms systems play a crucial role. The authors propose
the conception of a navigation system based on a trajectory generated from digitized road network map. The real
trajectory is compared with the generated ideal trajectory in order to calculate the deviation that can be used in the
navigation process. In further studies, the real time measuring platform will be developed and adapted in car vehicle.

REFERENCES
1. K.R. Britting, Inertial Navigation Systems Analysis (ARTECH HOUSE, Norwood, 2010).
2. D. Titterton and J. Weston, Strapdown Inertial Navigation Technology 2nd Edition, The Institution of Engineering
and Technology, London, 2004.
3. S.Amin and M.Reaz and S.Nasir and M.Bhuian and M.Ali, A Novel Vehicle Stationary Detection Utilizing Map
Matching and IMU Sensors, The Scientific World Journal, Malaysia, 2014
4. K.Besseghieur and W.Kaczmarek and J.Panasiuk and P.Prusaczyk, Formation control of mobile robots under
ROS, Proceedings of the 23th International Conference – Engineering Mechanics, Svratka, 2017.
5. K.Besseghieur and W.Kaczmarek and J.Panasiuk, Multi-robot Control via Smart Phone and Navigation in Robot
Operating System, ‘Problemy Mechatroniki. Uzbrojenie, lotnictwo, inżynieria bezpieczeństwa’, 2017
6. F. Liu and S.Cao and Y. Chen and X. Su, GPS/SINS/MC Integrated Navigation Algorithm Research Based on
Zero Velocity Update, Proceedings of the 36th Chinese Control Conference, Dalian, 2017.
7. M. Spangenberg and V. Calmettes and J.Y. Toutneret, Fusion of GPS, INS and odometric data for automotive
navigation, 15th European Signal Processing Conference, Poznań, 2007.
8. H.J. Chu and G.J. Tsai and K.W. Chiang and T.T. Duong, GPS/MEMS INS Data Fusion and Map Matching in
Urban Areas. Sensors, 2013.
9. B.S. Cho and W.S. Moon and W.J. Seo and W.R. Baek, A dead reckoning localization system for mobile robots
using inertial sensors and wheel revolution encoding, Journal of Mechanical Science and Technology, Springer,
2011.
10. L. Xiaofang and M. Yuliang and X.Ling and C. Jiabin and S. Chunlei, Applications of Zero-velocity Detector
and Kalman Filter in Zero Velocity Update for Inertial Navigation System. IEEE Chineese Guidance, Navigation
and Control Conference, Yantai, 2014.
11. Y. Wu, Versatile Land Navigation Using Inertial Sensors and Odometry: Self-calibration, In-motion Alignment
and Positioning. Inertial Sensors and Systems – Symposium Gyro Technology, Karlsruhe, 2014.
12. M.A. Quddus and W.Y. Ochieng and L. Zhao and R.B. Noland, A general map matching algorithm for transport
telematics applications, GPS Solutions, Springer-Verlag, 2003, pp 157-167.
13. X. Kang and W. Wu, An improved Map Matching Algorithm, Mechanics and Materials, Switzeland, 2013,
pp 2947-2952.
14. W. Cho and E. Choi, A GPS Trajectory Map-Matching Mechanisms with DTG Big Data on the HBase System,
International Conference on Big Data Applications and Services, At Jeju, 2015.
15. P. Merriaux and Y. Dupuis and P. Vasseur and X. Savatier, Wheel Odometry-based Car Localization and
Tracking on Vectorial Map, International Conference on Intelligent Transportation Systems, Qingdao, 2014
16. P. Bonnifait and P.Bouron and D.Meizel and P.Crubille, Dynamic Localization of Car-like Vehicles using Data
Fusion of Redundant ABS Sensors, The Journal of Navigation, The Royal Institute of Navigation, 2003.
17. J. Daniel and A. Birouche and J.P. Lauffenburger and M.Basset, Navigation-based constrained trajectory
generation for advanced driver assistance systems, Int. J. Vehicle Autonomous Systems, Inderscience
Publishers, 2011, pp.269-296.

020062-8