Filtro de Partículas

Visão geral

Um filtro de partículas (particle filter) — também conhecido como Monte Carlo Sequencial (Sequential Monte Carlo, SMC) — é um método de filtragem Bayesiana não paramétrica (nonparametric Bayesian filtering) para estimar o estado oculto (hidden state) de um sistema ao longo do tempo quando as dinâmicas e/ou medições são não lineares (nonlinear) e não Gaussianas (non-Gaussian). Diferentemente da família do Filtro de Kalman (Kalman Filter) (que depende de suposições Gaussianas ou linearizações), filtros de partículas aproximam a distribuição a posteriori completa com um conjunto de amostras ponderadas (“partículas”).

Filtros de partículas são amplamente usados em robótica para rastreamento (tracking), localização de robôs (robot localization) e problemas relacionados à Localização e Mapeamento Simultâneos (Simultaneous Localization and Mapping, SLAM), onde a incerteza pode ser multimodal (por exemplo, leituras ambíguas de sensores) e os modelos de movimento/medição raramente são perfeitamente lineares ou Gaussianos.

Este artigo se insere em Filtragem Bayesiana (Bayesian Filtering): é uma das principais ferramentas para estimação recursiva de estado quando filtros em forma fechada são inviáveis.

Formulação do problema: modelos em espaço de estados (dinâmicos)

Filtros de partículas tipicamente assumem um modelo em espaço de estados Markoviano (Markovian):

Transição de estado (modelo de movimento (motion model))
[ x_t \sim p(x_t \mid x_{t-1}) ]
Observação (modelo de sensor (sensor model))
[ y_t \sim p(y_t \mid x_t) ]

Objetivo: estimar recursivamente a distribuição de filtragem (filtering distribution) (crença): [ p(x_t \mid y_{1:t}) ] onde (y_{1:t} = {y_1,\dots,y_t}).

A recursão de filtragem Bayesiana é:

Prever [ p(x_t \mid y_{1:t-1}) = \int p(x_t \mid x_{t-1}) , p(x_{t-1}\mid y_{1:t-1}) , dx_{t-1} ]
Atualizar [ p(x_t \mid y_{1:t}) \propto p(y_t \mid x_t), p(x_t \mid y_{1:t-1}) ]

Para modelos não lineares/não Gaussianos, essas integrais e distribuições em geral não são tratáveis analiticamente — filtros de partículas as aproximam por amostragem.

Ideia-chave: representar a posteriori com partículas ponderadas

Um filtro de partículas mantém (N) partículas: [ {x_t^{(i)}, w_t^{(i)}}{i=1}^N ] de modo que: [ p(x_t \mid y{1:t}) \approx \sum_{i=1}^N w_t^{(i)} , \delta(x_t - x_t^{(i)}) ] onde (\delta(\cdot)) é um delta de Dirac (Dirac delta) e os pesos satisfazem (\sum_i w_t^{(i)} = 1).

Intuitivamente:

Cada partícula é uma hipótese sobre o estado atual.
Cada peso indica o quão consistente essa hipótese é com as observações.

Você pode estimar esperanças como (E[f(x_t)\mid y_{1:t}]) por: [ \sum_{i=1}^N w_t^{(i)} f(x_t^{(i)}) ]

O ciclo prever–atualizar em filtros de partículas

Um filtro de partículas de base comum é o filtro bootstrap (bootstrap filter) (também chamado de SIR: Amostragem–Importância–Reamostragem (Sampling-Importance-Resampling)). Ele usa o prior de transição (p(x_t\mid x_{t-1})) como a distribuição proposta.

Etapa 1: Prever (propagar partículas)

Para cada partícula: [ x_t^{(i)} \sim p(x_t \mid x_{t-1}^{(i)}) ]

Isso implementa a etapa Bayesiana de previsão via Monte Carlo: você empurra as partículas através do modelo de movimento.

Etapa 2: Atualizar via ponderação por importância

Após observar (y_t), compute pesos não normalizados: [ \tilde{w}t^{(i)} = w{t-1}^{(i)} , p(y_t \mid x_t^{(i)}) ] e então normalize: [ w_t^{(i)} = \frac{\tilde{w}t^{(i)}}{\sum{j=1}^N \tilde{w}_t^{(j)}} ]

Isso é amostragem por importância (importance sampling) em um contexto sequencial (ver também Amostragem por Importância (Importance Sampling)).

Etapa 3: Reamostrar (opcional, mas comum)

Ao longo do tempo, os pesos tendem a ficar muito desiguais: a maioria das partículas fica com peso minúsculo, e algumas poucas dominam. A reamostragem substitui o conjunto ponderado por um conjunto não ponderado (ou igualmente ponderado), sorteando partículas proporcionalmente aos seus pesos.

Após reamostrar, tipicamente define-se: [ w_t^{(i)} = \frac{1}{N} ]

A reamostragem combate o colapso de pesos, mas pode reduzir a diversidade (empobrecimento de partículas). Esse trade-off é central na filtragem por partículas.

Visão de amostragem por importância (distribuição proposta geral)

O filtro bootstrap usa a proposta (q(x_t \mid x_{t-1}^{(i)}, y_t) = p(x_t \mid x_{t-1}^{(i)})). De forma mais geral, você pode amostrar de qualquer proposta (q) e corrigir com pesos de importância:

Amostrar: [ x_t^{(i)} \sim q(x_t \mid x_{t-1}^{(i)}, y_t) ]
Ponderar: [ \tilde{w}t^{(i)} = w{t-1}^{(i)} \cdot \frac{p(y_t \mid x_t^{(i)}), p(x_t^{(i)} \mid x_{t-1}^{(i)})} {q(x_t^{(i)} \mid x_{t-1}^{(i)}, y_t)} ]

Usar uma proposta melhor pode reduzir drasticamente a variância dos pesos — especialmente quando as observações são muito informativas.

Um resultado clássico: a proposta “ótima” (minimizando a variância dos pesos) é: [ q^*(x_t \mid x_{t-1}, y_t) = p(x_t \mid x_{t-1}, y_t) ] mas ela frequentemente é intratável, então filtros práticos a aproximam (por exemplo, com propostas baseadas em Filtro de Kalman Estendido (Extended Kalman Filter, EKF)/Filtro de Kalman Unscented (Unscented Kalman Filter, UKF)).

Degenerescência: por que a reamostragem é necessária

Degenerescência de pesos (weight degeneracy) significa que, após várias iterações, a maioria das partículas carrega peso desprezível. Na prática, o “tamanho amostral” colapsa mesmo que (N) seja grande.

Um diagnóstico padrão é o tamanho efetivo da amostra (effective sample size, ESS): [ N_{\text{eff}} = \frac{1}{\sum_{i=1}^N (w_t^{(i)})^2} ]

(N_{\text{eff}} \approx N): pesos razoavelmente uniformes.
(N_{\text{eff}} \ll N): degenerescência severa.

Uma regra comum: reamostrar quando (N_{\text{eff}} < \tau N) para (\tau \in [0.3, 0.8]).

Métodos de reamostragem (e seus trade-offs)

A reamostragem gera um novo conjunto de partículas no qual partículas com alto peso são duplicadas e as de baixo peso são descartadas.

Estratégias comuns:

Reamostragem multinomial (multinomial resampling): mais simples; maior variância.
Reamostragem sistemática (systematic resampling): baixa variância, muito comum em robótica.
Reamostragem estratificada (stratified resampling): também baixa variância.
Reamostragem residual (residual resampling): aloca deterministamente cópias inteiras mais um restante estocástico.

Na prática, reamostragem sistemática ou estratificada são escolhas padrão populares devido a melhor eficiência estatística.

Empobrecimento de partículas e rejuvenescimento

A reamostragem reduz a degenerescência, mas pode criar empobrecimento de partículas (particle impoverishment): muitas cópias idênticas de uma partícula, reduzindo a cobertura do espaço de estados — especialmente quando o ruído de processo é pequeno.

Mitigações comuns:

Adicionar perturbação (jitter) após reamostrar (cuidado: isso muda o modelo implícito, a menos que seja justificado).
Reamostrar-mover (resample-move): após reamostrar, aplicar um movimento de MCMC que deixe a posteriori-alvo invariante (ver Monte Carlo via Cadeias de Markov (Markov Chain Monte Carlo, MCMC)). Isso “rejuvenesce” a diversidade.
Usar propostas melhores: incorporar a observação atual na proposta para que partículas caiam em regiões de alta verossimilhança.
Aumentar o ruído de processo se ele estiver submodelado (erro de modelagem frequentemente aparece como empobrecimento).

Pseudocódigo do algoritmo de filtro de partículas (bootstrap/SIR)

Given particles {x_{t-1}^{(i)}, w_{t-1}^{(i)}} for i=1..N and new observation y_t:

1) Predict:
   for i=1..N:
       sample x_t^{(i)} ~ p(x_t | x_{t-1}^{(i)})

2) Update:
   for i=1..N:
       w_t^{(i)} <- w_{t-1}^{(i)} * p(y_t | x_t^{(i)})
   normalize weights so sum_i w_t^{(i)} = 1

3) Resample (if needed, e.g., if ESS < threshold):
   draw N particles from {x_t^{(i)}} with probabilities {w_t^{(i)}}
   set all weights to 1/N

Exemplo prático 1: rastreamento 1D de objeto com outliers (ruído não Gaussiano)

Imagine rastrear uma posição 1D (x_t) com uma caminhada aleatória (random walk) tipo velocidade:

Movimento: [ x_t = x_{t-1} + u_t + \epsilon_t,\quad \epsilon_t \sim \mathcal{N}(0,\sigma^2) ]
Medição com outliers ocasionais (caudas pesadas (heavy tails)): [ y_t = x_t + \eta_t ] onde (\eta_t) é uma mistura: com probabilidade 0.9, (\mathcal{N}(0, r^2)); com probabilidade 0.1, uma distribuição ampla de outliers.

Um filtro de Kalman tem dificuldade porque o ruído de medição não é Gaussiano; um filtro de partículas pode codificar diretamente a verossimilhança de mistura (mixture likelihood) (p(y_t\mid x_t)).

Código mínimo ilustrativo em estilo Python (foco: lógica, não otimização):

import numpy as np

def systematic_resample(weights, rng=np.random.default_rng()):
    N = len(weights)
    positions = (rng.random() + np.arange(N)) / N
    cumsum = np.cumsum(weights)
    idx = np.searchsorted(cumsum, positions)
    return idx

def particle_filter_step(particles, weights, y, u, sigma, r, outlier_r, outlier_p=0.1):
    rng = np.random.default_rng()
    N = len(particles)

    # Predict
    particles = particles + u + rng.normal(0, sigma, size=N)

    # Update: mixture likelihood
    innov = y - particles
    like_nom = np.exp(-0.5*(innov/r)**2) / (np.sqrt(2*np.pi)*r)
    like_out = np.exp(-0.5*(innov/outlier_r)**2) / (np.sqrt(2*np.pi)*outlier_r)
    likelihood = (1-outlier_p)*like_nom + outlier_p*like_out

    weights = weights * likelihood
    weights = weights / (weights.sum() + 1e-12)

    # ESS-based resampling
    ess = 1.0 / np.sum(weights**2)
    if ess < 0.5 * N:
        idx = systematic_resample(weights, rng)
        particles = particles[idx]
        weights = np.ones(N) / N

    return particles, weights

Este exemplo destaca dois pontos fortes de filtros de partículas:

Você pode usar verossimilhanças arbitrárias, incluindo misturas e distribuições de caudas pesadas.
A posteriori pode se tornar multimodal (multi-modal) se as medições forem ambíguas.

Exemplo prático 2: localização de robô móvel (Localização de Monte Carlo)

Em localização 2D, o estado do robô pode ser: [ x_t = (x, y, \theta) ] com controles (odometria (odometry)) conduzindo (p(x_t\mid x_{t-1}, u_t)), e sensores (por exemplo, lidar) fornecendo (p(y_t\mid x_t, \text{map})).

Localização de Monte Carlo (Monte Carlo Localization, MCL) é essencialmente um filtro de partículas em que:

Prever: amostrar cada partícula usando um modelo de movimento ruidoso a partir da odometria.
Atualizar: ponderar partículas pelo quão bem suas leituras de sensor previstas correspondem às leituras reais em comparação com um mapa conhecido (modelo de feixe (beam model), modelo de campo de verossimilhança (likelihood field model)).
Reamostrar: concentrar partículas em torno de poses plausíveis.

Por que filtros de partículas se encaixam bem:

A posteriori pode ser multimodal (por exemplo, corredores simétricos).
O modelo de medição pode ser complexo e não Gaussiano.
Você pode incorporar restrições do mapa e oclusões de forma probabilística.

Esse filtro de partículas de localização frequentemente é um bloco de construção dentro de variantes de Localização e Mapeamento Simultâneos.

Variantes e extensões comuns

Filtro de partículas bootstrap / SIR

Proposta: prior de transição (p(x_t\mid x_{t-1}))
Simples e amplamente usado
Pode falhar quando as medições são muito “agudas” (os pesos colapsam rapidamente)

Filtro de Partículas Auxiliar (APF)

Melhora a reamostragem ao selecionar partículas ancestrais usando uma estimativa do quão bem elas explicarão a nova observação. Isso ajuda quando algumas partículas são muito mais promissoras antes de você amostrar seus descendentes.

Filtros de partículas informados por EKF/UKF

Usam aproximações Gaussianas locais para construir propostas melhores:

Proposta centrada perto de estados prováveis dado (y_t)
Reduz substancialmente a variância dos pesos em sistemas com observações bem restritivas

Essa ideia se conecta a Filtro de Kalman Estendido e Filtro de Kalman Unscented: esses filtros fornecem condicionais aproximadas úteis para propostas.

Filtro de Partículas Rao–Blackwellizado (RBPF)

Se parte do modelo for condicionalmente linear-Gaussiana, você pode integrá-la analiticamente e apenas amostrar as variáveis restantes. Isso reduz a variância e pode ser dramaticamente mais eficiente (ver Rao-Blackwellização (Rao-Blackwellization)).

Uma aplicação famosa em robótica é o FastSLAM: partículas representam trajetórias do robô e, condicionadas a cada trajetória, estimativas de marcos são mantidas analiticamente (frequentemente com pequenos filtros de Kalman).

Reamostrar-mover / rejuvenescimento com MCMC

Após reamostrar, aplicar um núcleo de MCMC que deixe (p(x_t\mid y_{1:t})) invariante, restaurando a diversidade. Especialmente útil em configurações de alta dimensionalidade ou baixo ruído.

Quando usar filtros de partículas (e quando não)

Filtros de partículas são uma escolha forte quando:

Modelos são não lineares e/ou não Gaussianos
A posteriori pode ser multimodal
Você precisa de uma forma flexível de incorporar verossimilhanças realistas de sensores
A dimensão do estado é moderada (comum em robótica: 3–15, às vezes maior com estrutura)

Eles podem ter dificuldade quando:

A dimensão do estado é muito alta (maldição da dimensionalidade (curse of dimensionality): o (N) necessário pode explodir)
A verossimilhança de observação é extremamente aguda e as propostas são ruins
O orçamento computacional é restrito (restrições de tempo real com (N) grande)

Nesses casos, você pode considerar:

Filtros Gaussianos (EKF/UKF) quando as suposições forem razoáveis
Métodos de suavização por grafo de fatores (factor-graph smoothing methods) (em lote ou incremental) quando você puder arcar com a otimização
Métodos de partículas estruturados (RBPF) para reduzir a dimensão amostrada

Dicas de implementação e armadilhas comuns

Use log-pesos para estabilidade numérica

Verossimilhanças podem sofrer subfluxo. Armazene (\log w) e normalize via log-soma-exp (log-sum-exp):

Calcule (\log \tilde{w}i = \log w{i,\text{prev}} + \log p(y_t\mid x_t^{(i)}))
Subtraia o maior log-peso antes de exponenciar.

Escolha \(N\) com base em ambiguidade e ruído

Mais ambiguidade/multimodalidade → mais partículas
Sensores mais informativos com propostas ruins → mais partículas (ou proposta melhor)

Não existe um (N) universal; sistemas robóticos frequentemente usam de centenas a dezenas de milhares, dependendo de computação e tamanho do mapa.

Reamostre de forma adaptativa (limiar de ESS)

Reamostrar a cada passo pode adicionar variância e empobrecimento desnecessários. Reamostragem baseada em ESS é um compromisso comum.

Valide os modelos, não apenas o código

Filtros de partículas são “honestos” sobre incompatibilidade de modelo: se seu modelo de movimento estiver errado ou sua verossimilhança de medição estiver mal calibrada, o filtro pode:

colapsar para modos errados,
ficar confiante demais,
ou falhar em rastrear.

Depuração prática frequentemente começa com gráficos de:

nuvens de partículas ao longo do tempo,
ESS ao longo do tempo,
distribuições de verossimilhança.

Aplicações em IA/robótica

Filtros de partículas são usados em muitas tarefas de inferência sequencial, incluindo:

Rastreamento de alvos (target tracking): rastreamento visual, rastreamento por radar/sonar, rastreamento de múltiplas hipóteses (filtros de partículas podem representar múltiplos modos).
Localização de robôs (MCL): estimar a pose em um mapa conhecido usando lidar, câmera, Wi‑Fi, UWB etc.
Variantes de SLAM: especialmente métodos baseados em RBPF quando a estrutura permite.
Detecção de falhas / dinâmicas com comutação (switching dynamics): filtros de partículas podem incorporar modos latentes discretos (por exemplo, “normal” vs “falha”) como parte do estado.
Inferência não linear de séries temporais em economia, navegação e processamento de sinais.

Filtros de partículas são conceitualmente próximos a Modelos Ocultos de Markov (Hidden Markov Models) (inferência recursiva em modelos de Markov), mas visam espaços de estados contínuos ou complexos onde a inferência exata em HMM é inviável.

Resumo

Filtros de partículas (SMC) aproximam a posteriori de filtragem Bayesiana (p(x_t\mid y_{1:t})) usando um conjunto de partículas ponderadas. Eles implementam a recursão prever–atualizar por meio de amostragem e ponderação por importância, e administram o colapso de pesos via reamostragem — ao mesmo tempo em que lidam com degenerescência e empobrecimento.

Sua principal vantagem é a flexibilidade: eles podem lidar com dinâmicas não lineares, ruído não Gaussiano e crenças multimodais — tornando-os uma ferramenta fundamental em rastreamento e localização em robótica. Seus principais desafios são o custo computacional e a escalabilidade para estados de alta dimensionalidade, o que motiva variantes como filtros de partículas auxiliares, propostas melhores e métodos Rao–Blackwellizados.