{'fraction_non_alphanumeric': 0.029612092515024585, 'fraction_numerical': 0.009761427790930614, 'mean_word_length': 4.526570048309178, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Crowd-sensing Simultaneous Localization and Radio Fingerprint Mapping based on Probabilistic Similarity Models

Simultaneous localization and mapping (SLAM) has been richly researched in past years particularly with regard to range-based or visual-based sensors. Instead of deploying dedicated devices that use visual features, it is more pragmatic to exploit the radio features to achieve this task, due to their ubiquitous nature and the wide deployment of Wifi wireless network. In this paper, we present a novel approach for crowd-sensing simultaneous localization and radio fingerprint mapping (C-SLAM-RF) in large unknown indoor environments. The proposed system makes use of the received signal strength (RSS) from surrounding Wifi access points (AP) and the motion tracking data from a smart phone (Tango as an example). These measurements are captured duration the walking of multiple users in unknown environments without map information and location of the AP. The experiments were done in a university building with dynamic environment and the results show that the proposed system is capable of estimating the tracks of a group of users with an accuracy of 1.74 meters when compared to the ground truth acquired from a point cloud-based SLAM.


I. INTRODUCTION
Over the past few decades, researchers are working on developing efficient methods and technologies to map the unknown environment and localize mobile devices (robots and smartphones) in that environment [1]- [3]. This process is well known by the term, Simultaneous Localization and Mapping (SLAM). Extensive researches have been done with regard to visual-based or range-based SLAM. It is elementary to detect loop closures, either implicitly (i.e., the extended Kalman filter-based [2] or the particle filter-based SLAM [4]) or explicitly (i.e., the graph-based SLAM [5]), that permits to correct the accumulated odometry error.
In order to perform loop closure detection in SLAM, dedicated device (i.e., laser range finder or visual camera) is required to measure the similarity of observations by scan matching [6] or feature matching [7], [8], which are usually computationally expensive. However, growing popularity of Wifi wireless network provides a new opportunity to detect loop closure and perform SLAM in a different way.
Most existing building with Wifi network deployed can be exploited for localization and mapping with low hardware requirement and computational cost due to their ubiquitous nature of in-built sensing capabilities [9]- [12]. The current signalstrength-based SLAM system has to use an analytical model to feature the radio signal propagation [3], [13]. However, it is not practical to build such a model due to multiple path propagation issue in indoor environments with unexpected occlusions. Radio frequency (RF) fingerprinting [14], [15], on the other hand, represents a location with a set of radio signals, which is considered to be more robust against the signal distortions. Therefore, we adopt this technique to simultaneously localize a user and create a radio map of the environment.
In opposite to the feature map or occupancy map built by visual cameras or laser range finders, our goal is to build a map (in particular a radio map) with RF fingerprint as feature, and use that for the localization. To ensure a good positioning accuracy, it is essential to have a fine-grained radio map [14], [15] and the one created by a single user obviously cannot satisfy the requirement. Therefore, a low cost method (e.g., acquire fingerprints via crowd-sensing by multiple users) to create the radio map is a necessity.
In this paper, we propose to fuse the motion tracking data from a pedestrian dead reckoning system and received signal strength (RSS) measurements from surrounding Wifi access point (AP), to estimate the trajectory of the users and map the radio fingerprints in unknown environments via a crowd-sensing fashion, using graph SLAM technique in the system backend. Although our inertial tracking unit is Tango, our system can be extended to include any devices that provide inertial tracking functions (for example low-cost IMU sensors in a mobile phone). We adopt the crowd-sensing nature in our system to conveniently map large indoor environments using multiple mobile devices. The proposed approach corrects the trajectory of multiple users by the radio fingerprints taken during the exploration of the environment without any prior knowledge of the infrastructure. Our system leverages the in-built sensing capabilities of smartphones and the crowd-sensing nature enables to further generate the fingerprint map in larger environments at lower cost, in contrast to traditional site surveying methods.
The key contributions of this paper are: • We propose to incorporate Wifi fingerprint and motion information for crowd-sensing SLAM in an unknown indoor environment; • We propose an algorithm that automatically learns a model to characterize the uncertainty of a loop based on the degree of similarity using the short term odometry data; • We thoroughly evaluate our approach in one building at our campus with an area of approx. 9000 square meters. We organize the rest of this paper as follows. We discuss the related work in Section II. In Section III, we give an overview of the system and explain each component afterwards. In section IV, we present the results of our experiments done using the proposed method. Finally, Section V concludes the paper with possible future work.

II. RELATED WORK
In this section, we present a summary of an extensive literature review on related work done in SLAM applications, using different kinds of techniques. Throughout the years, many techniques and algorithms have been introduced to address the SLAM problem [16], [17]. Popular techniques include visual-SLAM, magnetic-SLAM, and Wifi-SLAM. Visual-SLAM methods, utilize RGB-D cameras like Kinect and Tango [18] to acquire 3D models of the environment. Magentic-SLAM systems, exploit magnetic field for localization and mapping of mobile robots [19]. These techniques use a Gaussian process to model the magnetic field intensity and a particle filtering to estimate the pose of mobile robot [20].
Wifi-SLAM [3], [13], [21] techniques use the radio signal and motion data of the device for localization and signal strength mapping in unknown environment. Authors in [22] extended this approach to include more sensory information, for example Bluetooth, LTE, and magnetic fields. The traditional fingerprinting-based approaches need a surveying phase to collect the radio measurements in an environment and annotate them with locations which are measured by an external reference system. This process is highly labour and time intensive, thus limiting the applicability of fingerprinting-based approaches. To overcome such limitations, researchers are moving towards finding low cost methods to generate the radio map. Such methods involve little human intervention [23], [24] as they leverage the in-built sensing capabilities of mobile phones. Hence, with SLAM technique, the hassle of site surveying can be avoided, and radio map can be updated conveniently whenever needed.
When the indoor environment becomes huge, generating the radio map with single mobile device becomes time consuming. The power of crowd-sensing comes into play in this scenario. Mobile crowd-sensing is a popular computing paradigm which enables ubiquitous mobile devices to collect sensing data at large scales [25], [26]. Crowd-sensing techniques can be utilized to unleash the potential of mobile phones of people who move inside the indoor environment [27]. Moreover, such systems do not require prior knowledge of floor plans or locations of wireless transmitters. Prior researches have harnessed the power of crowd-sensing to reconstruct indoor floorplans by combining user mobility traces, visual [28], and Wifi fingerprinting for indoor Wifi monitoring (Pazl) [29]. In our system, we combine crowdsensed RSS from Wifi APs and Google Tango trajectory information. The system implementation is explained in detail in section III

III. CROWD-SENSING SLAM BASED ON POSE GRAPH OPTIMIZATION
We present a novel approach that incorporates radio fingerprint measurement and motion information for crowd-sensing SLAM in an unknown infrastructure. Particularly, our approach does not need any prior information about location of the access point nor does it require a labor-intensive phase to collect the measurements in advance. Our approach features a cost-effective alternative for trajectory estimation of multiple users in unknown environments. The estimated trajectory can be used to create a radio map of the environment for the localization of a user afterwards.
The goal is to infer the entire trajectories from observations taken at different times without any prior knowledge of the environment. The problem addressed here is known as SLAM, with a variety of solutions have been proposed in the literature [4], [30]- [32]. In Graph-based SLAM [4], a graph is constructed from the raw sensor measurements. Nodes in the graph are represented by the pose of the user. The edge between two nodes encodes the spatial constraint that links them. A constraint is either sequential odometry measurement or the transformation (i.e., loop closure) determined by aligning the measurements at two non-consecutive poses. Since the observations are noisy, all constraints are additionally parameterized with a certain degree of uncertainty. The problem turns into finding the best configuration of the poses to minimize these constraints.
Loop closure is essential for a SLAM system, since it allows to correct the accumulated odometric errors and create a consistent map of the environment. It represents a situation that users have revisited a previously observed location. The detection of a loop can be achieved by feature or scan matching algorithms using visual cameras or laser range finders [7], [33].
Formally, we denote x = {x 1 , ..., x T } ⊺ as the path of the user to be estimated up to time T , where x t = (x t , y t , θ t ) is the global 2D location and heading of the user at time t. Let z ij and Σ ij denote the mean and covariance of a measurement (i.e., constraint) between node i and j. Let C be the set containing indices of all pairs of constraints in the graph.ẑ ij (x i , x j ) is the prediction of a measurement based on the current configuration of node i and j. The graph-based SLAM aims to find the best configuration of x to minimize the following equation: In particular for graph-based SLAM, z ij is expressed as a rigid-body transformation between node i and j. Given a signal strength measurement from an AP, it is straightforward to know if an area has been visited by a user, since each reported RSS value is associated with a unique MAC address. However, estimating the precise transformation between two observations turns out to be tricky, since RF signal neither reports distance nor bearing, and the detection range of an AP can be up to 50 meters, which is usually much larger than accumulated error of a pedestrian dead reckoning system. This is quite different from laser range finder, where the transformation can be estimated by matching of two laser scans [6]. A number of researchers use analytical models to predict propagation of radio signal over a distance. Many factors (examples include multiple path or obstruction from obstacles) will distort the propagation of the signal, and it is not practical to model all these aspects. Instead of modeling them explicitly, this paper represents the location with radio fingerprints. This is motivated by the fact that the similarity of two fingerprints highly depends on the locations of the two measurements.
We claim a loop closure if the similarity between two radio measurements at times i and j reaches a threshold ϑ s . We then infer that their positions are the same and add a constraint z ij = (0, ..., 0) to the graph. Actually, the two locations are unlikely  to be exactly the same, which will introduce a small amount of error to the loop closure. The error can be compensated by associating a covariance Σ ij to the constraint. A choice of this can be a diagonal matrix with small values on the main diagonal. Our solution is a careful examination of the uncertainty of a loop closure based on the degree of similarity in a training phase. Based on the training data, we automatically learn a nonparametric model to feature the variance of the distance given the similarity of two location fingerprints. The following subsections will describe each component of our proposed solutions in details.

A. Radio Fingerprints and the Similarity
RF fingerprinting represents a location with a set of radio signals from the nearby transmitters, for example Wifi APs, RFID, and Bluetooth. These fingerprints are considered to be robust against location-specific distortions as compared to the propagation model-based approaches, since they can capture the unpredicted characteristics of the existing radio infrastructure. This is quite similar to appearance-based approach, where the scene is represented by a number of visual features [34]. Extracting this kind of features involves a large amount of computation, while this process can be ignored for the radio fingerprint since each AP is unique and can be used as a feature to identify a place.
We represent a fingerprint at time t as a pair F t = (f t , x t ). f t consists of the signal strength from L access points measured at location x t : f t = {f t,1 , ..., f t,L }. The similarity function sim(F i , F j ) returns a positive scalar value, representing the similarity between two vectors F i and F j . In our experiments, we adopt the cosine similarity which has been extensively used by many researchers [35], [36]: We refer the readers to [15], [37] for a comparison of different similarity measures.

B. RSS Thresholding
The time required to compute the similarity increases linearly with the number of detected APs in the two fingerprints. The computational cost can be very high in densely AP covered scenarios such as indoor stadium or airport. A large amount of computational time can be saved if the size of the measurements can be reduced. Therefore, we propose to filter out the observations whose RSS values are below a threshold ϑ r .
Thresholding prunes observations with smaller RSS values, which represent spurious readings. In addition, larger RSS values indicate a location close to the access point with more confidence. They are expected to better constrain the location of the user. In the experimental section, we show that thresholding technique provides better accuracy, but with less computational time.

C. Model Training
An uncertainty estimation of the constraint is required for all edges in a SLAM graph. For odometry-based edges, this parameter is obtained from the motion model. We now need to derive a model to feature the uncertainty of the observationbased edges. Our solution is to train such a model by passing over the sensor data which is recorded at hand as shown in Figure 1.
Although the error from odometry accumulates in the long term, it is sufficiently small for a short time of duration. In this work, we assume odometry is accurate enough if the distance traveled is less than 30 m. This value should be modified based on the accuracy of dead reckoning system, but according to our knowledge 30 m is a suitable value for most inertial tracking platforms. Therefore, we compute the degree of similarity for fingerprint pairs whose position is close. These values are annotated with the distance of the two locations. As a result, we will get a set of K training samples: {s k , d k } K k=1 , where s k is the similarity and d k is the distance of the fingerprint pair. We then train a model which features the variance of distance given a similarity by binning. That is, for a similarity value s, we compute the variance of the samples that sites in the small interval b around s: where c(b) counts the number of samples in interval b. Although binning is a simple way for smoothing, the computation is efficient, since assigning a sample into a bin is straightforward. The resulted variance is stored in a look up table which could be used in the second stage of SLAM, as shown in Figure 1.

D. Merging Two Tracks at Different Times
To incorporate the crowd-sensed measurements from multiple users, it is necessary to merge tracks from different users. This allows to perform loop closure detection among different tracks and make a full use of the crowd-sensed data. We assume the orientation of the device is known or can be approximately estimated by an external system. This is quite reasonable for the following reasons: compass can directly offer the orientation if the placement of the device is fixed. For arbitrary placements, authors in [38] proposed an approach to determine the walking direction of a pedestrian by projecting the displacement vectors onto a plane.
In our experiment, we assume every user started from the same location. Thus, an edge is added to link the first node between two tracks. The transformation along x and y is set to be zero and the orientation θ is approximated by the orientation difference between the two nodes. The covariance along x and y is determined by the covariance look up table as detailed in Sect.III-C and orientation covariance is set to a large value (i.e., 1000), which means that we do not have any knowledge about the orientation of the two poses based on only RF observations. In case that the relationship between the initial locations is unknown, it can be determined by state-of-the-art probability-based approaches such as the Kalman filter or the particle filter [4], [14].

E. Finding Loop Closure Candidates
We first compute the relative distance and orientation of two fingerprints F i and F j . If they are smaller than pre-defined thresholds, we compute the similarity s ij between F i and F j . We add a tuple < i, j, s ij > as a candidate of loop closure if the similarity exceeds a threshold ϑ s , which is one of the few parameters that has to be supplied in our approach. The impact of ϑ s on the performance is not too critical, as shown in our experiments. In most cases, ϑ s = 0.8 gives a good accuracy. We reject the similarity with values smaller than ϑ s , to avoid false positive loop closures. It is worth mentioning that this process is applied not only to the nodes in the same track, but also to the nodes between two tracks to leverage crowd sourced measurements collected by multiple users. Constraints inferred from odometry and radio measurements from three users are illustrated in Figure 3.

F. Screening Loop Closure Candidates
Incorrect loop closure is catastrophic to a SLAM system, as it will ruin the consistency of a trajectory and the map. We perform the following check of a loop candidate before we finally add it to the graph for optimization: • We discard a loop < i, j, s ij > if the difference of i and j is smaller than M to prevent from detecting loops when the user is still at the same location; • For each constraint < i, j, s ij >, we check if there exists another candidate < i, k, s ik > that lies within ϑ w meters before or after j in the track. If yes, the one with low similarity value will be removed. One could think about other heuristic approaches to filter out the suspicious loop closures. For example, authors in [39] propose to group the loop closures that close in time and check the temporal consistency with previous scenes for robust loop closure detection. However, this goes beyond the focus of this paper, hence, we evaluate the performance of the system without further loop consistency check.

Pose3
Posei Pose1 Posej User1 Fig. 3. Example of constraints inferred from the measurements taken by three users. After screening, the remaining constraints will be added as edges to the graph. We set the transformation of the edge to zero for both translation and orientation. Covariance of the translation can be found in the look up table we computed in Section III-C. The orientation covariance is set to 1000.

G. Pose Graph Optimization
We finally optimize the graph consisting of poses and constraints based on the pose graph optimization technique. We choose Levenberg-Marquardt in g2o as the implementation [5]. The algorithm is freely available and is proven to be one of the state-of-the-art SLAM algorithms.

A. Experimental Details
We program the Tango phone (with Android 6.0.1) to receive the signal strength from APs and simultaneously upload them to the server every five seconds. Meanwhile, the pose as well as the point cloud from the device are sent to the server every one second. We evaluated the performance of our approach on the third floor of our campus building with a size of 130 m×70 m, as shown in Fig. 4. This environment consists of concrete walls, corridors, soft room partitions, and wide open space. A person was asked to hold the phone and walk around the environment along different paths with a normal walking speed. In total, we recorded four tracks at different times. For each track, we asked the user to start from the same position. The total distance traveled is 1533 meters with a duration of 3740 seconds and a number of 2211 unique MAC addresses are detected. This results in four log files consisting of 748 measurements, with 207, 170, 181, and 190 in each track respectively. A snapshot of the environment is shown in Fig. 2(a).

B. Point Cloud-based SLAM as Ground Truth
We compared our results against a point cloud-based GraphSLAM. We implemented loop closure detection based on point cloud using the open source point cloud library (PCL) [40]. We identify the Harris keypoints in a pair of point clouds and compute the corresponding SHOT descriptors [41]. We match these descriptors with KNN and find an initial transformation using SVD (singular value decomposition). The transformation is further refined by ICP (iterative closest point). If the number of matched points exceeds a threshold (half size of the points), a loop closure is confirmed and added to the graph as constraints. We treat this as the ground truth to evaluate the accuracy of our approach.
The accuracy is shown by the root mean square error (RMSE) of the distance between the ground truth and our estimation. Our experiments show that we are able to achieve an accuracy of 1.74 meters over an area of approx. 9000 square meters, as shown in Figure 4. The optimized track is annotated with the RF measurement and can serve as the radio map for the positioning of other users.

C. Impact of Different RSS Threshold ϑ r
In the first series of experiments, we examined the accuracy under the impact of RSS thresholding technique. The results are listed in Table I. We set the similarity threshold ϑ s = 0.8 and use a binning size of b = 0.1. According to the distribution of the RSS, we vary ϑ r from -90 to -45 to analyze its impact on the positioning accuracy. As can be seen from Table I,   In densely AP covered areas, many APs report very low signal strength due to the regular occlusions in indoor environments, which will reduce the overall similarity between two fingerprints as well as the final accuracy we achieved. A suitable threshold will give a good accuracy, as it filters out the suspicious signals. However, a threshold larger than -50 leads to a bad result (for example, 3.86 meters of error at running time of 0.52 seconds with ϑ r = −50). The estimation, ground truth, and odometry of individual tracks are visualized in Figure 5. A part of estimated trajectory and the constraints inferred are shown in Figure 6.   Table II. We choose a binning size of b = 0.1 and a RSS threshold of ϑ r = −70. We vary the threshold ϑ s from 0.1 to 0.98 to see the accuracy as well as the number of constraints inferred. As can be seen from Table II, the threshold has a high impact on the number of constraints, thus an impact on the accuracy. Applying a high threshold will result in a small number of constraints and a decrease of the accuracy; while a small threshold yields a large number of constraints and an improvement of the accuracy. For example, we obtain a mean accuracy of 1.74 m with ϑ s = 0.8, which is an improvement of 53.8% as compared to the accuracy with ϑ s = 0.98 (i.e., 3.77 m ). Yet, such an improvement is at the expense of more number of constraints added (i.e., 457 constraints with ϑ s = 0.8 as compared to 54 with ϑ s = 0.98). But the accuracy does not get improved with a threshold smaller than 0.5. One reason could be because a low similarity value always comes along with a very high covariance, and has very less strength to correct the odometric error. A value of 0.8 seems to be a good trade off between the accuracy and the number of constraints inferred.

E. Impact of the Binning Size of Training
In the last series of experiments, we examined the accuracy under the impact of various binning size b as shown in Table  III. We choose a similarity threshold of ϑ s = 0.8 and RSS threshold of ϑ r = −70. We set parameter b to the following values to evaluate its impact on the accuracy, i.e., b = {0.05, 0.1, 0.2, 0.4, 1.0}. As can be seen from Table III, the best choice of b is 0.1. The covariance estimated with a large b is usually too large to compensate for the error from the odometry, while a small b seems to well characterize the model. Covariance added here is a key to optimize the pose graph, as it is the only information to measure how close the two locations are in a loop, therefore, a careful examination of the parameter will lead to an improvement of the accuracy. The covariance is much smaller as compared to the ranging of a Wifi access point (up to 50 meters). This is why we are still able to correct the accumulated odometry error. The approach presented here provides a way to automatically calibrate the uncertainty model using odometric measurements.

F. Computational Time
The time consumed at each stage of our approach is listed in Table IV. We processed the measurements with an Intel Core i5-4200M @ 2.5GHz CPU, with 4GB RAM. As can be seen from Table IV, the entire data processing of radio fingerprint and odometry is almost 70 times faster than the data recording stage. Optimization of the graph only took 0.31 seconds. Although our implementation is offline, loop-closure detection and pose graph optimization can be possibly made online considering the time consumption of the system as shown in Table IV.

V. CONCLUSIONS AND FUTURE WORK
In this paper, we presented a novel approach for crowd-sensing simultaneous localization and radio fingerprint mapping (C-SLAM-RF) in unknown environments using radio signals collected from multiple users. The proposed system makes use of an inertial tracking system and the signal strength measurements from surrounding wireless access points. We evaluated the proposed approach in a large scale environment and an accuracy of 1.74 meters is achieved over an area of approx. 9000 square meters. In the future, we would like to investigate how to create a finer radio fingerprint map from the coarsely sampled human trajectories. Another direction would be to replace Tango with the low-cost IMU sensors embedded in a smartphone for pedestrian dead reckoning [42], [43].