A Graph Neural Network Approach for Solving the Ranked Assignment Problem in Multi-Object Tracking

Título: Uma Abordagem baseada em Redes Neurais de Grafos para Resolver o Problema de Atribuição Classificada no Rastreamento de Múltiplos Objetos

1. O Problema

O rastreamento de múltiplos objetos (MOT - Multi-Object Tracking) é fundamental para a segurança de veículos autônomos e robótica. Um componente crítico do MOT é a associação de dados, onde as medições dos sensores devem ser vinculadas às trajetórias (tracks) existentes.

• Contexto: O artigo foca no filtro $\delta$-GLMB ($\delta$-Generalized Labeled Multi-Bernoulli), que oferece uma solução matematicamente ótima para MOT. No entanto, para ser viável em tempo real, o filtro exige um processo de "truncamento" (redução) do número de hipóteses geradas.
• Desafio: Esse truncamento envolve resolver o Problema de Atribuição Classificada (Ranked Assignment Problem - RAP). O objetivo é encontrar não apenas a melhor associação (custo mínimo), mas um conjunto de $k$ melhores associações ordenadas.
• Limitações Atuais:
  • Algoritmo de Murty: Resolve o problema de forma ótima, mas possui complexidade computacional alta, tornando-se inviável para cenários em tempo real ou com muitos sensores (MS-MOT).
  • Amostragem de Gibbs: É mais eficiente computacionalmente, mas sacrifica a precisão, frequentemente falhando em encontrar as melhores associações classificadas.
  • Complexidade NP-difícil: O problema torna-se exponencialmente difícil em configurações multi-sensor.

2. Metodologia

Os autores propõem o RAPNet (Ranked Assignment Prediction Graph Neural Network), uma arquitetura de Deep Learning baseada em Grafos para aproximar a solução ótima do RAP.

• Modelagem do Problema:
  • A matriz de custos tradicional (onde linhas são trajetórias e colunas são medições) é transformada em um grafo bipartido.
  • Nós Fonte ($V_s$): Representam as trajetórias.
  • Nós Alvo ($V_t$): Representam as medições e casos de "má detecção" (misdetection).
  • Arestas: Conectam fontes a alvos, com atributos de peso baseados nos valores de custo da matriz.
• Arquitetura do RAPNet:
  • Segue uma estrutura Encoder-Decoder.
  • Encoder: Utiliza camadas de Redes Neurais de Grafos (GCN) e Redes de Atenção em Grafos (GAT) para processar as características dos nós e arestas. As características são normalizadas e agregadas para capturar o contexto global do grafo.
  • Decoder: Utiliza redes LSTM (Long Short-Term Memory) para gerar múltiplas previsões de atribuição simultaneamente. O modelo é treinado para prever um número fixo máximo de soluções ($k_{max} = 10$), permitindo que o modelo aprenda a estrutura de várias classificações de custo.
  • Função de Perda: Classificação binária ponderada (Binary Cross-Entropy) comparando a saída da rede com as soluções ótimas geradas pelo algoritmo de Murty.
• Pós-Processamento:
  • Como a saída da rede pode conter atribuições inválidas (ex: uma coluna atribuída duas vezes), um módulo de pós-processamento baseado em uma estratégia gulosa é aplicado.
  • Este módulo expande as previsões, considerando valores acima de um limiar ($\theta_{sig} = 0.5$) para garantir a validade das associações e selecionar as $k$ melhores soluções válidas.

3. Contribuições Principais

1. Fundamentação Teórica: Introdução da teoria fundamental para descrever problemas de atribuição em MOT usando grafos bipartidos, habilitando o uso de algoritmos baseados em Deep Learning.
2. Novo Framework (RAPNet): Proposta de uma arquitetura específica de GNN para prever atribuições classificadas, superando a limitação de métodos anteriores focados apenas na melhor solução única.
3. Nova Métrica de Avaliação (Weighted Position - wp): Desenvolvimento de uma pontuação que avalia não apenas a precisão exata, mas a posição da atribuição predita em relação à ótima. Isso é crucial para MOT, onde as primeiras $k$ soluções (as mais prováveis) têm maior peso na segurança do sistema.

4. Resultados Experimentais

O RAPNet foi comparado ao Algoritmo de Murty (ótimo) e ao Amostrador de Gibbs (sub-ótimo) em dados sintéticos e dados de simulação MOT.

• Precisão:
  • O RAPNet com pós-processamento (RAPNet-PP) superou consistentemente o Amostrador de Gibbs em métricas de precisão e custo, especialmente para os primeiros $k$ atributos.
  • Para matrizes pequenas (comum em cenários MOT típicos, onde o número de trajetórias é < 9), o RAPNet-PP alcançou precisão de 99% na primeira atribuição e 95% na segunda, superando o Gibbs (que caiu para 18% na segunda).
• Métrica Weighted Position (wp):
  • O RAPNet-PP obteve uma pontuação wp superior ao Gibbs, indicando que suas soluções, mesmo quando não perfeitamente ótimas, estavam muito próximas das melhores soluções possíveis.
• Complexidade Computacional:
  • Sem batch: O RAPNet é mais lento que os métodos tradicionais devido à sobrecarga da criação de grafos e inferência da rede.
  • Com batch (processamento em lote): O tempo de inferência por grafo torna-se comparável ao do Amostrador de Gibbs, enquanto o Algoritmo de Murty mostra um aumento drástico no tempo de execução conforme o tamanho da matriz cresce.
  • O tempo do RAPNet permanece relativamente constante para grafos maiores, ao contrário dos métodos tradicionais que escalam mal.

5. Significado e Conclusão

O trabalho demonstra que as Redes Neurais de Grafos são uma ferramenta viável e promissora para resolver problemas de otimização combinatória complexos como o RAP no contexto de MOT.

• Impacto: Oferece um caminho para substituir métodos computacionalmente caros (Murty) ou imprecisos (Gibbs) em sistemas de rastreamento em tempo real, especialmente em cenários multi-sensor.
• Futuro: Os autores planejam reduzir a complexidade computacional (otimizando a criação de grafos) e estender o framework para lidar com problemas de atribuição em cenários multi-sensor (MS-MOT), onde a complexidade é ainda maior. A abordagem baseada em GNN permite a incorporação de características adicionais (como representações explícitas de trajetórias) que os métodos tradicionais não utilizam.

Em resumo, o RAPNet representa um avanço significativo ao combinar a precisão teórica necessária para filtros Bayesianos avançados com a eficiência de inferência do Deep Learning.