Filtros de Partículas

Un tratamiento más técnico de esta publicación de blog se publicó originalmente en el blog de Udacity .

Los robots usan un algoritmo sorprendentemente simple pero poderoso para averiguar dónde están en un mapa, un problema que los ingenieros llaman localización. El algoritmo conocido como filtrado de partículas se ve increíblemente genial. La primera parte de este artículo de dos partes fue publicada aquí . En este primer artículo, aclararemos las matemáticas necesarias para construir sus propios filtros de partículas.

L os coches autónomos están diseñados para comportarse como los conductores humanos. Un sistema típico de automóvil autónomo se compone de seis componentes. Cada uno de los seis componentes resuelve un problema crítico necesario para la conducción, autónoma o no. Se puede pensar que los componentes realizan las funciones que imitan a los conductores humanos, que son:

Localización : ¿Dónde estamos?
Planificación de rutas : ¿Cómo llegamos al destino?
Percepción : ¿Qué más hay en los alrededores?
Predicción : ¿Cómo será el entorno un poco más tarde?
Planificación : ¿Cuál es el rumbo que seguiremos en los próximos segundos?
Control : ¿Cómo vamos a seguir el rumbo que queremos?

La localización para humanos tiende a ser muy fácil. Por lo general, recordamos de memoria dónde estamos en el mundo, a menudo con la ayuda de un dispositivo GPS como un teléfono inteligente que nos ayuda a identificar nuestra ubicación con mucha más precisión en un mapa. También usamos pistas visuales como señales de navegación, marcas de carriles y nuestra comprensión de otros vehículos, la carretera y los alrededores para asegurarnos de estar siempre en el carril correcto, en la carretera correcta y en la dirección correcta.

Cuando se trata de localización, la conducción autónoma también requiere la posición y la dirección en la que se mueve el vehículo, también llamado rumbo. Sin embargo, a diferencia de los humanos, el nivel de precisión que requieren los vehículos autónomos es muy alto. No basta con saber que un vehículo está en el carril derecho y va paralelo al carril. Se necesita una alta precisión para la planificación. Si la localización está desviada por más de unos pocos centímetros sobre la posición o por más de unos pocos grados sobre el rumbo, el componente de planificación podría generar un rumbo desastroso que resulte en una colisión entre muchos otros resultados no deseados.

Al igual que los humanos, los vehículos autónomos obtienen su primera estimación de la posición y el rumbo de un GPS. Los receptores GPS, incluso los más pequeños que se encuentran en un teléfono inteligente, tienden a ser bastante precisos. Sin embargo, la precisión de la información de localización recibida de un GPS es inadecuada para una conducción autónoma segura. Por ejemplo, la posición informada puede estar desviada entre un metro y varios metros o, en el peor de los casos, incluso más.

La precisión fluctúa con frecuencia y de manera salvaje según factores como la cantidad de satélites visibles para el receptor, los reflejos de los haces de los satélites en objetos grandes como edificios y la absorción por parte de los elementos atmosféricos.

Si eso no es lo suficientemente malo, la velocidad a la que el GPS actualiza la información de localización también es bastante lenta, oscilando entre 1 y 10 Hz. Incluso a 10 Hz, un vehículo que se mueve a 20 km/h tarde se habría movido aproximadamente medio metro entre dos actualizaciones de GPS.

Para mitigar la incertidumbre en la localización debido al movimiento, los vehículos autónomos utilizan unidades de medida inerciales (IMU). Las IMU son rápidas y precisas y miden la aceleración y la velocidad de giro de un vehículo. Esta información se puede utilizar para determinar la posición del automóvil entre dos actualizaciones de GPS sucesivas. Las IMU tienden a acumular pequeños errores de aproximación con el tiempo, pero ese no es el problema que estamos tratando aquí.

El problema central con el que debe lidiar el sistema de localización es que las actualizaciones de GPS son intrínsecamente inexactas. En lugar de informar una posición exacta, por ejemplo, el GPS informa una pequeña área en el suelo donde es probable que haya un vehículo presente cuando el GPS se actualice. Nos referimos a esta área como un punto GPS.

El problema de realizar una localización precisa se reduce al problema de reducir el área del punto GPS.

Una de las técnicas que se han utilizado en robótica para la localización precisa, partiendo de una menos precisa, se conoce como filtrado de partículas . Es útil cuando el entorno tiene varios puntos de referencia, es decir, objetos estacionarios grandes que no cambian con frecuencia de ubicación, apariencia y tamaño. Estos pueden ser edificios, torres de telefonía celular, pilares de puentes, postes de servicios públicos o señales de tráfico y señalización.

Para entender cómo se filtran las partículas utilizaremos una analogía. Supón que vuelves cansado a la habitación de un hotel, apagas las luces y te tiras en la cama boca abajo. Te despiertas en medio de la noche y quieres saber dónde estás. Por supuesto, recuerda haber chocado contra la cama, pero le gustaría saber en qué dirección está mirando, dónde están los interruptores de luz y dónde están sus pantuflas. Esto requiere más precisión que un vago recuerdo de estar en la cama.

Para orientarte rápidamente, haces uso del entorno. Primero te imaginas en diferentes lugares de la cama. Luego sientes los objetos 'punto de referencia' en los alrededores tocándolos e identificándolos. Puede empujar una botella de agua de una mesa cercana o golpearse el dedo del pie contra una silla. Estas observaciones le brindan pistas importantes sobre dónde es probable que se encuentre en el ámbito de la cama del hotel. Como recuerda dónde estaban la botella, la mesa y la silla en relación con la cama, puede inferir su posición en la cama con mayor precisión. Con cada nueva observación, puede descartar ciertas ubicaciones en la cama y aumentar sus posibilidades de estar en otras ubicaciones.

Así es exactamente como funciona el filtrado de partículas para vehículos autónomos. Armado con un punto GPS inicial, el vehículo conoce su posición aproximada y rumbo en el mapa. Esta posición aproximada se divide luego en pequeñas celdas imaginarias. El vehículo también sabe qué puntos de referencia hay en las cercanías de esa ubicación aproximada. Luego, el vehículo mide la distancia a estos puntos de referencia utilizando un lidar integrado. El sistema de localización luego compara estas medidas con cada celda imaginaria. A medida que se prueban más y más puntos de referencia, la mayoría de las celdas se descartan y solo unas pocas altamente probables permanecen como ubicaciones probables.

El nombre filtrado de partículas proviene del hecho de que la ubicación de cada celda imaginaria se representa como una partícula en el mapa y descartamos partículas filtrándolas calculando distancias a puntos de referencia y descartando partículas que no parecen estar a la distancia correcta de los hitos

La animación a continuación muestra la ubicación inicial de las partículas que abarcan un área considerable, que podría extenderse a través de varios carriles, carreteras y áreas abiertas. La detección o sondeo del entorno se muestra mediante rayos azules. El punto verde que representa la posición más probable inicialmente salta alrededor del mapa, pero se asienta muy rápidamente a medida que se descartan más y más partículas al detectar el entorno.

El filtrado de partículas es un algoritmo increíblemente simple que impulsa muchos robots y automóviles autónomos. Nvidia Drive Labs ha publicado un vídeo breve sobre cómo la localización puede beneficiarse de los mapas enriquecidos, con una variedad de puntos de referencia. Uber ATG ha publicado un blog sobre cómo mejoran la precisión del GPS aquí .