Indoor Localization Method Based on Sequential
Motion Tracking Using Topological Path Map
YU-CHEOL LEE 1,2, (Member, IEEE), AND HYUN MYUNG 2,3, (Senior Member, IEEE)
1Intelligence and Robot System Research Group, Electronics and Telecommunications Research Institute, Daejeon 34129, South Korea 2Robotics Program, Korea Advanced Institute of Science and Technology, Daejeon 34141, South Korea
3School of Electrical Engineering, Korea Advanced Institute of Science and Technology, Daejeon 34141, South Korea
Corresponding author: Hyun Myung ([email protected])
This work was supported in part by the Institute of Information and Communications Technology Planning and Evaluation (IITP, South Korea), through the Ministry of Science and ICT, under Grant 2018-0-00205, the Development of Core Technology of Robot Task-Intelligence for Improvement of Labor Condition, and in part by the Technology Innovation Program under Grant 10076532, the Development of Embedded Directional Drilling Robot for Drilling and Exploration
through the Ministry of Trade, Industry, and Energy (MOTIE), South Korea.
ABSTRACT This paper proposes a novel indoor localization method based on sequential motion
track-ing (SMT) ustrack-ing a topological path map that can improve the shortcomtrack-ings of traditional methods ustrack-ing range-only measurement sensors. The proposed method consists of map generation and location estimation. First, in the map preparation, we present the construction method of a radio fingerprint map and the topological path map. The radio fingerprint map contains radio signals moderated by a median filter, and the topological path map includes possible path motions in the form of nodes and edges using a floorplan drawing. Second, for location estimation, fingerprint analysis and SMT methods are developed. Fingerprint analysis finds the global region based on a histogram evaluation between the radio fingerprint map and online observations, which rely on Wi-Fi. The SMT determines the optimal position on the topological path map by considering the historical motion data and the fingerprint analysis result. Finally, the experimental results show that the proposed method is robust to the uncertainty of the fingerprint analysis using the range sensors and that it can accurately track global positions with efficient computations.
INDEX TERMS Fingerprint analysis, indoor localization, range measurement sensor, sequential motion
tracking, topological path map.
I. INTRODUCTION
Currently, indoor localization technology is becoming grad-ually more significant given the increased level of demand for location-based services (LBS) capable of obtaining highly accurate physical locations of devices or people in indoor environments [1], [2]. It is important in the expanding field of LBS to include indoor navigation [3], smart-home systems [4], disaster management [5], business analytics [6], human resource management [7] and a number of other func-tions. These applications require indoor localization technol-ogy that can achieve high accuracy, broad public usability, and reliable performance to match the capabilities of outdoor GPS.
As the simplest LBS at the system level, specially designed beacons and stations can be installed in indoor spaces to
The associate editor coordinating the review of this manuscript and approving it for publication was Eyuphan Bulut.
provide reliable position information. The additional infras-tructure for LBS requires various specifications, such as ultra-wideband (UWB) [8], radio frequency identification devices (RFID) [9], barcoding technology [10], visible light [11], and acoustic signals [12], among others depending on the appli-cation. These approaches are widely used in the industrial and small business realms, such as logistics warehouses, hospitals, and factories of all sizes due to their excellent localization stability. The additional costs of the required hardware when configuring LBS, however, present a critical obstacle preventing wider public use.
For cost-effective LBS at the device level, mobile personal devices such as smartphones and wearable devices are used to estimate indoor positions by observing the radio signals of surrounding Wi-Fi [13], [14]. This approach has grown to be the most commonly used localization method in pub-lic LBS given that the wide-scale proliferation of mobile devices with wireless communication capability has made the
VOLUME 7, 2019
2169-3536 2019 IEEE. Translations and content mining are permitted for academic research only.
localization of such devices synonymous to the localization of the corresponding users. It is possible to implement a low-cost LBS system even in a pervasive network environment with existing radio communication and Wi-Fi signals without building additional infrastructure for LBS.
The fingerprint analysis is the most prevalent localization method based on Wi-Fi devices at the region-level of fin-gerprint resolution for academic and commercial localization systems [15], [16]. In the offline phase, the map-generation module should compile a radio signal map or a database with fingerprints or scene sets of received signal strength (RSS) levels for locations at a specified density for a point of interest. In the online phase, the localization module selects the location of the fingerprint having the highest similarity by matching the observed RSS readings against the radio signal map. A number of algorithms have been developed to calculate the similarity, which is expressed as a likeli-hood value. These include probabilistic methods [15], [17], artificial neural networks [18], the k-nearest neighbor (kNN) method [19], and the support vector machine (SVM) [20]. Despite advances in algorithmic techniques, however, this approach is limited in its ability to improve the accuracy beyond fingerprint-level resolutions.
An inertial-based method has also been developed with various filters to improve the accuracy of fingerprint analyses by fusing dead-reckoning data and Wi-Fi radio signals [21], [22]. This approach is becoming more popular with the advent of mobile devices equipped with accelerom-eters and gyroscope sensors. In this approach, the represen-tative methods involve the use of Kalman filters [23], infor-mation filters [24], and particle filters [25], which enable localization even in the region where there is no radio signal map between the fingerprint nodes.
However, the inertial-based method has certain techni-cal limitations, specifitechni-cally the accumulated measurement errors of the sensor and the computational burden of the algorithm [26], [27]. With regard to the first issue, filters employing a motion model with a high degree of freedom easily encounter falsely estimated locations when the cumula-tive errors of dead-reckoning measurements exceed a critical point or with heavy multipath effects of Wi-Fi radio signals in an indoor environment. Regarding the second issue, the filters associated with this method require strong computational resources to operate the complex algorithms; e.g., the particle filter should calculate iterative processes which can manage several hundreds of samples. This is a major obstacle when applying the inertial-based localization method to mobile devices given their limited computing ability.
This paper proposes an indoor localization method based on sequential motion tracking (SMT) to mitigate the short-comings of the inertial-based method using range measure-ment sensors. SMT can estimate accurate locations and track continuous trajectories by fusing topological path map and historical motion data based on fingerprint analysis results.
The novelty of SMT can resolve the incorrect local-ization problem which arises due to unstable results of
fingerprint analyses and the accumulated errors of dead-reckoning measurements, by matching the local sequential trajectories between a topological path map and historical motion observations. In addition, SMT finds the optimal loca-tion on the topological path map with relatively few compu-tational resources and relatively few hypotheses as well. It is effective for the mobile devices such as the smartphones and the wearable devices that should manage low computational complexity to expand the usability of indoor localization.
This research makes two major contributions in the areas of map generation and range-based localization. First, we define the map data and develop the map-building method required for localization in indoor environments. The map data con-sists of a radio fingerprint map and a topological path map. The radio fingerprint map for the fingerprint analysis contains basic radio information including the acquisition location, the RSS value, and the media access control (MAC) address, corresponding to the Wi-Fi device installed in the space. The topological path map for SMT stores sequential motion data consisting of the nodes and edges as motion candidates with which to connect the locations of the different finger-prints. The map-generation method can extract the node and edge data between the locations of the fingerprints using the floorplan data for the indoor space and a path-planning algorithm.
Second, we propose a new hierarchical localization frame-work with only range sensors. The localization frameframe-work consists of a fingerprint analysis and the SMT method, which work in a complementary manner to improve the accuracy of estimating locations and tracking trajectories. The fingerprint analysis finds the global region of the current location by matching Wi-Fi observations against a radio map. This allows the selection of a specific region of fingerprints to extract the candidate group of trajectories. SMT determines a certain trajectory in the resulting area of the fingerprint analysis using historical motion changes and the topological path map. It chooses the optimal trajectory and calculates the accurate location considering the motion histories.
The paper is organized as follows. SectionIIdefines the map data and explains the map-building method. SectionIII
presents the localization method, consisting of the finger-print analysis and the SMT method. SectionIVevaluates the effectiveness of the proposed method experimentally. Finally, conclusions are discussed in SectionV.
II. MAP GENERATION
A map is a key form of media which delivers spatial infor-mation with which to perform successful localization. Over the past three decades, many researchers have developed various mapping methods for indoor localization. In those studies, it was necessary to undertake simultaneous local-ization and mapping (SLAM) or concurrent mapping and localization (CML) given that the mapping and localization performances affect each other significantly. As a practical approach, spatial data annotated with acquired locations are constructed with the SLAM technology [28], [29], updated
by crowdsourcing [30], [31], and provided for the localiza-tion method in advance.
This section defines the typical formats of the radio fin-gerprint map and the topological path map. Subsequently, it explains the method used to extract the map information from spatial data including radio signals and the floorplan data according to the measured locations. First, the radio fingerprint map is obtained with a median filter, which is based on the inter-point distance, to reduce the effects of local noise caused by dynamic changes in the environment. Second, the topological path map is automatically produced based on the path-generation algorithm using the floorplan drawing and the locations of fingerprints.
A. RADIO FINGERPRINT MAP
The radio fingerprint map provides radio signal data mea-sured at an interesting point called the fingerprint, as used in the fingerprint analysis to find the region which includes the current location. Spatial data processed by SLAM or crowdsourcing are used to build the radio fingerprint map. The basic unit of the radio fingerprint map Mf is a fingerprint
node bias follows:
Mf = {bi|i = 1, . . . , B}, (1)
where Mf is defined as the group of B fingerprint nodes. Each
fingerprint node contains the location of the place (¯xi, ¯yi)
where the radio signal data are measured. Each also contains the MAC address mcjand the RSS values rssjof the
surround-ing R Wi-Fi access points, expressed as follows:
bi=(¯xi, ¯yi, ri), ri= {mcj, rssj|j = 1, . . . , R}. (2)
The MAC address is a unique identifier corresponding to the Wi-Fi device, and it can be used as an indicator to compare the current observation to the radio fingerprint map. The fingerprint analysis evaluates the RSS difference between the radio fingerprint map and the current measurement and then selects the best fingerprint node, which yields the lowest RSS difference.
The RSS values in the fingerprint node are calculated using a median filter to smooth the noise of the radio signals in the spatial data. The RSS information in the spatial data includes noise stemming from various disturbances, such as structural barriers, certain materials, and electronic facilities in the indoor environment. In particular, Wi-Fi radio signals are influenced by dynamic changes in the space, such as the movement of people or any interior remodeling taking place. Therefore, reducing the noise in the radio signal is important for an accurate fingerprint analysis, and the median filter can help moderate the effect of radio noise in the fingerprint node.
Figure1 describes the concept of evaluating RSS values
of the radio fingerprint map using the median filter. The Euclidean distance Dmrepresents the coverage region of one
fingerprint node and is predetermined by the resolution of the fingerprint analysis. To build the radio fingerprint map, Dm
is assigned as a threshold parameter to segment the spatial data into the clusters using k-d tree [32]. In the i-th cluster,
FIGURE 1. Fingerprint data as calculated by a median filter. The spatial data is divided into clusters based on geometric distance Dmusing k-d tree. Given the i -th cluster, the location of the i -th fingerprint node ( ¯xi, ¯yi) (black dot) is calculated by the middle point of the measuring points of the spatial data (gray dots). And the RSS value rssjis determined by the average of all RSS values having the same MAC address mcjin the i -th cluster data.
the middle point of the spatial data is defined as the location of
i-th fingerprint node (¯xi, ¯yi). If Q radio signals have the same
MAC addresses (∀mcq = mcj) in the i-th cluster, the RSS
value rssj is defined as the average RSS value of the spatial
data as follows: rssj= 1 Q Q X q=1 rssq, ∀mcq= mcj. (3)
Note that, the measuring point (xq, yq) corresponding to rssq
is within the distance Dmfrom the fingerprint location (¯xi, ¯yi)
because it should satisfy the clustering condition based on the threshold distance.
B. TOPOLOGICAL PATH MAP
The topological path map provides movable motion trajec-tories in the form of motion nodes and edges in the SMT localization method. The method of building the topological path map has two steps. First, a grid-based map in a pixel-wise format represents the existence of objects [33]; it is extracted from the floorplan data with the physical scale of one grid cell. The nodes and edges of the movable motions then form the basic configuration of the topological path map. These are calculated based on the A* [34] and Bresenham’s line [35] algorithms using the grid-based map and the locations of the fingerprints. The motion node and edge information are used as reference data during the SMT localization method.
The grid-based map is composed of many grid cells illus-trating the locations of objects in the space. In many types of floorplan information, an image in raster format represented by a combination of pixels can be converted into a grid-based map with the physical resolution of one pixel (grid cell). Each grid cell has an occupancy value representing the presence or absence of an object. The occupancy value is used to identify the structure of the space and serves as key information when generating paths which allow the possible avoidance of obstacles.
Using the grid-based map, the path map Mpcorresponding
to the combinations of the locations of B fingerprints is obtained by A* and Bresenham’s line algorithms, as follows:
Mp=pij|i 6= j; i =1, . . . , B ; j = 1, . . . , B , (4)
where pij denotes the path motion connecting the locations
of the i-th and the j-th fingerprint nodes. The function fp
generates the path motion between two fingerprint node bi
and bj and the basic configuration of the path motion is Pij
sets of motion nodes vkijand edges ekijas follows:
pij= fp(bi, bj;Mg) = {vkij, ekij
k =1, . . . , Pij}, (5)
where Mg is the grid-based map extracted from the
floor-plan and Pij is variable depending on the input of the
fin-gerprint nodes. The k-th motion node vkij is defined as the locations of the starting and arrival points of straight line (xskij, yskij, xekij, yekij) that are connected without hitting any obstacles. And the k-th motion edge consists of the length
dijkand the orientation angleφijkas follows:
vkij=(xskij, yskij, xekij, yeijk), ekij=(dijk, φijk). (6) When two locations in the motion node data are determined by the path-generation algorithm, the length and the orien-tation of the motion edge data are calculated by the simple geometrical relationships below:
dijk = q (xekij− xskij)2+(yek ij− yskij)2 φk ij =tan −1 ye k ij− yskij xekij− xskij ! . (7)
In the path map, the locations of two fingerprint nodes
biand bj are set as the starting location of the first motion
node (xs1ij, ys1ij) and the arrival location of the last motion node (xePijij, yePijij), respectively, as follows:
(xs1ij, ys1ij) = (¯xi, ¯yi), (xe Pij
ij , ye Pij
ij ) = (¯xj, ¯yj). (8)
Figure2shows the method used to extract the path motions of the topological path map between two fingerprint nodes. When the locations of the two fingerprint nodes are selected on the radio fingerprint map, the A* path generator extracts the optimal approach, consisting of a grid combination with the shortest distance which avoids obstacles. This grid set is converted to a group of path motions consisting of nodes and edges by Bresenham’s line algorithm. As Bresenham’s line algorithm rapidly searches the pixel indices corresponding to a certain line on an image, it is used to find the arrival location of the motion node on the topological path map. While mov-ing from the startmov-ing location of the motion node along the grid set with the shortest path, the grid cell requiring a change of the moving direction is determined as the arrival location of the motion node. Algorithm 1 explains the function fpused
to extract the motion nodes and edges of the topological path map.
FIGURE 2. Generating the motion nodes and edges of the topological path map. When two locations of the fingerprint nodes are chosen in the radio fingerprint map, the A* algorithm computes a grid set
{gh
h = 1, . . . , H } with the shortest path using the grid-based map. The Bresenham’s line algorithm then converts the grid set into the path motion consisting of the nodes and the edges {vk
ij, ekij}. III. LOCALIZATION FRAMEWORK
Localization framework is designed based on a hierarchi-cal estimation approach consisting of a fingerprint analysis and the SMT method. First, the fingerprint analysis finds the global region which includes the current location using the (radio) fingerprint map and radio signal measurements, after which the SMT method determines the exact location on the topological trajectory using the (topological) path map and the dead-reckoning motion. Despite the fact that range sensors such as a Wi-Fi receiver and dead-reckoning devices measure the radio signal and the local motion data with large errors, respectively, the SMT method can estimate the accurate locations by periodically correcting the errors with the path map.
A. FINGERPRINT ANALYSIS
The main objective of the fingerprint analysis is to search for the global region in which the current location exists using the fingerprint map and radio observations. The fingerprint analysis uses three steps, as shown in Figure3.
1) RADIO SIGNAL OBSERVATION
The Wi-Fi receiver measures the current observation of the radio signal data ztat time t via
zt = {(mcti, rssti) |i = 1, . . . , Z }, (9) where the current radio signal is composed of Z datasets with the MAC address mctiand the RSS value rssti.
2) LIKELIHOOD CALCULATION
The function of likelihood values L(zt;M
f) is defined using
the similarity of the RSS values between the current observa-tion zt and the fingerprint map Mf:
L(zt;Mf) = {`i|i = 1, . . . , B}. (10)
Here,`iis determined to correspond with the i-th fingerprint
FIGURE 3. Flowchart diagram of the fingerprint analysis and SMT method to implement accurate localization using range measurement sensors only. The fingerprint analysis finds a global region covering the current location using the Wi-Fi receiver and the fingerprint map, after which the SMT estimates the current location in the global region of the fingerprint analysis using the dead-reckoning sensor and the path map.
number of fingerprint nodes. Each likelihood value is calcu-lated according to the product of the probability depending on the RSS residual between the current observation and the reference of fingerprint node as follows:
`i = P(zt|bi) = Z Y j=1 Pσr(rssi− rsstj) ∀(mci= mctj), rssi∈bi, rsstj ∈z t, (11)
where the MAC addresses mciand mctjare used as identifiers
to find the compared RSSI values. The residual correspond-ing to each MAC address (rssi− rsstj) is then a variable to
calculate the likelihood value using a Gaussian probability distribution with the predefined standard deviationσr.
3) GLOBAL REGION SEARCH
The region in the global coordinates in which the current loca-tion is included is determined by choosing the most closely matching fingerprint node by:
bg=arg max
bi
`i, i = 1, . . . , B, (12)
where bgis the highest likelihood value among all the
finger-print nodes. The global region of the fingerfinger-print analysis Rg
Algorithm 1 Generation of the Path Motions Using the
Loca-tions of Fingerprints and the Grid-Based Map
1: Calculate the shortest grid cells {gh|h = 1, . . . , H }
between fingerprint nodes bi and bj using the A*
algo-rithm with the grid-based map Mg
2: Initialize the index of the grid cells and the path motions:
h ←1, k ← 1
3: Assign a location of fingerprint node bi as the starting
location of the first motion node: (xskij, yskij)k=1←(¯xi, ¯yi)
4: for h = 2 to H do
5: Generate a Bresenham’s line from the starting location of motion node (xskij, yskij) to the grid cell gh
6: if the Bresenham’s line crosses an obstacle then
7: Assign a location of grid cell ghas an arrival location
(xekij, yekij) of the motion node
8: Calculate the length dijkand the orientation angleφijk of the motion edge
9: Add the new path motion {vkij, ekij}and k ← k + 1
10: Set the arrival location of the latest motion node
as a new starting location of the motion node: (xskij, yskij) ← (xek−1ij , yek−1ij )
11: end if
12: h ← h +1
13: end for
14: Assign the size of the path motion: Pij← k
15: Assign the location of the fingerprint node bj
to the arrival location of the last motion node: (xekij, yekij)k=Pij←(¯xj, ¯yj)
16: Calculate the length (dijk)k=Pij and orientation angle (φkij)k=Pijof the last motion edge
17: Add the last path motion: {vkij, ekij}k=P ij
is defined as the candidate area in which the current location exists as follows:
Rg= E[(¯xg, ¯yg), 6g]. (13)
The location of fingerprint node bgis set to the middle point
of the current global region (¯xg, ¯yg), and the uncertainty6g
is the radius of a circle predefined as a few dozen meters reflecting the accuracy of the fingerprint analysis. Rg
pro-vides useful information that is used in the SMT method to select an adequate topology trajectory on the path map. B. SEQUENTIAL MOTION TRACKING
The SMT method can estimate the location accurately using a dead-reckoning sensor, such as an inertial measurement unit (IMU) and a gyroscope. The SMT fuses the various forms of information, including the topology trajectory of the path map, the global region of the fingerprint analysis, and the historical motion variation of the dead-reckoning sensor, in order to determine a precise localization. This process has five major steps, as shown in Figure3. First, the SMT extracts adequate path motion from the path map within the global region from the fingerprint analysis. Second, random
FIGURE 4. Extraction of the path motion candidates from the path map and assignment of the hypothesis using the global region from the fingerprint analysis in accordance with steps (a) to (c). (a) The path motions in the path map are extracted from the grid-based map considering the obstacle avoidance. (b) The group of candidate path motionsPtgis selected from the path motions in the path map by using the condition that the starting location of the motion node is included within the global regionRg. (c) The path motion of the i -th hypothesisptiis randomly assigned as one of the candidate path motionsPt
g. And the state of the i -th hypothesisxtiis initialized as the starting location and the orientation of the path motionpti.
hypotheses representing the current locations are assigned with regard to the extracted path motions. Third, the location of each hypothesis is evaluated by means of likelihood cal-culation by matching of the sequential motion data between the path map and the dead-reckoning measurement. Fourth, the best hypothesis with the highest likelihood is selected as the current location. Last, each hypothesis is checked with two constraints, the global region condition and the edge length condition, to improve the robustness of hypothesis allocation.
1) PATH MOTION EXTRACTION
Path motions corresponding to the current location are selected from the path map when utilizing the SMT method.
The group of candidate path motions Ptg should meet the
condition such that the starting location of the first motion node (xs1gj, ys1gj) is included within the global region6g of
the fingerprint analysis:
Ptg = f(Mf;Rg) = {pgj (¯x t g, ¯ytg) − (xs1gj, ys1gj) ≤6g; j =1, . . . , B}. (14) 2) NEW HYPOTHESIS ASSIGNMENT
A group of hypotheses Xt consists of the hypothesis data xti, the importance weight wti, and the path motion pti, as follows:
Xt = {(xti, wti, pti) p
t
i ∈Ptg; i =1, ..., X }, (15)
where X is the size of the allocated hypotheses. The path motion ptiis randomly selected from the pool of the candidate path motions Ptgand consists of Pisets of motion nodes and
edges. Each hypothesis data xtiis defined as a state (˜xit, ˜yti, ˜θit) and the state motion, consisting of the moving distance and the turning angle ( ˜dit, ˜ϕti), as shown below:
xit =[(˜xit, ˜yti, ˜θit), (˜dit, ˜ϕit)]. (16) The importance weight wti corresponding to each hypoth-esis consists of the dead-reckoning motion ( ˆdit, ˆϕit) and the
likelihood probability wti,
wti=[( ˆdit, ˆϕti), wti], (17)
where ( ˆdit, ˆϕit) represents the accumulated distance and angle of the dead-reckoning measurement, and wti is an indicator of the similarity between the path motion and the dead-reckoning observation. Note that ( ˆdit, ˆϕti) and ( ˜dit, ˜ϕit) are independent information not affecting each other. Unlike ( ˜dit, ˜ϕit), ( ˆdit, ˆϕit) is updated using only the measured dead-reckoning observation without any noise models.
In this stage, if a new hypothesis needs to be added to the group of hypotheses, the initial state (˜xit, ˜yti, ˜θit) is assigned as the starting location of the first motion node (xs1i, ys1i) and the orientation angle of the first motion edgeφ1i in the allocated path motion pti. As the state motion and the dead-reckoning motion, the moving distances ( ˜dit, ˆdit) and the orientation angles ( ˜ϕit, ˆϕit) are initialized to zero andφ1i, respectively. The initial likelihood probability wtishould be normalized as 1/X in accordance with the total number of hypotheses X .
Figure4illustrates the process of the first and second steps of the SMT method, i.e., extracting the group of candidate path motions and setting the data for the hypothesis. The small points and the arrows represent the path motions, which consist of nodes and edges. The candidate path motions Ptg are located inside the global region Rgfrom the fingerprint
analysis as expressed by the large dotted circle. They serve as candidates to allocate the path motion of the hypothesis in use. The state of the i-th hypothesis xtiis designated using the path motion pti, which is randomly selected from the group of candidates Ptg.
3) HYPOTHESIS UPDATE
The likelihood of an importance weight represents the degree of matching between the dead-reckoning motion ( ˆdit, ˆϕit) and the state motion ( ˜dit, ˜ϕit). To calculate this likelihood, the dead-reckoning motion and the state motion are esti-mated with prior information and the recent motion action
[1dt1ϕt]T as follows: ˆdt i ˆ ϕt i = ˆ dit−1 ˆ ϕt−1 i + 1dt 1ϕt ˜dt i ˜ ϕt i = ˜ dit−1 ˜ ϕt−1 i + 1dt 1ϕt + e t d etϕ . (18)
The state motion ( ˜dit, ˜ϕit) should be updated by the motion action (1dt, 1ϕt) and the dead-reckoning noise (et
d, etϕ).
Noise can be randomly added to the state motion with the zero-mean Gaussian function in order to reflect the errors of the motion action.
The likelihood probability function has two weight
argu-ments Pσd and Pσθ which are calculated using the
dead-reckoning motion and the hypothesis data following the path motion as follows:
wti = P( ˆdit, ˆϕit xti) = Pσd( ˆdit − ˜dit) · Pσθ( ˆϕit− ˜ϕit). (19) The likelihood probability wti is determined by the product of two Gaussian distributions with zero means and predefined standard deviations ofσd andσθ. The functions of the
dis-tributions Pσd and Pσθ respectively calculate the similarity of the distance ( ˆdit− ˜dit) and the heading angle ( ˆϕit− ˜ϕt
i)
between the accumulated measurement by dead-reckoning and the estimated state motion of the hypothesis.
The state of the hypothesis is updated by composing the starting location of the current node of path motion (xski, yski) and the estimated state motion ( ˜dit, ˜ϕit) as follows:
˜ xit ˜ yti ˜ θt i = xski + ˜ditcos ˜ϕit yski + ˜ditsin ˜ϕit ˜ ϕt i , (20)
where (xski, yski) is the reference point of the localization based on the path map and is used to reset the accumulated errors included in the estimated state motion by changing the allocated path motion..
Figure 5 shows the concept of the third process of the
SMT method that computes the state of the hypothesis using the dead-reckoning observation and the path map. The path motion of the hypothesis (red straight lines) can be estimated by selecting the most closely matching trajectory between the path motions (gray dotted lines) and the dead-reckoning mea-surement (blue straight line). The state of hypothesis (green circle) can be determined with a suitable location along the path motion of the hypothesis using the accumulated motion action.
4) BEST HYPOTHESIS SELECTION
The SMT method must calculate the current location based on the likelihood probability of the hypothesis matching the path map and the dead-reckoning measurements. Dur-ing the localization step based on the likelihood probability, the hypothesis with the highest likelihood is considered to be most appropriate for the path motion corresponding to the current location. Therefore, the hypothesis data with the
maximum likelihood value xt
g is selected among all of the
FIGURE 5. The path motion of the hypothesisptican be selected among the path motion candidates on the mapPt
gusing the dead-reckoning motion ( ˆdit, ˆϕt
i). The state of the hypothesisxtiis calculated as a certain location along the trajectory of the estimated state motion using the accumulated motion of the dead-reckoning measurement.
hypotheses, and its state (˜xt
g, ˜ytg, ˜θgt) is defined as the current
location and orientation in a global coordinate system:
xtg=arg max xt
i
wti, i = 1, . . . , X. (21)
5) CHECK CONSTRAINTS
With localization based on multiple hypotheses, a periodic resampling process to generate new hypotheses is required to maintain the robustness of the localization. Two constraints are proposed to distinguish a hypothesis following an incor-rect path trajectory corresponding to the actual location: the global region and the edge length conditions. If the hypothesis cannot satisfy these two constraints, they should be reallo-cated to other path motions so as to manage the robustness of the hypothesis distribution. In the opposite case, hypotheses following the correct path trajectory should be retained in the SMT method to improve the accuracy of the localization.
Definition 1: Global Region Condition
The location of the correct hypothesis should be placed inside the global region of the fingerprint analysis as follows:
(˜x t i, ˜yti) − (¯xgt, ¯ytg) ≤6g. (22)
If (˜xit, ˜yti) does not meet this condition, and the hypothesis
xt
i should be initialized as new data by returning it to a new
hypothesis assignment.
Definition 2: Edge Length Condition
The location of the correct hypothesis should be inside the current edge following the trajectory of the path motion. Thus, the moving distance of estimated state motion ˜ditshould be less than the length of the current edge dik:
˜
dit < dik, k ≤ Pi. (23)
Hypothesis xti can be recursively calculated through a hypothesis update. If this is not the case, the node and edge in the current path motion should be changed to the next set by increasing the index k within Pi. As the state motion
FIGURE 6. The experimental processes and results of map extraction and localization: (a) the square pattern of the floor is used to calculate the global location as the ground truth. (b) The fingerprint nodes (red circles). (c) The topological path motions (gray lines). (d) The trajectories of two localization experiments (start location: triangle, finish location: rectangle, straight line: actual location, dotted line: estimated location).
and the orientation angles ( ˜ϕit, ˆϕit) are initialized as zero and φk+1
i , respectively. In particular, the starting location of the
current node of path motion (xski, yski) is replaced with the next node information, which has the effect of eliminating the accumulated errors included in the estimated state motion through (20).
IV. EXPERIMENTAL EVALUATION
We conducted experiments in an office environment using multiple smartphone devices to verify the effectiveness of the
SMT method. SubsectionIV-Adescribes the map-building
results in an experimental area of about 59m × 57m where 26 Wi-Fi APs are installed. The next subsectionIV-Bpresents the localization results of the SMT, including comparisons with other methods.
A. MAP EXTRACTION
A global coordinate system should be defined in the floorplan of the experimental site and should be provided in advance. To do this, the floorplan is converted into a pixel-wise image
(grid-based map) with knowledge of the physical size of one pixel (grid cell), and a certain location is determined by the simple pixel count (grid count). In addition, as shown in Figure6(a), a uniform pattern of the floor plate provides an effective means of specifying an arbitrary location in the real world. In this paper, these methods enable the definition of the global coordinate system for localization by interconnecting the real and the image domains into a single origin.
After defining the global coordinate, we stored the spatial data, including the radio signals of the surrounding Wi-Fi APs tagged with the measuring location, after which the boundary of the median filter was set at a fixed interval of 1m, with 200 fingerprint nodes generated from the radio signals of the spatial data collected from approximately 2, 000 locations. Figure 6(b) shows the locations of the fingerprint nodes in the radio fingerprint map; these are denoted by the red circles on the floorplan. The fingerprint node includes data such as its location, the MAC address and the RSS value for each Wi-Fi AP installed in the space. This information is included in the fingerprint analysis in the form of the text file.
The topological path map contains movable path motions represented as sequential nodes and edges connecting the locations of the different fingerprint nodes. On determining one fingerprint node, the A* algorithm and the Bresenham’s line method generate the path motions to move to other fingerprint nodes considering the locations of obstacles in the floorplan drawing. Figure6(c) displays the path motions on the floorplan, where the gray line of an edge connects
the nodes. The total number of path motions was 48, 846,
which were produced using a combination of 200 fingerprint nodes and was utilized as reference motion data during SMT localization.
B. LOCALIZATION EVALUATION
Experiments were conducted to evaluate the accuracy of the localization process and the robustness of the heterogeneous devices used here. We gathered spatial data including the radio signals of the Wi-Fi APs and the dead-reckoning mea-surements of the IMU and a gyroscope installed on a smart-phone following the straight lines shown in Figure6(d). The dotted lines are trajectories estimated using the SMT method with 30 hypotheses. Note that the dead-reckoning measure-ments consist of accelerations and angular velocities for three axes; these are used to calculate the moving distances and the turning angles by integration in the time domain and with the geometrical rotation matrix and detection of the gait motion.
To evaluate the accuracy performance depending on the algorithms and the parameters, the smartphone stores spatial data along the red color trajectory shown in Figure 6(d).
Figure 7shows the cumulative distribution function (CDF)
of the localization error. SMT, the proposed method under-takes localization according to different hypotheses. Here the numbers behind the letters of SMT indicate the total number of hypotheses used for the localization. FP is the
FIGURE 7. Localization results of the algorithms.
TABLE 1.Comparison of computational complexities.
result only from the well-known Horus system that adopts a random probabilistic inference model of RSS from the AP [15]. PF500 is the fusion algorithm based on a particle filter with 500 samples that can integrate the RSS of the Wi-Fi AP and the dead-reckoning positions of the IMU and the gyroscope for comparison in experiments [36]. The 80th percentile accuracy levels of SMT30, PF500, and FP are 1.27m, 3.38m, and 5.49m, respectively. We can confirm that the SMT method achieves the best accuracy compared to the FP and PF500 methods.
Table1 indicates the comparison result of computational resources as assessed in terms of the processing time and memory usage. Each algorithm was performed in the mobile PC that consists of 1.4GHz quad-core CPU and 2GB RAM. The results in Figure6(d) show the average processing time per one localization iteration while tracking the red color trajectory. SMT needs to allocate the largest memory for localization operation because of the use of the topological path map, but its value is of no significant difference from FP and PF500. As a result, SMT can estimate accurate local-ization with only a small increase of computational burden compared with FP. This is a practical contribution when applying LBS to smartphones with regard to computational complexity.
To examine the robustness of the SMT method, we con-ducted another experiment using heterogeneous devices with different specifications of sensors following the blue color
trajectory shown in Figure 6(d). The CDF values of the
localization error of the SMT with 30 hypotheses are plotted
in Figure 8. The curves have similar shapes and
demon-strate the robustness and applicability of SMT on various smartphones. In the space structure, the SMT shows many
FIGURE 8. Localization results from different devices.
localization errors at a starting point near the blue triangle in Figure6(d) due to the various path motion candidates, but the error can be gradually reduced by passing through a place with an altered orientation of motion, such as an intersection. This provides robustness to the spatial shape when applying LBS in various environments with corners.
V. CONCLUSIONS AND FUTURE RESEARCH
This paper presents a new indoor localization system which fuses fingerprint analysis and the SMT method using topo-logical path map. We initially described the mapping method for a radio fingerprint map and a topological path map. Subsequently, using the constructed maps, we proposed the-oretical models for the hierarchical localization framework consisting of a fingerprint analysis and the SMT method to estimate indoor locations. Compared to legacy fingerprint analysis methods and the use of a traditional particle filter, the experimental results show that SMT-based localization is more accurate, more robust, and more adaptive to spa-tial shapes. It also allows reduced levels of computational resources because it uses relatively few hypotheses compared with PF. We evaluated the localization performance in an indoor office environment, and the results confirm the high accuracy of SMT for heterogeneous mobile devices such as smartphones with limited computational resources.
The SMT-based localization opens several directions for future research. In our current implementation, we evaluated the SMT method with a uniform density of fingerprint nodes to estimate the current location. We assume that the perfor-mance of SMT method can be improved by changing the density of fingerprint nodes. In addition, we are planning to apply the SMT method to the pedestrian localization in the various layout environments such as hospital, complex mall, factory in order to expand the application fields.
REFERENCES
[1] A. Basiri et al., ‘‘Indoor location based services challenges, requirements and usability of current solutions,’’ Comput. Sci. Rev., vol. 24, pp. 1–12, May 2017.
[2] S. He and S.-H. G. Chan, ‘‘Wi-Fi fingerprint-based indoor positioning: Recent advances and comparisons,’’ IEEE Commun. Surveys Tuts., vol. 18, no. 1, pp. 466–490, 1st Quart., 2015.
[3] D. Han, S. Jung, M. Lee, and G. Yoon, ‘‘Building a practical Wi-Fi-based indoor navigation system,’’ IEEE Pervasive Comput., vol. 13, no. 2, pp. 72–79, Apr./Jun. 2014.
[4] K. Lin, M. Chen, J. Deng, M. M. Hassan, and G. Fortino, ‘‘Enhanced fingerprinting and trajectory prediction for IoT localization in smart build-ings,’’ IEEE Trans. Autom. Sci. Eng., vol. 13, no. 3, pp. 1294–1307, Jul. 2016.
[5] M. Erdelj, M. Król, and E. Natalizio, ‘‘Wireless sensor networks and multi-UAV systems for natural disaster management,’’ Comput. Netw., vol. 124, pp. 72–86, Sep. 2017.
[6] S. Dhar and U. Varshney, ‘‘Challenges and business models for mobile location-based services and advertising,’’ Commun. ACM, vol. 54, no. 5, pp. 121–128, May 2011.
[7] X. Luo, W. J. O’Brien, and C. L. Julien, ‘‘Comparative evaluation of received signal-strength index (RSSI) based indoor localization techniques for construction jobsites,’’ Adv. Eng. Inform., vol. 25, no. 2, pp. 355–363, Apr. 2011.
[8] Y. Xu, Y. S. Shmaliy, Y. Li, and X. Chen, ‘‘UWB-based indoor human localization with time-delayed data using EFIR filtering,’’ IEEE Access, vol. 5, pp. 16676–16683, 2017.
[9] C.-H. Huang, L.-H. Lee, C. C. Ho, L.-L. Wu, and Z.-H. Lai, ‘‘Real-time RFID indoor positioning system based on Kalman-filter drift removal and Heron-bilateration location estimation,’’ IEEE Trans. Instrum. Meas., vol. 64, no. 3, pp. 728–739, Mar. 2015.
[10] A. Serra, D. Carboni, and V. Marotto, ‘‘Indoor pedestrian navigation system using a modern smartphone,’’ in Proc. 12th Int. Conf. Hum. Comput. Interact. Mobile Devices Services, Lisbon, Portugal, Sep. 2010, pp. 397–398.
[11] J. Armstrong, Y. A. Sekercioglu, and A. Neild, ‘‘Visible light position-ing: A roadmap for international standardization,’’ IEEE Commun. Mag., vol. 51, no. 12, pp. 68–73, Dec. 2013.
[12] W. Huang et al., ‘‘Swadloon: Direction finding and indoor localization using acoustic signal by shaking smartphones,’’ IEEE Trans. Mobile Com-put., vol. 14, no. 10, pp. 2145–2157, Oct. 2015.
[13] Q. Li, W. Li, W. Sun, J. Li, and Z. Liu, ‘‘Fingerprint and assistant nodes based Wi-Fi localization in complex indoor environment,’’ IEEE Access, vol. 4, pp. 2993–3004, 2016.
[14] P. Jiang, Y. Zhang, W. Fu, H. Liu, and X. Su, ‘‘Indoor mobile localization based on Wi-Fi fingerprint’s important access point,’’ Int. J. Distrib. Sensor Netw., vol. 11, no. 4, Apr. 2015, Art. no. 429104.
[15] M. Youssef and A. Agrawala, ‘‘The Horus WLAN location determination system,’’ in Proc. 3rd Int. Conf. Mobile Syst. Appl. Services, Seattle, WA, USA, Jun. 2005, pp. 205–218.
[16] G. Ding, Z. Tan, J. Wu, J. Zeng, and L. Zhang, ‘‘Indoor fingerprinting localization and tracking system using particle swarm optimization and Kalman filter,’’ IEICE Trans. Commun., vol. 98, no. 3, pp. 502–514, Mar. 2015.
[17] Q. Jiang, Y. Ma, K. Liu, and Z. Dou, ‘‘A probabilistic radio map construc-tion scheme for crowdsourcing-based fingerprinting localizaconstruc-tion,’’ IEEE Sensors J., vol. 16, no. 10, pp. 3764–3774, May 2016.
[18] N. Li, J. Chen, Y. Yuan, X. Tian, Y. Han, and M. Xia, ‘‘A Wi-Fi indoor localization strategy using particle swarm optimization based artificial neural networks,’’ Int. J. Distrib. Sensor Netw., vol. 12, Mar. 2016, Art. no. 4583147.
[19] Y. Xie, Y. Wang, A. Nallanathan, and L. Wang, ‘‘An improved K-nearest-neighbor indoor localization method based on spearman distance,’’ IEEE Signal Process. Lett., vol. 23, no. 3, pp. 351–355, Mar. 2016.
[20] W. Kim, J. Park, J. Yoo, H. J. Kim, and C. G. Park, ‘‘Target localization using ensemble support vector regression in wireless sensor networks,’’ IEEE Trans. Cybern., vol. 43, no. 4, pp. 1189–1198, Aug. 2013. [21] W. Kang and Y. Han, ‘‘SmartPDR: Smartphone-based pedestrian dead
reckoning for indoor localization,’’ IEEE Sensors J., vol. 15, no. 5, pp. 2906–2916, May 2015.
[22] Z. Chen, Q. Zhu, and Y. C. Soh, ‘‘Smartphone inertial sensor-based indoor localization and tracking with ibeacon corrections,’’ IEEE Trans. Ind. Informat., vol. 12, no. 4, pp. 1540–1549, Aug. 2016.
[23] O. Kaltiokallio, R. Hostettler, N. Patwari, and R. Jäntti, ‘‘Recursive Bayesian filters for RSS-based device-free localization and tracking,’’ in Proc. Int. Conf. Positioning Indoor Navigat. (IPIN), Nantes, France, Sep. 2018, pp. 1–8.
[24] A. Kushki, K. N. Plataniotis, and A. N. Venetsanopoulos, ‘‘Intel-ligent dynamic radio tracking in indoor wireless local area net-works,’’ IEEE Trans. Mobile Comput., vol. 9, no. 3, pp. 405–419, Mar. 2010.
[25] X.-Y. Liu, S. Aeron, V. Aggarwal, X. Wang, and M.-Y. Wu, ‘‘Adap-tive sampling of RF fingerprints for fine-grained indoor localiza-tion,’’ IEEE Trans. Mobile Comput., vol. 15, no. 10, pp. 2411–2423, Oct. 2016.
[26] A. Varshavsky, E. de Lara, J. Hightower, A. Lamarca, and V. Otsason, ‘‘GSM indoor localization,’’ Pervasive Mobile Comput., vol. 3, no. 6, pp. 698–720, Dec. 2007.
[27] H. Xie, T. Gu, X. Tao, H. Ye, and J. Lu, ‘‘A reliability-augmented parti-cle filter for magnetic fingerprinting based indoor localization on smart-phone,’’ IEEE Trans. Mobile Comput., vol. 15, no. 8, pp. 1877–1892, Aug. 2016.
[28] J. Huang, D. Millman, M. Quigley, D. Stavens, S. Thrun, and A. Aggarwal, ‘‘Efficient, generalized indoor Wi-Fi GraphSLAM,’’ in Proc. IEEE ICRA, Shanghai, China, May 2011, pp. 1038–1043.
[29] F. Herranz, ÃĄ. Llamazares, E. Molinos, M. Ocaña, and M. A. Sotelo, ‘‘Wi-Fi SLAM algorithms: An experimental comparison,’’ Robotica, vol. 34, no. 4, pp. 837–858, Apr. 2016.
[30] P. Wilk, J. Karciarz, and J. Swiatek, ‘‘Indoor radio map mainte-nance by automatic annotation of crowdsourced Wi-Fi fingerprints,’’ in Proc. Int. Conf. Indoor Positioning Indoor Navigat. (IPIN), Oct. 2015, pp. 1–8.
[31] C. Wu, Z. Yang, and Y. Liu, ‘‘Smartphones based crowdsourcing for indoor localization,’’ IEEE Trans. Mobile Comput., vol. 14, no. 2, pp. 444–457, Feb. 2015.
[32] M. Otair, ‘‘Approximate k-nearest neighbour based spatial cluster-ing uscluster-ing kd tree,’’ Int. J. Database Manage., vol. 5, no. 1, p. 97, Feb. 2013.
[33] W. Burgard, M. Hebert, and M. Bennewitz, ‘‘World modeling,’’ in Springer Handbook of Robotics, B. Siciliano and O. Khatib, Eds. Berlin, Germany: Springer, 2016, pp. 1135–1152.
[34] J. Yao, C. Lin, X. Xie, A. J. Wang, and C.-C. Hung, ‘‘Path plan-ning for virtual human motion using improved A* star algorithm,’’ in Proc. 7th Int. Conf. Inf. Technol., Las Vegas, NV, USA, Apr. 2010, pp. 1154–1158.
[35] A. T. Rashid, A. A. Ali, M. Frasca, and L. Fortuna, ‘‘Path planning with obstacle avoidance based on visibility binary tree algorithm,’’ Robot. Auton. Syst., vol. 61, no. 12, pp. 1440–1449, Dec. 2013.
[36] Y. Shu, C. Bo, G. Shen, C. Zhao, L. Li, and F. Zhao, ‘‘Magicol: Indoor localization using pervasive magnetic field and opportunistic WiFi sens-ing,’’ IEEE J. Sel. Areas Commun., vol. 33, no. 7, pp. 1443–1457, Jul. 2015.
YU-CHEOL LEE received the B.S. degree from the School of Mechanical Engineering, Yonsei Uni-versity, Seoul, South Korea, and the B.S. degree from the School of Electrical and Electronic Engineering, Yonsei University, in 2004, and the M.S. degree from the Department of Mechanical Engineering, Pohang University of Science and Technology (POSTECH), Pohang, South Korea, in 2006. He is currently pursuing the Ph.D. degree in the Robotics Program with the Korea Advanced Institute of Science and Technology (KAIST), Daejeon, South Korea. Since 2006, he has been a Senior Researcher with the Intelligence and Robot Sys-tem Research Group, Electronics and Telecommunications Research Insti-tute (ETRI), Daejeon. He has participated in numerous large-scale research projects performing a leading role as a researcher and the manager. His research achievements have been presented at prominent international con-ferences and journals, including the IEEE, ASME, RSJ, and KRoS, at which he has received outstanding research awards. His current research interests include the localization and map building for intelligent vehicles, and the navigation technology for pedestrians in indoor and outdoor environments.
HYUN MYUNG received the B.S., M.S., and Ph.D. degrees in electrical engineering from the Korea Advanced Institute of Science and Tech-nology (KAIST), Daejeon, South Korea, in 1992, 1994, and 1998, respectively. He was a Senior Researcher with the Electronics and Telecom-munications Research Institute, Daejeon, from 1998 to 2002, the CTO and the Director of the Digital Contents Research Laboratory, Emersys Corporation, Daejeon, from 2002 to 2003, and a Principle Researcher with the Samsung Advanced Institute of Technology, Yongin, South Korea, from 2003 to 2008. Since 2008, he has been a Professor with the Department of Civil and Environmental Engineering, KAIST, where he is currently a Professor with the School of Electrical Engineering and the Head of the KAIST Robotics Program. His current research interests include structural health monitoring using robotics, artificial intelligence, simultaneous localization and mapping, robot navigation, machine learning, deep learning, and swarm robots.
