Advanced Heuristic Drift Elimination for Indoor

2014 International Conference on Indoor Positioning and Indoor Navigation, 27th-30th October 2014
Advanced Heuristic Drift Elimination for Indoor
Pedestrian Navigation
Ho Jin Ju
Seoul National University,
Dept. of Mechanical and Aerospace
Engineering/ ASRI
Seoul 151-744, South Korea
[email protected]
Min Su Lee
Seoul National University,
Dept. of Mechanical and Aerospace
Engineering/ ASRI
Seoul 151-744, South Korea
[email protected]
Soyeon Lee
ETRI,
Positioning/Navigation Technology Research Section
Daejeon, 305-700, South Korea
[email protected]
Abstract— In this paper, we proposed Advanced Heuristic
Drift Elimination (AHDE) which can remove azimuth drift error
in indoor environments. In Pedestrian Dead Reckoning (PDR)
system, azimuth error is one of the main factors that cause
estimated position error. In order to reduce azimuth error,
several methods are used. Heuristic Drift Elimination (HDE)
algorithm proposed by Johann Borenstein shows great strength
in indoor environments. HDE assumes that generally walls and
corridors are straight and either parallel or orthogonal to each
other in man-made building. They called the typical directions of
walls and corridors as the dominant directions. HDE is corrected
if the computed azimuth angle matches the closest dominant
direction. HDE also has limitation when the pedestrian walks in
various directions because HDE can cause a new azimuth error
by matching the closed dominant direction. To overcome these
limitations, we propose AHDE which is based on INS-EKFZUPT (IEZ) by using foot-mounted IMU. The algorithm consists
with the following two steps. First, it determines whether a
pedestrian is walking straight forward or not. If a pedestrian is
not walking straight forward, the algorithm estimates the biases
of accelerometers and gyroscopes by Zero velocity UPdaTe
(ZUPT) method. However if the pedestrian is walking straight
forward, the algorithm determines whether the pedestrian is
walking along the dominant direction or not. When it is
determined that pedestrian is walking along the dominant
direction, the algorithm corrects the computed azimuth angle to
the closest dominant direction. When it is determined that the
pedestrian is not walking along the dominant direction but
walking straight with no change in azimuth, AHDE applies a
correction to the gyro output which contains the bias error.
Experimental results show that the accuracy of AHDE is
improved compared to HDE and the algorithm is a powerful
method which can reduce the azimuth error in complex motion.
Keywords— heuristic drift elimination; pedestrian deadreckoning; indoor navigation; dominant direction; zero velocity
update
Chan Gook Park
Seoul National University
Dept. of Mechanical and Aerospace
Engineering/ ASRI
Seoul 151-744, South Korea
[email protected]
Sangjoon Park
ETRI,
Positioning/Navigation Technology Research Section
Daejeon, 305-700, South Korea
[email protected]
I.
INTRODUCTION
PDR is one of the Pedestrian Navigation System based on
inertial sensors do not using any infra structures. MEMS
Inertial Measurement unit (IMU) which contains three-axis
accelerometers, gyroscopes and magnetometers is used to
estimate pedestrian’s position in PDR. In recent years, MEMS
technology has allowed the production of inexpensive
lightweight and small-sized inertial sensors with low power
consumption. These are desirable properties for a portable
navigation system, but the accuracy of MEMS IMU is
relatively very low. To overcome the disadvantages, various
kinds of PDR algorithms have been developed.
PDR is a dead reckoning system having the assumption that
the position of a pedestrian is changed by step movement.
Based on that, PDR estimates the position of a pedestrian by
observing the movement of step. In PDR system, azimuth error
is one of the main factors that cause estimated position error. In
order to reduce azimuth error, several methods are proposed :
Zero Angular Rate Update (ZARU), Heuristic Drift Reduction
(HDR), Heuristic Drift Elimination (HDE) and improved
Heuristic Drift Elimination (iHDE) are developed with footmounted IMU. When the shoe contacts with the ground, the
velocity and angular rate of the shoe becomes nearly zero.
Therefore, ZARU in [1] assume that the angular rate of footmounted IMU is zero. This algorithm can reduce azimuth drift
by eliminating gyro bias. HDR and HDE algorithms are
proposed by Johann Borenstein [2-3]. The algorithm has its
strength in indoor environments but has another limitations in
under diverse situations.
HDR is based upon the premise that a person is walking
straight forward along corridors. Usually, when a pedestrian
walks straight, there is no change in azimuth. The HDR method
estimates the likelihood that the pedestrian walks straight. If
the likelihood is low, HDR has no effect, but if the likelihood is
high, HDR applies a correction to the gyro output which
2014 International Conference on Indoor Positioning and Indoor Navigation, 27th-30th October 2014
contains the bias error. HDE method not only reduces azimuth
drift, but also eliminates azimuth error nearly to zero in some
situations. HDE assume that most walls and corridors are
straight and either parallel or orthogonal to each other in manmade building. They called the typical directions of walls and
corridors as dominant directions.
HDE is similar to HDR, but HDE corrects the computed
azimuth angle unlike HDR which uses the rate of turn. HDE is
corrected in that case the computed azimuth angle matches the
closest dominant direction.
In [4], iHDE-based PDR method was proposed by A.R.
Jime´nez et al. iHDE is similar to HDE but EKF based iHDE
has an adaptive confidence estimator for the elimination of
heading error. iHDE showed great performance in indoor
environments. However, iHDE degrades considerably when a
pedestrian is not walking along dominant direction for a long
time.
To overcome these limitations, we proposes AHDE which
is based on INS-EKF-ZUPT (IEZ) by using foot-mounted IMU.
AHDE mainly consists of two steps. The first step of AHDE is
classifying the motion type. After determining the motion,
measurements are updated according to the motion. Finally,
experimental results are given showing the improved accuracy
of the algorithm compared to HDR and HDE respectively.
II.
INS-EKF-ZUPT
We use the Extended Kalman Filter (EKF)-based PDR
algorithm which proposed by Foxlin [5]. To estimate position
and attitude of an Inertial Navigation System (INS), EKFbased Zero velocity UPdaTe (ZUPT) are used. ZUPT assert
that the velocity of foot mounted IMU are nearly zero when the
foot is attached on the ground. EKF works with the 15-element
error state vector : d x = [dj , d wb , d r , d v, d a b ] . This 15-element
error state vector contains the biases of accelerometer and
gyroscopes ( d wb , d a b ), as well as, the errors of attitude,
position and velocity ( dj , d r , d v ). 5 components have 3-axis
data each.
Fig. 1 shows the main blocks in the IEZ with Advanced
Heuristic Drift Elimination (AHDE). The errors of INS can
not be estimated by ZUPT alone because it is hard to estimate
the yaw and the biases of gyroscopes associated with vertical
axis exactly. Therefore, we proposed AHDE which can
estimate the yaw and the biased of gyroscopes.
III.
walls and corridors as dominant directions. HDE is corrected
such that the computed azimuth angle matches the closest
dominant direction. HDE also has limitation when the
pedestrian walks in various directions because HDE can cause
a new azimuth error by matching the closed dominant direction.
To overcome these limitations, we proposed AHDE which
is based on INS-EKF-ZUPT by using foot-mounted IMU.
A. Pedestrian motion detection
AHDE mainly consists of two steps. The first step of
AHDE is classifying the motion of pedestrian. Mainly, 3 type
motions are classified according to the previous position data.
Fig. 2 shows the process of classifying 3 type motions : nonstraight motion, straight motion, straight motion along the
dominant direction.
First, AHDE determines whether a pedestrian is walking
straight forward or not. To determine straight motion, positions
of previous 5 steps and current step are used. Using a lot of
steps can detect straight motion accurately but also large delay
occurs in the detection. We determine motion of pedestrian by
using positions of previous 5 steps and current step. We
perform linear regression which fits a straight line based on
perpendicular offsets through the 6 positions. Fig. 3 shows the
example of the linear regression based on perpendicular offsets
by using the 6 position. Rk , Rk -1 , Rk - 2 , Rk -3 , Rk - 4 , Rk -5 are the
positions of current and previous steps. The perpendicular
distance from a line y = a + bx to position Ri is given by Eq. (1).
Figure.1 The proposed AHDE method with IEZ framework
ADVANCED HEURISTIC DRIFT ELIMINATION
In this paper, we proposed AHDE which can remove
azimuth drift error in indoor environments.
HDE show great strength in indoor environments. However,
these methods also have a limitation. HDE can correct
computed azimuth angle, but it can only be used in some
limited environments. HDE assume that most walls and
corridors are straight and either parallel or orthogonal to each
other in man-made building. They call the typical directions of
Figure.2 The flow chart of the proposed AHDE method
2014 International Conference on Indoor Positioning and Indoor Navigation, 27th-30th October 2014
thq = a + 2 pq , where pq is error variance of yaw (8)
Figure.3 Positions of previous 5 steps and current step
The sum of the squares of the perpendicular offsets is given by
Eq. (2). From the function D, partial derivatives to a and b are
obtained given by Eq. (3). Solving the Eq. (3), values (a, b) are
obtained which minimize the function D as shown by Eq. (4).
And then a best-fit line is obtained by selecting the value of b
that minimizes the function D.
di =
yi - (a + bxi )
(1)
1 + b2
k
D=
åd
2
(2)
i
i = k -5
k
¶D
2
=
( yi - (a + bxi ))(-1) = 0
2 å
¶a 1 + b i = k -5
(3)
k
k
( y - (a + bxi )) 2 (-1)(2b)
¶D
2
=
( yi - (a + bxi ))(- xi ) + å i
=0
2 å
¶b 1 + b i = k -5
(1 + b 2 ) 2
i = k -5
a = y - bx
(4)
2
b = B ± B +1
B=
k
k
1 k
1 k
( å yi 2 - ( å yi ) 2 ) - ( å xi 2 - ( å xi ) 2 )
6 i = k -5
6 i = k -5
i = k -5
i = k -5
k
2(6 xy -
å xy)
i
i
i = k -5
ì Non - straight motion, where min( D) ³ thD
(5)
í
where min( D) < thD
î Straight motion,
Minimized D means the sum of the squares of the
perpendicular offsets. Therefore we used this value to detect
the straight motion because D is the criterion of how the
pedestrian walks as given by Eq. (5).
Second, if the pedestrian is walking straight forward,
AHDE determines whether the pedestrian is walking along the
dominant direction or not. It depends on the direction of fitted
straight line and dominant direction of the building. As given
by Eq. (6, 7), the error in yaw is computed as a substraction
between the direction of fitted straight line and closest
dominant direction of the building. The error in yaw is used to
detect whether the pedestrian is walking along the dominant
direction or not as given by Eq. (8). A threshold is depends on
the error variance of yaw in EKF.
dq = q fitted line - q closest dominant direction
B. Measurement update according to the motion
3 type motions are classified by AHDE as non-straight
motion, straight motion and straight motion along the
dominant direction. In this step, after determining the
motion, measurements are updated according to the motion.
1) Non-straight motion
If a pedestrian is not walking straight forward, AHDE
does nothing. In this situation, INS errors are estimated by
IEZ. It is hard to estimate the yaw and the biases of
gyroscopes associated with vertical axis exactly, so the
error variance of yaw axis increase.
2) Straight motion
If the pedestrian is not walking along the dominant
direction but walking straight forward, AHDE applies a
correction to the gyro bias. When gyro bias remains,
although pedestrian walks straight, stride direction drifts
slowly as shown in Fig. 4. Stride direction means the
direction of movement during 1 step as given by Eq. (9)
where the kth step. As given by Eq. (10), a substraction
between the current stride direction and the 5th previous
stride direction is used as the measurement of the EKF.
Dt is the time between current step and 5th previous step.
Eq. (11) is the measurement matrix.
æ R - Ry , k -1 ö
(9)
q S ,k = arctan çç y ,k
÷÷
è Rx , k - Rx , k -1 ø
(q - q
)
d wkn = A × S ,k S ,k - 4 ,
where A is 3th rowvector of Cnb (10)
Dt
H = [ 01´3 [0 0 1] 01´3
01´3
01´3 ]
3) Straight motion along the dominant direction
If the pedestrian is walking along the dominant direction,
AHDE applies a correction to the yaw error. Eq.(6) is used as
the measurement of the EKF. Eq.(1) is the measurement
matrix
H = [[0 0 1] 01´3 01´3 01´3 01´3 ]
(11)
(6)
Figure.4 Drift of Stride direction due to gyro bias
Straight motion,
where dq ³ thq (7)
ì
í
î Straight motion(along the dominant direction), where dq < thq
(11)
2014 International Conference on Indoor Positioning and Indoor Navigation, 27th-30th October 2014
IV.
path)
EXPERIMENTAL RESULTS
For comparing the IEZ, HDE and AHDE, several tests were
performed using foot mounted IMU.
1) Walking along the corridors in Indoor
We tested algorithms in the building for a closed
360m path which has 4 dominant directions. In this case,
both HDE and AHDE have small return position errors
than IEZ.
2) Walking on the open space
We tested algorithms on the rooftop for a closed
340m path. In this case, pedestrian walks various motions.
Sometimes pedestrian walks along the dominant direction,
walks straight forward or turns. The result of IEZ has some
return position error due to the bias in the gyroscopes. The
result of HDE has large return position error because HDE
can cause a new azimuth error by matching the closed
dominant direction. Relatively, the result of AHDE has
small return position errors than IEZ and HDE.
V.
Figure.6 Tests on the open space (walking on the open space for a closed
340m path)
CONCLUTIONS
In this paper, we proposed AHDE which can remove azimuth
drift error in indoor environments. We analyzed the limitation
of HDE and IEZ and overcame the limitation by proposed
AHDE. Experimental results show that the accuracy of AHDE
is improved than using HDE and IEZ respectively. AHDE also
has limitations when pedestrian is walking on the open space a
long time. However, in general situation, it is a powerful
method which can reduce the azimuth error of the PDR system.
ACKNOWLEDGMENT
This work was supported by the IT R&D program of
MSIP/KEIT. [10044844, Development of ODM-interactive
Software Technology supporting Live-Virtual Soldier Exercises]
Figure.5 Tests in the building (walking along the corridors for a closed 360m
REFERENCES
[1]
[2]
[3]
[4]
[5]
S. Rajagopal, “Personal dead reckoning system with shoe mounted
inertial sensors,” In Master of Science Thesis, Stockholm, Sweeden,
2008, pp. 1-45.
Borenstein, Johann, Lauro Ojeda, and Surat Kwanmuang. "Heuristic
reduction of gyro drift for personnel tracking systems." Journal of
Navigation 62.01 (2009): 41-58.
Borenstein, Johann, and Lauro Ojeda. "Heuristic drift elimination for
personnel tracking systems." Journal of Navigation 63.04 (2010): 591606.
Jiménez, A. R., et al. "Improved Heuristic Drift Elimination (iHDE) for
pedestrian navigation in complex buildings." Indoor Positioning and
Indoor Navigation (IPIN), 2011 International Conference on. IEEE,
2011.
E. Foxlin, “Pedestrian tracking with shoe-mounted inertial sensors,”
IEEE Computer Graphics and Applications, no. December, pp. 38–46,
2005

Download Report