50 4. Designtime frame t T. At each state stall possible predecessor states are visited. It isreasonable to limit the number of possible predecessor states to the surrounding areaof a given state. So by restricting the transitions between states to the neighbour-hood of the next two states in both horizontal directions and the next state in thevertical direction this leads to 75 predecessor states and is called a(5, 5, 3) transitionmodel. These constraints limit the number of needed computations to the tractablepolynomial complexity of 75 · T · S. In the UMIC scene, around 60k states with edgesize of 60 cm are defined. Thus, a sequence of T= 10 measurements leads to 45 · 106needed computations, that are processed very quickly, as the implemented decoderis able to compute 5 · 106states per second on an Intel i7-QuadCore@3Ghz.4.3.1.1 Parameter EstimationThe parameters of the HMM , that are evaluated by the Viterbi Decoder component,are given by the emission- and transition probabilities. These parameters are esti-mated during a training phase and are cached in the Environment component. Thedefault HMM parameter training method is given by the Baum­Welch algorithm.But for such a training, a corpus of location annotated RSSI readings is needed.That corpus needs to contain training data for all possible states, representing lo-cations in the 3D-space, so that the practicality of this approach can be excluded.Therefore, the parameters of both probabilities are acquired from other sources.The combined SSMs over all APs is understood as a generative model for the emissionprobabilities thus these parameters can be obtained easily. But for the transitionprobabilities, no such convenient data source is at hand. The only available sourceof information, which can be exploited for modelling constraints on the movementbetween states in the 3D-space, is the 3D-model that is already used for drivingthe raytracer. At least the most critical information for modelling the transitions,the restriction which states are impassable due to blocking material, are retrievedfrom the building structure. Incorporating such knowledge is used to reject pathhypothesis that move through walls, floors or other forbidden zones.4.3.1.2 Emission ProbabilitiesThe model parameters for the emission probabilities p( s| x) are obtained from thestored radio propagation Models. In the UMIC scenario a hidden state is config-ured to represent the neighbourhood of 3 adjacent voxels for each dimension. Theemission probability is modelled as a multivariate Gaussian with a constant pooledcovariance matrix = I. The Naps-dimensional mean vector for p( s| x) is obtained bycalculating the arithmetic mean of the RSSI values from the 27-voxel-neighbourhoodfor each AP dimension. Although the variance of these voxel-neighbourhoods canbe calculated this does not represent any conclusive information source. The realvariance of the received RSSI values is driven by multiple effects like multipathpropagation, body shadowing and other probably location dependant noise. Noneof these effects are captured in the radio propagation model4, so the model dropsthe variance altogether. By transforming the Gaussians with = I into logspace,4Simulating the effect of multipath radio propagation on the variance could be enabled by thepossibility to dissect the raytracer results into the different recursion depths that are triggered for