Android

24 abr, 2018

Repensando o GPS: Engenharia de localização de última geração na Uber

Publicidade

A localização e a navegação usando sistemas de posicionamento global (GPS) estão profundamente enraizadas em nossas vidas diárias e são particularmente cruciais para os serviços da Uber. Para orquestrar embarques rápidos e eficientes, nossas tecnologias de GPS precisam saber a localização de passageiros e motoristas correspondentes, bem como fornecer orientação de navegação da localização atual do motorista, até onde o passageiro precisa ser buscado e, depois, para o destino escolhido pelo passageiro.

Para que esse processo funcione perfeitamente, as estimativas de localização para os passageiros e motoristas precisam ser o mais precisas possível.

Desde o lançamento (literal!) do GPS em 1973, avançamos nossa compreensão do mundo, experimentamos um crescimento exponencial do poder computacional disponível para nós e desenvolvemos algoritmos poderosos para modelar a incerteza de campos como a robótica. Enquanto nossas vidas se tornaram cada vez mais dependentes do GPS, os fundamentos de como o GPS funciona não mudaram muito, o que leva a limitações significativas de desempenho.

Em nossa opinião, é hora de repensar algumas das suposições iniciais que eram verdadeiras em 1973 sobre onde e como usamos o GPS, bem como o poder computacional e as informações adicionais que podemos mobilizar para aprimorá-lo.

Enquanto o GPS funciona bem sob o céu limpo, suas estimativas de localização podem ser altamente imprecisas (com uma margem de erro de 50 metros ou mais) quando mais precisamos: em áreas urbanas densamente povoadas e altamente construídas, onde muitos de nossos usuários estão localizados.

Para superar esse desafio, desenvolvemos uma atualização de software de GPS para Android que melhora substancialmente a precisão da localização em ambientes urbanos por meio de uma arquitetura cliente-servidor que utiliza mapas 3D e realiza cálculos probabilísticos sofisticados sobre dados GPS disponíveis por meio das APIs GNSS do Android.

Neste artigo, discutiremos por que o GPS pode ter um desempenho ruim em ambientes urbanos e descreveremos como consertamos isso usando algoritmos avançados de processamento de sinal implantados em escala em nossa infraestrutura de servidores.

Figura 1: O GIF acima apresenta uma comparação do GPS padrão (vermelho) com a nossa estimativa de localização aprimorada (azul) para uma corrida de busca ao passageiro da Uber HQ em São Francisco. Nossa localização estimada segue de perto o verdadeiro caminho percorrido pelo passageiro, enquanto o GPS mostra caminhos muito grandes.

Um pouco de contexto no GPS/GNSS

Antes de discutirmos detalhadamente nossa abordagem, vamos fazer uma rápida recapitulação de como o GPS funciona para entender por que ele pode ser impreciso em ambientes urbanos altos.

O GPS é uma rede de mais de 30 satélites operados pelo governo dos EUA, orbitando a Terra a uma altitude de cerca de 20.000 quilômetros. (A maioria dos celulares hoje em dia podem captar satélites “GLONASS” russos semelhantes).

Esses satélites enviam sinais de radiofrequência que receptores de GPS, como os encontrados em telefones celulares, podem bloquear. É importante ressaltar que esses satélites anunciam a hora em que lançam seus sinais.

Para cada satélite cujo sinal o receptor processa, a diferença entre o tempo de recepção e o tempo de lançamento (tempo-de-voo), multiplicado pela velocidade da luz, é chamada de pseudorange. Se os relógios do satélite e do receptor estiverem sincronizados e o sinal viajar ao longo do caminho da linha de visão direta, então isso será igual à distância real ao satélite.

No entanto, os relógios não são sincronizados, portanto, o receptor precisa resolver quatro incógnitas, suas próprias coordenadas 3D no globo e seu viés de relógio. Assim, precisamos de um mínimo de quatro satélites (quatro equações) para resolver essas quatro incógnitas.

Se ignorarmos o viés do relógio, podemos interpretar intuitivamente a estimativa de localização realizada pelo receptor GPS interceptando esferas centralizadas nos satélites com o raio de cada esfera dado pelo pseudorange.

Na prática, um receptor GPS processa sinais de um número significativamente maior de satélites (até 20 satélites GPS e GLONASS são visíveis em um campo aberto), e ter mais do que o número mínimo de equações fornece robustez extra a ruído, bloqueios, etc.

Além de GPS e GLONASS, alguns novos/futuros receptores podem/irão processar sinais de outros sistemas de satélite. Outros sistemas de satélites de navegação que entram em operação são o Galileo, operado pela União Europeia; IRNSS na Índia, e BeiDou, operado pela China. O termo mais geral GNSS (sistemas globais de navegação por satélite) engloba esses sistemas. (Nós usaremos este termo no restante do artigo).

Figura 2: Nesta interpretação simplificada do cálculo do receptor GPS, as esferas se cruzam no centro dos locais de satélite conhecidos.

Por que a localização GNSS é imprecisa em ambientes urbanos

Uma suposição importante por trás do posicionamento baseado em GNSS é que o receptor tem uma linha direta de visão para cada satélite cujo pseudorange está sendo computado. Isso funciona perfeitamente em terreno aberto, mas realmente se decompõe em ambientes urbanos, como mostra a Figura 3, abaixo:

Figura 3: Bloqueio de linha de visão e reflexos fortes podem causar grandes erros de GPS.

Os edifícios costumam bloquear as linhas de visão para os satélites, de modo que o receptor frequentemente processa sinais que correspondem a fortes reflexos que vem de outros edifícios.

A imprecisão significativa (compensações positivas) nos pseudoranges resultantes desse fenômeno pode levar a erros nas estimativas de posição que podem ser de 50 metros ou mais nos cânions urbanos.

A maioria de nós que vagueamos, dirigimos ou solicitamos um Uber nas grandes cidades experimentou esses problemas em primeira mão.

Forças do sinal de satélite para o resgate

Nossa abordagem para melhorar a precisão da localização faz com que um recurso do bloqueio de sinais GNSS cause problemas para os receptores padrão. Como? Para telefones Android, a API do LocationManager fornece não apenas a estimativa de posição do telefone, mas também a relação sinal-ruído (SNR) para cada satélite GNSS em exibição. Se colocarmos essas informações de “intensidade de sinal” junto com mapas 3D, poderemos obter informações de localização muito valiosas.

A Figura 4, abaixo, mostra uma versão simplificada de como SNRs de satélite e mapas 3D podem ser usados para inferir em qual lado da rua estamos:

Figura 4: As forças do sinal de satélite, quando combinadas com mapas 3D, fornecem informações valiosas sobre a localização.

Ampliando os detalhes, nossa abordagem baseia-se em colocar a seguinte intuição em uma estrutura matemática: se o SNR de um satélite for baixo, então o caminho da linha de visão provavelmente será bloqueado ou sombreado; se o SNR for alto, então o LOS será provavelmente claro.

O qualificador “provavelmente” é crucial aqui: mesmo quando o receptor está em uma área sombreada, sinais refletidos fortes ainda podem alcançá-lo, e mesmo se estiver em uma área clara, o sinal recebido pode ser fraco (devido a interferência destrutiva entre LOS e caminhos refletidos, um fenômeno conhecido como desvanecimento de múltiplos caminhos).

Além disso, em geral, o mapa 3D não é inteiramente preciso, e certamente não captura bloqueios aleatórios de grandes objetos em movimento que não estão no mapa, como caminhões. Isso adiciona incerteza adicional ao processo.

Correspondência de sombra probabilística usando traçado de raio

Embora a intuição sobre as forças do sinal de satélite que transportam informações úteis de localização seja sólida, ela deve ser desenvolvida dentro de uma estrutura probabilística.

Para qualquer localização possível para o receptor, podemos verificar se o raio que une o local ao satélite está bloqueado usando nosso mapa 3D. Agora, usando um modelo para a distribuição de probabilidade do SNR sob LOS e condições sombreadas, determinamos a probabilidade do SNR medido para aquele satélite.

Por exemplo, se o local estiver sombreado, então a probabilidade de um SNR alto é baixa. A probabilidade global de um determinado local, com base nos SNRs do satélite, é o produto das probabilidades correspondentes aos diferentes satélites.

Fazendo isso através de uma grade de possíveis localizações, obtemos uma superfície de probabilidade – ou mapa de calor – de possíveis localizações de receptor, com base apenas nas forças do sinal de satélite. Chamamos esse procedimento de correspondência de sombra probabilística.

Figura 5: Raio traçando de um local possível para cada satélite para correspondência de sombra probabilística. Isso é feito para milhares de locais hipotéticos.

A superfície de probabilidade, ou mapa de calormda correspondência de sombra probabilística, resume as informações das medições de satélite SNR. No entanto, como vemos na Figura 6, abaixo, esse mapa de calor pode ser bastante complicado.

Ela pode ter muitos pontos de acesso distintos e amplamente separados (máximos locais), muitas vezes correspondendo a um determinado lado da rua, mas às vezes ainda no local errado (ou seja, fantasmas). A fim de restringir nossa estimativa de localização e evitar o bloqueio nos fantasmas, devemos agora fundir essa informação com ainda mais informações.

Figura 6. Um mapa de calor de localização calculado com base nas intensidades do sinal de satélite pode ter muitos pontos de acesso. No exemplo acima, nossa estimativa de localização aprimorada (caminho azul, elipse de incerteza preta) segue a verdade do solo (caminho amarelo), enquanto o GPS padrão (caminho vermelho, elipse de incerteza cinza) é impreciso.

Fusão de informações via filtro de partículas

Para telefones Android, as informações que usamos, além das intensidades de sinal de satélite, geralmente são apenas sobre a correção de posição padrão do GNSS, mas também podem ser locais Android Fused, que podem incluir posicionamento baseado em WiFi.

Uma vez que esta localização pode ser muito imprecisa, a fusão instantânea de tempo único (one-shot) da correção GNSS com probabilidades de correspondência de sombra normalmente leva a um desempenho insatisfatório.

Para aproveitar as informações das intensidades do sinal de satélite, confiamos menos em GPS nas áreas construídas (a elipse cinza de incerteza do GPS na Figura 6 é um modelo típico que usamos, enquanto a elipse de incerteza preta para GPS aprimorado é um resultado do nosso algoritmo).

Portanto, usamos medições passadas e restringimos a evolução da localização ao longo do tempo usando um modelo de movimento adaptado para a aplicação (por exemplo, movimento do pedestre versus do veículo). Isso é realizado usando um filtro de partículas, que se aproxima da distribuição de probabilidade da localização do receptor em qualquer momento determinado por um conjunto de partículas ponderadas. Em outras palavras, estimamos onde o telefone está usando milhares de locais hipotéticos (ou seja, partículas).

Com o tempo, os pesos de probabilidade e as localizações de partículas evoluem com base nas medições e no modelo de movimento. Como o mapa de calor da correspondência de sombra probabilística tem tantos máximos locais e devido a correção GNSS pode ter valores extremos tão grandes, não podemos usar técnicas padrão como o filtro de Kalman ou o filtro de Kalman estendido, que dependem da distribuição de probabilidade rastreada sendo bem aproximada por uma distribuição Gaussiana em forma de sino. O filtro de partículas nos permite aproximar distribuições arbitrárias, às custas de maior complexidade, e é aí que entra nossa infraestrutura de servidores.

Figura 7: A estimativa de localização obtida como o centroide ponderado do ponto de acesso fornecido pelo filtro de partículas geralmente corrige erros de GPS muito grandes. O raio de incerteza (círculo branco) para GPS melhorado é baseado na dispersão do conjunto de partículas e é frequentemente uma medida mais realista do que o pequeno raio de incerteza (círculo preto) tipicamente reportado para GPS bruto mesmo quando os erros reais de posição são grandes.

Do processamento de sinal ao software em escala

A combinação de filtragem de partículas e traçado de raios introduz complexidade ao ecossistema do servidor back-end, criando um serviço muito dinâmico/imponente.

Figura 8: O sistema de aprimoramento GPS da Uber é composto de um serviço de filtro de partículas, serviço de gerenciamento de bloco de mapa 3D, um serviço gerenciador, API HTTP Uber, armazenamento em nuvem e integra-se a outros serviços Uber.

Há dois tipos de estado em jogo: o estado do filtro de partículas por usuário e os mapas 3D por região, usados ​​para o rastreamento de raios. O uso de filtros de partículas requer um nível de afinidade do servidor.

Cada novo pedido para o nosso serviço deve ser roteado para o mesmo servidor de back-end para processamento, a fim de atualizar o filtro de partículas correto. Além disso, devido ao grande tamanho dos mapas 3D, cada servidor de back-end pode conter apenas algumas pequenas seções do mundo 3D em RAM.

Como cada servidor pode conter apenas alguns quilômetros quadrados de dados de mapas, nem todos os servidores são capazes de atender a todos os usuários. Essencialmente, a implementação dos sistemas de back-end para nossa solução exigiu a criação de uma camada de roteamento de sessão fixa que leva em conta o estado do mapa 3D do servidor.

Além de testes internos e avaliações de desempenho, também executamos verificações pontuais em nossos próprios dispositivos Android, usando uma versão interna do aplicativo Uber do passageiro, conforme ilustrado na Figura 9 abaixo:

Figura 9: Comparação de ponto vermelho/ponto azul em nossa versão interna do aplicativo do passageiro permite que os funcionários da Uber verifiquem nossa solução em qualquer lugar do mundo.

Avançando

A estimativa precisa do local do passageiro e do motorista é um requisito crucial para cumprir a missão da Uber de fornecer um transporte tão confiável quanto água corrente, em qualquer lugar, para todos.

Para cumprir nossa missão, a equipe de Detecção, Inteligência e Pesquisa está trabalhando em uma variedade de abordagens para melhorar a localização com o uso criativo de sensores e computação em dispositivos móveis, juntamente com o poder computacional de nossa infraestrutura de servidores.

A combinação de processamento avançado de sinais, algoritmos de aprendizagem de máquina e software em escala tem um enorme potencial, e estamos sempre à procura de indivíduos talentosos e altamente motivados (engenheiros de software e algoritmos, engenheiros de visualização de dados e engenheiros de aprendizagem de máquina) para se juntar a nós a fim de realizar esse potencial.

Interessado em aprender mais? Veja nossa apresentação recente nessa pesquisa:

Danny Iland, Andrew Irland, Upamanyu Madhow e Brian Sandler são membros da equipe de Detecção, Inteligência e Pesquisa da Uber. Danny, Andrew e Upamanyu faziam parte do grupo original que liderou essa pesquisa na Universidade da Califórnia, em Santa Bárbara.

Depois de transformar esse trabalho em uma startup, eles demonstraram a filtragem de partículas baseada em servidor para melhorar a localização em São Francisco usando um mapa 3D construído a partir de dados LiDAR aéreos publicamente disponíveis. Eles se juntaram à Uber em julho de 2016.

***

Este artigo é do Uber Engineering. Ele foi escrito por Danny Iland, Andrew Irish, Upamanyu Madhow e Brian Sandler. A tradução foi feita pela Redação iMasters com autorização. Você pode conferir o original em: https://eng.uber.com/rethinking-gps/