Get Complete Project Material File(s) Now! »

## Partially Observed Dynamical System: The Filtering Problem

A dynamical system is a system whose internal state, represented by a random variable x, evolves over time causally, that is, the next state of the system depends only on past and present states. Additionally, when the knowledge of past states carries no additional information that would help determine the future state of a dynamical system and what simply matters is the current state, it is said that the dynamical system veries the Markov property [Markov, 1954]. In the rest of this document, we are interested in dynamical systems meeting this property1. More particularly, we focus on those systems whose dynamics can be represented by: xt = f (xt1;wt); 8t 1; (2.1) where xt and xt1 represent the state of the system at time t and t 1 respectively, f is a deterministic function modeling the system dynamics, and (wt)t1 is a noisy process representing exogenous factors that may aect the evolution of the system. From a probabilistic perspective, the system’s dynamics can be characterized by a probability distribution p(xtjxt1) often called the state-transition model. In such a model, the noise (wt)t1 from Equation 2.1 is represented by the non-deterministic characteristic of the model. Usually, a knowledge Bel0 regarding the system’s initial state at time t = 0, also called prior, is provided in form of a probability distribution p(x0). Formally, such a distribution denes the possible values of the initial state of the system and their corresponding probabilities.

A partially observed dynamical system is a system in which it is not possible to have the complete access to the internal state; instead, sensors are used to obtain noisy (partial) measurements also referred to as observations2 represented by a random variable z. It is said that the system’s state is hidden. The observation zt received from the system at a given time t can be modeled as: zt = h(xt; vt); 8t 1; (2.2).

where xt represents the state of the system at time t, h is a known deterministic observation function of the sensor network, and (vt)t1 is a noisy process modeling the imperfection of the sensors used. It is assumed that both noisy processes (wt) and (vt) are mutually independent. From a probabilistic perspective, the observation process can be characterized by a probability distribution p(ztjxt) often called the observation model which allows to relate the noisy measurement obtained to the system’s state. A graphical representation of the evolution of a partially observed dynamical system is illustrated in Figure 2.1.

### Analytical Approaches

Analytical solutions usually proceed by approximating the nonlinear system’s dynamics by a linear function. By doing so, these solutions aim to exploit the intrinsic linearity properties during the computation of integrals within the ltering procedure. These solutions assume, as in the case of the Kalman lter, the Gaussian form of the probability distribution over the system’s state. Among the existing methods, we can name the Extended Kalman lter (EKF) [Jazwinski, 1970, Einicke and White, 1999] and the Unscented Kalman lter (UKF) [Julier and Uhlmann, 1997, 2004]. While the quality of the results obtained with these analytical solutions is quite satisfactory in the context of weakly nonlinear systems, they badly perform in case of strong non-linearity (i.e., multi-modal distributions) as stated in [Einicke, 2012].

#### Monte Carlo Approaches

Unlike analytical approaches, Monte Carlo solutions do not try to approximate, by a linear function, the dynamics of the system under consideration. Moreover, they do not make any assumptions regarding the form of the probability distribution over the system’s states. Instead, they consider representing the belief Belt(xt) using a set of pointsalso referred to as samples or particles from the state space, and they simply proceed by simulating, over time, the evolution of these points using the function characterizing the system dynamics. Monte Carlo approaches, therefore, are able to handle multi-modal distributions and they are more appropriate when the dynamics of the system is strongly nonlinear. Further details regarding these approaches are discussed in Chapter 3.

**Regularized Particle Filter**

When the underlying system’s dynamics function is subject to little noise, then the particle lter, as described above, is not appropriate anymore. This is because duplicating a particle, at the resampling step, will lead to a particle that will evolve quite similarly as the original one, thus leading in the long term to the sample impoverishment phenomenon [Arulampalam et al., 2002]. Regularized particle lters (RPFs) have been introduced [LeGland et al., 1998, Musso et al., 2001] with the aim to prevent this phenomenon.

The main idea of RPFs is to resample from a continuous approximation of the probability density function p(xtjz1:t) instead of its discrete approximation (see Equation 3.7), hence producing a new set of particles with N dierent particles. The continuous approximation of the posterior distribution is usually computed as follows (see Figure 3.3): p(xtjz1:t) ^p(xtjz1:t) = XN i=1 wi t:K(xt xi t); (3.10) where K(x) = 1 nxK(x ) is the rescaled kernel density, K(:) is the considered kernel function, is the kernel bandwidth and nx is the dimension of the state space. A kernel K could be any symmetric density function such that K > 0, R K(x)dx = 1, R xK(x)dx = 0 and R (x)dx < 1. Examples of such a kernel include Gaussian kernel, Epanechnikov kernel and cosine kernel. Usually, the covariance matrix of the underlying samples is often used as additional information when designing the kernel. For example, this matrix can be used to dene the covariance matrix of a Gaussian kernel.

**Motion Tracking**

In this section, we are interested in methods that have been developed to address the problem of pedestrian behavior estimation from the sole point of view of trajectory tracking. Generally, in methods designed for motion tracking, the considered pedestrian’s behavior is represented by physical attributes in relation with his motion such as the position, the velocity, and/or the acceleration. Moreover, a predictive pedestrian motion model is required as an input to the inference process. In the following sections, we will discuss motion models found in the literature and associated works in which they were used for tracking purposes.

**Simple motion models**

In the literature, some works [Fod et al., 2002, Cui et al., 2005, Arras et al., 2008] make simple assumptions regarding the human motion and consider that it can be represented by a constant velocity model modulated by some noise. While this assumption simplies the computation of the estimate of the target location via the use of Kalman lters [Kalman, 1960] (see Section 2.3), it does not often reect the reality. Indeed, constant velocity models consider that a given pedestrian will continue to move in the direction in which he was last observed (see Figure 4.1). This is, of course, not always the case as, for example, in presence of obstacles.

**Motion models handling static obstacles**

In order to deal with obstacles, a general approach consists in taking into account the environment while performing motion path planning to the destination point targeted by the pedestrian. The most popular method for performing path planning is the well known A* Algorithm [Hart et al., 1968] which allows to compute a least-cost path from a given initial point to another one in the environment while avoiding obstacles.

In [Liao et al., 2003], the authors proposed a Voronoi graph based motion model which constrains the location of moving targets to lie on edges of a Voronoi graph extracted from a map of the environment. The Voronoi graph (see Figure 4.2) provides a natural discretization of the environment on which the authors apply unsupervised learning techniques to derive typical motion patterns of people walking through the environment. Their model is then combined with a particle lter for tracking purposes.

Bennewitz et al. [2005] proposed a model based on groups of trajectories represented as closelyspaced sequences of waypoints. Their model represents people’s motion patterns learned from a collection of trajectories, and is used to classify to which group a tracked trajectory belongs; thus enabling to predict an individual’s motion. More specically, from each pattern, a hidden Markov model is derived and used as the baseline for motion prediction. With respect to constant velocity models, both path planning and Voronoi motion model have the advantage of integrating the topology of the environment. However, as pointed out in [Tastan and Sukthankar, 2011], these methods are not based on actual human proles and cannot be easily generalized. Moreover, these models as well as the one proposed by Bennewitz et al. do not take into account dynamic obstacles (e.g., presence of other pedestrians 4) in the surrounding of the considered pedestrian.

**Table of contents :**

**Chapter 1 Introduction**

1.1 Examples and Motivations

1.2 Problematic

1.3 Literature snapshot and current limitations

1.4 Contributions

1.5 Document Structure

**Part I Bayesian Filtering**

**Chapter 2 The Filtering Problem**

2.1 Partially Observed Dynamical System: The Filtering Problem

2.2 Bayesian Filter

2.3 Kalman Filter

2.4 Other Approaches

2.4.1 Analytical Approaches

2.4.2 Monte Carlo Approaches

2.5 Conclusion

**Chapter 3 Particle Filtering**

3.1 Monte Carlo methods

3.2 Importance Sampling Principle

3.3 Sequential Importance Sampling

3.4 Particle Filter

3.5 Regularized Particle Filter

3.6 Conclusion

**Part II Single-Target Behavioral Tracking**

**Chapter 4 Algorithms for estimating pedestrian’s behavior**

4.1 Introduction

4.2 Motion Tracking

4.2.1 Simple motion models

4.2.2 Motion models handling static obstacles

4.2.3 Motion models handling dynamic obstacles

4.2.3.1 Cellular-based motion models

4.2.3.2 Physics-based motion models

4.2.4 Overview of pedestrian tracking related works

4.3 Activity Recognition

4.3.1 Overview

4.3.1.1 Low-level activities

4.3.1.2 High-level activities

4.3.2 Graphical model based approaches

4.3.3 Syntactic approaches

4.3.4 Description-based approaches

4.4 Simultaneous Tracking and Activity Recognition

4.5 Conclusion

**Chapter 5 Inferring pedestrian behaviors from agent-based simulations**

5.1 Introduction

5.1.1 The STAR approach and current limitations

5.1.2 Agent-based behavioral simulators: an alternative to graphical models

5.1.3 Contributions

5.2 Autonomous agent-based behavioral simulation

5.2.1 Environment’s Service Representation

5.2.2 Action Selection Mechanisms

5.2.3 High-level Planners

5.2.4 Summary

5.3 Agent-Based Behavior Tracking

5.3.1 Process Overview

5.3.2 System Dynamics

5.3.3 Observation Model

5.4 Implementation

5.4.1 Simulator

5.4.2 Interactions with objects

5.4.3 System Architecture

5.5 Experimental Evaluations

5.5.1 Performance metrics

5.5.2 Virtual-world based experiments

5.5.2.1 Experimental Setup

5.5.2.2 Scenario 1: target with a xed motivation

5.5.2.3 Scenario 2: target with a varying motivation

5.5.2.4 Scenario 3: exogenous events

5.5.3 Real-world based experiments

5.5.3.1 Experimental Setup

5.5.3.2 Scenario 1

5.5.3.3 Scenario 2

5.6 Conclusion and Discussion

5.6.1 Contributions

5.6.2 Research directions

**Part III Multi-Target Behavioral Tracking**

**Chapter 6 The Multi-Target Tracking Problem**

6.1 Introduction

6.2 Problem Formulation

6.2.1 System Dynamics

6.2.2 Observation Model

6.2.2.1 Observation-Generation-related Assumptions

6.2.2.2 Observation Generation Procedure

6.2.3 Summary

6.3 Data-Association Problem

6.3.1 Global Nearest Neighbor

6.3.2 Multiple Hypothesis Tracker

6.3.2.1 Gating Procedure

6.3.2.2 Generation of Hypotheses

6.3.2.3 Hypothesis Probability Computation

6.3.2.4 Hypothesis Reduction Techniques

6.3.3 Joint Probabilistic Data Association Filter

6.3.3.1 Feasible (Joint Association) Hypothesis Generation

6.3.3.2 Computation of the jk coecients

6.4 Management of Targets’ Interactions

6.4.1 Observation-based Interactions

6.4.1.1 Approaches with observation-based potential functions

6.4.1.2 Learning-based Approaches

6.4.1.3 Interaction model-based Approaches

6.4.2 Dynamics-based Interactions

6.4.2.1 Approaches with state-based potential functions

6.4.2.2 Interaction Model-based Approaches

6.4.3 Summary

6.5 Conclusion

**Chapter 7 Tracking Multiple Interacting Targets – An Interaction-Model Based Factored**

7.1 Introduction

7.2 Problem Statement

7.3 Dynamics-based Interaction Representation

7.4 Estimation of Targets’ Predicted Distributions

7.4.1 Bayesian formulation of target predicted distributions

7.4.2 Exploiting the locality of interactions

7.4.3 Probability distribution aggregation

7.4.3.1 Overview

7.4.3.2 Eect-based partitioning

7.4.3.3 Estimation of the predicted distribution

7.4.4 Heuristics for aggregating probability distributions

7.4.4.1 Denition of the anity function

7.4.4.2 Partitioning of the probability distribution

7.4.4.3 Computing the representative states

7.4.5 Summary

7.5 Implementation Using Particle Filtering

7.5.1 Monte Carlo JPDAF

7.5.1.1 Soft-gating procedure

7.5.1.2 MC-JPDAF algorithm

7.5.1.3 Summary

7.5.2 Dealing with non-covered areas in (MC-)JPDAF

7.5.3 Tracking interacting targets with JPDA-like lter

7.5.3.1 Managing targets’ interactions

7.5.3.2 Particle reduction policy

7.5.3.3 Summary

7.5.4 Multiple-representative-based soft-gating

7.5.5 Summary

7.5.6 Complexity analysis

7.6 Experimental Evaluations

7.6.1 Simulator

7.6.2 Performance metrics

7.6.3 Single-representative-based evaluations

7.6.3.1 Experimental setup

7.6.3.2 Impact analysis of

7.6.3.3 Impact analysis of N

7.6.3.4 Impact analysis of K

7.6.3.5 Summary

7.6.4 Multiple-representative-based evaluations: an illustrative scenario

7.6.4.1 Experimental setup

7.6.4.2 Impact of multiple representatives at the prediction step .

7.6.4.3 Impact of multiple representatives at correction step

7.6.4.4 Summary

7.6.5 Multiple-representative-based evaluations: a complex scenario

7.6.5.1 Experimental setup

7.6.5.2 Single versus multiple representative(s)

7.6.5.3 Impact analysis of the clustering methodology

7.6.5.4 Impact analysis of the reduction policy

7.6.5.5 Impact analysis of N

7.6.5.6 Impact analysis of K

7.6.5.7 Coupling with an external re-identication module

7.7 Conclusion and Discussion

**Chapter 8 Conclusion**

8.1 Contributions

8.1.1 Simultaneous tracking and activity recognition

8.1.2 Management of target interactions

8.2 Future Work

8.2.1 Real-world evaluations

8.2.2 Target re-identication

8.2.3 Sensor control decision policies

8.2.4 Beyond behavioral tracking

8.3 Application domains

8.3.1 Behavioral model calibration

8.3.2 Telemedicine monitoring service

**Bibliography**