Estás leyendo la publicación: Planificación de ruta 2D con CNN: hacia la IA
Publicado originalmente en Hacia la IA.
Una red neuronal convolucional (CNN) es un modelo popular para resolver tareas como clasificación de imágenes, segmentación, detección de objetos, etc. Este es un experimento para evaluar su aplicación para resolver problemas simples de planificación de rutas 2D. El lenguaje de programación utilizado es Python, con PyTorch, NumPy y OpenCV como bibliotecas principales. Puedes encontrar el código fuente en mi GitHub.
La tarea
En pocas palabras, dado un mapa de cuadrícula de ocupación, la planificación de rutas 2D se trata de encontrar la ruta más corta posible a seguir desde un punto de partida dado hasta una posición de destino deseada (), evitando cualquier obstáculo durante la trayectoria. La robótica es uno de los principales campos en los que la planificación de rutas es crítica. Se desarrollaron algoritmos como A*, D*, D* lite y variantes relacionadas para resolver este tipo de problema. Hoy en día, la inteligencia artificial (IA), especialmente con el aprendizaje por refuerzo, se usa ampliamente para dar cuenta de eso. De hecho, las CNN suelen ser la columna vertebral de algunos algoritmos de aprendizaje por refuerzo. Este experimento trata de abordar instancias simples de planificación de rutas mediante .
el conjunto de datos
El principal problema al que me enfrenté fue (como siempre en el aprendizaje automático) dónde encontrar los datos. Terminé creando mi propio conjunto de datos para la planificación de rutas al hacer mapas 2D aleatorios. El proceso de creación de un mapa es muy sencillo:
- Comencemos con una matriz cuadrada vacía de 100×100 píxeles.
- Para cada elemento (píxel) de la matriz, extraiga un número aleatorio del 0 al 1 de una distribución uniforme. Si > , establezca ese píxel en 1; de lo contrario, configúrelo en 0. Aquí hay un parámetro que representa la probabilidad de que un píxel sea un obstáculo (es decir, una posición que no se puede atravesar) y, por lo tanto, es proporcional a la dificultad de encontrar un camino factible en ese mapa.
- Entonces vamos a explotar el operador morfológico de apertura para obtener un efecto de “bloques” que se asemeje mejor a los mapas de cuadrícula de ocupación reales. Al variar el tamaño del elemento estructurante morfológico y el parámetro, podemos generar mapas con diferentes niveles de dificultad.
- A continuación, para cada mapa, tenemos que elegir 2 posiciones diferentes: el y el . Esa elección es nuevamente casual, pero esta vez tenemos que asegurarnos de que la distancia euclidiana entre y sea mayor que un umbral dado para que la instancia sea desafiante. De lo contrario, nuestra red no aprenderá mucho de ella.
- Finalmente, necesitamos encontrar el camino más corto de a . Esa será la verdad fundamental para nuestro entrenamiento. Para este propósito, he usado el popular algoritmo D* lite. En particular, he escrito una implementación personalizada que restringe la solución para mantener un margen de al menos 1 celda libre de cualquier obstáculo. La razón de esto es simplemente que estaba trabajando en un proyecto robótico en el que necesitábamos una modificación de este tipo, ya que nuestro robot a menudo chocaba contra las paredes mientras seguía la trayectoria original de D* lite. Al usar la restricción de margen, pudimos superar el problema. Y dado que (inicialmente) se pensó que esta CNN se usaría en ese mismo robot, decidí mantener nuestra implementación personalizada.
El conjunto de datos comprende alrededor de 230 000 muestras (170 000 para entrenamiento, 50 000 para pruebas y 15 000 para validación). Se descubrió que generar tal cantidad de datos utilizando el proceso anterior no era factible con mi computadora portátil de nivel básico. Es por eso que he reescrito la implementación personalizada de D* lite como un módulo de extensión de python usando el Aumentar biblioteca c++. No tengo puntos de referencia, pero con el módulo de extensión, pude generar más de 10 000 muestras/hora, mientras que con la implementación de Python puro, la tasa fue de aproximadamente 1 000 muestras/hora (en mi viejo pero dorado Intel Core i7–6500U con 8 GB de memoria RAM). La implementación personalizada de D* lite está disponible aquí.
Tenga en cuenta que, a veces, la posición de destino puede parecer colocada sobre un obstáculo. En esos casos, la trayectoria de verdad del terreno termina con la última posición factible (es decir, una celda que no es un obstáculo, un 0 en el mapa matriz) más cercana a la meta. Esa es otra pequeña diferencia con el D* lite original.
Hice algunas comprobaciones sencillas de los datos, por ejemplo, eliminando mapas cuya similitud de coseno era muy alta y cuyas coordenadas de inicio y meta estaban demasiado cerca.
He subido el conjunto de datos en kaggledonde también puedes encontrar un sencillo computadora portátil mostrando cómo acceder a las muestras. Sobre el GitHub repositorio, también puede encontrar un script de conveniencia que le permite crear su propio conjunto de datos desde cero.
arquitectura modelo
El modelo sigue una arquitectura de codificador-decodificador, con un total de 20 capas convolucionales divididas en 3 bloques de convolución (la parte de codificación), seguidos de otros 3 bloques de convolución transpuesta (la parte de decodificación). Cada bloque consta de 3 capas convolucionales de 3×3, con normalización por lotes y activación de ReLU entre cada una de ellas. Finalmente, hay otras 2 capas de conversión, además de la capa de salida. Desde un punto de vista de alto nivel, el objetivo del codificador es encontrar una representación comprimida pero relevante de la entrada. Luego, eso se enviará a la parte del decodificador, que intentará reconstruir el mismo mapa de entrada, pero esta vez incorporando información útil que debería ayudar a encontrar la ruta óptima de a .
Las entradas esperadas de esta red son:
- mapa: a [n, 3, 100, 100] tensor que representa los mapas de cuadrícula de ocupación. De ahora en adelante, es el . Tenga en cuenta que el número de canales es 3 en lugar de simplemente 1. Más sobre esto más adelante.
- comenzar: a [n, 2] tensor que contiene las coordenadas del punto de partida en cada mapa
- meta: a [n, 2] tensor que contiene las coordenadas del punto objetivo en cada mapa
La capa de salida de la red aplica la sigmoideo función, proporcionando efectivamente un “mapa de puntuación” en el que cada elemento tiene un valor entre 0 y 1 proporcional a la probabilidad de pertenecer a la ruta más corta de a . A continuación, puede reconstruir la ruta comenzando desde y eligiendo iterativamente el punto con la puntuación más alta en el vecindario actual de 8. El proceso termina una vez que encuentra un punto con las mismas coordenadas que . En aras de la eficiencia, he usado un algoritmo para este propósito. Esta idea fue inspirada por este papel.
Entre los bloques codificador y decodificador del modelo, inserté 2 conexiones de salto. El modelo ahora realmente se parece a la arquitectura (aunque es mucho más pequeña) de Red en U. Las conexiones de omisión inyectan la salida de una capa oculta dada en otras capas más profundas en la red. Se emplean cuando nos preocupamos por los detalles de la imagen que se está reconstruyendo (de hecho, U-Net se desarrolló para la segmentación de imágenes médicas, donde los detalles son críticos). En nuestra tarea, los detalles que nos importan son la posición exacta de , y todos los obstáculos que debemos sortear en nuestra trayectoria. Inicialmente, no incluí ninguna conexión de salto, pero luego descubrí que esto mejoró enormemente la convergencia de entrenamiento y los resultados generales del modelo.
Capacitación
Entrené al modelo durante aproximadamente 15 horas o 23 períodos en Google Colab. La función de pérdida empleada fue el error cuadrático medio (MSE) entre el mapa de puntuación proporcionado por el modelo y el mapa de verdad del terreno (GT). Este último se obtuvo creando una matriz de 100×100 llena de ceros y luego agregando un 1 en cada ubicación correspondiente a un punto perteneciente al camino obtenido con el D* lite. Probablemente haya mejores opciones que MSE, pero me he quedado con él debido a su simplicidad y facilidad de uso.
se fijó inicialmente en 0,001 con un CosenoRecocidoConWarmRestartsscheduler (ligeramente modificado para disminuir la tasa máxima de aprendizaje después de cada reinicio). El tamaño del lote se fijó en 160 muestras.
En cuanto a la regularización, traté de aplicar un desenfoque gaussiano a los mapas de entrada y también una pequeña omisión en la primera capa de convolución. Ninguna de esas técnicas produjo ningún efecto relevante, así que al final las dejé.
El problema de las circunvoluciones
Al principio, alimenté el modelo usando el mapa de cuadrícula de ocupación tal como estaba. Es decir, la entrada era un tensor con forma [n, 1, 100, 100] (más las posiciones de inicio y meta). Con esta configuración, no pude lograr ningún resultado satisfactorio. La pérdida dejó de disminuir casi instantáneamente. En consecuencia, los caminos reconstruidos fueron solo trayectorias aleatorias que fallaron por completo en la posición objetivo y atravesaron los obstáculos.
Una de las características clave del operador de convolución es que es invariancia de posición. Lo que aprende un filtro convolucional es, de hecho, un patrón específico de píxeles que es recurrente en la distribución de datos en la que se ha entrenado. Los patrones pueden, por ejemplo, representar esquinas o bordes verticales.
No importa qué patrón aprenda un filtro, el punto es que aprende a reconocerlo independientemente de su posición en la imagen. Esa es sin duda una característica deseable para tareas como la clasificación de imágenes, donde un patrón que caracteriza la clase de destino podría aparecer en cualquier parte de la imagen. Pero en nuestro caso, la ¡la posición es crítica! Necesitamos que la red sea muy consciente de dónde comienza y dónde termina la trayectoria deseada.
Codificación posicional al rescate
La codificación posicional es una técnica para inyectar información sobre la posición de los datos incrustándolos (generalmente mediante una simple suma) en los propios datos. Por lo general, se aplica en el procesamiento del lenguaje natural (PNL) para hacer que un modelo sea consciente de la posición de las palabras en una oración. Pensé que algo así también podría ser útil para nuestra tarea.
La codificación posicional clásica (ver el artículo La atención es todo lo que necesitas) explota una serie de sinusoide para codificar cada posición.
Realicé algunos experimentos al agregar una codificación posicional de este tipo a los mapas de ocupación de entrada, pero no fue mejor. Probablemente porque al agregar información sobre cada posición posible en el mapa, estamos yendo en contra de la propiedad de invariancia de posición de un filtro convolucional. Los filtros presentados antes son inútiles ahora, ya que sus pesos deben ajustarse para tener en cuenta todas y cada una de las posibles posiciones diferentes en la imagen de entrada. Eso es, por supuesto, inviable.
La idea que tuve se basa en la observación de que para la planificación de rutas, no estamos realmente interesados en posiciones en términos pero sólo en alcance. En concreto, nos interesa la posición de cada celda en el mapa de ocupación con respecto al punto de inicio y el punto de meta. Por ejemplo, tome una celda de coordenadas. Realmente no me importa saber si es igual a (45, 89) en lugar de (0, 5). Debería ser mucho más útil saber que está a 34 celdas y a 15 celdas de .
Lo que hice fue crear 2 canales adicionales para cada mapa de cuadrícula de ocupación que ahora tiene la forma [3, 100, 100] (sin considerar el tamaño del lote). El primer canal es el mapa de vainilla, como lo era anteriormente. El segundo canal representa una codificación posicional que asigna a cada píxel un valor relativo a la posición inicial. La misma historia para el tercero, pero esta vez usando la posición. Dichas codificaciones se realizan mediante la creación de 2 mapas de características a partir de una función gaussiana 2d centrada en y respectivamente. Sigma fue elegido para ser una quinta parte del tamaño del núcleo (como es habitual en los filtros gaussianos). Entonces, en nuestro caso, sigma era 20, ya que el tamaño del kernel es igual al lado del mapa, que es 100.
Esta vez, mientras inyectamos información útil sobre las ubicaciones deseadas de inicio y final de nuestra trayectoria, restauramos parcialmente la consistencia con la invariancia posicional de nuestros filtros. Los patrones que se pueden aprender ahora dependen solo de la distancia con respecto a un punto dado en lugar de cada ubicación posible en el mapa. 2 patrones iguales a las mismas distancias de o ahora causarán la misma activación de un filtro. Encontré que este pequeño truco es muy efectivo en la convergencia del entrenamiento.
Resultados y conclusiones
Probé el modelo entrenado en 51103 muestras.
- El 95% del total de las muestras de prueba pudieron proporcionar una solución utilizando la búsqueda bidireccional. Es decir, el algoritmo logró encontrar un camino de a en 48556 muestras utilizando el mapa de puntuación proporcionado por el modelo, mientras que no pudo hacerlo para las 2547 restantes.
- El 87% del total de las muestras de prueba presentó una solución válida. Es decir, una trayectoria de a que no atraviesa ningún obstáculo (este valor no tiene en cuenta la restricción de margen de obstáculo de 1 celda).
- En las muestras válidas, el error promedio entre los caminos reales y las soluciones ofrecidas por el modelo es de 33 celdas. Eso es bastante alto, dado que los mapas son de 100×100 celdas. Los errores van desde un mínimo de 0 (es decir, una reconstrucción “perfecta” de la ruta de verdad del suelo, encontrada en 2491 muestras) hasta un máximo de… 745 celdas (bueno, este modelo definitivamente no reemplazará el piloto automático de un Tesla)
Inmediatamente, encontrará algunos de los resultados del conjunto de prueba. El lado izquierdo de las imágenes muestra la solución proporcionada por la red entrenada, mientras que el lado derecho muestra la solución del algoritmo D* lite.
Si has llegado hasta aquí, déjame agradecerte por tu tiempo. Como puede ver, este trabajo está lejos de ser un resultado de última generación, pero me divertí un poco mientras lo codificaba y espero que usted también lo haya disfrutado.
2D Path Planning With CNN se publicó originalmente en Towards AI en Medium, donde las personas continúan la conversación resaltando y respondiendo a esta historia.
Publicado a través de Hacia la IA
