2.3. Tracking 17Figure 2.5 The Tracking problem consists of finding the best output sequence sT1ofpositions for an input sequence of measured signals. Both sequences are not requiredto have the same length due to probable further preprocessing steps.especially the Newtonian laws of motion, gives valuable hints for finding the bestsolution for the tracking problem. Tracking vehicles in an outdoor scenario is aclassical example for a case where the corresponding required runtime informationis also available from the built-in sensors. On the other hand in indoor scenarios,it is less likely that the availability of information as speed or acceleration can bepresumed.Another class of mobility models are derived from stochastic processes. A very simpleone is given by the Brownian motion or more general the Random walk model. Bothmodels simulate movement by stepping forward in a randomly chosen direction. TheBrownian motion model assumes an asymptotically small step-width approachingzero. These models can easily be enhanced to use other probability models insteadof simple uniform or normal ones. This can be done by incorporating the historyor the predecessors of states in the sequence and leads to the formalism of Markov chains.The information of direction is already used in a first order Markov chain, but for theevaluation of direction changes higher order Markov chains are needed. For examplein the presented localization system, the direction information is used in a first orderHMM to penalize movements into directions with less free space. The degree of freespace at a given location and a given direction can be retrieved from the 3D scene.This leads to the so called Geographical-restriction models. These models deriverules for the transition from one state to another by extracting information from anavailable map of the environment. Such a rule is given by disallowing the transitionsinto regions of space, that are blocked either directly or indirectly by obstacles. Afurther modelling of temporal variations in these restrictions can be used to markobstacles as active or inactive. An obvious use-case is given in the form of timecontrolled door locks.Another simple model, driven by prior geographical information, is the so calledPathway mobility model for vehicle navigation. A map containing a grid of streetsand intersections is used to model movement restricted to the streets with a simpledecision rule for the crossings. At each crossing the probability of moving forwardis 0.5 whereas the movement to the left or the right is 0.25. The constraints of such