Filtros de partículas

Um tratamento mais técnico desta postagem de blog foi originalmente publicado no blog da Udacity .

Os robôs usam um algoritmo surpreendentemente simples, mas poderoso, para descobrir onde estão em um mapa, um problema chamado pelos engenheiros de localização. O algoritmo conhecido como filtragem de partículas parece incrivelmente legal. A primeira parte deste artigo de duas partes foi publicada aqui . Neste primeiro artigo, vamos elucidar a matemática necessária para construir seus próprios filtros de partículas.

Os carros autônomos são projetados para se comportar de maneira muito parecida com os motoristas humanos . Um sistema típico de carro autônomo é composto de seis componentes. Cada um dos seis componentes resolve um problema crítico necessário para dirigir, autônomo ou não. Os componentes podem ser pensados ​​como executando as funções que imitam os motoristas humanos, que são:

Localização : Onde estamos?
Planejamento de rota : Como chegamos ao destino?
Percepção : O que mais há nos arredores?
Previsão : Como será o ambiente um pouco mais tarde?
Planejamento : Qual é o curso que seguiremos nos próximos segundos?
Controle : Como vamos seguir o rumo que queremos?

A localização para humanos tende a ser muito fácil. Normalmente, lembramos da memória onde estamos no mundo, geralmente auxiliados por um dispositivo GPS como um smartphone que nos ajuda a identificar nossa localização com muito mais precisão em um mapa. Também usamos pistas visuais como sinais de navegação, marcações de faixa e nossa compreensão de outros veículos, da estrada e dos arredores para garantir que estamos sempre na faixa certa, na estrada certa e na direção certa.

Quando se trata de localização, a direção autônoma também requer a posição e a direção em que o veículo está se movendo, também chamado de direção. No entanto, ao contrário dos humanos, o nível de precisão exigido pelos veículos autônomos é muito alto. Não basta apenas saber que um veículo está na faixa da direita e paralelo à faixa. Alta precisão é necessária para o planejamento. Se a localização estiver errada por mais de alguns centímetros em relação à posição ou em mais de alguns graus em relação ao rumo, o componente de planejamento pode gerar um curso desastroso, resultando em uma colisão entre muitos outros resultados indesejados.

Como os humanos, os veículos autônomos obtêm sua primeira estimativa de posição e direção a partir de um GPS. Os receptores de GPS, mesmo os minúsculos encontrados em um smartphone, tendem a ser bastante precisos. No entanto, a precisão das informações de localização recebidas de um GPS é inadequada para uma direção autônoma segura. Por exemplo, a posição relatada pode variar de um metro a vários metros ou, no pior dos casos, ainda mais.

A precisão varia com frequência e descontroladamente, dependendo de fatores como o número de satélites visíveis para o receptor, reflexos de feixes de satélite em objetos grandes como edifícios e absorção por elementos atmosféricos.

Se isso não for ruim o suficiente, a taxa na qual o GPS atualiza as informações de localização também é bastante lenta, variando entre 1–10 Hz. Mesmo a 10 Hz, um veículo se movendo a 20 km/h atrasado teria se movido cerca de meio metro entre duas atualizações de GPS.

Para mitigar a incerteza na localização devido ao movimento, os veículos autônomos usam unidades de medida inercial (IMUs). As IMUs são rápidas e precisas e medem a aceleração e a taxa de curva de um veículo. Esta informação pode então ser usada para determinar a posição do carro entre duas atualizações sucessivas do GPS. As IMUs tendem a acumular pequenos erros de aproximação ao longo do tempo, mas esse não é o problema com o qual estamos lidando aqui.

O principal problema com o qual o sistema de localização precisa lidar é que as atualizações do GPS são inerentemente imprecisas. Em vez de relatar uma posição exata, por exemplo, o GPS informa uma pequena área no solo onde é provável que um veículo esteja presente quando o GPS se atualizar. Referimo-nos a esta área como um ponto de GPS.

O problema de realizar uma localização precisa se reduz ao problema de reduzir a área do ponto GPS.

Uma das técnicas que têm sido utilizadas na robótica para localização precisa, a partir de uma menos precisa, é conhecida como filtragem de partículas . É útil quando o ambiente possui vários pontos de referência, ou seja, objetos grandes e estacionários que não mudam frequentemente de localização, aparência e tamanho. Podem ser edifícios, torres de telefonia celular, pilares de pontes, postes de serviços públicos ou sinais de trânsito e sinalizações.

Para entender como as partículas filtram, usaremos uma analogia. Suponha que você volte cansado para um quarto de hotel, apague as luzes e caia na cama de barriga para baixo. Você acorda no meio da noite e quer descobrir onde está. Claro, você se lembra de ter caído na cama, mas gostaria de saber em que direção está olhando, onde estão os interruptores de luz e onde estão seus chinelos. Isso exige mais precisão do que uma vaga lembrança de estar na cama.

Para se orientar rapidamente, você faz uso dos arredores. Você primeiro se imagina em locais diferentes na cama. Então você sente os objetos 'marcos' nos arredores, tocando e identificando-os. Você pode empurrar uma garrafa de água de uma mesa próxima ou bater com o dedo do pé em uma cadeira. Essas observações fornecem pistas importantes sobre onde você provavelmente estará no reino da cama do hotel. Como você se lembra onde a mamadeira, a mesa e a cadeira estavam em relação à cama, você pode inferir sua posição na cama com mais precisão. A cada nova observação, você pode descartar determinados locais da cama e aumentar suas chances de estar em outros locais.

É exatamente assim que a filtragem de partículas funciona para veículos autônomos. Armado com um ponto GPS inicial, o veículo conhece sua posição aproximada e direção no mapa. Esta posição aproximada é então dividida em pequenas células imaginárias. O veículo também sabe quais pontos de referência existem nas proximidades desse local difícil. O veículo então avalia a distância até esses pontos de referência usando um lidar a bordo. O sistema de localização então registra essas medições em cada célula imaginária. À medida que mais e mais pontos de referência são investigados, a maioria das células é descartada e apenas algumas altamente prováveis ​​permanecem como locais prováveis.

O nome filtragem de partículas vem do fato de que a localização de cada célula imaginária é representada como partícula no mapa e descartamos as partículas filtrando-as calculando distâncias para pontos de referência e descartando partículas que não parecem estar à distância certa de os marcos.

A animação abaixo mostra a localização inicial das partículas abrangendo uma área considerável, que pode se espalhar por várias pistas, estradas e áreas abertas. A detecção ou sondagem do ambiente é mostrada pelos raios azuis. O ponto verde que representa a posição mais provável inicialmente salta pelo mapa, mas se acomoda muito rapidamente à medida que mais e mais partículas são descartadas pela detecção do ambiente.

A filtragem de partículas é um algoritmo incrivelmente simples que alimenta muitos robôs e carros autônomos. Nvidia Drive Labs lançou um pequeno vídeo sobre como a localização pode se beneficiar de mapas avançados, com uma variedade de pontos de referência. O Uber ATG publicou um blog sobre como eles melhoram a precisão do GPS aqui .