La compatibilidad conjunta por ramificación y acotación (JCBB, por sus siglas en inglés) es un algoritmo de asociación de datos utilizado en la localización y mapeo simultáneos (SLAM) y en visión por computadora para emparejar características observadas con un mapa o modelo conocido. Fue introducido por José Neira y Juan D. Tardós en 2001 en su artículo "Data Association in Stochastic Mapping Using Joint Compatibility". El algoritmo aborda el problema de determinar qué mediciones de sensores corresponden a qué puntos de referencia o características del mapa, un paso crítico para la estimación precisa del estado en robótica móvil.
A diferencia de los enfoques más simples de vecino más cercano que evalian la compatibilidad de cada característica de forma independiente, JCBB evalúa la compatibilidad conjunta de un conjunto de emparejamientos considerando las correlaciones estadísticas entre todas las características del conjunto. Esta prueba conjunta es más robusta frente a falsos emparejamientos, especialmente en entornos con características repetitivas o ambiguas. El algoritmo busca en el espacio de posibles conjuntos de emparejamientos mediante una estrategia de ramificación y acotación, que poda sistemáticamente las ramas que no pueden conducir a una mejor solución, asegurando que el conjunto encontrado sea el más grande que sea conjuntamente compatible.
Descripción general del algoritmo
JCBB opera sobre un conjunto de características predichas (del mapa actual) y un conjunto de características observadas (de los datos del sensor). Cada observación puede asignarse como máximo a una característica predicha, y cada característica predicha puede emparejarse como máximo con una observación. El objetivo es encontrar el conjunto de emparejamientos de cardinalidad máxima tal que el vector de innovación conjunta (la diferencia entre las mediciones observadas y las predichas) esté dentro de un umbral de chi-cuadrado, teniendo en cuenta la matriz de covarianza completa.
La búsqueda por ramificación y acotación construye un árbol donde cada nodo representa una asignación parcial de observaciones a características. En cada paso, el algoritmo expande el nodo considerando la siguiente observación no asignada y probando su compatibilidad con cada característica restante, tanto individualmente como de forma conjunta con los emparejamientos ya asignados. Si la prueba de compatibilidad conjunta falla, esa rama se poda. La búsqueda continúa hasta que se exploran todos los nodos, y se devuelve el mejor conjunto (el más grande). Para mejorar la eficiencia, el algoritmo utiliza un ordenamiento heurístico de las observaciones, típicamente por su compatibilidad individual, para encontrar buenas soluciones temprano y podar de manera más agresiva.
Prueba de compatibilidad conjunta
El núcleo de JCBB es la prueba de compatibilidad conjunta. Dado un conjunto de emparejamientos, la prueba calcula el vector de innovación conjunta y su matriz de covarianza. La distancia de Mahalanobis de este vector se compara con un umbral de chi-cuadrado con grados de libertad iguales a la dimensión del vector de innovación. Si la distancia está por debajo del umbral, el conjunto se considera conjuntamente compatible. Esta prueba es más potente que las pruebas individuales porque captura las correlaciones entre características, que surgen de la incertidumbre en la pose del robot y la covarianza del mapa. Por ejemplo, dos características que son individualmente compatibles con diferentes puntos del mapa podrían ser conjuntamente incompatibles si la geometría relativa entre ellas no coincide con el mapa.
Aplicaciones y extensiones
JCBB se ha aplicado ampliamente en sistemas SLAM, particularmente en robótica móvil de interiores y exteriores. A menudo se utiliza como módulo de asociación de datos de front-end antes de la optimización o el filtrado. El algoritmo también se ha adaptado para su uso en SLAM visual, donde las características son puntos clave detectados en imágenes de cámaras, y en el registro de nubes de puntos 3D. Las extensiones incluyen combinar JCBB con el consenso de muestra aleatoria (RANSAC) para la estimación inicial de la pose, y usarlo en un marco jerárquico para manejar mapas grandes. En la práctica, JCBB puede ser computacionalmente costoso para un gran número de características, por lo que se han propuesto variantes para reducir el espacio de búsqueda, como el uso de un grafo de compatibilidad y algoritmos de clique máximo, que son equivalentes a JCBB en términos de la solución pero pueden ser más rápidos.
Relación con otros métodos
JCBB se compara a menudo con otras técnicas de asociación de datos como el vecino más cercano por compatibilidad individual (ICNN), que es rápido pero propenso a falsos emparejamientos, y con métodos basados en grafos que resuelven el problema del clique máximo. El enfoque de ramificación y acotación garantiza encontrar la solución globalmente óptima bajo el criterio de compatibilidad conjunta, mientras que los métodos heurísticos pueden conformarse con conjuntos subóptimos. Sin embargo, la optimalidad tiene un costo de mayor complejidad computacional, lo que hace que JCBB sea adecuado para procesamiento fuera de línea o para entornos con un número moderado de características. En los sistemas SLAM modernos, JCBB a veces se reemplaza por métodos aprendidos basados en aprendizaje automático o aprendizaje profundo para el emparejamiento de características, pero sigue siendo un algoritmo fundamental en el campo.
Véase también
Referencias
- Neira, J., & Tardós, J. D. (2001). Data association in stochastic mapping using joint compatibility. IEEE Transactions on Robotics and Automation, 17(6), 890-897.