Particle Filter

Também chamado: sequential Monte Carlo, SMC, bootstrap filter
Categoria: State estimation & navigation › Localisation
Tags: state-estimation, localization, bayesian-filtering, probabilistic-robotics, monte-carlo

Um método de estimação de estado que representa uma crença como um conjunto de amostras ponderadas, movendo-as com um modelo de movimento, ponderando-as pela verossimilhança do sensor e reamostrando.

Definição

Filtro de partículas (particle filter) é um estimador bayesiano recursivo que representa a distribuição de probabilidade sobre o estado de um sistema com um conjunto de amostras, chamadas partículas, cada uma com um peso. A abordagem também é conhecida como Monte Carlo sequencial (sequential Monte Carlo); sua forma mais citada, o filtro bootstrap, foi publicada por Gordon, Salmond e Smith em 1993. Na robótica, tornou-se padrão com a localização de Monte Carlo (Monte Carlo localization), desenvolvida por Dellaert, Fox, Burgard e Thrun, e é tratada em profundidade em Probabilistic Robotics.

Cada atualização tem três passos. No passo de predição, cada partícula é movida de acordo com o modelo de movimento, com ruído adicionado para refletir a incerteza da odometria ou do controle. No passo de atualização, cada partícula recebe um peso conforme o quanto a última medição do sensor concorda com o estado que ela representa. No passo de reamostragem, um novo conjunto de partículas é sorteado em proporção aos pesos, de modo que hipóteses prováveis são duplicadas e as improváveis desaparecem. A estimativa pode ser lida da média ponderada, da melhor partícula ou de um agrupamento de partículas.

Ao contrário do filtro de Kalman e suas extensões, um filtro de partículas não supõe que a crença seja gaussiana. Ele pode manter várias hipóteses separadas ao mesmo tempo, como um robô que poderia estar em um de dois corredores idênticos, ou um objeto seguro em uma mão que poderia estar em várias poses compatíveis com os contatos sentidos até então. O custo é computacional: o número de partículas necessário cresce rapidamente com a dimensão do estado, e se poucas partículas caírem perto do estado verdadeiro, o filtro pode colapsar em uma resposta errada. Por isso os filtros práticos usam reamostragem de baixa variância, reamostram apenas quando o tamanho efetivo da amostra cai, adaptam o número de partículas e injetam partículas aleatórias para se recuperar de falhas.

Por que importa

Muitos problemas de estimação em robótica são não lineares e ambíguos, com crenças que têm vários picos em vez de um. O filtro de partículas lida com eles diretamente, e é por isso que é a base da localização 2D padrão em robôs móveis e uma ferramenta comum para estimar a pose de objetos a partir de contato e tato.

Principais aplicações

Localização de robôs móveis em relação a um mapa conhecido (localização de Monte Carlo)
Estimativa da pose de um objeto na mão a partir de propriocepção e contato tátil
Rastreamento de pessoas e objetos em cenas congestionadas ou com oclusões
SLAM com filtros de partículas Rao–Blackwellizados, como FastSLAM e GMapping
Localização global e recuperação quando um robô é movido sem saber

Na prática

Um robô de armazém que roda a pilha de navegação do ROS normalmente se localiza com o AMCL, um pacote de localização de Monte Carlo adaptativa. Na inicialização, o operador fornece uma pose inicial aproximada, e alguns milhares de partículas são espalhadas ao redor dela. À medida que o robô se desloca, a odometria das rodas move as partículas e cada varredura do lidar as repondera em relação ao mapa de ocupação armazenado; a nuvem se concentra em torno da pose verdadeira em poucos metros de percurso. Os engenheiros ajustam os parâmetros de ruído da odometria para corresponder ao trem de tração real, definem os números mínimo e máximo de partículas e observam a nuvem de partículas no RViz: uma nuvem que se divide em dois agrupamentos em um corredor repetitivo é sinal de que o filtro está rastreando duas hipóteses e precisa de um elemento distintivo para resolvê-las.

Equívocos comuns

Mais partículas sempre resolvem problemas de precisão — a quantidade de partículas necessária cresce rapidamente com a dimensão do estado, então problemas de alta dimensão precisam de distribuições de proposta melhores ou de estrutura, não só de mais amostras
Um filtro de partículas é só um filtro de Kalman mais lento — ele representa crenças não gaussianas e com vários picos que filtros do tipo Kalman não conseguem representar
Reamostrar a cada passo é sempre o melhor — reamostrar com frequência demais descarta diversidade; muitos filtros reamostram apenas quando o tamanho efetivo da amostra cai abaixo de um limiar
O filtro sempre vai se recuperar de uma estimativa errada — depois que as partículas colapsaram longe do estado verdadeiro, elas não conseguem voltar a menos que partículas aleatórias sejam injetadas

Quem deve saber

Engenheiros de localização e navegação de robôs móveis
Desenvolvedores de estimação de estado e SLAM
Pesquisadores de manipulação que estimam a pose de objetos pelo tato
Estudantes de robótica que estudam robótica probabilística

Tecnologias relacionadas

Localização de Monte Carlo (Monte Carlo Localization, AMCL)
Filtro de Kalman (Kalman Filter)
FastSLAM
Amostragem por importância (Importance Sampling)
Mapa de grade de ocupação (Occupancy Grid Map)

Termos relacionados

Projetos relacionados

Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
GTSAM: Factor-graph optimization library powering many modern SLAM backends
OpenVINS: The reference open platform for visual-inertial state estimation research
AprilTag: The standard visual fiducial marker system for robot localization and pose estimation
GLIM: GPU-accelerated 3D lidar SLAM framework for any range sensor, from AIST

Vídeos

Understanding the Particle Filter | | Autonomous Navigation, Part 2: MATLAB
Particle Filter - 5 Minutes with Cyrill: Cyrill Stachniss