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

1. Problem Statement

The paper addresses a critical bottleneck in Multi-Object Tracking (MOT), specifically within the $\delta$-Generalized Labeled Multi-Bernoulli ($\delta$-GLMB) filter.

• Context: In MOT, measurements (detections) must be associated with existing tracks. The $\delta$-GLMB filter provides a mathematically optimal solution but suffers from an exponentially growing number of hypotheses.
• The Challenge: To make the filter real-time capable, the number of hypotheses must be truncated. This requires solving the Ranked Assignment Problem: finding the top-$k$ lowest-cost associations between tracks and measurements (including misdetections), not just the single optimal one.
• Current Limitations:
  • Murty's Algorithm: Solves the problem optimally but has high computational complexity, making it slow for large-scale or multi-sensor scenarios.
  • Gibbs Sampling: Faster than Murty's but often sacrifices accuracy, particularly for lower-ranked assignments (beyond the top 1 or 2).
• Goal: Develop a Deep Learning (DL) approach that approximates the ranked assignment solution with the speed of sampling methods but the accuracy closer to optimal algorithms, specifically leveraging Graph Neural Networks (GNNs).

2. Methodology: RAPNet

The authors propose the Ranked Assignment Prediction Graph Neural Network (RAPNet). The methodology transforms the assignment problem into a graph-based learning task.

A. Problem Formulation as a Bipartite Graph

• The cost matrix $C_Z$ (rows = tracks, columns = measurements/misdetections) is converted into a bipartite graph $G = \{V_s, V_t, E\}$.
  • Source Nodes ($V_s$): Represent tracks.
  • Target Nodes ($V_t$): Represent measurements and potential misdetections.
  • Edges ($E$): Represent possible associations. Edge attributes ($a_{ij}$) correspond to the cost values $c_{ij}$.
  • Constraints: Modeled as a weighted bipartite matching problem where each source node connects to exactly one target, and each target connects to at most one source.

B. Network Architecture (Encoder-Decoder)

RAPNet follows an encoder-decoder structure designed to predict $k_{max}$ assignment solutions simultaneously.

1. Graph Creation & Feature Extraction:

   • Since the number of tracks and measurements varies, raw cost values cannot be used directly as node features.
   • Instead, statistical features are extracted for each row/column: ratio of non-$\infty$ values, min, max, mean, and $L_2$-norm.
   • Edge attributes are derived directly from the cost matrix values.

2. Encoder:

   • Node/Edge Processing: Uses Graph Convolutional Networks (GCN) and Graph Attention Networks (GAT) to aggregate neighborhood information.
   • Mirroring: To handle the bipartite nature, source and target nodes are mirrored and updated in parallel layers.
   • Feature Combination: Encoded node features ($x_s, x_t$) are multiplied element-wise based on edge indices to create edge-level features ($x_{mul}$).
   • Output Dimension: The encoder outputs features scaled by $k_{max}$ (set to 10 in experiments) to predict multiple hypotheses.

3. Decoder:

   • Uses Long Short-Term Memory (LSTM) layers to process the encoded features, generating $k_{max}$ distinct feature sets.
   • Dependency Modeling: The output of layer $i$ is concatenated with the output of layer $i-1$ to create dependencies between the predicted assignments (ensuring the $k$-th assignment is distinct from the previous ones).
   • Final Output: A binary classification output ($y_{pred}$) of shape $|E| \times k_{max}$, indicating the probability of an edge being part of a specific assignment.

4. Post-Processing (Greedy Strategy):

   • Since neural networks may produce invalid assignments (e.g., a column assigned twice), a greedy post-processing algorithm is applied.
   • It selects the maximum probability per row, then iteratively selects the next highest valid probabilities (above a threshold $\theta_{sig}=0.5$) to fill the assignment matrix, ensuring validity constraints are met.

C. Training

• Loss Function: Weighted Binary Cross-Entropy (BCE) to handle class imbalance (sparse valid edges vs. many invalid edges).
• Targets: Optimal assignments generated by Murty's algorithm.
• Data: Trained on both synthetic graphs and graphs extracted from a simulated MOT scenario (PM-$\delta$-GLMB).

3. Key Contributions

1. Novel Framework: Introduction of RAPNet, the first GNN-based approach specifically designed to solve the Ranked Assignment Problem (predicting top-$k$ solutions) rather than just the single optimal assignment.
2. Graph Representation: A robust method for transforming variable-sized cost matrices into fixed-feature bipartite graphs suitable for GNNs, handling dynamic track/measurement counts.
3. New Evaluation Metric: Proposal of the Weighted Position (wp) score. Unlike simple accuracy, this metric evaluates how close a predicted assignment is to the optimal rank, weighting earlier assignments more heavily.
   • Formula: $wp = \sum w_i \kappa_i$, where $\kappa_i$ scores the rank proximity (3 for exact match, 2 for near match, 1 for far match).
4. Post-Processing Algorithm: A greedy strategy to correct invalid outputs from the neural network, significantly improving the validity and quality of the final assignments.

4. Experimental Results

The RAPNet was evaluated against Murty's Algorithm (Optimal) and Gibbs Sampling (Approximate) using synthetic and simulated MOT data.

• Accuracy:
  • RAPNet-PP (with post-processing) significantly outperforms the Gibbs sampler in accuracy for assignments $i=2, 3, 4$.
  • For the top assignment ($i=1$), Gibbs sampling is optimal (by design in the setup), but RAPNet-PP achieves 99% accuracy.
  • RAPNet-PP achieves a wp score of 2.80 compared to Gibbs' 2.11 on simulation data (Murty's is 3.0).
• Cost:
  • RAPNet-PP produces lower total costs than Gibbs sampling for smaller matrices ($\nu_s < 9$).
  • Gibbs sampling outperforms RAPNet only on very large matrices where RAPNet's fixed $k_{max}$ limit becomes a bottleneck.
• Computational Complexity:
  • Unbatched: RAPNet is slower than Gibbs/Murty due to GNN overhead.
  • Batched: When processing batches (size 32) on a GPU, RAPNet's per-graph time becomes comparable to Gibbs sampling.
  • Scalability: Unlike Murty's algorithm, which slows down drastically as matrix size increases, RAPNet maintains relatively constant inference time per graph, making it highly scalable for batch processing.

5. Significance and Future Work

• Significance: This work bridges the gap between the mathematical optimality of $\delta$-GLMB filters and the speed of Deep Learning. It demonstrates that GNNs can effectively learn complex combinatorial optimization problems like ranked assignment, offering a viable alternative to computationally expensive exact solvers in real-time autonomous driving systems.
• Future Directions:
  • Reducing computational complexity (currently dominated by the encoder).
  • Extending the framework to Multi-Sensor MOT (MS-MOT), which involves NP-hard complexities.
  • Incorporating explicit track representations (beyond just cost values) as additional node features to leverage the GNN's flexibility.

In conclusion, RAPNet offers a promising, data-driven alternative to traditional assignment algorithms, achieving superior accuracy over Gibbs sampling while maintaining competitive inference speeds when batched, thus enabling more robust and efficient multi-object tracking.