# Measuring the Uncertainty of Probabilistic Maps Representing Human Motion for Indoor Navigation

Authors: Susanna Kaiser; Maria Garcia Puyol; Patrick Robertson
Journal: Mobile Information Systems
 (2016)

---

## Abstract

Indoor navigation and mapping have recently become an important field of interest for researchers because global navigation satellite systems (GNSS) are very often unavailable inside buildings. FootSLAM, a SLAM (Simultaneous Localization and Mapping) algorithm for pedestrians based on step measurements, addresses the indoor mapping and positioning problem and can provide accurate positioning in many structured indoor environments. In this paper, we investigate how to compare FootSLAM maps via two entropy metrics. Since collaborative FootSLAM requires the alignment and combination of several individual FootSLAM maps, we also investigate measures that help to align maps that partially overlap. We distinguish between the map entropy conditioned on the sequence of pedestrian’s poses, which is a measure of the uncertainty of the estimated map, and the entropy rate of the pedestrian’s steps conditioned on the history of poses and conditioned on the estimated map. Because FootSLAM maps are built on a hexagon grid, the entropy and relative entropy metrics are derived for the special case of hexagonal transition maps. The entropy gives us a new insight on the performance of FootSLAM’s map estimation process.


---

## Body

## 1. Introduction

Over the last few years professional and consumer location based applications have grown supported by digital cartography and GNSS (Global Navigation Satellite System), where real-time location estimation is combined with accurate maps. Motivated by the success of outdoor navigation the demand for indoor or underground navigation has increased. However, in indoors GNSS is often unavailable [1].Different techniques address the particular challenges in indoor navigation. An overview of existing techniques is given in [2] and more recently in [3]. One approach is to install additional transmitters (GNSS Pseudolites) or receivers (e.g., RFIDs (Radio Frequency Identification), UWBs (Ultra Wide Band transmitters)). Another possibility is to use existing radio base stations originally installed for other purposes (such as UMTS or WLAN) or to enhance the quality of the GNSS signals (high sensitivity receivers and/or assisted GNSS services). The main drawback of these techniques is that new infrastructure needs to be installed and maintained to achieve high positioning accuracy. Another promising approach that deals with the problems of indoor navigation is the use of foot mounted inertial sensors [4] or other suitable forms of pedestrian dead reckoning (PDR) with alternate sensor placements or including additional sensors like cameras or magnetic field sensors [5]. In this case, no extra infrastructure is needed and the sensors can usually be implemented at low cost. In this paper, we will focus on positioning estimation for pedestrians based purely on PDR.Foot mounted inertial measurement units (IMUs) can be used very effectively with the supply of zero velocity updates (ZUPTs) to a PDR estimation algorithm [4], reducing the nonlinear error growth over time to a reasonably small linear drift. The drift experienced by all PDR approaches can be addressed by using available floor plans to constrain the estimate [6–8]. However, maps of indoor scenarios may be only partially available, completely unavailable, outdated, or proprietary. To address the problem of unknown maps, the principle of Simultaneous Localization and Mapping (SLAM) using PDR can be called into play [9, 10]. SLAM estimates the location and a suitable presentation of the environment conditioned on a sequence of noisy measurements.In this paper, we focus on FootSLAM [11] to estimate useful maps of probabilistic human motion (in the following referred to as probabilistic maps). FootSLAM is a form of SLAM for pedestrians. Rooted in a Bayesian estimation formulation, FootSLAM allows for the generation of a rich map for the visited areas, in our case aprobabilistic transition map built on a hexagon raster, while simultaneously making accurate estimates of the pedestrian’s pose, her position and orientation, within the map. FootSLAM builds on a Rao-Blackwellized particle filter (RBPF) [12] based on the FastSLAM factorization [13] to process human odometry, that is, human step measurements obtained, for example, with an IMU located on the pedestrian’s shoe or in the pocket [14]. These odometry measurements are computed by an unscented Kalman Filter [15–17] using the raw IMU data and are then used as input to the FootSLAM particle filter. Each particle in the particle filter [18] randomly draws odometry errors and effectively represents one hypothesis for the path followed by the pedestrian. Those particles that revisit similar transitions are rewarded and are more likely to represent the actual path that the pedestrian followed. More precisely, each particle learns the FootSLAM map by counting each transition it makes across the edges of the hexagons and stores its whole path through the hexagonal grid.The FootSLAMprobabilistic transition maps are uncertain because they are estimated from human odometry. A suitable metric of the uncertainty of transition maps has not yet been addressed but having one would be useful for performance evaluation, theoretical analysis, map comparison, map combination, and map selection. Map combination and selection are, for instance, needed by the so-called “Turbo” FeetSLAM algorithm [19] whereby several maps resulting from several datasets are processed and combined in an iterative way to obtain a more accurate and extensive map of an environment.The paper is organized as follows: First, we will discuss the term uncertainty and give an overview of different uncertainty metrics related to the probabilistic map. After that, we will give an overview of the related work (Section1.2). In Section 2, we will describe FootSLAM’s Bayesian formulation and how the map is generated during the FootSLAM estimation process. Next, Section 3 will introduce the representation of the pedestrian’s history of poses as a random walk on a weighted graph, and Section 4 presents the derivation of the entropy and relative entropy metrics. Finally, we will show experimental results and outline the main conclusions.


### 1.1. Uncertainty

In the context of localization we can find different map definitions (Figure1). For instance, we can differentiate between roadmaps, floor plans, topological maps, or images like satellite images, and so forth. We can calculate the entropy of any of these maps to obtain a measure of theinformation content of that map. However, the nature of the maps estimated by a SLAM algorithm is completely different. If we use human odometry and process it using FootSLAM, we obtain a human motion map that is inherently a probabilistic representation of human motion. This map is uncertain because it is being estimated from odometry, which in turn is also uncertain due to uncertainty in the sensor measurements. Our goal is to derive a metric that reflects the uncertainty of a map.Figure 1
Overview of different kinds of maps. Entropy calculations of maps like roadmaps, floor plans, topological maps, and different kinds of images (e.g., satellite images) lead to information content measurements, whereas entropy calculations of estimated maps lead to a measure of the uncertainty of the map.The termuncertainty has different definitions, depending on the context. In this article, we discuss how to measure the uncertainty ofprobabilistic maps. In our analysis of maps based on human odometry we distinguish between the following:(a)
The inherentuncertainty at the human motion level: This uncertainty represents the pedestrian’s choice about his next steps. Naturally, it is very difficult if not impossible to model and characterize this process accurately. For instance, intentions will vary from person to person, be time variant, and will encompass at least the history of poses of that person.(b)
Theuncertainty of the map itself: Since we estimate transitions given a set of observations, maps are uncertain. For instance, main corridors and some areas of a building such as conference rooms are visited more often than other rooms; likewise, public buildings such as airports or shopping centers are more frequently visited than residential buildings. Therefore, the number of observations is dependent on the location. Other sources of uncertainty at the map level are, for example, the fact that measurements are usually collected by means of inaccurate sensors and the nature of the discrete map representation itself.We propose to compute the uncertainty of a map via two information theoretic metrics: the entropy of a map and the relative entropy between two maps. The random variableM will refer to the map, the discrete stochastic process Z to the step measurements, and the discrete stochastic process P to the pedestrian poses. We append 0:k to the stochastic process variable if we refer to the sequence of that variable until time index k and 0:k-1 if we refer to the past history of that variable.Following [20] we definedifferential entropy as the entropy of a continuous random variable, simply shortened byentropy and denoted by ħ. In the case of a discrete stochastic process, such as the sequence of pedestrian poses P0:k, we defineentropy rate as the rate ofgrowth of its entropy and denote it by H.We are interested in two different kinds of entropies: (i) a measure of the uncertainty of the mapM itself, which can serve as a metric for the goodness of the map; (ii) the entropy rate of the pedestrian’s steps. This second metric gives us insight regarding the uncertainty of the next pedestrian’s step, which is influenced by the interplay between the constraints of the environment and the pedestrian’s choice of movement therein.Each of the two kinds of entropies mentioned above can be computed conditioned on the following: (i) the sequence (or accordingly history) of noisy measurementsZ1:k=Z1:k, where Z1:k is a given measurement sequence; (ii) the sequence (or accordingly history) of poses P0:k=P0:k, where P0:k is the output of a genie; (iii) the true map M=M (also from a perfect genie). Here, the genie is an entity that knows the true sequence of poses or the true map. Note that pose sequences start at time k=0 due to initialization, whereas the measurements start at time k=1 [11]. An overview of the different kinds of entropies is given in Table 1.Table 1
Different kinds of entropy metrics. We distinguish between map entropy and step entropy rate given the sequence of measurementsZ1:k, the sequence of poses P0:k, or the map M.
Map entropy Step entropy rate Source ħ M ∣ Z 1 : k = Z 1 : k lim k → ∞ ⁡ H P k ∣ Z 1 : k - 1 = Z 1 : k - 1 FootSLAM Convergence⇓ ħ M ∣ P 0 : k = P 0 : k lim k → ∞ ⁡ H P k ∣ P 0 : k - 1 = P 0 : k - 1 Genie pose Infinite observations⇓ No uncertainty H P k ∣ P k - 1 = P k - 1 , M = M Genie mapThe entropyħ(M∣Z1:k=Z1:k) and the corresponding entropy rate H(Pk∣Z1:k-1=Z1:k-1) represent the uncertainty of the map and the step conditioned on thenoisy measurements, respectively. Following the dynamic Bayesian network representation of FootSLAM [21] the state Zk is a noisy measurement of the true step vector Uk, influenced by the error state Ek and additional white noise.The entropiesħ(M∣P0:k=P0:k) and H(Pk∣P0:k-1=P0:k-1) aim for the uncertainty of the map and the pedestrian’s next step, respectively, conditioned on thesequence of poses given by a genie. In our subsequent numerical evaluations we cannot resort to a genie; hence we shall assume that FootSLAM achieves good convergence and we can therefore approximate the output of the genie using our FootSLAMestimated sequence of poses. If perfect convergence is achieved, that is, the estimated FootSLAM map leads to same discrete transitions in the map, then we are able to determine the map entropy ħ(M∣P0:k=P0:k) and the step entropy rate H(Pk∣P0:k-1=P0:k-1). In the following sections we refer to the entropies conditioned on the estimated sequence of poses, assuming sufficiently good convergence.The entropies conditioned on thetrue map (last row of Table 1) are metrics that we are not able to calculate since we do not know the map itself because it is being estimated from finite and not necessarily representative walks. The true map itself, also an output of a genie, can be considered as a result of an infinitely long and representative pose sequence: P0:∞. The map entropy given the true map will obviously result in no remaining uncertainty. The step entropy rate given the true map H(Pk∣M=M) is the remaining uncertainty of the next step of the pedestrian that is only influenced by the pedestrian’s free choice within the perfectly known physical constraints and other physical features of the environment like obstacles and signs. In addition, it is to be expected that such influencing factors are dependent on the individual and the state of the individual and her context (such as travel plans). In this paper, we shall quantify the uncertainty based on a very simple and time-invariant model of human motion, namely, a first-order Markov process that encodes the probability of anybody’s next steps at a particular location in the environment. Since we have no observation of the physical environment, we shall rely on the human pose sequence as the only state that we can use to encode the environment’s influence on motion. This is to say, an infinitely long sequence of representative poses is as informative about the person’s next step as the perfect map.Hence the step entropy rate will be assumed to be constant over time and the step entropy rate given the genie history of posesH(Pk∣P0:k-1=P0:k-1) approaches asymptotically this constant for k→∞: (1)limk→∞HPk∣P0:k-1=P0:k-1=HPk∣Pk-1=Pk-1,M=M.


### 1.2. Related Work

Following Bjørke [22], Shannon’s information theory inspired several research articles in cartography for quantifying theefficiency of a map. Bjørke described in his article the problems of the pure Shannon theory applied to cartography. In his article he gives a comprehensive overview of the related work before 1996. He distinguishes between thesyntactic, semantic, and pragmatic aspects of communication originally defined in [23] and also given in [24] as level A, level B, and level C, respectively. In his work, he focuses on applying the Shannon information theory to the syntactic component of a map and defines the termsmap entities andmap information source. He distinguishes betweentopological entropy,metrical entropy, andpositional entropy. In addition he pointed out that one way to deal with spatial correlation within the map is the computation of the weighted mean of the entropy at different orders of neighborhood.In our work we concentrate on the Shannon theory applied to the syntactic component of our FootSLAM probabilistic maps (built on a hexagon grid) as Bjørke did. In addition, we restrict our problem to calculating the positional entropy. Per definition of the positional entropy, all occurrences of the map entities are seen as unique events and spatial correlations are not considered. Our work differs from Bjørke’s in that we address the problems of calculating the entropy and relative entropy for the special case of FootSLAM transition maps based on hexagons to quickly compare and align maps.Another approach to evaluate maps that uses the properties of the entropy is the so-called local entropy map [25]. Guo proposes a nonparametric analysis approach that detects spatially varying multivariate relationships based on the Rényi entropy in local regions of the geographic space. The multivariate Rényi entropy [26] is the generalization of Shannons’ entropy, originally introduced by Shannon in 1948 [27], and is computed over a d-dimensional data space. The concept of an entropy map was already used in robotics in 2008 [28], where the optical flow estimates of different images of an object (e.g., visual landmarks) are analyzed with a Bayesian analysis and the resulting conditional probability distributions (belief distributions) are compressed by computing the Shannon entropy that provides a measure of ambiguity for the belief distribution [28]. The authors generate a database for different objects and store it’s entropy maps, in this case the information relating ambiguity to camera (viewing position).In [29] Blanco et al. address the uncertainty of maps obtained using a mobile robot SLAM algorithm with RBPFs. The problem is similar to ours, but in contrast to a hexagon based map, the map is based on an occupancy grid, whereby the region is divided into cells (squares) and the binary probability of occupancy/freeness of that cell is stored. Blanco et al. propose to calculate the entropy-based information I=∑x,y‍(Hmax-Hx,y) for all cells x,y of a map to eliminate the influence of the cells not discovered by the robot. In their article, they give also an overview of the related work regarding measuring the uncertainty of the robot pose and/or the map. The map mean information is compared to the joint entropy of the map and the robot path proposed by [30] and it is shown that in the case of the joint entropy defined by Stachniss et al. the map entropy dominates so that the path entropy is hidden. In addition, in [30] the entropy of the individual maps is calculated, whereas Blanco et al. propose to use theexpected map, a weighted average of all particle’s maps of the RBPF, what we have called accumulated map, in order to measure also the consistency of the individual maps.The predictability ofhuman motion is intensively studied in [31] and more recently in [32]. Based on the mobility patterns of mobile phone users Song et al. showed that human motion is highly predictable [31]. Here, a combination of the empirically determined user entropy and Fano’s inequality is used to evaluate predictability. However, topological constraints are not considered in their evaluation. Smith et al. refine these limits by considering in addition topological constraints like unreachable areas. They provide a lower upper bound for the predictability of human motion and use the “Geolife dataset” for their evaluation (182 individual GPS trajectories over a period of five years).None of these references handles the problem of measuring the quality ofprobabilistic maps as used in FootSLAM. More specifically, FootSLAM maps are built on a hexagonal grid. Maps based on hexagons are widely used, for example, in game programming (Charles S. Roberts 1961, [33]) for regulating movement or in mobile communications to divide a geographic area in cells (cellular network), but in such cases it is not necessary to compare the hexagon maps with one another. Also the maps do not encode probabilistic motion. Our work differs from the work above in the following points:(i)
FootSLAMprobabilistic transition maps are built on a hexagon grid, where hexagon edge transitions are counted and stored, encoding transition probabilities.(ii)
The pedestrian’s trajectory on the hexagonal grid can be viewed as a random walk on a weighted graph. It is possible to compute the entropy rate of the pedestrian’s steps on a FootSLAM hexagon map. The theory of a random walk on a finite network was introduced by Doyle and Snell in [34] further described by Lovász [35]. More information can be found in [20].(iii)
We also take into account the number of visits to each hexagonal cell.


## 1.1. Uncertainty

In the context of localization we can find different map definitions (Figure1). For instance, we can differentiate between roadmaps, floor plans, topological maps, or images like satellite images, and so forth. We can calculate the entropy of any of these maps to obtain a measure of theinformation content of that map. However, the nature of the maps estimated by a SLAM algorithm is completely different. If we use human odometry and process it using FootSLAM, we obtain a human motion map that is inherently a probabilistic representation of human motion. This map is uncertain because it is being estimated from odometry, which in turn is also uncertain due to uncertainty in the sensor measurements. Our goal is to derive a metric that reflects the uncertainty of a map.Figure 1
Overview of different kinds of maps. Entropy calculations of maps like roadmaps, floor plans, topological maps, and different kinds of images (e.g., satellite images) lead to information content measurements, whereas entropy calculations of estimated maps lead to a measure of the uncertainty of the map.The termuncertainty has different definitions, depending on the context. In this article, we discuss how to measure the uncertainty ofprobabilistic maps. In our analysis of maps based on human odometry we distinguish between the following:(a)
The inherentuncertainty at the human motion level: This uncertainty represents the pedestrian’s choice about his next steps. Naturally, it is very difficult if not impossible to model and characterize this process accurately. For instance, intentions will vary from person to person, be time variant, and will encompass at least the history of poses of that person.(b)
Theuncertainty of the map itself: Since we estimate transitions given a set of observations, maps are uncertain. For instance, main corridors and some areas of a building such as conference rooms are visited more often than other rooms; likewise, public buildings such as airports or shopping centers are more frequently visited than residential buildings. Therefore, the number of observations is dependent on the location. Other sources of uncertainty at the map level are, for example, the fact that measurements are usually collected by means of inaccurate sensors and the nature of the discrete map representation itself.We propose to compute the uncertainty of a map via two information theoretic metrics: the entropy of a map and the relative entropy between two maps. The random variableM will refer to the map, the discrete stochastic process Z to the step measurements, and the discrete stochastic process P to the pedestrian poses. We append 0:k to the stochastic process variable if we refer to the sequence of that variable until time index k and 0:k-1 if we refer to the past history of that variable.Following [20] we definedifferential entropy as the entropy of a continuous random variable, simply shortened byentropy and denoted by ħ. In the case of a discrete stochastic process, such as the sequence of pedestrian poses P0:k, we defineentropy rate as the rate ofgrowth of its entropy and denote it by H.We are interested in two different kinds of entropies: (i) a measure of the uncertainty of the mapM itself, which can serve as a metric for the goodness of the map; (ii) the entropy rate of the pedestrian’s steps. This second metric gives us insight regarding the uncertainty of the next pedestrian’s step, which is influenced by the interplay between the constraints of the environment and the pedestrian’s choice of movement therein.Each of the two kinds of entropies mentioned above can be computed conditioned on the following: (i) the sequence (or accordingly history) of noisy measurementsZ1:k=Z1:k, where Z1:k is a given measurement sequence; (ii) the sequence (or accordingly history) of poses P0:k=P0:k, where P0:k is the output of a genie; (iii) the true map M=M (also from a perfect genie). Here, the genie is an entity that knows the true sequence of poses or the true map. Note that pose sequences start at time k=0 due to initialization, whereas the measurements start at time k=1 [11]. An overview of the different kinds of entropies is given in Table 1.Table 1
Different kinds of entropy metrics. We distinguish between map entropy and step entropy rate given the sequence of measurementsZ1:k, the sequence of poses P0:k, or the map M.
Map entropy Step entropy rate Source ħ M ∣ Z 1 : k = Z 1 : k lim k → ∞ ⁡ H P k ∣ Z 1 : k - 1 = Z 1 : k - 1 FootSLAM Convergence⇓ ħ M ∣ P 0 : k = P 0 : k lim k → ∞ ⁡ H P k ∣ P 0 : k - 1 = P 0 : k - 1 Genie pose Infinite observations⇓ No uncertainty H P k ∣ P k - 1 = P k - 1 , M = M Genie mapThe entropyħ(M∣Z1:k=Z1:k) and the corresponding entropy rate H(Pk∣Z1:k-1=Z1:k-1) represent the uncertainty of the map and the step conditioned on thenoisy measurements, respectively. Following the dynamic Bayesian network representation of FootSLAM [21] the state Zk is a noisy measurement of the true step vector Uk, influenced by the error state Ek and additional white noise.The entropiesħ(M∣P0:k=P0:k) and H(Pk∣P0:k-1=P0:k-1) aim for the uncertainty of the map and the pedestrian’s next step, respectively, conditioned on thesequence of poses given by a genie. In our subsequent numerical evaluations we cannot resort to a genie; hence we shall assume that FootSLAM achieves good convergence and we can therefore approximate the output of the genie using our FootSLAMestimated sequence of poses. If perfect convergence is achieved, that is, the estimated FootSLAM map leads to same discrete transitions in the map, then we are able to determine the map entropy ħ(M∣P0:k=P0:k) and the step entropy rate H(Pk∣P0:k-1=P0:k-1). In the following sections we refer to the entropies conditioned on the estimated sequence of poses, assuming sufficiently good convergence.The entropies conditioned on thetrue map (last row of Table 1) are metrics that we are not able to calculate since we do not know the map itself because it is being estimated from finite and not necessarily representative walks. The true map itself, also an output of a genie, can be considered as a result of an infinitely long and representative pose sequence: P0:∞. The map entropy given the true map will obviously result in no remaining uncertainty. The step entropy rate given the true map H(Pk∣M=M) is the remaining uncertainty of the next step of the pedestrian that is only influenced by the pedestrian’s free choice within the perfectly known physical constraints and other physical features of the environment like obstacles and signs. In addition, it is to be expected that such influencing factors are dependent on the individual and the state of the individual and her context (such as travel plans). In this paper, we shall quantify the uncertainty based on a very simple and time-invariant model of human motion, namely, a first-order Markov process that encodes the probability of anybody’s next steps at a particular location in the environment. Since we have no observation of the physical environment, we shall rely on the human pose sequence as the only state that we can use to encode the environment’s influence on motion. This is to say, an infinitely long sequence of representative poses is as informative about the person’s next step as the perfect map.Hence the step entropy rate will be assumed to be constant over time and the step entropy rate given the genie history of posesH(Pk∣P0:k-1=P0:k-1) approaches asymptotically this constant for k→∞: (1)limk→∞HPk∣P0:k-1=P0:k-1=HPk∣Pk-1=Pk-1,M=M.


## 1.2. Related Work

Following Bjørke [22], Shannon’s information theory inspired several research articles in cartography for quantifying theefficiency of a map. Bjørke described in his article the problems of the pure Shannon theory applied to cartography. In his article he gives a comprehensive overview of the related work before 1996. He distinguishes between thesyntactic, semantic, and pragmatic aspects of communication originally defined in [23] and also given in [24] as level A, level B, and level C, respectively. In his work, he focuses on applying the Shannon information theory to the syntactic component of a map and defines the termsmap entities andmap information source. He distinguishes betweentopological entropy,metrical entropy, andpositional entropy. In addition he pointed out that one way to deal with spatial correlation within the map is the computation of the weighted mean of the entropy at different orders of neighborhood.In our work we concentrate on the Shannon theory applied to the syntactic component of our FootSLAM probabilistic maps (built on a hexagon grid) as Bjørke did. In addition, we restrict our problem to calculating the positional entropy. Per definition of the positional entropy, all occurrences of the map entities are seen as unique events and spatial correlations are not considered. Our work differs from Bjørke’s in that we address the problems of calculating the entropy and relative entropy for the special case of FootSLAM transition maps based on hexagons to quickly compare and align maps.Another approach to evaluate maps that uses the properties of the entropy is the so-called local entropy map [25]. Guo proposes a nonparametric analysis approach that detects spatially varying multivariate relationships based on the Rényi entropy in local regions of the geographic space. The multivariate Rényi entropy [26] is the generalization of Shannons’ entropy, originally introduced by Shannon in 1948 [27], and is computed over a d-dimensional data space. The concept of an entropy map was already used in robotics in 2008 [28], where the optical flow estimates of different images of an object (e.g., visual landmarks) are analyzed with a Bayesian analysis and the resulting conditional probability distributions (belief distributions) are compressed by computing the Shannon entropy that provides a measure of ambiguity for the belief distribution [28]. The authors generate a database for different objects and store it’s entropy maps, in this case the information relating ambiguity to camera (viewing position).In [29] Blanco et al. address the uncertainty of maps obtained using a mobile robot SLAM algorithm with RBPFs. The problem is similar to ours, but in contrast to a hexagon based map, the map is based on an occupancy grid, whereby the region is divided into cells (squares) and the binary probability of occupancy/freeness of that cell is stored. Blanco et al. propose to calculate the entropy-based information I=∑x,y‍(Hmax-Hx,y) for all cells x,y of a map to eliminate the influence of the cells not discovered by the robot. In their article, they give also an overview of the related work regarding measuring the uncertainty of the robot pose and/or the map. The map mean information is compared to the joint entropy of the map and the robot path proposed by [30] and it is shown that in the case of the joint entropy defined by Stachniss et al. the map entropy dominates so that the path entropy is hidden. In addition, in [30] the entropy of the individual maps is calculated, whereas Blanco et al. propose to use theexpected map, a weighted average of all particle’s maps of the RBPF, what we have called accumulated map, in order to measure also the consistency of the individual maps.The predictability ofhuman motion is intensively studied in [31] and more recently in [32]. Based on the mobility patterns of mobile phone users Song et al. showed that human motion is highly predictable [31]. Here, a combination of the empirically determined user entropy and Fano’s inequality is used to evaluate predictability. However, topological constraints are not considered in their evaluation. Smith et al. refine these limits by considering in addition topological constraints like unreachable areas. They provide a lower upper bound for the predictability of human motion and use the “Geolife dataset” for their evaluation (182 individual GPS trajectories over a period of five years).None of these references handles the problem of measuring the quality ofprobabilistic maps as used in FootSLAM. More specifically, FootSLAM maps are built on a hexagonal grid. Maps based on hexagons are widely used, for example, in game programming (Charles S. Roberts 1961, [33]) for regulating movement or in mobile communications to divide a geographic area in cells (cellular network), but in such cases it is not necessary to compare the hexagon maps with one another. Also the maps do not encode probabilistic motion. Our work differs from the work above in the following points:(i)
FootSLAMprobabilistic transition maps are built on a hexagon grid, where hexagon edge transitions are counted and stored, encoding transition probabilities.(ii)
The pedestrian’s trajectory on the hexagonal grid can be viewed as a random walk on a weighted graph. It is possible to compute the entropy rate of the pedestrian’s steps on a FootSLAM hexagon map. The theory of a random walk on a finite network was introduced by Doyle and Snell in [34] further described by Lovász [35]. More information can be found in [20].(iii)
We also take into account the number of visits to each hexagonal cell.


## 2. Preliminary on FootSLAM Map Representation

### 2.1. FootSLAM Bayesian Formulation

Following the dynamic Bayesian network representation of [11] for FootSLAM, the person’s step measurements Z1:kU, what we call odometry, are processed by a RBPF to compute his steps U0:k by estimating the (correlated) errors E0:k that distort the measurements. The estimated steps are then used to infer the pedestrian’s sequence of poses P0:k within the time-invariant map M, by adding each step vector to the previous estimated pose.FootSLAM’s goal is to estimate the joint posteriorp({PUE}0:k,M∣Z1:kU) [11]. In order to compute it, FootSLAMs RBPF factorizes it into(2)pPUE0:k,M∣Z1:kU=pM∣P0:k︸mappingproblem·pPUE0:k∣Z1:kU︸localizationproblem,where the first term corresponds to the map estimation problem and the second term corresponds to the localization problem. In this paper, we focus on the mapping term, since we aim to obtain a metric to measure the quality of the maps.


### 2.2. Hexagon Transition Probabilities

FootSLAM uses a regular discretization of the 2D space to map the pedestrian’s steps. The environment is divided into a setH of Nh uniform adjacent hexagons: H={h0,h1,…,hi,…,hNh-1}. This partitioning allows for using a first-order Markov process model for the pedestrian’s motion: each next step of the pedestrian is drawn from a location dependent probability distribution that only depends on his current position (i.e., a person with no memory). We believe that the probabilities of the directions of a person’s next step are approximately independent of the past when using hexagons of radius 0.25 m to 1 m. This is because we are interested in capturing attributes of the physical environment and this does not depend on individual step lengths. The influence on human motion of features like walls, doors, and furniture is roughly on this order of scale. Smaller grids would mean that the transition probabilities of neighboring cells become more correlated (transitions would then be over counted) and larger grids would be unable to capture local features very well and would result in less predictive maps.Note that for convenience we will change the notation used in our original FootSLAM paper [11] and use the indices i and j to refer to the hexagons in the grid and the index m to refer to the particles and eliminate the explicit use of the variable e for the edges in the formulas.For each one of the hexagons in the gridhi, let j↦i refer to the index of any of the six neighboring hexagons of hi. Two hexagons hi and hj are neighbors if they are connected through one edge. Let eij refer to the edge of hexagon hi that connects it to hexagon hj and eji the edge of hj that connects it to hi (Figure 2).Figure 2
A pedestrian takes a stepUk in order to move from pose Pk-1 in hi to pose Pk in neighboring hexagon hj by crossing edge eij.The random variableM denoting the map is unknown to us. We can only estimate the probability of the map conditioned on the sequence of pedestrian’s poses P0:k, that is, p(M∣P0:k). Thanks to our hexagon discretization, the map random variable M can be decomposed as follows:(3)M=M→0,M→1,…,M→i,…,M→Nh-1,where M→i is a random variable vector of length 6 denoting the transition probabilities of the hexagon with index i. With this, the map estimation problem becomes(4)pM∣P0:k=∏ipM→i∣P0:k.Here, we have assumed that the map factors into conditionally independent components. At each hexagonal cell, M→i={Mhieij}={Mij}∀j↦i represents the set of six transition probabilities across the six edges of the hexagon hi:(5)Mij=pPk=hj∣Pk-1=hi∀j⟼i.Note that the notation Pk=hj means that the pose Pk lies in hexagon hj. As a result, Mij is the probability associated with the step taken at time k that makes the pedestrian move from pose Pk-1 in hi to pose Pk in neighboring hexagon hj by crossing edge eij (Figure 2). In addition we can state that ∑j↦i‍Mij=1∀i.


### 2.3. Learning the Transition Map

In FootSLAM, following the FastSLAM factorization [13] each particle m learns what we call atransition map by observing the poses, that is, by counting each transition that it makes from Pk-1m in hi to Pkm in hj across edge eij. Each particle stores the hexagons it visits hi along with the number of times that it crossed each one of its six edges eij, what we call thehexagon transition counters (C→):(6)M→m=hi,C→im∀hi∈H,where(7)C→im=Cijm∀j⟼i,M→m is the map of particle m, and Cijm is the number of times the particle m crossed edge eij of hexagon hi. In FootSLAM we set Cij=Cji because it is assumed that it is equally likely to cross any edge in either direction.The particle maps can be compressed in the form of an accumulated posterior map. The accumulated posterior map is calculated using the weighted sum of allNp particles maps:(8)C→icum=Cijcum∀j⟼iwith(9)Cijcum=∑m∈NpCijm·wm,where wm is the particle’s weight in the particle filter learnt during the FootSLAM estimation process. The particle’s accumulated maps can be used to estimate the distribution of the true (but unknown) edge crossing probabilities affected by human motion in the map M. As proposed in [29] we focus on the entropy of theaccumulated map in order to measure the consistency of the individual particle maps.Learning the map is based on Bayesian learning of multinomial distributions using Dirichlet priors [36]. More specifically, we assume that p(M→i∣P0:k-1) follows a Dirichlet distribution. The Dirichlet distribution of the random variable p(M→i∣P0:k-1) is the multivariate extension of the beta distribution. In contrast to our previous work, where we assumed that p(Mij∣P0:k-1) follows a beta distribution, here we assume that p(M→i∣P0:k-1) follows a Dirichlet distribution. This can be done because both distributions result in the same transition probabilities. The Dirichlet distribution is usually parametrized by a vector u→i of J positive real numbers:(10)u→i=uij∀j⟼i,with(11)ui=∑j↦iuij.The distribution can be written as(12)fx→i,u→i=1Bu→i∏j=1Jxijuij-1,where (13)Bu→i=∏j=1JΓuijΓ∑j=0Juijis the beta function and (14)Γx=∫0∞e-ttx-1dtis the gamma function, and with digamma function (15)Ψx=ddxln⁡Γx=Γ′xΓx.In our case, at each hexagonhi we have J=6 events (crossing one of the six edges) with probabilities M→i={Mij}∀j↦i. Each one of these events has been observed uij-1 times. The Dirichlet distribution represents the belief that the probabilities of the J events are Mij.We can use this assumption to compute the probability of next step by marginalizing over the map [11]:(16)pPkm∣P0:k-1m=∫MpPkm∣Pk-1m,M·pM∣P0:k-1mdM≜I,where we have made use of the fact that the pose of the pedestrian at time step k is conditionally independent on the history of poses up to k-2 conditioned on the map. If Pkm lies in hj and Pk-1m lies in hi then the above equation results in(17)I=∫Mi→pPkm∣Pk-1m,M→i·pM→i∣P0:k-1mdM→i.Using the fact thatp(Pkm∣Pk-1m,M→i)=Mij and that p(M→i∣P0:k-1m) follows a Dirichlet distribution with parameters ui→, we obtain:(18)I∝uijuim=Cij+αijCi+αim,where Cij is the number of transitions across edge eij of hexagon hi in the map of the particle m computed up to step k and Ci=∑j↦i‍Cij. The terms αij and αi=∑j↦i‍αij represent the a priori virtual counts regarding the transition counts across the edges of hexagon hi for particle m. When no other prior information is available, αij has been chosen to be αij=0.8∀{i,j,m}; that is, a uniform prior distribution, with respect to the edges, is assumed. The value 0.8 was chosen empirically from several experiments to be the best value for the prior distribution with respect to FootSLAM’s convergence behavior.


## 2.1. FootSLAM Bayesian Formulation

Following the dynamic Bayesian network representation of [11] for FootSLAM, the person’s step measurements Z1:kU, what we call odometry, are processed by a RBPF to compute his steps U0:k by estimating the (correlated) errors E0:k that distort the measurements. The estimated steps are then used to infer the pedestrian’s sequence of poses P0:k within the time-invariant map M, by adding each step vector to the previous estimated pose.FootSLAM’s goal is to estimate the joint posteriorp({PUE}0:k,M∣Z1:kU) [11]. In order to compute it, FootSLAMs RBPF factorizes it into(2)pPUE0:k,M∣Z1:kU=pM∣P0:k︸mappingproblem·pPUE0:k∣Z1:kU︸localizationproblem,where the first term corresponds to the map estimation problem and the second term corresponds to the localization problem. In this paper, we focus on the mapping term, since we aim to obtain a metric to measure the quality of the maps.


## 2.2. Hexagon Transition Probabilities

FootSLAM uses a regular discretization of the 2D space to map the pedestrian’s steps. The environment is divided into a setH of Nh uniform adjacent hexagons: H={h0,h1,…,hi,…,hNh-1}. This partitioning allows for using a first-order Markov process model for the pedestrian’s motion: each next step of the pedestrian is drawn from a location dependent probability distribution that only depends on his current position (i.e., a person with no memory). We believe that the probabilities of the directions of a person’s next step are approximately independent of the past when using hexagons of radius 0.25 m to 1 m. This is because we are interested in capturing attributes of the physical environment and this does not depend on individual step lengths. The influence on human motion of features like walls, doors, and furniture is roughly on this order of scale. Smaller grids would mean that the transition probabilities of neighboring cells become more correlated (transitions would then be over counted) and larger grids would be unable to capture local features very well and would result in less predictive maps.Note that for convenience we will change the notation used in our original FootSLAM paper [11] and use the indices i and j to refer to the hexagons in the grid and the index m to refer to the particles and eliminate the explicit use of the variable e for the edges in the formulas.For each one of the hexagons in the gridhi, let j↦i refer to the index of any of the six neighboring hexagons of hi. Two hexagons hi and hj are neighbors if they are connected through one edge. Let eij refer to the edge of hexagon hi that connects it to hexagon hj and eji the edge of hj that connects it to hi (Figure 2).Figure 2
A pedestrian takes a stepUk in order to move from pose Pk-1 in hi to pose Pk in neighboring hexagon hj by crossing edge eij.The random variableM denoting the map is unknown to us. We can only estimate the probability of the map conditioned on the sequence of pedestrian’s poses P0:k, that is, p(M∣P0:k). Thanks to our hexagon discretization, the map random variable M can be decomposed as follows:(3)M=M→0,M→1,…,M→i,…,M→Nh-1,where M→i is a random variable vector of length 6 denoting the transition probabilities of the hexagon with index i. With this, the map estimation problem becomes(4)pM∣P0:k=∏ipM→i∣P0:k.Here, we have assumed that the map factors into conditionally independent components. At each hexagonal cell, M→i={Mhieij}={Mij}∀j↦i represents the set of six transition probabilities across the six edges of the hexagon hi:(5)Mij=pPk=hj∣Pk-1=hi∀j⟼i.Note that the notation Pk=hj means that the pose Pk lies in hexagon hj. As a result, Mij is the probability associated with the step taken at time k that makes the pedestrian move from pose Pk-1 in hi to pose Pk in neighboring hexagon hj by crossing edge eij (Figure 2). In addition we can state that ∑j↦i‍Mij=1∀i.


## 2.3. Learning the Transition Map

In FootSLAM, following the FastSLAM factorization [13] each particle m learns what we call atransition map by observing the poses, that is, by counting each transition that it makes from Pk-1m in hi to Pkm in hj across edge eij. Each particle stores the hexagons it visits hi along with the number of times that it crossed each one of its six edges eij, what we call thehexagon transition counters (C→):(6)M→m=hi,C→im∀hi∈H,where(7)C→im=Cijm∀j⟼i,M→m is the map of particle m, and Cijm is the number of times the particle m crossed edge eij of hexagon hi. In FootSLAM we set Cij=Cji because it is assumed that it is equally likely to cross any edge in either direction.The particle maps can be compressed in the form of an accumulated posterior map. The accumulated posterior map is calculated using the weighted sum of allNp particles maps:(8)C→icum=Cijcum∀j⟼iwith(9)Cijcum=∑m∈NpCijm·wm,where wm is the particle’s weight in the particle filter learnt during the FootSLAM estimation process. The particle’s accumulated maps can be used to estimate the distribution of the true (but unknown) edge crossing probabilities affected by human motion in the map M. As proposed in [29] we focus on the entropy of theaccumulated map in order to measure the consistency of the individual particle maps.Learning the map is based on Bayesian learning of multinomial distributions using Dirichlet priors [36]. More specifically, we assume that p(M→i∣P0:k-1) follows a Dirichlet distribution. The Dirichlet distribution of the random variable p(M→i∣P0:k-1) is the multivariate extension of the beta distribution. In contrast to our previous work, where we assumed that p(Mij∣P0:k-1) follows a beta distribution, here we assume that p(M→i∣P0:k-1) follows a Dirichlet distribution. This can be done because both distributions result in the same transition probabilities. The Dirichlet distribution is usually parametrized by a vector u→i of J positive real numbers:(10)u→i=uij∀j⟼i,with(11)ui=∑j↦iuij.The distribution can be written as(12)fx→i,u→i=1Bu→i∏j=1Jxijuij-1,where (13)Bu→i=∏j=1JΓuijΓ∑j=0Juijis the beta function and (14)Γx=∫0∞e-ttx-1dtis the gamma function, and with digamma function (15)Ψx=ddxln⁡Γx=Γ′xΓx.In our case, at each hexagonhi we have J=6 events (crossing one of the six edges) with probabilities M→i={Mij}∀j↦i. Each one of these events has been observed uij-1 times. The Dirichlet distribution represents the belief that the probabilities of the J events are Mij.We can use this assumption to compute the probability of next step by marginalizing over the map [11]:(16)pPkm∣P0:k-1m=∫MpPkm∣Pk-1m,M·pM∣P0:k-1mdM≜I,where we have made use of the fact that the pose of the pedestrian at time step k is conditionally independent on the history of poses up to k-2 conditioned on the map. If Pkm lies in hj and Pk-1m lies in hi then the above equation results in(17)I=∫Mi→pPkm∣Pk-1m,M→i·pM→i∣P0:k-1mdM→i.Using the fact thatp(Pkm∣Pk-1m,M→i)=Mij and that p(M→i∣P0:k-1m) follows a Dirichlet distribution with parameters ui→, we obtain:(18)I∝uijuim=Cij+αijCi+αim,where Cij is the number of transitions across edge eij of hexagon hi in the map of the particle m computed up to step k and Ci=∑j↦i‍Cij. The terms αij and αi=∑j↦i‍αij represent the a priori virtual counts regarding the transition counts across the edges of hexagon hi for particle m. When no other prior information is available, αij has been chosen to be αij=0.8∀{i,j,m}; that is, a uniform prior distribution, with respect to the edges, is assumed. The value 0.8 was chosen empirically from several experiments to be the best value for the prior distribution with respect to FootSLAM’s convergence behavior.


## 3. Pedestrian’s History of Poses as a Random Walk on a Weighted Graph

In the following we describe how we can map the history of poses onto a weighted graph to apply the theory of a random walk on a weighted graph. This is a prerequisite for our entropy and entropy rate calculations that are described in Section4.Consider now the stochastic process of the history of pedestrian posesP0:k-1. This sequence of random variables isstationary, given that the distribution of the sequence p(P0:k-1) is time-invariant; that is, we can shift the history of poses by any shift l, Pl:k-1+l and the joint distribution remains the same. Furthermore, at time step k, the random variable Pk depends only on the previous one Pk-1 and is conditionally independent of all the other previous random variables P0:k-2; that is, p(Pk∣P0:k-1)=p(Pk∣Pk-1). This kind of process is called a Markov chain of order one [20].IfP0:k-1 is a Markov chain P, then Pk-1 is the state at time k-1. In our case the set of states corresponds to the pedestrian being located at any of the hexagons of the set H={h0,h1,…,hi,…,hNh-1}. In the same way the pedestrian can start his walk in any of the hexagons and move from one hexagon to the next and the associated Markov chain can start in any of the states and can move successively from one state to the next (Figure 3). Each one of these moves is calledstep ortransition.Figure 3
Undirected graph (b) associated with the FootSLAM transition map (a). Each visited hexagon (in gray) is related to a state in the graph. The outer hexagons around the visited ones are drawn with a dashed line and represented by the statehout. The edges crossed by the pedestrian are marked in blue and represented in the graph by blue links. The pedestrian can move from one state (hexagon) to another with aconductance of cij, as shown next to each link.
(a) (b)In addition, since the probabilityp(Pk=hj∣Pk-1=hi) does not depend on k, the Markov chain is time-invariant. Thus, the chain can be defined by the initial distribution x→0=p(P0) and the so-calledtransition matrixP→. The transition matrix represents all possible transitions from any hexagon (state) in the hexagonal grid (Markov chain) to any other hexagon (state). The transition matrix for our transition map is therefore a Nh×Nh matrix:(19)P→=p0,0⋯p0,Nh-1⋮⋱⋮pNh-1,0⋯pNh-1,Nh-1.Clearly, each row of the transition matrix will consist of six elements unequal to zero at the connecting hexagons and zeros for the remaining elements. Note that we assume that, with every step the pedestrian takes, he is located at a different hexagon; that is,pii=0. Furthermore, any Markov transition matrix has to fulfill the condition (20)∑jpij=1∀j=0,…,Nh-1.FootSLAM maps consist of a set of visited hexagons with their corresponding edge transition counters (6). However, the pedestrian can leave the mapped area with a positive probability (thanks to the α term in (18)), making our transition map virtually infinite. Nevertheless, we can assume that the transition map lies on a globe (Figure 4) so that the associated Markov chain is finite. Proceeding like this, the following properties hold:(i)
The grid of hexagons has no borders but yet isfinite; that is, the Markov chain is finite. Furthermore, we can study the subset of states of the Markov chain corresponding to the hexagons that the pedestrian visited (in dark grey in Figures 4 and 3).(ii)
The Markov chain represented by the grid of hexagons isirreducible (also called ergodic): it is possible to reach any hexagon from any other hexagon in a finite number of steps.(iii)
The Markov chain isaperiodic; that is, the states do not return to the starting position with a certain period.(iv)
The Markov chain isrecurrent; that is, with a probability of one it is possible to return to a hexagon within finite time.Figure 4
Globe representation of a FootSLAM map obtained in an office environment. The hexagons visited by the pedestrian are marked in darker colors.For any irreducible and aperiodic Markov chain with transition matrixP→, there exists a unique stationary distribution π→={πi}∀hi∈H that is independent from the initial distribution x→0 of the chain and that satisfies [20, 37](21)π→P→=π→.The sequence of pedestrian poses conditioned on the map actually falls into the Markov chain category of random walk (poses) on a weighted graph or network (map) [20, 38]. A network is defined as an undirected graph G with a set of vertices (nodes) corresponding to the states and a set of links that connect the nodes. Each link is associated with a nonnegative weight cij=cji, usually calledconductance in electric networks. It is easy to verify that in FootSLAM these conductances can be defined as cij=Cij+αij=cji for any pair of neighboring hexagons, since Cij=Cji (it is equally likely to cross edges eij and eji) and αij=0.8∀i,j.The random walkP0:k-1=P0:k-1 corresponds to a sequence of hexagons (nodes in the graph). At each time step k-1 with Pk-1=hi, the next connecting hexagon Pk=hj is chosen according to a probability proportional to the weights cij. Thus, we can define the transition probabilities as follows [20, 38]:(22)pij=cijci=Cij+αijCi+αi,where ci=∑j‍cij.Such a process is called arandom walk on the weighted graph G with edge weights {cij} [38]. If we define (23)cG=∑i∈Hci=∑i∈HCi+αi=CM+αMwith CM=∑i∈H‍Ci and αM=∑i∈H‍αi, and(24)πi=cicG=Ci+αiCM+αM,such a Markov chain has the additional property that it is reversible with respect to the probability π→; that is, (25)πipij=πjpji∀i,j.As a result, π→ represents the unique stationary distribution for the reversible Markov chain [37].Our goal in this paper is to derive a metric to compare thegoodness characteristics of different FootSLAM transition maps. For this purpose, we now introduce the concepts of map entropy, step entropy rate, relative map entropy, and relative step entropy rate within the context of FootSLAM. Note that in the following we will omit the indices m or cum since all the equations apply for both a particle’s transition map and the accumulated map.


## 4. Entropy and Relative Entropy

### 4.1. Map Entropy and Step Entropy Rate

#### 4.1.1. Map Entropy Conditioned on the Sequence of Poses

In this section we address the computation of the uncertainty of the mapM conditioned on the sequence of poses P0:k=P0:k, which can be calculated as the average of the hexagon entropies:(26)ħM∣P0:k=P0:k=1Nh∑i∈HħM→i∣P0:k=P0:k,given that the discretization into a grid of hexagons renders the local maps M→i independent of each other (4). Here, P0:k refers to the output of a genie that we approximate with our FootSLAM estimated sequence of poses assuming convergence of the FootSLAM algorithm. The entropy ħ(p(M∣P0:k=P0:k)) takes into account how many times a transition of the map is measured and how certain a learned transition is. In the following for convenience we abbreviate the condition P0:k=P0:k with P0:k.The entropy measures the uncertainty of a random variable as the average amount of information needed to describe it [20]. To compute the entropy of p(M→i∣P0:k) we rely on the assumption that p(M→i∣P0:k) follows a Dirichlet distribution, which is a continuous distribution. We now introduce the formula for the entropy of a continuous random variable x, usually calleddifferential entropy, which is [20](27)ħx=-∫x=-∞x=∞pxlog⁡pxdx.If the logarithm has 2 as base, then the entropy is expressed in bits. In this paper, we will use the unit bits. Note that the range of the entropy defined in this manner is (-∞,0] bits. The lower the entropy value, the lower the uncertainty about the random variable.In our casep(x)=p(M→i∣P0:k) follows a Dirichlet distribution with parameters ui→={uij}={Cij+αij}∀j↦i. As a result, the differential entropy has the following closed form [39]:(28)ħM→i∣P0:k-1=log⁡BCi+αi+Ci+αi-6ΨCi+αi-∑j↦iCij+αij-1ΨCij+αij,with the same beta, gamma, and digamma functions definitions as in Section 2.3. The maximum entropy of the total map (obtained by inserting (28) in (26)) occurs for Cij+αij=1∀j↦i and has a value of ħ(M→i∣P0:k-1)=-4.79bits.


#### 4.1.2. Entropy Rate of the Pedestrian’s Steps

Consider now the Markov chainP of the sequence of pedestrian poses P0:k=P0:k on one estimate M of the map. The appropriate question to address is therate of growth of its entropy with k.The entropy rate of a stationary stochastic processX0:k is [20](29)HX=limk→∞HXk∣X0:k-1.In the case of our stationary Markov chainP with stationary distribution π→ and transition matrix P→, the entropy rate is reduced to [20](30)HP=limk→∞HPk∣P0:k-1=limk→∞HPk∣Pk-1=∑hi∈Hπi∑j↦iHPk∣Pk-1,with(31)HPk∣Pk-1=-pijlog⁡pij.By inserting (22) and (24) in (31) we obtain(32)HP=-∑i∈HCi+αiCM+αM∑j↦iCij+αijCi+αilog⁡Cij+αijCi+αi.The entropy rate of the sequence of pedestrian poses provides us with the stationary growing rate of the step entropy, that is, the uncertainty regarding each next step.The maximum entropy occurs with an equally probable Markov chain (πi=1/Nh∀is.t.hi∈H) with uniform transition probabilities (pij=1/6∀j↦i) and has a value of H(P)=2.584bits.


### 4.2. Relative Entropy and Relative Entropy Rate

#### 4.2.1. Relative Map Entropy Conditioned on the Sequence of Poses

The relative entropy (or Kullback-Leibler (KL) divergence),dKL(p∥q), provides a metric of the difference between two probability density functions p(x) and q(x) of the same random variable x. The KL divergence is a measure of the inefficiency when q(x) is used as an approximation of the true distribution p(x) [20]. To describe p(x) with the approximating distribution q(x) we will need (33)ħpx+dKLpx∥qxbits,instead of ħ(p(x))bits. With this definition dKL is always greater than 0 and 0 if and only if p(x)=q(x).The relative entropy between two distributionsp and q of a continuous random variable x is defined as [20](34)dKLp∥q=∫-∞∞pxlog⁡pxqxdx.In our case, we have two sequences of pedestrian posesP0:kp=P0:kp and P0:kq=P0:kq, each yielding an estimate of the same map p=p(Mp∣P0:k) and q=p(Mq∣P0:kq), respectively, and our goal is to compute the relative entropy between them.Similarly to the derivation of the map entropy conditioned on the sequence of poses in Section4.1.1, to compute the map relative entropy we rely on the assumption that the local maps at each hexagon are independent of each other, thus yielding(35)dKLp∥q=∑i∈HMpdKLpi∥qi,where (36)pi=pM→ip∣P0:kp,qi=pM→iq∣P0:kq.Furthermore, we assume thatpi and qi follow each a Dirichlet distribution with parameters ui→={uij}={Cijp+αijp} and vi→={vij}={Cijq+αijq}, respectively. Then resolving (34) for a Dirichlet distribution we obtain [40](37)dKLp∥q=∑ilog⁡ΓCip+αipΓCiq+αiq+∑j↦ilog⁡ΓCijp+αijpΓCijq+αijq+∑j↦iCijq+αijq-Cijp-αijp·ΨCijq+αijq-ΨCiq+αiq,with the same functions definitions as in Section 2.3.This equation for the relative entropy provides us with the difference between two distributions of the same map and therefore can be used on a hexagon basis to detect similarities.


#### 4.2.2. Relative Entropy Rate of the Pedestrian’s Step

The KL divergence rate between two stationary Markov chainsP and Q of two different sequences P0:kp=P0:kp and P0:kq=P0:kq of the stochastic process P0:k with transition matrices P→ and Q→, respectively, can be computed as [38](38)DKLP∥Q=limk→∞DKLPkp∣P0:k-1p∥Pkq∣P0:k-1q=∑i∈Pπip∑j∈Qpijlog⁡pijqij,where π→p={πip}, i∈P is the unique stationary distribution of P→.In our case, letP0:k-1p and P0:k-1q be two different histories of pedestrian poses, each one corresponding to the Markov chains P and Q with transition matrices P→ and Q→, respectively, and each one generating one instance of the map, Mp and Mq. With these assumptions, the following equation holds:(39)DKLP∥Q=∑hi∈HMpπip∑j↦ipijlog⁡pijqij,where HMp is the set of hexagons of map Mp.Inserting (22) and (24) in (39) we finally obtain(40)DKLP∥Q=∑hi∈HMpCip+αipCMp+αMp·∑j↦iCijp+αijpCip+αiplog⁡Cijp+αijp/Cip+αipCijq+αijq/Ciq+αiq,where the superindices p and q indicate that the counters belong to map Mp and map Mq, respectively.


## 4.1. Map Entropy and Step Entropy Rate

### 4.1.1. Map Entropy Conditioned on the Sequence of Poses

In this section we address the computation of the uncertainty of the mapM conditioned on the sequence of poses P0:k=P0:k, which can be calculated as the average of the hexagon entropies:(26)ħM∣P0:k=P0:k=1Nh∑i∈HħM→i∣P0:k=P0:k,given that the discretization into a grid of hexagons renders the local maps M→i independent of each other (4). Here, P0:k refers to the output of a genie that we approximate with our FootSLAM estimated sequence of poses assuming convergence of the FootSLAM algorithm. The entropy ħ(p(M∣P0:k=P0:k)) takes into account how many times a transition of the map is measured and how certain a learned transition is. In the following for convenience we abbreviate the condition P0:k=P0:k with P0:k.The entropy measures the uncertainty of a random variable as the average amount of information needed to describe it [20]. To compute the entropy of p(M→i∣P0:k) we rely on the assumption that p(M→i∣P0:k) follows a Dirichlet distribution, which is a continuous distribution. We now introduce the formula for the entropy of a continuous random variable x, usually calleddifferential entropy, which is [20](27)ħx=-∫x=-∞x=∞pxlog⁡pxdx.If the logarithm has 2 as base, then the entropy is expressed in bits. In this paper, we will use the unit bits. Note that the range of the entropy defined in this manner is (-∞,0] bits. The lower the entropy value, the lower the uncertainty about the random variable.In our casep(x)=p(M→i∣P0:k) follows a Dirichlet distribution with parameters ui→={uij}={Cij+αij}∀j↦i. As a result, the differential entropy has the following closed form [39]:(28)ħM→i∣P0:k-1=log⁡BCi+αi+Ci+αi-6ΨCi+αi-∑j↦iCij+αij-1ΨCij+αij,with the same beta, gamma, and digamma functions definitions as in Section 2.3. The maximum entropy of the total map (obtained by inserting (28) in (26)) occurs for Cij+αij=1∀j↦i and has a value of ħ(M→i∣P0:k-1)=-4.79bits.


### 4.1.2. Entropy Rate of the Pedestrian’s Steps

Consider now the Markov chainP of the sequence of pedestrian poses P0:k=P0:k on one estimate M of the map. The appropriate question to address is therate of growth of its entropy with k.The entropy rate of a stationary stochastic processX0:k is [20](29)HX=limk→∞HXk∣X0:k-1.In the case of our stationary Markov chainP with stationary distribution π→ and transition matrix P→, the entropy rate is reduced to [20](30)HP=limk→∞HPk∣P0:k-1=limk→∞HPk∣Pk-1=∑hi∈Hπi∑j↦iHPk∣Pk-1,with(31)HPk∣Pk-1=-pijlog⁡pij.By inserting (22) and (24) in (31) we obtain(32)HP=-∑i∈HCi+αiCM+αM∑j↦iCij+αijCi+αilog⁡Cij+αijCi+αi.The entropy rate of the sequence of pedestrian poses provides us with the stationary growing rate of the step entropy, that is, the uncertainty regarding each next step.The maximum entropy occurs with an equally probable Markov chain (πi=1/Nh∀is.t.hi∈H) with uniform transition probabilities (pij=1/6∀j↦i) and has a value of H(P)=2.584bits.


## 4.1.1. Map Entropy Conditioned on the Sequence of Poses

In this section we address the computation of the uncertainty of the mapM conditioned on the sequence of poses P0:k=P0:k, which can be calculated as the average of the hexagon entropies:(26)ħM∣P0:k=P0:k=1Nh∑i∈HħM→i∣P0:k=P0:k,given that the discretization into a grid of hexagons renders the local maps M→i independent of each other (4). Here, P0:k refers to the output of a genie that we approximate with our FootSLAM estimated sequence of poses assuming convergence of the FootSLAM algorithm. The entropy ħ(p(M∣P0:k=P0:k)) takes into account how many times a transition of the map is measured and how certain a learned transition is. In the following for convenience we abbreviate the condition P0:k=P0:k with P0:k.The entropy measures the uncertainty of a random variable as the average amount of information needed to describe it [20]. To compute the entropy of p(M→i∣P0:k) we rely on the assumption that p(M→i∣P0:k) follows a Dirichlet distribution, which is a continuous distribution. We now introduce the formula for the entropy of a continuous random variable x, usually calleddifferential entropy, which is [20](27)ħx=-∫x=-∞x=∞pxlog⁡pxdx.If the logarithm has 2 as base, then the entropy is expressed in bits. In this paper, we will use the unit bits. Note that the range of the entropy defined in this manner is (-∞,0] bits. The lower the entropy value, the lower the uncertainty about the random variable.In our casep(x)=p(M→i∣P0:k) follows a Dirichlet distribution with parameters ui→={uij}={Cij+αij}∀j↦i. As a result, the differential entropy has the following closed form [39]:(28)ħM→i∣P0:k-1=log⁡BCi+αi+Ci+αi-6ΨCi+αi-∑j↦iCij+αij-1ΨCij+αij,with the same beta, gamma, and digamma functions definitions as in Section 2.3. The maximum entropy of the total map (obtained by inserting (28) in (26)) occurs for Cij+αij=1∀j↦i and has a value of ħ(M→i∣P0:k-1)=-4.79bits.


## 4.1.2. Entropy Rate of the Pedestrian’s Steps

Consider now the Markov chainP of the sequence of pedestrian poses P0:k=P0:k on one estimate M of the map. The appropriate question to address is therate of growth of its entropy with k.The entropy rate of a stationary stochastic processX0:k is [20](29)HX=limk→∞HXk∣X0:k-1.In the case of our stationary Markov chainP with stationary distribution π→ and transition matrix P→, the entropy rate is reduced to [20](30)HP=limk→∞HPk∣P0:k-1=limk→∞HPk∣Pk-1=∑hi∈Hπi∑j↦iHPk∣Pk-1,with(31)HPk∣Pk-1=-pijlog⁡pij.By inserting (22) and (24) in (31) we obtain(32)HP=-∑i∈HCi+αiCM+αM∑j↦iCij+αijCi+αilog⁡Cij+αijCi+αi.The entropy rate of the sequence of pedestrian poses provides us with the stationary growing rate of the step entropy, that is, the uncertainty regarding each next step.The maximum entropy occurs with an equally probable Markov chain (πi=1/Nh∀is.t.hi∈H) with uniform transition probabilities (pij=1/6∀j↦i) and has a value of H(P)=2.584bits.


## 4.2. Relative Entropy and Relative Entropy Rate

### 4.2.1. Relative Map Entropy Conditioned on the Sequence of Poses

The relative entropy (or Kullback-Leibler (KL) divergence),dKL(p∥q), provides a metric of the difference between two probability density functions p(x) and q(x) of the same random variable x. The KL divergence is a measure of the inefficiency when q(x) is used as an approximation of the true distribution p(x) [20]. To describe p(x) with the approximating distribution q(x) we will need (33)ħpx+dKLpx∥qxbits,instead of ħ(p(x))bits. With this definition dKL is always greater than 0 and 0 if and only if p(x)=q(x).The relative entropy between two distributionsp and q of a continuous random variable x is defined as [20](34)dKLp∥q=∫-∞∞pxlog⁡pxqxdx.In our case, we have two sequences of pedestrian posesP0:kp=P0:kp and P0:kq=P0:kq, each yielding an estimate of the same map p=p(Mp∣P0:k) and q=p(Mq∣P0:kq), respectively, and our goal is to compute the relative entropy between them.Similarly to the derivation of the map entropy conditioned on the sequence of poses in Section4.1.1, to compute the map relative entropy we rely on the assumption that the local maps at each hexagon are independent of each other, thus yielding(35)dKLp∥q=∑i∈HMpdKLpi∥qi,where (36)pi=pM→ip∣P0:kp,qi=pM→iq∣P0:kq.Furthermore, we assume thatpi and qi follow each a Dirichlet distribution with parameters ui→={uij}={Cijp+αijp} and vi→={vij}={Cijq+αijq}, respectively. Then resolving (34) for a Dirichlet distribution we obtain [40](37)dKLp∥q=∑ilog⁡ΓCip+αipΓCiq+αiq+∑j↦ilog⁡ΓCijp+αijpΓCijq+αijq+∑j↦iCijq+αijq-Cijp-αijp·ΨCijq+αijq-ΨCiq+αiq,with the same functions definitions as in Section 2.3.This equation for the relative entropy provides us with the difference between two distributions of the same map and therefore can be used on a hexagon basis to detect similarities.


### 4.2.2. Relative Entropy Rate of the Pedestrian’s Step

The KL divergence rate between two stationary Markov chainsP and Q of two different sequences P0:kp=P0:kp and P0:kq=P0:kq of the stochastic process P0:k with transition matrices P→ and Q→, respectively, can be computed as [38](38)DKLP∥Q=limk→∞DKLPkp∣P0:k-1p∥Pkq∣P0:k-1q=∑i∈Pπip∑j∈Qpijlog⁡pijqij,where π→p={πip}, i∈P is the unique stationary distribution of P→.In our case, letP0:k-1p and P0:k-1q be two different histories of pedestrian poses, each one corresponding to the Markov chains P and Q with transition matrices P→ and Q→, respectively, and each one generating one instance of the map, Mp and Mq. With these assumptions, the following equation holds:(39)DKLP∥Q=∑hi∈HMpπip∑j↦ipijlog⁡pijqij,where HMp is the set of hexagons of map Mp.Inserting (22) and (24) in (39) we finally obtain(40)DKLP∥Q=∑hi∈HMpCip+αipCMp+αMp·∑j↦iCijp+αijpCip+αiplog⁡Cijp+αijp/Cip+αipCijq+αijq/Ciq+αiq,where the superindices p and q indicate that the counters belong to map Mp and map Mq, respectively.


## 4.2.1. Relative Map Entropy Conditioned on the Sequence of Poses

The relative entropy (or Kullback-Leibler (KL) divergence),dKL(p∥q), provides a metric of the difference between two probability density functions p(x) and q(x) of the same random variable x. The KL divergence is a measure of the inefficiency when q(x) is used as an approximation of the true distribution p(x) [20]. To describe p(x) with the approximating distribution q(x) we will need (33)ħpx+dKLpx∥qxbits,instead of ħ(p(x))bits. With this definition dKL is always greater than 0 and 0 if and only if p(x)=q(x).The relative entropy between two distributionsp and q of a continuous random variable x is defined as [20](34)dKLp∥q=∫-∞∞pxlog⁡pxqxdx.In our case, we have two sequences of pedestrian posesP0:kp=P0:kp and P0:kq=P0:kq, each yielding an estimate of the same map p=p(Mp∣P0:k) and q=p(Mq∣P0:kq), respectively, and our goal is to compute the relative entropy between them.Similarly to the derivation of the map entropy conditioned on the sequence of poses in Section4.1.1, to compute the map relative entropy we rely on the assumption that the local maps at each hexagon are independent of each other, thus yielding(35)dKLp∥q=∑i∈HMpdKLpi∥qi,where (36)pi=pM→ip∣P0:kp,qi=pM→iq∣P0:kq.Furthermore, we assume thatpi and qi follow each a Dirichlet distribution with parameters ui→={uij}={Cijp+αijp} and vi→={vij}={Cijq+αijq}, respectively. Then resolving (34) for a Dirichlet distribution we obtain [40](37)dKLp∥q=∑ilog⁡ΓCip+αipΓCiq+αiq+∑j↦ilog⁡ΓCijp+αijpΓCijq+αijq+∑j↦iCijq+αijq-Cijp-αijp·ΨCijq+αijq-ΨCiq+αiq,with the same functions definitions as in Section 2.3.This equation for the relative entropy provides us with the difference between two distributions of the same map and therefore can be used on a hexagon basis to detect similarities.


## 4.2.2. Relative Entropy Rate of the Pedestrian’s Step

The KL divergence rate between two stationary Markov chainsP and Q of two different sequences P0:kp=P0:kp and P0:kq=P0:kq of the stochastic process P0:k with transition matrices P→ and Q→, respectively, can be computed as [38](38)DKLP∥Q=limk→∞DKLPkp∣P0:k-1p∥Pkq∣P0:k-1q=∑i∈Pπip∑j∈Qpijlog⁡pijqij,where π→p={πip}, i∈P is the unique stationary distribution of P→.In our case, letP0:k-1p and P0:k-1q be two different histories of pedestrian poses, each one corresponding to the Markov chains P and Q with transition matrices P→ and Q→, respectively, and each one generating one instance of the map, Mp and Mq. With these assumptions, the following equation holds:(39)DKLP∥Q=∑hi∈HMpπip∑j↦ipijlog⁡pijqij,where HMp is the set of hexagons of map Mp.Inserting (22) and (24) in (39) we finally obtain(40)DKLP∥Q=∑hi∈HMpCip+αipCMp+αMp·∑j↦iCijp+αijpCip+αiplog⁡Cijp+αijp/Cip+αipCijq+αijq/Ciq+αiq,where the superindices p and q indicate that the counters belong to map Mp and map Mq, respectively.


## 5. Experimental Results

### 5.1. Experiment Settings

#### 5.1.1. General Settings

Two pedestrians have collected a total of 6 datasets{D1,…,D6} within the same office environment (depicted in Figure 5). In these datasets, the pedestrians walked 8, 6.2, 5.5, 5.3, 13.7, and 25.7 minutes, respectively, wearing a foot mounted IMU (XSens MTx). The distances walked were 406, 326, 257, 310, 750, and 978 meters, respectively. The data were preprocessed by a ZUPT aided unscented Kalman Filter [17] and then used as input for the FootSLAM algorithm, which was executed offline. In our experiment, the radius of the hexagons was r=0.5m and the number of particles used in the RBPF was Np=10000. The resulting posterior maps are denoted as {M1,…,M6}. It should be noted that the main contribution of this paper is the analysis of FootSLAM maps regardless of the underlying accuracy of the odometry, as long as convergence can be attained. As has been shown in [14] FootSLAM works also, for example, with pedestrian odometry generated from a sensor carried in a pocket.Figure 5
The floor plan of the second floor of the office building, where the walks were conducted.Having introduced the general settings, we will next describe the problems that arise when comparing maps that cover different areas using the entropy as a metric. After that we will provide a discussion about the advantages/disadvantages of the differential entropy versus the entropy rate. In the following, let mapsize refer to the number of hexagons Nh visited by the pedestrian, which can be directly related to the area covered by the walk.


#### 5.1.2. Dependence of the Entropy with the Size of the Map

The map entropy of (26) and step entropy rate of (30) depend on the size of the map. If we wish to compare a set of Nw maps M={M1,…,MNw}, we need to make sure that they cover the same area. We can achieve this by adding to each map the the hexagons visited by other maps that are not included in that map (with their transition counters set to zero, but keeping the α terms). For instance, Figure 6 shows the map area covered by 6 maps M1–M6 (depicted in Figure 8). All visited hexagons of all maps are combined in a total map with Nhc hexagons.Figure 6
Total overlapping map built from a combination of FootSLAM results ofD1–D6. The accumulated posterior maps of D1–D6 can be seen in Figure 8.


#### 5.1.3. Differential Entropy versus Entropy Rate

The advantage of using the differential map entropy is that it reflects better the total number of visits per hexagon, as we shall show. Maps corresponding to walks that revisit areas more often will result in lower entropy. To illustrate that, we have applied differentmap strengthening factors to map M6 and computed its differential entropy (Figure 7). The objective of the map strengthening factor is to increase (or decrease) the belief of the map by multiplying the transition counters with the map strengthening factor. Figure 7 shows that the differential entropy decreases linearly with the logarithm of the map strengthening factor despite the fact that we only increased the total counters of each hexagon and did not change the relationship of the edge transition probabilities.Figure 7
Differential map entropy conditioned on the sequence of poses (28) of map M6 for different map strengthening factors. For a map strengthening factor greater than 100, the differential entropy decreases linearly with the logarithm of the strengthening factor.Figure 8
Accumulated posterior map ofD1–D6. The starting position is marked in red and is well known. The respective map entropy ħ(M∣P0:k) and the step entropy rate values H(Pk∣P0:k-1) of the maps M1 to M6 are shown in the text boxes.
(a)
M 1 (b)
M 2 (c)
M 3 (d)
M 4 (e)
M 5 (f)
M 6


### 5.2. Entropy and KL-Divergence Results

#### 5.2.1. Map Entropy and Step Entropy Rate

We are interested in obtaining the uncertainty of each one of the maps. We can do this by computing, for each map, the map entropy and the step entropy rate conditioned on the poses, respectively. Figure8 shows visual presentations of the resulting posterior maps of our 6 datasets. The starting position of the pedestrian is shown as a red hexagon. The corresponding map entropy and the step entropy rate values of the maps M1 to M6 are shown in the text boxes of Figure 8. We have computed, for each map, the entropy of all hexagons depicted in Figure 6. We could also use a bounding box around all maps, but the differences between the entropy values will be smaller due to the added hexagons with maximum entropy. M6 shows the lowest map entropy and step entropy rate. The results of M6 are closely followed by M5, and M3 presents the highest entropy, reflecting the uncertainty over the large unvisited areas. This corresponds to visual inspection of Figure 8: map M6 is the most extensive and accurate and M3 the least. The distinction between the map entropy and the step entropy rate is reflected in the range of values; for example, the difference between maps M3 and M6 is 0.31 and 0.11 for the map entropy and the step entropy rate, respectively. These 6 maps do not differ very much in the number of transition counters per hexagon; therefore, the range of the differential entropy values is not significant. The difference between the entropies would be more prominent if, for example, one walk had revisited some areas much more often than the others.We have illustrated the behavior of the differential entropy (Figure9) and the entropy rate (Figure 10) over time for dataset D4. In addition, visual representations of the best and accumulated posterior distributions resulting from our FootSLAM estimator are shown in Figure 11 for the time indices k equal to 48, 50, 88, 128, and 154. Here, the best particle map is depicted in blue and the accumulated map in gray. The entropy calculations are based on the map size at each time index. From Figures 9 and 10 we can infer that during the estimation the entropy is generally decreasing as expected. Before time index k=50 (Figure 11(a)) new area is explored. At time index k=50 the estimations converge (Figure 11(b)) which is reflected in the high decrease of entropy. After this, new area is explored resulting in an increase of the entropy. This is shown in Figure 11(c) as light gray area. After some time some of the particle map hypotheses will be rewarded and others will be killed due to resampling (e.g., time index k=128 and k=154, Figures 11(d) and 11(e)), with a sudden decrease in entropy. One can see from the figures that the small jumps in the curves reflect very well the exploring and convergence events.Figure 9
Differential entropy for datasetD4 over time. At the beginning the entropy is maximum: -4.78bits. At time index k=50 the estimations converge (see also Figure 11(b)) which is reflected in the high decrease of entropy at this time index. After that, new area is explored resulting in an increase before it decreases again. The jumps reflect very well the exploring and convergence situations.Figure 10
Entropy rate for datasetD4 over time. At the beginning the entropy is maximum: 2.58bits. The results are similarly to Figure 9, but the range of values is lower than with the differential entropy.Figure 11
Accumulated posterior map obtained by FootSLAM estimation at time indicesk equal to 48, 50, 88, 128, and 154. Different shades of gray encode the weight of the corresponding particle (darker means higher weight). The current position is marked in red. The best posterior map is shown in blue.
(a)
Time indexk=48 (b)
Time indexk=50 (c)
Time indexk=88 (d)
Time indexk=128 (e)
Time indexk=154


#### 5.2.2. KL Divergence between Two Maps

In this section we are interested in showing the KL divergence between two maps as we rotate and translate one of them. As an example, we chooseM5 and M6 assuming that both maps fit into each other at the beginning.We now apply different transformations toM5 (rotations and translations in x- and y-direction) [19] and compute the KL divergence between the M5 transformed and M6 unchanged. Figures 12 and 13 show the results for the KL divergence (37) for different shifts of M5 along the x-axis and along the y-axis, respectively.Figure 12
Relative entropy between two mapsM6 and M5 translated along the x-axis. The peaks down to a minimum at 0 shift shows the best fit of the two maps. The maps were already aligned before shifting M5.Figure 13
Relative entropy between two mapsM6 and M5 translated along the y-axis. The maps were already aligned before shifting M5. The peak is more steep along the y-axis than along the x-axis due to the building structure and the direction of the shift.From the shifts alongx- and y-axis one can see peaks down to a minimum at 0 shift in both cases (as expected, because they were already aligned) where the two maps fit best. The main difference between the two figures is that the KL divergence grows slowly with the shifts along the x-axis, since the maps still share a portion of the corridor (with similar transitions). Therefore, the peak is more steep with the transformation along the y-axis.Finally, Figure14 shows the KL divergence between M5 rotated a the starting hexagon (in red) and M6 unchanged. The minimum is reached when the two maps are aligned (M5 unchanged), but we can see that towards the rotation value of π radians there is a local minimum due to the symmetries in the building that make the left side of the corridor fall onto the right side of the corridor and vice versa. These results suggest that we can use the KL divergence between two maps to find the best geometric transformation that places the two maps within the same coordinate system as an alternative for the Bayesian correlation function proposed in [19]. Similar results but with smaller differences can be obtained with the relative entropy rate of the pedestrian’s step (40).Figure 14
Relative entropy between two mapsM6 and M5, where M5 is rotated about its starting position. The peak down to a minimum at 0 shift shows the best fit of the two maps. One can see that towards the rotation value of π radians there is a local minimum due to the symmetries of the building.


## 5.1. Experiment Settings

### 5.1.1. General Settings

Two pedestrians have collected a total of 6 datasets{D1,…,D6} within the same office environment (depicted in Figure 5). In these datasets, the pedestrians walked 8, 6.2, 5.5, 5.3, 13.7, and 25.7 minutes, respectively, wearing a foot mounted IMU (XSens MTx). The distances walked were 406, 326, 257, 310, 750, and 978 meters, respectively. The data were preprocessed by a ZUPT aided unscented Kalman Filter [17] and then used as input for the FootSLAM algorithm, which was executed offline. In our experiment, the radius of the hexagons was r=0.5m and the number of particles used in the RBPF was Np=10000. The resulting posterior maps are denoted as {M1,…,M6}. It should be noted that the main contribution of this paper is the analysis of FootSLAM maps regardless of the underlying accuracy of the odometry, as long as convergence can be attained. As has been shown in [14] FootSLAM works also, for example, with pedestrian odometry generated from a sensor carried in a pocket.Figure 5
The floor plan of the second floor of the office building, where the walks were conducted.Having introduced the general settings, we will next describe the problems that arise when comparing maps that cover different areas using the entropy as a metric. After that we will provide a discussion about the advantages/disadvantages of the differential entropy versus the entropy rate. In the following, let mapsize refer to the number of hexagons Nh visited by the pedestrian, which can be directly related to the area covered by the walk.


### 5.1.2. Dependence of the Entropy with the Size of the Map

The map entropy of (26) and step entropy rate of (30) depend on the size of the map. If we wish to compare a set of Nw maps M={M1,…,MNw}, we need to make sure that they cover the same area. We can achieve this by adding to each map the the hexagons visited by other maps that are not included in that map (with their transition counters set to zero, but keeping the α terms). For instance, Figure 6 shows the map area covered by 6 maps M1–M6 (depicted in Figure 8). All visited hexagons of all maps are combined in a total map with Nhc hexagons.Figure 6
Total overlapping map built from a combination of FootSLAM results ofD1–D6. The accumulated posterior maps of D1–D6 can be seen in Figure 8.


### 5.1.3. Differential Entropy versus Entropy Rate

The advantage of using the differential map entropy is that it reflects better the total number of visits per hexagon, as we shall show. Maps corresponding to walks that revisit areas more often will result in lower entropy. To illustrate that, we have applied differentmap strengthening factors to map M6 and computed its differential entropy (Figure 7). The objective of the map strengthening factor is to increase (or decrease) the belief of the map by multiplying the transition counters with the map strengthening factor. Figure 7 shows that the differential entropy decreases linearly with the logarithm of the map strengthening factor despite the fact that we only increased the total counters of each hexagon and did not change the relationship of the edge transition probabilities.Figure 7
Differential map entropy conditioned on the sequence of poses (28) of map M6 for different map strengthening factors. For a map strengthening factor greater than 100, the differential entropy decreases linearly with the logarithm of the strengthening factor.Figure 8
Accumulated posterior map ofD1–D6. The starting position is marked in red and is well known. The respective map entropy ħ(M∣P0:k) and the step entropy rate values H(Pk∣P0:k-1) of the maps M1 to M6 are shown in the text boxes.
(a)
M 1 (b)
M 2 (c)
M 3 (d)
M 4 (e)
M 5 (f)
M 6


## 5.1.1. General Settings

Two pedestrians have collected a total of 6 datasets{D1,…,D6} within the same office environment (depicted in Figure 5). In these datasets, the pedestrians walked 8, 6.2, 5.5, 5.3, 13.7, and 25.7 minutes, respectively, wearing a foot mounted IMU (XSens MTx). The distances walked were 406, 326, 257, 310, 750, and 978 meters, respectively. The data were preprocessed by a ZUPT aided unscented Kalman Filter [17] and then used as input for the FootSLAM algorithm, which was executed offline. In our experiment, the radius of the hexagons was r=0.5m and the number of particles used in the RBPF was Np=10000. The resulting posterior maps are denoted as {M1,…,M6}. It should be noted that the main contribution of this paper is the analysis of FootSLAM maps regardless of the underlying accuracy of the odometry, as long as convergence can be attained. As has been shown in [14] FootSLAM works also, for example, with pedestrian odometry generated from a sensor carried in a pocket.Figure 5
The floor plan of the second floor of the office building, where the walks were conducted.Having introduced the general settings, we will next describe the problems that arise when comparing maps that cover different areas using the entropy as a metric. After that we will provide a discussion about the advantages/disadvantages of the differential entropy versus the entropy rate. In the following, let mapsize refer to the number of hexagons Nh visited by the pedestrian, which can be directly related to the area covered by the walk.


## 5.1.2. Dependence of the Entropy with the Size of the Map

The map entropy of (26) and step entropy rate of (30) depend on the size of the map. If we wish to compare a set of Nw maps M={M1,…,MNw}, we need to make sure that they cover the same area. We can achieve this by adding to each map the the hexagons visited by other maps that are not included in that map (with their transition counters set to zero, but keeping the α terms). For instance, Figure 6 shows the map area covered by 6 maps M1–M6 (depicted in Figure 8). All visited hexagons of all maps are combined in a total map with Nhc hexagons.Figure 6
Total overlapping map built from a combination of FootSLAM results ofD1–D6. The accumulated posterior maps of D1–D6 can be seen in Figure 8.


## 5.1.3. Differential Entropy versus Entropy Rate

The advantage of using the differential map entropy is that it reflects better the total number of visits per hexagon, as we shall show. Maps corresponding to walks that revisit areas more often will result in lower entropy. To illustrate that, we have applied differentmap strengthening factors to map M6 and computed its differential entropy (Figure 7). The objective of the map strengthening factor is to increase (or decrease) the belief of the map by multiplying the transition counters with the map strengthening factor. Figure 7 shows that the differential entropy decreases linearly with the logarithm of the map strengthening factor despite the fact that we only increased the total counters of each hexagon and did not change the relationship of the edge transition probabilities.Figure 7
Differential map entropy conditioned on the sequence of poses (28) of map M6 for different map strengthening factors. For a map strengthening factor greater than 100, the differential entropy decreases linearly with the logarithm of the strengthening factor.Figure 8
Accumulated posterior map ofD1–D6. The starting position is marked in red and is well known. The respective map entropy ħ(M∣P0:k) and the step entropy rate values H(Pk∣P0:k-1) of the maps M1 to M6 are shown in the text boxes.
(a)
M 1 (b)
M 2 (c)
M 3 (d)
M 4 (e)
M 5 (f)
M 6


## 5.2. Entropy and KL-Divergence Results

### 5.2.1. Map Entropy and Step Entropy Rate

We are interested in obtaining the uncertainty of each one of the maps. We can do this by computing, for each map, the map entropy and the step entropy rate conditioned on the poses, respectively. Figure8 shows visual presentations of the resulting posterior maps of our 6 datasets. The starting position of the pedestrian is shown as a red hexagon. The corresponding map entropy and the step entropy rate values of the maps M1 to M6 are shown in the text boxes of Figure 8. We have computed, for each map, the entropy of all hexagons depicted in Figure 6. We could also use a bounding box around all maps, but the differences between the entropy values will be smaller due to the added hexagons with maximum entropy. M6 shows the lowest map entropy and step entropy rate. The results of M6 are closely followed by M5, and M3 presents the highest entropy, reflecting the uncertainty over the large unvisited areas. This corresponds to visual inspection of Figure 8: map M6 is the most extensive and accurate and M3 the least. The distinction between the map entropy and the step entropy rate is reflected in the range of values; for example, the difference between maps M3 and M6 is 0.31 and 0.11 for the map entropy and the step entropy rate, respectively. These 6 maps do not differ very much in the number of transition counters per hexagon; therefore, the range of the differential entropy values is not significant. The difference between the entropies would be more prominent if, for example, one walk had revisited some areas much more often than the others.We have illustrated the behavior of the differential entropy (Figure9) and the entropy rate (Figure 10) over time for dataset D4. In addition, visual representations of the best and accumulated posterior distributions resulting from our FootSLAM estimator are shown in Figure 11 for the time indices k equal to 48, 50, 88, 128, and 154. Here, the best particle map is depicted in blue and the accumulated map in gray. The entropy calculations are based on the map size at each time index. From Figures 9 and 10 we can infer that during the estimation the entropy is generally decreasing as expected. Before time index k=50 (Figure 11(a)) new area is explored. At time index k=50 the estimations converge (Figure 11(b)) which is reflected in the high decrease of entropy. After this, new area is explored resulting in an increase of the entropy. This is shown in Figure 11(c) as light gray area. After some time some of the particle map hypotheses will be rewarded and others will be killed due to resampling (e.g., time index k=128 and k=154, Figures 11(d) and 11(e)), with a sudden decrease in entropy. One can see from the figures that the small jumps in the curves reflect very well the exploring and convergence events.Figure 9
Differential entropy for datasetD4 over time. At the beginning the entropy is maximum: -4.78bits. At time index k=50 the estimations converge (see also Figure 11(b)) which is reflected in the high decrease of entropy at this time index. After that, new area is explored resulting in an increase before it decreases again. The jumps reflect very well the exploring and convergence situations.Figure 10
Entropy rate for datasetD4 over time. At the beginning the entropy is maximum: 2.58bits. The results are similarly to Figure 9, but the range of values is lower than with the differential entropy.Figure 11
Accumulated posterior map obtained by FootSLAM estimation at time indicesk equal to 48, 50, 88, 128, and 154. Different shades of gray encode the weight of the corresponding particle (darker means higher weight). The current position is marked in red. The best posterior map is shown in blue.
(a)
Time indexk=48 (b)
Time indexk=50 (c)
Time indexk=88 (d)
Time indexk=128 (e)
Time indexk=154


### 5.2.2. KL Divergence between Two Maps

In this section we are interested in showing the KL divergence between two maps as we rotate and translate one of them. As an example, we chooseM5 and M6 assuming that both maps fit into each other at the beginning.We now apply different transformations toM5 (rotations and translations in x- and y-direction) [19] and compute the KL divergence between the M5 transformed and M6 unchanged. Figures 12 and 13 show the results for the KL divergence (37) for different shifts of M5 along the x-axis and along the y-axis, respectively.Figure 12
Relative entropy between two mapsM6 and M5 translated along the x-axis. The peaks down to a minimum at 0 shift shows the best fit of the two maps. The maps were already aligned before shifting M5.Figure 13
Relative entropy between two mapsM6 and M5 translated along the y-axis. The maps were already aligned before shifting M5. The peak is more steep along the y-axis than along the x-axis due to the building structure and the direction of the shift.From the shifts alongx- and y-axis one can see peaks down to a minimum at 0 shift in both cases (as expected, because they were already aligned) where the two maps fit best. The main difference between the two figures is that the KL divergence grows slowly with the shifts along the x-axis, since the maps still share a portion of the corridor (with similar transitions). Therefore, the peak is more steep with the transformation along the y-axis.Finally, Figure14 shows the KL divergence between M5 rotated a the starting hexagon (in red) and M6 unchanged. The minimum is reached when the two maps are aligned (M5 unchanged), but we can see that towards the rotation value of π radians there is a local minimum due to the symmetries in the building that make the left side of the corridor fall onto the right side of the corridor and vice versa. These results suggest that we can use the KL divergence between two maps to find the best geometric transformation that places the two maps within the same coordinate system as an alternative for the Bayesian correlation function proposed in [19]. Similar results but with smaller differences can be obtained with the relative entropy rate of the pedestrian’s step (40).Figure 14
Relative entropy between two mapsM6 and M5, where M5 is rotated about its starting position. The peak down to a minimum at 0 shift shows the best fit of the two maps. One can see that towards the rotation value of π radians there is a local minimum due to the symmetries of the building.


## 5.2.1. Map Entropy and Step Entropy Rate

We are interested in obtaining the uncertainty of each one of the maps. We can do this by computing, for each map, the map entropy and the step entropy rate conditioned on the poses, respectively. Figure8 shows visual presentations of the resulting posterior maps of our 6 datasets. The starting position of the pedestrian is shown as a red hexagon. The corresponding map entropy and the step entropy rate values of the maps M1 to M6 are shown in the text boxes of Figure 8. We have computed, for each map, the entropy of all hexagons depicted in Figure 6. We could also use a bounding box around all maps, but the differences between the entropy values will be smaller due to the added hexagons with maximum entropy. M6 shows the lowest map entropy and step entropy rate. The results of M6 are closely followed by M5, and M3 presents the highest entropy, reflecting the uncertainty over the large unvisited areas. This corresponds to visual inspection of Figure 8: map M6 is the most extensive and accurate and M3 the least. The distinction between the map entropy and the step entropy rate is reflected in the range of values; for example, the difference between maps M3 and M6 is 0.31 and 0.11 for the map entropy and the step entropy rate, respectively. These 6 maps do not differ very much in the number of transition counters per hexagon; therefore, the range of the differential entropy values is not significant. The difference between the entropies would be more prominent if, for example, one walk had revisited some areas much more often than the others.We have illustrated the behavior of the differential entropy (Figure9) and the entropy rate (Figure 10) over time for dataset D4. In addition, visual representations of the best and accumulated posterior distributions resulting from our FootSLAM estimator are shown in Figure 11 for the time indices k equal to 48, 50, 88, 128, and 154. Here, the best particle map is depicted in blue and the accumulated map in gray. The entropy calculations are based on the map size at each time index. From Figures 9 and 10 we can infer that during the estimation the entropy is generally decreasing as expected. Before time index k=50 (Figure 11(a)) new area is explored. At time index k=50 the estimations converge (Figure 11(b)) which is reflected in the high decrease of entropy. After this, new area is explored resulting in an increase of the entropy. This is shown in Figure 11(c) as light gray area. After some time some of the particle map hypotheses will be rewarded and others will be killed due to resampling (e.g., time index k=128 and k=154, Figures 11(d) and 11(e)), with a sudden decrease in entropy. One can see from the figures that the small jumps in the curves reflect very well the exploring and convergence events.Figure 9
Differential entropy for datasetD4 over time. At the beginning the entropy is maximum: -4.78bits. At time index k=50 the estimations converge (see also Figure 11(b)) which is reflected in the high decrease of entropy at this time index. After that, new area is explored resulting in an increase before it decreases again. The jumps reflect very well the exploring and convergence situations.Figure 10
Entropy rate for datasetD4 over time. At the beginning the entropy is maximum: 2.58bits. The results are similarly to Figure 9, but the range of values is lower than with the differential entropy.Figure 11
Accumulated posterior map obtained by FootSLAM estimation at time indicesk equal to 48, 50, 88, 128, and 154. Different shades of gray encode the weight of the corresponding particle (darker means higher weight). The current position is marked in red. The best posterior map is shown in blue.
(a)
Time indexk=48 (b)
Time indexk=50 (c)
Time indexk=88 (d)
Time indexk=128 (e)
Time indexk=154


## 5.2.2. KL Divergence between Two Maps

In this section we are interested in showing the KL divergence between two maps as we rotate and translate one of them. As an example, we chooseM5 and M6 assuming that both maps fit into each other at the beginning.We now apply different transformations toM5 (rotations and translations in x- and y-direction) [19] and compute the KL divergence between the M5 transformed and M6 unchanged. Figures 12 and 13 show the results for the KL divergence (37) for different shifts of M5 along the x-axis and along the y-axis, respectively.Figure 12
Relative entropy between two mapsM6 and M5 translated along the x-axis. The peaks down to a minimum at 0 shift shows the best fit of the two maps. The maps were already aligned before shifting M5.Figure 13
Relative entropy between two mapsM6 and M5 translated along the y-axis. The maps were already aligned before shifting M5. The peak is more steep along the y-axis than along the x-axis due to the building structure and the direction of the shift.From the shifts alongx- and y-axis one can see peaks down to a minimum at 0 shift in both cases (as expected, because they were already aligned) where the two maps fit best. The main difference between the two figures is that the KL divergence grows slowly with the shifts along the x-axis, since the maps still share a portion of the corridor (with similar transitions). Therefore, the peak is more steep with the transformation along the y-axis.Finally, Figure14 shows the KL divergence between M5 rotated a the starting hexagon (in red) and M6 unchanged. The minimum is reached when the two maps are aligned (M5 unchanged), but we can see that towards the rotation value of π radians there is a local minimum due to the symmetries in the building that make the left side of the corridor fall onto the right side of the corridor and vice versa. These results suggest that we can use the KL divergence between two maps to find the best geometric transformation that places the two maps within the same coordinate system as an alternative for the Bayesian correlation function proposed in [19]. Similar results but with smaller differences can be obtained with the relative entropy rate of the pedestrian’s step (40).Figure 14
Relative entropy between two mapsM6 and M5, where M5 is rotated about its starting position. The peak down to a minimum at 0 shift shows the best fit of the two maps. One can see that towards the rotation value of π radians there is a local minimum due to the symmetries of the building.


## 6. Conclusion

In this article, we have derived different metrics for map comparison and map alignment. FootSLAM maps are probabilistic representations of human motion that can be explored by information theory. Formap comparison we affiliated themap entropy as well as thestep entropy rate for the special case of FootSLAM probabilistic maps. The first one is a measure ofuncertainty of a map and takes into account the number of times a region is (re)visited. The second one represents thegrowth in uncertainty with each new step. We have shown that both metrics are suitable for map comparison, where the range of the first one is larger than the second. They are also useful for the collaborative and iterative FeetSLAM algorithm, where comparing the available maps can help to decide in which order to combine them. With these metrics the complexity of the FeetSLAM algorithm can be lowered in order to allow online map merging. In addition to the entropy metrics we have derived therelative map entropy and therelative step entropy rate formap alignment. It has been shown that these metrics are very helpful to find the best geometric transformation between two maps.In our work, we have concentrated on the calculation of the entropy of FootSLAM maps to obtain a measure of the quality of the map, where no failure rate (e.g., crossing a wall, room failures) is considered. To reflect the failure rate within a map our idea is to take ground truth points or other suitable arrangements for each room and parts of the corridors and to measure the position error in terms of room fitting which is foreseen for future work. In addition, maps of another structure like different sizes of hexagons, other raster formats, or 3-dimensional maps, and so forth, are under investigation. Finally, future work also comprises the extension of the entropy calculation including spatial relationships between hexagons.



---

*Source: 9595306-2016-10-10.xml*