\section{Standard Particle Filtering}
\label{sec:rse}

In this section, we present two common localisation schemes based on particle filtering using two different transition models for propagating new states and an identical evaluation step for udpating the weights. 

%As mentioned before, we consider indoor localisation as a time-sequential, non-linear and non-Gaussian state estimation problem. 
Recursive filters, like the aforementioned particle filter, use all observations $\mObsVec_{t}$ until the current time $t$ for computing an estimation of the hidden state $\mStateVec_{t}$.
In a Bayesian setting, this can be formalized as the computation of the posterior distribution:
	%
	\begin{equation}
		\arraycolsep=1.2pt
		\begin{array}{ll}
			&p(\mStateVec_{t} \mid \mObsVec_{1:t}) \propto\\ 
				&\underbrace{p(\mObsVec_{t} \mid \mStateVec_{t})}_{\text{evaluation}}
				\int \underbrace{p(\mStateVec_{t} \mid \mStateVec_{t-1}, \mObsVec_{t-1})}_{\text{transition}}
				\underbrace{p(\mStateVec_{t-1} \mid \mObsVec_{1:t-1})d\vec{q}_{t-1}}_{\text{recursion}}
		\end{array}
		\label{equ:bayesInt}
	\end{equation}
	%
Here, the previous observation $\mObsVec_{t-1}$ is included into the state transition \cite{Ebner-15}.
The transition is used as proposal distribution, also known as CONDENSATION algorithm \cite{Isard98:CCD}. 
%This algorithm also performs a traditional resampling step.

For indoor localisation we define the hidden state $\mStateVec$ as follows:
	\begin{equation}
		\mStateVec = (x, y, z, \mStateHeading, \mStatePressure),\enskip
		x, y, z, \mStateHeading, \mStatePressure \in \R \enspace.
	\end{equation}
	%
where $x, y, z$ represent the position in 3D space, $\mStateHeading$ the user's heading and $\mStatePressure$ the relative atmospheric pressure prediction in hectopascal (hPa). 
All relevant sensor measurements are incorporated into the observation $\mObsVec$ given by
	%
	\begin{equation}
		\mObsVec = (\mObsHeading, \mObsSteps, \mRssiVec_\text{wifi}, \mObsPressure) \enspace,
	\end{equation}
	%
Here, $\mObsHeading$ and $\mObsSteps$ describe the relative angular change and the number of steps detected for the pedestrian between two consecutive timesteps. 
Further, $\mRssiVec_\text{wifi}$ contains the measurements of all nearby \docAP{}s (\docAPshort{}).  
Finally, $\mObsPressure$ is the relative barometric pressure with respect to a fixed reference. 

%\subsection{Evaluation}

We assume a statistical independence of all sensors. The probability density of the state evaluation is then given by the following components:
	%
	\begin{equation}
		%\begin{split}
			p(\vec{o}_t \mid \vec{q}_t) = 
			p(\vec{o}_t \mid \vec{q}_t)_\text{baro} 
			\,p(\vec{o}_t \mid \vec{q}_t)_\text{wifi}
			\enspace
		%\end{split}
		\label{eq:evalBayes}
	\end{equation}
	%
%The current pressure value is evaluated using $p(\vec{o}_t \mid \vec{q}_t)_\text{baro}$ and absolute position information is given by $p(\vec{o}_t \mid \vec{q}_t)_\text{wifi}$ for \docWIFI{}. 

The smartphone's barometer is used to infer the likeliness of the current $z$-location in $p(\vec{o}_t \mid \vec{q}_t)_\text{baro}$ and thus enables to walk stairs or to drive elevators.
Here, every predicted relative pressure $\mState_t^{\mStatePressure}$ is compared with the observed one $\mObs_t^{\mObsPressure}$ using a normal distribution.
The state's relative pressure prediction $\mStatePressure$ is estimated within each transition from $\mStateVec_{t-1}$ to $\mStateVec_t$ by tracking the pressure between every height-change on the $z$-axis \cite{Fetzer2016OMC}.

Absolute position information is given by $p(\vec{o}_t \mid \vec{q}_t)_\text{wifi}$ for \docWIFI{}.
We are using the wall attenuation factor model based on Friis transmission equation to predict an \docAP{}'s (\docAPshort{}) signal strength at an arbitrary position $\fPos{\mStateVec_t} = (x, y,z)^T$.
This predicted signal strength is then matched against the current observation $\mObs_t^{\mRssiVec_\text{wifi}}$ received from this particular \docAPshort{}, providing a likelihood of the pedestrian being at $\fPos{\mStateVec_t}$.
The positions of detected \docAPshort{}'s are known beforehand.
The main advantage of this approach is that no time-consuming initial calibration phase and updates in case of infrastructural changes are needed \cite{Ebner-17}.

%Barometer 
%Due to noisy sensors, we calculate the average $\overline{\mObsPressure}$ of several sensor readings and the sensor's uncertainty $\sigma_\text{baro}$.
%This average serves as relative base for all future measurements and is carried out while the pedestrian chooses his destination \cite{Fetzer2016OMC}.
	
%The evaluation step for time $t$ is given by
		%
%		\begin{equation}
%			p(\mObsVec_t \mid \mStateVec_t)_\text{baro} = \mathcal{N}(\mObs_t^{\mObsPressure} \mid \mState_t^{\mStatePressure}, \sigma_\text{baro}^2) \enspace.
%			\label{eq:baroEval}
%		\end{equation}
		%		
%Here, every predicted relative pressure $\mState_t^{\mStatePressure}$ is compared with the observed one $\mObs_t^{\mObsPressure}$ using a normal distribution.
%The state's relative pressure prediction $\mStatePressure$ is estimated within each transition from $\mStateVec_{t-1}$ to $\mStateVec_t$ by tracking every height-change ($z$-axis):
	%		
%	\begin{equation}
%		\mState_{t}^{\mStatePressure} = \mState_{t-1}^{\mStatePressure} + \Delta z \cdot b
%		,\enskip
%		\Delta z = \mState_{t-1}^{z} - \mState_{t}^z
%		,\enskip
%		b \in \R
%		\enspace ,
%		\label{eq:baroTransition}
%	\end{equation}
	%
%Here, $b$ denotes the common pressure change in $\frac{\text{hPa}}{\text{m}}$.

%WI-FI
%Signal strength models are a well-established and popular method for estimating a pedestrian's position in indoor environments. 
%We are using the wall attenuation factor model based on Friis transmission equation to predict an \docAP{}’s (\docAPshort{}) signal strength at an arbitrary position $\mStateVec_t$ \cite{Ebner-15}.
%Here, the positions of detected \docAP{}s (\docAPshort{}) are known beforehand.
%The main advantage of this approach is that no time-consuming initial calibration phase and updates in case of infrastructural changes are needed.
%Using the 3D distance $d$ and the number of floors $\Delta f$ between the transmitter and the state-in-question, it can be described by
		%	
%		\begin{equation}
%			P_r(d, \Delta f) = \mTXP - 10 \mPLE \log_{10}{\frac{\mMdlDist}{\mMdlDist_0}} + \Delta{f} %\mWAF \enspace ,
%			\label{eq:waf}
%		\end{equation}
		%
%where $\mTXP$ contains the AP’s signal strength at $\mMdlDist_0$ and $\mPLE$ models the signal’s depletion with growing distance. 
%The attenuation per floor is described by $\mWAF$.
%To reduce the system's setup time, we use the same values for all \docAP{}s at the cost of accuracy.
			
%By assuming statistical independence, the overall probability can be determined using
		%		
%		\begin{equation}
%			\mProb(\mObsVec_t \mid \mStateVec_t)_\text{wifi} =
%			\prod\limits_{i=1}^{n} \mathcal{N}(\mRssi_\text{wifi}^{i} \mid P_{r}(\mMdlDist_{i}, \Delta{f_{i}}), \sigma_{\text{wifi}}^2) \enspace .
%			\label{eq:wifiTotal}
%		\end{equation}
%The uncertainty of the measurements is given by $\Delta{f_{i}}$. More details on this approach and possible extensions can be found in \cite{Ebner-15} and \cite{Ebner-17}.


%\subsection{Graph-based Transition}

%Keine Überschriften. Transition über liste trennen

As mentioned before, we are searching for a solution to satisfy both, sample diversity and focus. 
Therefore, we utilize two very different transition models, each providing one of these abilities.
\begin{itemize}
	\item The \textit{graph-based transition} samples only new states that are allowed by a gridded graph, which is generated from the building's floorplan. Thus walking through walls, ceilings or obstacles is prohibited. Additionally, the human movement is considered by randomly walking along adjacent edges into a given direction until a to-be-walked distance is reached. To provide a direction and distance, turns and steps are detected using the smartphone's IMU. All this promises a very focused propagation for new states and draws only valid movements.
%
	\item \textit{The simple transition} is a continuous model, that draws new states depending on a random direction and distance provided by a multivariate normal distribution. That means, no environmental knowledge and no statement about the pedestrian's (real) movement are considered. 
\end{itemize}
For further explanations and details of the localisation filter please refer to \cite{Ebner-15}.

Given the above, we are now able to implement two different localisation schemes, one for each transition model presented.
The graph-based transition keeps the localisation error low by using a very realistic propagation model, while being prone to sample impoverishment. 
On the other hand, the simple transition provides a high diversity with a robust, but uncertain position estimation. 
Both are evaluating a state $\mStateVec_{t}$ using \eqref{eq:evalBayes}.
In the upcoming, the filter using the graph-based transition is refereed to as \textit{graph-based filter} and the filter using the simple transition as \textit{simple filter}.

% 
%In the following, two very different transition models, each providing one of this abilities, are presented. 

%The first transition model is based upon random walks on a gridded graph $G=(V,E)$ with vertices $\mVertexA \in V$ and undirected edges $\mEdgeAB \in E$, which is generated from the buildings floorplan \cite{Ebner-16}.
%Starting at the vertex of the position $\fPos{\mStateVec_{t-1}} = (x, y,z)^T$ a new particle is sampled by walking along adjacent nodes into a given walking-direction $\gHead$ until a distance $\gDist$ is reached \cite{Ebner-15}.
%During the random walk, each edge has its own probability $p(\mEdgeAB)$ which depends on the edge’s direction $\angle \mEdgeAB$ and the pedestrian’s current heading $\gHead$.
%The to-be-walked edge is thus drawn according to their resemblance:
		%
%		\begin{equation}
%			p(\mEdgeAB)_\text{head} = p(\mEdgeAB \mid \gHead) = \mathcal{N} (\angle \mEdgeAB \mid \gHead, \sigma_\text{head}^2)
%			\enspace .
%			\label{eq:transHeading}
%		\end{equation}
		%
%While the distribution \refeq{eq:transHeading} does not integrate to $1.0$ due to circularity of angular data, in our case, the normal distribution can be assumed as sufficient for small enough $\sigma^2$.

%To provide $\gHead$ and $\gDist$, steps and turns are detected using the smartphone's IMU, implemented as described in \cite{Ebner-15}.
%The number of steps detected since the last transition is used to estimate the to-be-walked distance $\gDist$ by assuming a fixed step-size with some deviation:
		%
%		\begin{equation}
%			\gDist = \mObs_{t-1}^{\mObsSteps} \cdot \mStepSize	+ \mathcal{N}(0, \sigma_{\gDist}^2)
%			\enspace .
%		\end{equation}
		%
%Turn-Detection supplies the magnitude of the detected heading change by integrating	over the gyroscope's change since the last transition. 
%Together with some deviation and the state's previous heading, the magnitude is used to estimate the current state's heading:
		%
%		\begin{equation}
%			\gHead = \mState_{t}^{\mStateHeading} = \mState_{t-1}^{\mStateHeading} + \mObs_{t-1}^{\mObsHeading}	+ \mathcal{N}(0, \sigma_{\gHead}^2) \\
%		\end{equation}
		%
%All this promises a very focused propagation for new particles and draws only valid movements, as ambient conditions (walls, doors, stairs, etc.) are considered.
%Additionally, the graph-based approach offers plenty of scope for further extension as can be seen in \cite{Ebner-16}.

%\subsection{Simple Transition}

%The second transition model is very simple and thus often used in scenarios with little or rough information provided by sensors. 
%Especially in cases without any regular statements about the pedestrian's movement. 
%This continuous model just moves into a random direction, ignoring the graph and thus any floorplan %knowledge:
%		%
%		\begin{equation}
%			\begin{split}	
%				\mProb(\mStateVec_{t} \mid \mStateVec_{t-1}) &=
%				\mathcal{N}\left(
%				\fPos{\mStateVec_{t}}
%				\mid{}
%				\fPos{\mStateVec_{t-1}}, 
%				\mat{\Sigma}_{\text{move}}
%				\right),\\
%				\mat{\Sigma}_{\text{move}} &= 
%				\begin{pmatrix}
%					\sigma_{\text{move}} & 0 & 0\\
%					0 & \sigma_{\text{move}} & 0\\
%					0 & 0 & \sigma_{\text{floor}}\\
%				\end{pmatrix}
%			\end{split}
%			\label{eq:simpleTrans}
%		\end{equation}
		%
%The only restriction made, is that newly drawn particles need to be somewhere in between the graphs boundaries and therefore have a valid vertex for $\fPos{\mStateVec_{t}}$. 
%If the particle does not satisfy this condition, the position of nearest available vertex is chosen instead.
%This ensures that a particle resides always on a valid vertex $\mVertexA$, what will be of importance for the upcoming IMMPF.




 
%For further explanations of the filtering process for indoor localisation please refer to \cite{Ebner-15}.



