A compatibilidade conjunta por branch and bound (JCBB, do inglês Joint Compatibility Branch and Bound) é um algoritmo de associação de dados utilizado em localização e mapeamento simultâneos (SLAM) e em visão computacional para corresponder características observadas a um mapa ou modelo conhecido. Foi introduzido por José Neira e Juan D. Tardós em 2001, no artigo "Data Association in Stochastic Mapping Using Joint Compatibility". O algoritmo aborda o problema de determinar quais medições de sensores correspondem a quais marcos ou características do mapa, uma etapa crítica para a estimativa precisa do estado em robótica móvel.
Diferentemente de abordagens mais simples de vizinho mais próximo, que avaliam correspondências de características individuais de forma independente, o JCBB avalia a compatibilidade conjunta de um conjunto de correspondências considerando as correlações estatísticas entre todas as características do conjunto. Esse teste conjunto é mais robusto contra correspondências falsas, especialmente em ambientes com características repetitivas ou ambíguas. O algoritmo busca no espaço de possíveis conjuntos de correspondências usando uma estratégia de branch and bound, que poda sistematicamente ramos que não podem levar a uma solução melhor, garantindo que o conjunto encontrado seja o maior que seja conjuntamente compatível.
Visão Geral do Algoritmo
O JCBB opera sobre um conjunto de características previstas (do mapa atual) e um conjunto de características observadas (dos dados do sensor). Cada observação pode ser atribuída a no máximo uma característica prevista, e cada característica prevista pode ser correspondida a no máximo uma observação. O objetivo é encontrar o conjunto de correspondências de cardinalidade máxima tal que o vetor de inovação conjunto (a diferença entre medições observadas e previstas) esteja dentro de um limite qui-quadrado, levando em conta a matriz de covariância completa.
A busca por branch and bound constrói uma árvore onde cada nó representa uma atribuição parcial de observações a características. A cada etapa, o algoritmo expande o nó considerando a próxima observação não atribuída e testando sua compatibilidade com cada característica restante, tanto individualmente quanto em conjunto com as correspondências já atribuídas. Se o teste de compatibilidade conjunta falhar, esse ramo é podado. A busca continua até que todos os nós sejam explorados, e o melhor conjunto (o maior) é retornado. Para melhorar a eficiência, o algoritmo usa uma ordenação heurística das observações, tipicamente por sua compatibilidade individual, para encontrar boas soluções cedo e podar de forma mais agressiva.
Teste de Compatibilidade Conjunta
O núcleo do JCBB é o teste de compatibilidade conjunta. Dado um conjunto de correspondências, o teste calcula o vetor de inovação conjunto e sua matriz de covariância. A distância de Mahalanobis desse vetor é comparada a um limite qui-quadrado com graus de liberdade iguais à dimensão do vetor de inovação. Se a distância estiver abaixo do limite, o conjunto é considerado conjuntamente compatível. Esse teste é mais poderoso que os testes individuais porque captura as correlações entre as características, que surgem da incerteza na pose do robô e da covariância do mapa. Por exemplo, duas características que são individualmente compatíveis com diferentes pontos do mapa podem ser conjuntamente incompatíveis se a geometria relativa entre elas não corresponder ao mapa.
Aplicações e Extensões
O JCBB tem sido amplamente aplicado em sistemas de SLAM, particularmente em robótica móvel indoor e outdoor. É frequentemente usado como um módulo de associação de dados de front-end antes da otimização ou filtragem. O algoritmo também foi adaptado para uso em SLAM visual, onde as características são pontos-chave detectados em imagens de câmeras, e no registro de nuvens de pontos 3D. Extensões incluem combinar o JCBB com o consenso de amostras aleatórias (RANSAC) para estimativa inicial de pose e usá-lo em uma estrutura hierárquica para lidar com mapas grandes. Na prática, o JCBB pode ser computacionalmente caro para grandes números de características, então variantes foram propostas para reduzir o espaço de busca, como o uso de um grafo de compatibilidade e algoritmos de clique máximo, que são equivalentes ao JCBB em termos de solução, mas podem ser mais rápidos.
Relação com Outros Métodos
O JCBB é frequentemente comparado a outras técnicas de associação de dados, como o vizinho mais próximo por compatibilidade individual (ICNN), que é rápido, mas propenso a correspondências falsas, e a métodos baseados em grafos que resolvem o problema do clique máximo. A abordagem de branch and bound garante encontrar a solução globalmente ótima sob o critério de compatibilidade conjunta, enquanto métodos heurísticos podem se contentar com conjuntos subótimos. No entanto, a otimalidade vem ao custo de maior complexidade computacional, tornando o JCBB adequado para processamento offline ou para ambientes com um número moderado de características. Em sistemas modernos de SLAM, o JCBB às vezes é substituído por métodos baseados em aprendizado, como aprendizado de máquina ou aprendizado profundo, para correspondência de características, mas continua sendo um algoritmo fundamental no campo.
Ver Também
Referências
- 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.