## 4 Mapless Localization
### Trajectory Learning from a Crowd  
In the particle filter framework, the sampling relies on the prior probability \(p(x_{t}|x_{t-1})\). Under the unknown-map situation, the learned trajectory compensates for the absence of the true map. The prior function is defined as follows,  
\[p(x_{t}|x_{t-1})=P_{HF}\cdot P_{TL}, \tag{41}\]  
where \(P_{TL}\) is a learned map and \(P_{HF}\) is for capturing a smoothed-curve representation of a time-series trajectory using the H-P filter introduced in Section 2.1:  
\[P_{HF}=N\left(\parallel x_{t}-x_{t-2}-2x_{t-1}\parallel^{2};0,\sigma_{v} \right), \tag{42}\]  
In Equation (42), it does not require the estimation of velocity. Now, we describe how to build \(P_{TL}\). In indoor spaces, people trace similar trajectories to save their travel distance and time. The underlying idea for trajectory learning is that people tend to follow similar trajectories when they have the same departure point and destination. The departure and destination points are automatically obtained by the landmark detection algorithm described in Section 3.3.2. Suppose that we sample the trajectories \(X_{j}^{k}\) obtained from \(M\) different people \(k=0,\ldots,M-1\) and that the trajectories may have different trajectory lengths \(j=0,\ldots,N^{(k)}-1\). Then, there might exist a hidden intended trajectory \(h_{1:k}\), representative of all \(X_{j}^{k}\). For example, \(h_{1:k}\) can be the average trajectory of \(X_{j}^{k}\). The goal is to learn the hidden intended trajectory \(h_{t}\). Dynamic time warping with Kalman smoothing [40] is applied to this problem. The hidden trajectory \(h_{t}\) has length \(O\) at \(t=0,\ldots,O-1\). The length \(O\) is initialized to an ample size, namely, \(O=2/M\sum_{k=1}^{M}N^{(k)}\). The trajectory learning method treats the samples \(X_{j}^{k}\) as observations of \(h_{t}\) such that  
\[h_{t+1} = f(h_{t})+w_{t}^{h},\;\;w^{h}\sim N(0,\Sigma^{h})\] \[X_{j}^{k} = h_{\frac{\tau}{\tau}}+w_{j}^{X},\;\;w^{X}\sim N(0,\Sigma^{X}).\]  
Here, the covariance \(\Sigma^{h}\) and \(\Sigma^{X}\) of the Gaussian noises \(w^{h}\) and \(w^{X}\) should be estimated. The subscript \(\tau_{j}^{k}\) is the time index of \(h\) corresponding to \(X_{j}^{k}\). Log-likelihood maximization is used to estimate the hidden trajectory \(h_{t}\) and the time indices \(\tau_{j}^{k}\), as follows,  
\[\max_{\tau,\Sigma^{(\cdot)}}\text{log}p(h,\tau;\Sigma^{z},\Sigma^{X}), \tag{43}\]  
where \(\Sigma^{(\cdot)}\) refers to \(\Sigma^{h}\) and \(\Sigma^{X}\). In the work by the authors of [40], an iterative algorithm for solving Equation (43) is introduced. First, while keeping \(\tau\) constant, it updates the covariance matrix \(\Sigma^{(\cdot)}\) by separate E and M steps. In the E step, a Kalman smoother is applied to obtain the pairwise marginals over the latent variables \(h_{1:t}\); the M step updates the covariance matrix \(\Sigma^{(\cdot)}\). Then, dynamic time warping is applied to calculate \(\hat{\tau}\) with the given \(\Sigma^{(\cdot)}\) through the following optimization. \[ \begin{array}{rcl}\hat{\tau}&=&\text{argmax}_{\tau}\text{log}p(h,\tau;\Sigma ^{(\cdot)})\\ &=&\text{argmax}_{\tau}\sum_{k=0}^{M-1}\sum_{j=0}^{N^{k}-1}[\text{log}p(X_{j}^ {k}|h_{\frac{\tau}{\tau}|\tau},\tau_{j}^{k})\\ &&+\text{log}p(\tau_{j}^{k}|\tau_{j-1}^{k})].\end{array}  \tag{44}\]The details of the dynamic programming for solving Equation (44) are described in the work by the authors of [40]. Now, we describe how to collect observations, that is, \(M\) trajectories \(X_{j}^{k}\). By the landmark detection introduced in Section 3.3.2, we can estimate the edge of any pair of trajectories. Additionally, the elements of the trajectories are filled with the estimates obtained from the particle filter from Section 4.1. To generalize map learning, suppose that we sample a set of \(n\) learned trajectories \(h^{1:n}=\{h^{(1)},h^{(2)},\cdots,h^{(n)}\}\), where each \(h^{(\cdot)}\) might have different start and end points and each \(h^{1:n}\) is exploited to obtain \(P_{TL}\) in Equation (41).