Así es como se localiza el «coche sin conductor» de Google

(Este artículo es la traducción del artículo que escribí en MappingIgnorance.org)

La localización, o conocer «dónde estoy» es un tema central de investigación en robótica móvil hoy día, y lo lleva siendo desde hace 30 años. No podríamos concebir ordenarle a un futuro asistente personal robótico «ve a la máquina de café y tráeme uno bien cargado» si el robot no es capaz de saber en cada instante durante su camino por dónde va, de manera que pueda ir planeando sus próximos pasos. Vagar dando tumbos está muy bien para las aspiradoras robóticas, pero no creo que podamos llegar mucho más lejos sin construir máquinas más inteligentes. Obviamente, los coches del futuro capaces de conducirse ellos sólos también deberán conocer dónde están para poder maniobrar a tiempo de coger una salida, respetar los distintos carriles de una carretera, etc. Esto conlleva dos retos: (1) el coche debe permanecer localizado con respecto a algún tipo de mapa, y (2) el método para localizarse debe ser eficiente, robusto y viable para funcionar en tiempo real.

El lector quizás piense que no es un gran problema. Total, todos tenemos sistemas de navegación basados en GPS (los llamados «GPS» a secas) en nuestros coches y funcionan estupendamente, ¿verdad? Bueno, en realidad no es tan sencillo… Para ponerte en el lugar de un coche-robot, imagina que te pones a conducir con los ojos cerrados, y solamente te van dictando las coordenadas GPS sin mucha más información. Sin ser capaz de percibir el  entorno, los peatones, el resto de vehículos que circulan en la vía, esa obra de ahí delante que pilla medio carril, aquella nueva rotonda que en el mapa del GPS no aparece, etc. me temo que no llegaríamos muy lejos antes de un desastroso desenlace. Además, la precisión del GPS para localización no es tan buena como muchos asumen, estando el 95% del tiempo por debajo de los 2 metros si sólo se usa información satelital. En cualquier carretera estrecha, esos dos metros son la diferencia entre ir por tu carril y provocar un accidente mortal. 

Así que vemos que el GPS está bien como complemento, pero no deberíamos fiarnos demasiado de él. Los humanos somos muy buenos percibiendo el entorno gracias a nuestro sentido de la vista, y estaría fenomenal conseguir que los coches del futuro sean capaces de ver, literalmente,  su entorno.

Muchos investigadores de este campo conocerán la famosa anécdota sobre cómo el pionero de la Inteligencia Artificial Marvin Minsky dirigió un proyecto fin de carrera de un estudiante para «resolver el problema de la visión artificial«… en 1966. Evidentemente, ¡aquí seguimos esperando a que termine ese largo verano y la visión por ordenador no está resuelta! Como curiosidad aparte, entre otros muchos logros científicos, Minsky aconsejó técnicamente a la novela y película de «2001: Una odisea en el espacio» como experto en Inteligencia Artificial.

A pesar del enorme despegue de la visión por ordenador, especialmente en los últimos 10 años, todos los que estamos en el tema sabemos lo frágiles y limitados que resultan en realidad hasta los mejores métodos actuales en comparación con las inmensas capacidades del cerebro humano para interpretar y entender imágenes.

Por tanto, en la actualidad uno de los sensores más valorados para vehículos autónomos no son las cámaras, sino los escáneres láser 3D o LIDARS (por sus siglas en inglés). Proporcionan una visión rápida y en 3D del entorno, incluyendo distancias (profundidad) y niveles de reflectancia de cada material para cada dirección del espacio. A pesar de ser totalmente inasumibles en soluciones comerciales de mercado (¡cada LIDAR puede costar ~$70,000 o más!) son muy populares en los laboratorios de investigación de todo el mundo, incluidos los de Google. El siguiente vídeo muestra en la práctica cómo se ve con «ojos de LIDAR 3D«:

 (Así es cómo «ve el mundo» un coche equipado con un LIDAR de última generación)

El trabajo presentado en [1] presenta una técnica robusta para que un vehículo se mantenga localizado empleando un LIDAR como éste. Uno de los autores es el renombrado  Sebastian Thrun, jefe del proyecto del coche sin conductor de Google, y muy prolífico investigador en robótica móvil (¡más de 54k citas y h-index de 113!). Aunque el artículo sólo asegura que ésta técnica se usó durante 10 trayectos de prueba en el campus de Stanford, suponemos que desde entonces formará parte del software habitual de los coches autónomos de Google.

Siguiendo la tradición en robótica móvil, se afronta la localización sólo tras haber realizado un mapa del entorno, que se usará para localizarse asumiendo que éste no va a cambiar mucho con el tiempo. Hay poderosas razones para proceder así: construir un mapa es uno de los mayores problemas de la robótica y la visión por ordenador (el problema se llama SLAM), así que lo que los investigadores solemos hacer es salir a coger datos controlando los vehículos de manera manual, y entonces echar el tiempo que sea necesario procesándolos en el laboratorio hasta que obtenemos un mapa aceptable. Sólo entonces, se proporciona este mapa al robot para que pueda localizarse en tiempo real, ya sea de nuevo teleoperado o moviéndose autónomamente.

En el caso del equipo de Thrun, a la nube de puntos 3D del LIDAR se incorpora la información de «color» que ve el láser: monitorizando el eco de los rayos láser infrarrojos, el sensor determine el nivel de gris (reflectancia) de cada punto escaneado del entorno. Componiendo ésta información con los puntos 3D se obtienen imágenes fotorealistas del mundo como las de abajo. Es importante insistir en que el nivel de gris no ha sido obtenido con ningún tipo de cámara, sino directamente a través de los millones de puntos por segundo adquiridos por un LIDAR.

A continuación se extrae solamente el plano horizontal de tierra, la única parte del entorno que se empleará de verdad para localización. Según los autores, quedarse con el entorno 3D completo no pareció aportar mucho; estoy seguro de que sin embargo sería fundamental si se emplean otros sensores, como cámaras ópticas. Al no grabar las «imágenes» del suelo con cámaras normales se evitan algunos problemas típicos de visión. Por ejemplo, nunca se verán sombras proyectadas por luz solar, ya que lo que se mide es directamente la reflectancia de cada punto desde el LIDAR. Además, las imágenes apenas varían con las condiciones meteorológicas.

Darse un par de vueltas con el coche grabando datos es lo más fácil de construir el mapa. Ahora, tendremos muchos GBs de datos en un disco duro con millones de puntos 3D, coordenadas de GPS con su error incluido y datos de sensores proprioceptivos como sistemas inerciales, el equivalente al oído interno en humanos, y encoders de las ruedas que cuentan el número de vueltas que éstas dan. ¿Qué hacer con todo esto?

Desde Carl F. Gauss sabemos que la minimización de residuos cuadráticos es un método excelente para ajustar cualquier modelo a datos experimentales, y el mapa de una ciudad es al fin y al cabo otro modelo matemático. Este acercamiento al problema desde la perspectiva de mínimos cuadráticos se llama «Graph SLAM» en la comunidad de investigadores. Lo de «grafo» en el nombre viene de la interpretación del problema como una red donde los nudos son variables a estimar y los datos «cuerdas» o «muelles» que restringen sus posiciones relativas. Ajustar el modelo equivale a buscar el punto de mínima energía, el punto al que los nudos tenderían si se les dejara solos.

Al final, el problema se reduce a minimizar esta función de coste:

donde  x son posiciones del coche,  g() es la función que modela la odometría (incrementos de rotación de las ruedas), h() es un modelo de observación que predice la apariencia que van a tener los puntos LIDAR según se vea el plano del suelo desde una determinada posición x, m es el mapa del suelo propiamente dicho, z las medidas del LIDAR, y las lecturas del GPS y b es una variable latente ingeniosamente introducida por los autores para modelar la lenta variación del sesgo/error en las señales de un GPS. La idea es ajustar todos las posiciones del coche  x y los valores del mapa  m tal que se ajusten lo más posible a todas las observaciones de todos los sensores a la vez. Ya que no todos los sensores son igualmente fiables, se introducen unas matrices de peso (las que aparecen invertidas) de forma que por ejemplo se haga más caso al contador de vueltas de las ruedas que al GPS.

Un modelo matemático muy bonito. Su único problema es que es intratable. Con millones de incógnitas y de datos, podría tardar una eternidad en ser optimizado. Así que el equipo de Stanford proponen quitar el mapa de la ecuación, en algo parecido a un clásico «divide y vencerás».

Primero, se afronta un modelo simplificado: solamente usando GPS y datos inerciales, se tiene una primera estimación de la trayectoria del coche. Asumiendo que las orientaciones (la dirección en que se mira) están más o menos correctas en este modelo, el problema se simplifica enormemente ya que solamente nos queda ajustar posiciones en el plano (2D), mucho más fácil de optimizar debido a que no meten no linealidades como sí hacen las incógnitas de ángulos y giros. Entonces, los mapas del suelo de puntos sobre los que el coche ha pasado más de una vez (los «cierres de bucle» como los llamamos en SLAM) se emparejan unos con otros para establecer nuevas restricciones adiciones entre las posiciones del coche. La idea es deshacernos de la incómoda función de observación h() de arriba, y centrarnos en optimizar solamente la trayectoria del vehículo. Así queda esta función de coste mucho más simple:

Aunque no lo parezca a simple vista, pensando qué son las variables que aparecen ahí se ve que el modelo tiene varios órdenes de magnitud menos incógnitas, pudiendo resolverse con un PC normal en apenas unos segundos. El resultado es un alineamiento casi perfecto de las distintas pasadas del coche sobre el mismo lugar, con errores típicos de sólo 5cm: 

Una vez corregida la trayectoria del coche, construir el mapa del suelo completo es una tarea trivial: sólo hay que proyectar geométricamente los datos del LIDAR desde cada una de las posiciones del vehículo, ya conocidas.

 

Por fin, podemos conducir el coche con el mapa cargado a bordo y que éste sea capaz de localizarse con precisión. Para hacerlo, se emplea un filtro de partículas (PF) que compara las medidas del LIDAR con la predicción del mapa del suelo. Un PF es un caso particular de estimador Bayesiano, similar a un algoritmo genético… pero con reglas sólidamente fundadas en la estadística (sin acritud :-P). La posición del coche se estima mediante unos cientos de hipótesis sobre su posición, que evolucionan en el tiempo de maneras que encajan (estadísticamente) con las medidas de los sensores del coche. Cada hipótesis predecirá una medida distinta del LIDAR, y solamente aquellas que más se acerquen a la realidad sobreviven; el resto son descartadas.

A pesar de la simplicidad, y limitaciones, de este tipo de filtros, han demostrado ser extremadamente robustos contra ruido y medidas de elementos inesperados en el entorno. En [1], el equipo de Stanford includo demuestra cómo un PF sin odometría ni GPS, solamente con el mapa, un LIDAR y el sistema inercial es perfectamente capaz de estimar no sólo la posición sino también la velocidad del vehículo. Evidentemente eso que no quiere decir que prescindamos de la odometría ni del GPS, pero indica que la calidad de la estimación no se debe a dichos sensores, cuya introducción sólo puede mejorar aún más la estimación total.

 En resumen: estamos aún muy lejos de ver coches realmente autónomos por las calles de nuestras ciudades debido sobre todo al elevado coste de los sensores LIDARs empleados en casi todos los prototipos de última generación. Pero hace 15 años hasta esto era ciencia ficción, así que permaneced atentos a los próximos avances… 😉

 

Referencias:

[1] LEVINSON, Jesse; MONTEMERLO, Michael; THRUN, Sebastian. Map-Based Precision Vehicle Localization in Urban Environments. En Robotics: Science and Systems. 2007.