- Como medições de posição e velocidade no mundo real sempre oscilam, o filtro de Kalman pode ser entendido como uma forma de combinar várias fontes de informação imperfeitas para produzir uma estimativa de estado mais confiável
- No exemplo da posição de um barco, um modelo com velocidade do motor de 10 m/s falha por causa de vento e ondas, e sensores como GPS também não são sempre precisos por conta de ruído ou falhas
- O código de exemplo faz 1000 passageiros criarem, cada um, uma estimativa baseada na velocidade e uma medição do sensor, e combina os dois valores com uma média ponderada para mostrar a intuição do filtro de Kalman
- A confiabilidade das fontes de informação é calculada pela variância das medições; o lado com maior variação recebe menos confiança, e o lado mais consistente recebe mais peso usando
1/variance
- Quando o sensor está normal, o sistema segue mais os valores do sensor; em trechos instáveis como
t=3 e t=6, sua influência diminui automaticamente, mantendo uma estimativa mais estável
Situações em que um filtro de Kalman é necessário
- O filtro de Kalman pode ser visto como um funil que comprime várias fontes de informação com ruído em um único valor estatístico mais preciso
- Matematicamente, ele envolve álgebra linear, probabilidade e cálculo, mas aqui o foco está mais na intuição do que na teoria completa
- Suponha que um barco parta do porto em
x=0 e se mova em uma dimensão, com o motor fornecendo uma velocidade constante de 10 m/s
- Em um mundo ideal, após 2 segundos a posição seria
2 * 10 = 20m, mas no mundo real a velocidade e a posição não se mantêm exatas por causa do motor, do vento e das ondas
- Portanto, só com a fórmula da posição é difícil ter certeza da posição real do barco
Sensores também não são perfeitos
- Se houver um sensor como GPS, é possível medir diretamente a posição em um instante específico, mas a medição do sensor também não é sempre exata
- Em 3 segundos, o GPS pode fornecer valores próximos da posição real, como 29.998 m e 30.002 m, mas em casos muito raros pode devolver algo bem fora, como 100 m
- Em áreas sem cobertura de satélite, o sensor de GPS pode praticamente deixar de funcionar
- Se o sensor nunca ficasse offline e pudesse medir qualquer valor desejado com precisão arbitrária, não haveria necessidade de filtro de Kalman
- O filtro de Kalman permite combinar várias fontes de informação, como estimativa de posição baseada na velocidade, estimativa via GPS, radar e sonar, para estimar a posição com mais precisão
Estimativa de posição vista no código
- O exemplo assume que há 1000 passageiros no barco, e que cada passageiro tem seu próprio dispositivo GPS
- Cada passageiro primeiro estima a nova posição somando à posição anterior a velocidade e a variação de fatores externos
from random import gauss
def new_position(last):
velocity = 10
wind = gauss(0, 2)
wave = gauss(0, 0.1)
return last + velocity + wind + wave
gauss gera valores aleatórios positivos ou negativos, e o segundo parâmetro representa o tamanho da variação- Como não é possível medir diretamente o efeito do vento e das ondas, o exemplo modela esse ruído com números aleatórios de média 0 e desvio padrão
2 e 0.1
- Na segunda etapa, o sensor retorna um valor medido somando ruído do sensor à posição real
def sensor(t):
if t == 3:
# oops, passing through a thunderstorm. GPS fluctuating!
sensor_noise = gauss(5, 10)
elif t == 6:
# uh-oh, satellite unavailable!
sensor_noise = gauss(-5, 10)
else:
sensor_noise = gauss(0, 1)
return true_position[t] + sensor_noise
- Em
t=3, o GPS oscila por causa de uma tempestade; em t=6, o cenário modela a indisponibilidade de satélite
- Mesmo no mesmo instante, cada passageiro obtém uma medição diferente do sensor
Trajetória real e média simples
- A posição real do barco é dada pela lista a seguir
true_position = [0, 9, 19.2, 28, 38.1, 48.5, 57.2, 66.2, 77.5, 85, 95.2]
- O barco parte do porto em
x=0, está a 9 m após 1 segundo, a 19.2 m após 2 segundos, e depois segue conforme os valores da lista
- O objetivo dos passageiros é prever, o mais precisamente possível, a posição em cada segundo usando medições com ruído e pouco confiáveis
- Em
t=1, se a estimativa baseada na velocidade de um passageiro for 9.37 e a medição do sensor for 8.98, a média simples será 9.17
- Quando a posição real é 9 m, essa média simples tem erro menor do que a estimativa de velocidade, mas pode ser pior do que a medição do sensor desse exemplo
Média ponderada e confiabilidade
- Em vez de média simples, usa-se uma média ponderada como método melhor
def combine(A, B, trustA, trustB):
total_trust = trustA + trustB
return (A * trustA + B * trustB) / total_trust
combine(9.37, 8.98, 10, 1) confia mais na estimativa de velocidade, então o resultado fica próximo de 9.37, dando 9.33combine(9.37, 8.98, 1, 10) confia mais na medição do sensor, então o resultado fica próximo de 8.98, dando 9.01- Essa média ponderada baseada em confiança é a principal intuição por trás do filtro de Kalman e o centro da força de combinação de dados
- Decidir em qual fonte confiar mais é algo determinado pela variância
- Fontes de informação cujas conclusões variam muito recebem menos confiança
- Fontes de informação consistentes recebem mais peso
- Se, entre 10 estações de rádio, 4 disserem que vai chover e 6 disserem que vai fazer sol, enquanto entre 10 sites 9 disserem que vai chover, os sites têm menor variância e podem ser considerados mais confiáveis
Etapa de atualização
- A atualização completa cria, para cada passageiro, uma estimativa baseada na velocidade e uma medição do sensor, depois calcula a confiança com base na variância desses dois conjuntos de medições
from statistics import variance
def update(t, last):
velocity_updates = []
sensor_updates = []
for p in range(1000):
velocity_updates.append(new_position(last[p]))
sensor_updates.append(sensor(t))
fluctuation_velocity = variance(velocity_updates)
fluctuation_sensor = variance(sensor_updates)
trust_velocity = 1 / fluctuation_velocity
trust_sensor = 1 / fluctuation_sensor
combined = []
for p in range(1000):
combined.append(combine(
A=velocity_updates[p],
B=sensor_updates[p],
trustA=trust_velocity,
trustB=trust_sensor
))
return sensor_updates, velocity_updates, combined
- Como quanto maior a variância menor a confiança, usa-se
1/variance
- Cada passageiro atualiza sua própria posição individualmente
- Depois que todas as posições dos passageiros são atualizadas, a estimativa da posição real do barco pode ser inferida pela média das posições dos passageiros
Como ler os resultados
- A função
update_plot armazena, para criar o gráfico, a posição real, a estimativa do sensor, a estimativa de velocidade e a estimativa combinada em cada instante
- O loop principal continua atualizando a estimativa da posição em cada instante usando a melhor estimativa atual que os passageiros possuem
- No gráfico, o envelope ao redor das linhas representa a incerteza; quanto maior a largura, maior a incerteza daquele valor
- No intervalo de
t=0.75 até t=1, quando o sensor está funcionando normalmente, a estimativa combinada de posição é melhor do que usar apenas a estimativa de velocidade, mas pode ser pior do que usar apenas a medição do sensor
- No intervalo de
t=2 até t=4, quando o sensor falha, a estimativa combinada mostra resultados melhores do que usar somente a medição defeituosa do sensor
- No intervalo de
t=4 até t=5, quando o sensor se recupera, o filtro de Kalman volta a preferir mais o sensor
Apêndice: gauss e variância
- A
normal distribution function gauss(0, 0.1) e gauss(0, 2) geralmente geram valores aleatórios próximos de 0
- O segundo parâmetro, o desvio padrão, controla o quanto as medições oscilam
gauss(0, 0.1) tende a produzir valores pequenos, próximos de 0, como 0.06, -0.07 e 0.02gauss(0, 2) tende a produzir valores mais espalhados, como 1.05, -1.06, 1.29 e -1.72
- No código de exemplo, assume-se que o vento varia mais e as ondas variam menos
- A variância é uma medida de consistência: quando a consistência é alta, a variância é baixa; quando a consistência é baixa, a variância é alta
- Uma distribuição com desvio padrão 2 tem variância 4, e uma distribuição com desvio padrão 0.1 tem variância 0.01
1 comentários
Opiniões no Hacker News
Li o texto com interesse, mas a implementação está errada. O maior erro é que ela não propaga a incerteza ao longo do eixo do tempo, o que subestima o erro
Isso também aparece no gráfico: a faixa de erro deveria conter o estado real na maior parte do tempo, mas no resultado isso não acontece
Não é que os passageiros acrescentem ruído à estimativa; do ponto de vista de um passageiro, dado o estado no instante k, o valor esperado do estado no instante k+1 é simplesmente
position_k+1 = position_k + velocity * Delta_t. Há ruído na dinâmica real, e o filtro reflete isso somando-o à covariância estimadaO motivo de o código não quebrar imediatamente é que ele tira muitas amostras da dinâmica com 1000 passageiros e calcula numericamente a variância do resultado, mas isso é bem diferente do que normalmente se faz na prática
Além disso, é um equívoco comum dizer que o GPS é afetado pelo clima; na realidade, não é. E a definição de consistência usada no texto também não é padrão. Em teoria da estimação, dizer que um estimador é consistente significa que, à medida que há mais dados, a estimativa converge para o valor verdadeiro
É bom que o texto explique de forma acessível para leitores leigos, mas alguns mal-entendidos parecem estar causando problemas. Sou pós-graduando em teoria da estimação, então posso ajudar se quiserem discutir mais
Cheguei a me perguntar por que aulas universitárias de processamento de sinais não ensinam o Kalman Filter de um jeito tão simples. Conceitos matemáticos devem mesmo ser ensinados matematicamente, mas, para quem não tem a base necessária, há perda de informação
Antigamente ensinei transformada discreta do cosseno e transformada wavelet com foco em imagens, e o método de dar a intuição antes do rigor sempre funcionou melhor do que a ordem inversa
Pode haver alguns motivos para professores não começarem pela intuição. Pode ser que o próprio professor tenha uma especialização mais profunda em números e manipulação de equações do que em intuição; pode ser que a competência pedagógica não seja recompensada e, por isso, o tempo necessário para explicar intuitivamente seja gasto escrevendo propostas de financiamento ou orientando doutorandos; e pode ser também que, depois de entender a matemática, uma explicação intuitiva passe a parecer o “caminho difícil” e o cérebro se recuse a voltar atrás
Acho que o terceiro motivo é especialmente o maior. Isso também é a diferença entre especialização e competência pedagógica, indo além do ensino de matemática. Para aprender a dar uma tacada de driver no golfe, talvez seja melhor aprender com alguém que começou batendo 100 jardas e depois passou a bater 300 jardas de forma consistente do que com a pessoa que bate mais longe
Como alerta geral para quem quer implementar um Kalman Filter, vale ler as primeiras páginas de https://www.stat.berkeley.edu/~brill/Stat248/kalmanfiltering... sobre como lidar com instabilidade numérica
Na prática, mesmo fazendo isso, raramente vi artefatos numéricos perceptíveis, mas é uma solução bastante atraente
Como complemento a este texto, se você quiser uma introdução mais rigorosa e matemática à família de Kalman Filters, recomendo muito este livro: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
É um livro escrito por um engenheiro de software que precisou implementar Kalman Filter no trabalho, então a forma como ele motiva e transmite os conceitos pode combinar bem com esse público. Ele foi escrito como notebooks Jupyter interativos, então é possível clonar o repositório, executar por conta própria e acompanhar
Ele começa com filtros simples e vai melhorando gradualmente, incorporando a regra de Bayes e expandindo para distribuições de probabilidade, oferecendo uma rampa de entrada suave para o Kalman Filter
Há um aspecto que ficou de fora. Ao fazer a média ponderada entre a previsão e a medição, os pesos do Kalman Filter podem mudar ao longo do tempo. Caso contrário, acho que ele receberia outro nome
Um bom exemplo é medir com um único sensor um valor que muda lentamente. Por exemplo, em um medidor de combustível, é melhor estimar que não há mudança em escala de segundos, mas as medições podem ter ruído, como o combustível chacoalhando dentro do tanque
Nesse caso, o Kalman Filter se parece com um filtro passa-baixas de primeira ordem com ganho que decai exponencialmente. A frequência de corte muda, de modo que ele encontra rapidamente o nível inicial em alguns segundos e, depois, pode ignorar o ruído com uma frequência de corte muito baixa, como 0,01 Hz
Um bom texto sobre uma ferramenta importante.
Pelo que entendo, o Kalman Filter linear é a solução ótima para problemas lineares, e é relativamente fácil de entender e implementar. Mas a maioria das aplicações que vi era não linear.
O Kalman Filter estendido e o Unscented Kalman Filter eram muito mais difíceis de entender e implementar, e havia menos materiais e bibliotecas, além de serem menos úteis.
Por exemplo, ao lidar com um dispositivo AHRS/GNSS CAN para pequenos UAVs, o Kalman Filter estendido que vi no PX4 ou no Ardupilot era muito complexo e tinha muitos parâmetros. Então era mais simples partir dos princípios básicos dos quaternions e corrigir aos poucos a solução do giroscópio na direção do “para cima” do acelerômetro e do vetor de inclinação do magnetômetro.
Se a magnitude da aceleração fosse muito diferente de 1G ou o vetor do campo magnético diferisse muito da intensidade do campo magnético terrestre local, eu reduzia o peso da atualização desse sensor ou a pulava, deixando o giroscópio seguir sozinho. Provavelmente o EKF tem grandes chances de ser a resposta certa, mas desisti de ajustá-lo de uma forma fácil de entender, construir, regular e diagnosticar.
No entanto, em quadricópteros, a grande dificuldade é a rotação. O modelo linear do Kalman Filter assume que tudo está em um espaço euclidiano, mas rotações vivem em uma variedade. No caso dos quaternions, essa variedade é o conjunto dos quaternions unitários.
Se você aplicar ingenuamente um EKF para estimar quaternions, eles deixam de ser quaternions unitários e a estimativa se estraga. Há métodos conhecidos para lidar com essa restrição de variedade, mas eles estavam entre as equações mais feias que já tentei transformar em código.
Como exemplo simples, dá para imaginar um estado
(x, y)que, por causa das leis da física, deve estar sempre no círculo unitário. A dinâmica realf(x, y)produz um novo ponto no círculo, mas a dinâmica aproximada linearizada não tem garantia de permanecer no círculo unitário, o que pode levar a estados não físicos ou a uma estimativa de estado ruim no EKF.Algumas opções que valem conferir são ForneyLab.jl, Infer.net, Gen.jl e Pyro.
Mas há muitas formas de usar um Kalman Filter e, dependendo de onde você começa, lidar corretamente com transformações não lineares pode se tornar extremamente trabalhoso.
Tenho miopia e astigmatismo e, quando fecho um olho e olho para algo como um relógio de parede, percebo que cada olho produz uma imagem distorcida de forma diferente. Os dois olhos são um pouco diferentes.
Mas, quando olho para o relógio com os dois olhos, a imagem fica muito mais nítida, melhor do que com qualquer um dos olhos sozinho. O cenário do texto em que 1000 passageiros de um navio informam suas coordenadas de GPS me lembrou esse fenômeno.
Acho que o cérebro também deve usar amplamente algoritmos inteligentes como o Kalman Filter.
Está certo entender o Kalman Filter como algo que estima valores melhores do que uma média simples a partir de observações com ruído?
Por exemplo, se eu medir algo 3 vezes e obtiver 7, 8 e 9, eu chutaria que o valor real é 8; o Kalman Filter produziria outra estimativa?
O Kalman Filter é tradicionalmente usado para estimar coisas que se movem ao longo do tempo. Pense em uma pessoa em um vídeo ou em algum tipo de passeio aleatório.
Se você assume que há uma relação, como velocidade e direção atual, entre dois instantes ou medições consecutivas, pode combinar a informação do modelo de movimento com a informação do modelo de medição ruidoso para estimar melhor a posição, o valor ou até todo o histórico de movimento.
Se o modelo de movimento estiver significativamente errado, a estimativa não melhora. Muitas extensões posteriores se concentram em incluir modelos de movimento mais sofisticados, como deslizamento de rodas em robótica.
Por exemplo, suponha que você esteja medindo uma constante. Como modelo básico, você pode ter uma constante com incerteza inicial, por exemplo uma distribuição Gaussian com desvio padrão, e medições também com ruído Gaussian e desvio padrão. Você pode ajustar a incerteza inicial em torno da constante que está tentando estimar e a incerteza das medições.
Nesse exemplo, o Kalman Filter não se comporta como uma média. Se as medições forem boas, ou seja, tiverem baixa incerteza, ele converge rapidamente; se as medições forem ruins, a estimativa oscila e leva mais tempo para convergir.
E não é verdade que o Kalman Filter seja usado apenas para coisas em movimento. Ele também é usado o tempo todo para estimativa de constantes, só é mais famoso em objetos em movimento.
O Kalman Filter lida com casos em que as amostras são correlacionadas por alguma dinâmica linear. A medição nem precisa ser o próprio objeto de interesse; também pode ser uma função linear desse objeto somada a ruído Gaussian.
Portanto, saber que você viu 7 na primeira medição altera a probabilidade de ver 8 na segunda. Se você apenas tirar a média amostral como acima, em geral ela não converge para o valor médio real.
O que ele produziria no exemplo depende do modelo exato. Mesmo no cenário mais simples imaginável, assim como em Bayes, é preciso especificar com qual valor esperado você começa.
Se você codificar essa expressão como um modelo Gaussian linear, isso vira um Kalman Filter.
Um texto curto que também me trouxe um insight ao entender o Kalman Filter foi a nota de John D. Cook: https://www.johndcook.com/blog/applied-kalman-filtering/
Enquanto a modelagem tradicional de sistemas baseada em cálculo e equações diferenciais considera que não há incerteza nos dados e que tudo está contido no modelo do sistema, estimadores baseados em dados veem que “tudo está nos dados” e ignoram completamente o modelo do processo físico que gera os dados
A beleza do Kalman Filter está em combinar essas duas abordagens
Há também outro artigo com boas visualizações: https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture...
É um texto que já apareceu três vezes no HN