el filtro de partículasdep.fie.umich.mx/~camarena/presentacionparticlefilter.pdfel filtro de...

El Filtro de PartículasJose Antonio Camarena Ibarrola

El Filtro de Partıculas– p.1/25

El Filtro de Partículas

Método Monte Carlo (basado en muestreo) parainferir el estado de un sistema que evoluciona en eltiempo en modelos de espacio de estados

La información acerca del estado es obtenida através de mediciones ruidosas realizadas en tiemposdiscretos


Modelos de espacio de estados discre-tos en tiempo

En estos modelos el estado de un sistema evolucionade acuerdo a

xk = fk(xk−1, vk−1) (1)

dondexk es un vector que representa el estado delsistema en el instantek, vk−1 es un vector de ruidodel estado yfk es una función posiblementeno-lineal que describe la evolución del vector deestado

El vector de estadoxk es latente o inobservable


Las Mediciones

La información acerca dexk se obtiene solo a travésde mediciones ruidosasxk gobernadas mediante laecuación

zk = hk(xk, nk)

dondehk es una función posiblemente no-lineal quedescribe el proceso de medición ynk es el vector deruido de la medición


Filtrado Optimo

El problema de filtrado involucra la estimación delvector de estado en el instantek dadas todas lasmediciones hasta el instantek, denotadasz1:kUsando el enfoque Bayesiano, este problema sepuede formalizar como la determinación de ladistribuciónp(xk|z1:k)

Esto se puede lograr recursívamente en dos pasosPredicciónCorrección


Predicción

p(xk|z1:k−1) se determina mediante

p(xk|z1:k−1) =

∫p(xk|xk−1)p(xk−1|z1:k−1)dxk−1

A su vez, para determinarp(xk−1|z1:k−1) se utiliza la misma

recursión

p(xk|xk−1) está dada por (??) (función que describe la

evolución del vector de estado)

La distribuciónp(xk|z1:k−1) se puede considerar como una

distribución a-priori dexk antes de recibir la mas reciente

observaciónzk


CorrecciónEn el paso de corrección, la distribución a-priori se actualiza con la nueva mediciónzkutilizando la regla de Bayes para obtener una distribución a-posteriori sobrexk

p(xk|z1:k) =p(zk|xk)p(xk|z1:k−1)

p(zk|z1:k−1)

donde la constante de normalización

p(zk|z1:k−1) =

∫p(zk|xk)p(xk|z1:k−1)dxk

depende de la función de verosimilitudp(zk|xk) definida por el modelo de mediciones y el

conocimiento estadistico que se tenga denk

A veces los cálculos para la predicción y corrección resultan intratables, de ahí la necesidad de

métodos aproximados como muestreo de Monte Carlo


Filtro de KalmanSi la distribuciónp(xk−1|z1:k−1) es gausiana, la distribución filtradap(xk|z1:k−1) será

gausiana si se satisfacen las siguientes dos condiciones:

Las funciones de evolución de estadofk y de mediciónhk son ambas lineales

El ruido del estadovk y de mediciónnk son ambos gausianos

Las ecuaciones de estado y de medición se reducen a

xk = Fkxk−1 + vk−1

zk = Hkxk + nk

dondeFk y Hk son las matrices de evolución de estado y de medición respectívamente que se

asumen conocidas yvk−1 y nk son variables aleatorias gausianas


Sequential Importance Sampling(SIS)

Cuando los pasos de predicción y correción son intratables

debemos recurrir a métodos aproximados como muestreos de

Monte Carlo

La idea es representar la función de densidad posterior

requerida mediante un conjunto de muestras aleatorias y sus

pesos asociados y realizar estimaciones en base a estas

A medida que el número de muestras aumenta estas

estimaciones tienden a las estimaciones bayesianas

Conviene considerar la distribución completa en el tiempo

k − 1, es decirp(x0:k−1|z1:k−1) en lugar dep(xk−1|z1:k−1), la

cual es la distribución marginal posterior con respecto axk−1


SIS

Conviene considerar la distribución completa en el tiempo

k − 1, es decirp(x0:k−1|z1:k−1) en lugar dep(xk−1|z1:k−1), la

cual es la distribución marginal posterior con respecto axk−1

La idea en SIS es aproximar la distribución posterior en el

tiempok − 1 con un conjunto de muestras pesadas tambien

llamadas PARTICULAS

{xi0:k−1, ω

ik−1}

Ni=1

y recursívamente actualizar estas partículas para obteneruna

aproximación de la distribución posterior en el siguiente paso

p(x0:k|z1:k)


SIS

{xi0:k−1, ωik−1}

Ni=1 denota un muestreo aleatorio que

caracteriza la pdf posteriorp(x0:k|z1:k)

x0:k es el conjunto de estados hasta el tiempok y lospesos están normalizados de modo que

∑i ω

ik = 1


Muestreo de la importancia

La idea es aproximar una distribución objetivop(x) usando muestras extraídas de una

distribución propuestaq(x) denominada “densidad de importancia”

p(x) es una densidad de probabilidad de la que es dificil extraer muestras pero si disponemos

de una funciónπ(x) proporcional ap(x) (i.e.p(x) α π(x)) que sí sabemos como evaluar

Adicionalmente, seanxi ∼ q(x), i = 1, ..., N muestras extraídas fácilmente de unaq(.)

propuesta

Entonces, una aproximación a la densidadp(.) está dada por

p(x) ≈

N∑i=1

ωiδ(x− xi)

dondeωi es el peso de la i-ésima partícula

ωi α π(xi)/q(xi)



Aplicando muestreo de importancia al problema deestimar la función de distribución de probabilidadposterior

p(x0:k|z1:k) ≈N∑i=1

ωikδ(x0:k − xi0:k)

Si las muestras fueron obtenidas a partir de unadensidad de importanciaq(x0:k|z1:k), entonces lospesos son:

ωik α

p(xi0:k|z1:k)

q(xi0:k|z1:k)



En cada iteración, tendríamos muestras queconstituyen una aproximación ap(x0:k−1|z1:k−1) yqueremos una aproximación ap(x0:k|z1:k) medianteun nuevo conjunto de muestras.

Factorizamos la densidad de importancia

q(x0:k|z1:k) = q(xk|x0:k−1, z1:k)q(x0:k−1|z1:k−1)

de esta manera podemos obtener el conjunto demuestrasxi0:k ∼ q(x0:k|z1:k) agregando al conjuntode muestrasxi0:k−1 ∼ q(x0:k−1|z1:k−1) el nuevoestadoxik ∼ q(xk|x0:k−1, z1:k)


Algoritmo SIS

{xik, ωik}

Ni=1 = SIS[{xik−1, ω

ik−1}

Ni=1]

FORi = 1 : Nextraexik ∼ q(xk|x

ik−1, zk)

Asigna a la particula un pesoωik de acuerdo a la

ec (??)

END FOR


Ejemplo con Filtro de Partículas SIS

La linea roja muestra el estadoxk de un sistema encada pasok

Los círculos azules son las medicioneszk en lospasos correspondientes

los puntos grises muestran las partículas generadaspor el algoritmo SIS en cada paso

el nivel de gris representa el peso de la partículacorrespondiente

En este ejemplo se usaron 50 partículas


Ejemplo de Seguimiento con Filtro dePartículas SIS


El problema de la degeneración

Este problema consiste en que a medida que kaumenta solo unas cuantas partículas tienen un pesosignificativo

Este problema se puede observar en la figura anterior

La degeneración se puede estimar mediante:

Neff =1∑N

i=1(ωik)

2

donde unNeff pequeño significa mayor varianza delos pesos y por ende mayor degeneración

Una forma de lidiar con el problema de ladegeneración es el remuestreo


Sampling Importance Resampling(SIR)

Consiste en extraer (con reemplazo) un nuevo conjunto de N

partículas a partir de la aproximación descreta de la

distribuciónp(xk|z1:k obtenida a partir de

p(xk|z1:k) ≈N∑i=1

ωikδxi

k

el remuestreo es realizado cada vez queNeff cae por debajo de

un valor umbral

observe que en vista de que la extracción se realiza con

reemplazo, las partículas con peso grande muy probablemente

serán extraídas en múltiples ocasiones mientras que las de poco

peso es improbable que sean extraídas en alguna ocasión

El peso de partículas nuevas es1/NEl Filtro de Partıculas– p.20/25

Empobrecimiento de las muestras

El remuestreo resuelve el problema de la degeneración

deshaciendose de las muestras con poco peso

Esto introduce un nuevo problema denominado

“Empobrecimiento de las muestras”

Como las partículas con peso grande serán extraídas en

múltiples ocasiones y las de poco peso dificilmente serán

extraídas, LA DIVERSIDAD DE LAS PARTICULAS

TIENDE A DISMINUIR CON CADA REMUESTREO

En un caso extremo, todas las partículas podría colapsar a una

sola partícula

esto afecta la calidad de la aproximación ya que se está

representando toda una distribución con unas cuantas muestrasEl Filtro de Partıculas– p.21/25

Filtro de partículas (PF)

{xik, ωi

k}Ni=1

= PF [{xik−1

, ωik−1

}Ni=1, zk]

FORi = 1 : N

extraexik∼ q(xk|x

ik−1

, zk)

Asigna a la particula un pesoωik

de acuerdo a la ec (??)

END FOR

Calcula el peso totalt =∑N

i=1ωik

FORi = 1 : N

Normalizaωik= t−1ωi

k

END FOR

CalcularNeff

IF Neff < NT

{xik, ωi

k}Ni=1

= RESAMPLE[{xik−1

, ωik−1

}Ni=1]

END IF


Ejemplo con Filtro SIR


Comparación

En la Fig B se puede ver de nuevo el problema de la

degeneración al grado de que la distribución termina siendo

dominada por una sola partícula

En cambio, en la Fig A, todas las partículas tienen el mismo

peso1/N

Sin embargo, se nota el empobrecimiento en la Fig A puesto

que las muestras tienen menor varianza que la Fig B

En ambos casos el número de paetículas utilizadas fueron 50


Referencias

1 Arulampalam, M.S., Maskell, S., Gordon, N. & Clapp, T.

(2002). A tutorial on particle filters for online

nonlinear/non-gaussian Bayesian tracking. IEEE Transactions

on Signal Processing. 50(2):174-188


el filtro de partículasdep.fie.umich.mx/~camarena/presentacionparticlefilter.pdfel filtro de...

Documents